资源描述
第4讲 图像压缩原理,学习目标,l 了解多媒体数据压缩编码的重要性和分类 l 掌握图像数据压缩编码常用算法的基本原理,数据压缩编码简介,图像数据压缩的主要依据有两个: 一是图像数据中有许多重复的数据,使用数学方法来表示这些重复数据就可以减少数据量; 另一个依据是人眼睛对图像细节和颜色的辨认有一个极限,把超过极限的部分去掉,这也就达到了数据压缩的目的。 有损压缩技术和无损压缩技术 基于数据冗余的压缩技术是无损压缩技术 基于人眼视觉特性的压缩技术是有损压缩技术。 实际上,图像压缩技术是各种有损和无损压缩技术的综合实现。,数据压缩方法的分类,根据编、解码后数据是否一致来进行分类,数据压缩的方法一般被划分为两类: 可逆编码(无损编码)。此种方法的解码图像与原始图像严格相同,压缩比大约在2:15:1之间。主要编码有Huffman编码、算术编码、行程长度编码等。 不可逆编码(有损编码)。此种方法的解码图像与原始图像存在一定的误差,但视觉效果一般可以接受,压缩比可以从几倍到上百倍调节。常用的编码有变换编码和预测编码。,根据压缩的原理分:,(1)预测编码。它是利用空间中相邻数据的相关性来进行压缩数据的。通常用的方法有脉冲编码调制(PCM)、增量调制(DM)、差分脉冲编码调制(DPCM)等。这些编码主要用于声音的编码。 (2)变换编码。该方法将图像时域信号转换为频域信号进行处理。这种转换的特点是把在时域空间具有强相关的信号转换到频域上时在某些特定的区域内能量常常集中在一起,数据处理时可以将主要的注意力集中在相对较小的区域,从而实现数据压缩。一般采用正交变换,如离散余弦变换(DCT)、离散傅立叶变换(DFT),(3)量化与向量量化编码。对模拟信号进行数字化时要经历一个量化的过程。为了使整体量化失真最小,就必须依据统计的概率分布设计最优的量化器。最优的量化器一般是非线性的,已知的最优量化器是Max量化器。我们对像元点进行量化时,除了每次仅量化一个点的方法外,也可以考虑一次量化多个点的做法,这种方法称为向量量化。即利用相邻数据间的相关性,将数据系列分组进行量化。,(4)信息熵编码。依据信息熵原理,让出现概率大的信号用较短的码字表示,反之用较长的码字表示。常见的编码方法有Huffman编码、Shannon编码以及算术编码。 (5)子带(subband)编码。将图像数据变换到频率后,按频率分带,然后用不同的量化器进行量化,从而达到最优的组合。或者分布渐进编码,在初始时,对某一个频带的信号进行解码,然后逐渐扩展到所有频带。,根据压缩的原理分:(续),信息熵及基本概念,1信息量与信息熵 信息量是指从N个相等的可能事件中选出一个事件所需要的信息度量或含量,也就是在辨识N个事件中特定的一个事件的过程中所需要提问“是或否”的最少次数。 设从N个数中选定任一个数xj的概率为p(xj),假定选定任意一个数的概率都相等,即p( xj ),因此定义信息量见公式4-5。定义信息量见公式4-5。,如果将信源所有可能事件的信息量进行平均,就得到了信息的“熵”,即信息熵。,式中,P(xj)是信源X发出xj的概率。I(xj)的含义是,信源X发出xj这个消息(随机事件)后,接收端收到信息量的量度。,(4-5),信源X发出的xj(j=1,2,n)共n个随机事件的自信息统计平均,即 H(X)称为信源X的“熵”,即信源X发出任意一个随机变量的平均信息量。 其中:等概率事件的熵最大,假设有N个事件,由(4-6)式得此时熵为:,(4-6),当P(x1)1时,P(x2)P(x3)P(xj)0,由(4-6)式得此时熵为,由上可得熵的范围为:,在编码中用熵值来衡量是否为最佳编码。若以Lc表示编码器输出码字的平均码长,则当 LcH(X) 有冗余,不是最佳。 LcH(X) 不可能。 LcH(X) 最佳编码(Lc稍大于H(X))。 熵值为平均码长Lc的下限。,平均码长Lc的计算公式为:,(j=1,2,n) (4-7),其中:P(xj) 是信源X发出xj的概率,L(xj)为xj的编码长。,冗余度、编码效率与压缩比,设原图像的平均码长为L,熵为H(X),压缩后图像的平均码长为Lc,则定义冗余度为(见公式4-8) : (4-8) 编码效率(见公式4-9): (4-9) 压缩比(见公式4-10): (4-10),在数字图像通信系统中,冗余度、编码效率与压缩比是衡量信源特性以及编解码设备性能的重要指标。,信息熵编码,信息熵编码也称为统计编码,是利用信息源出现的概率来进行编码,目前比较常见的信息熵编码包括哈夫曼编码、香农-范诺编码、行程编码和算术统计编码等。,1哈夫曼编码,基本原理 依据信源字符出现的概率大小来构造代码,对出现概率较大的信源字符,给予较短码长,而对于出现概率较小的信源字符,给予较长的码长,最后使得编码的平均码字最短。,具体的编码步骤如下: (1)将信源符号出现的概率按由大到小的顺序排序。 (2)将两处最小的概率进行组合相加,形成一个新的概率。 (3)将新出现的概率与未编码的字符一起重新排序。 (4)重复步骤(2)、(3),直到出现的概率和为1。 (5)分配代码。代码分配从最后一步开始反向进行,对最后两个概率一个赋予0代码,一个赋予1代码。如此反向进行到开始的概率排列。在此过程中,若概率不变则采用原代码。,例1:设输入图像的灰度级a1,a2,a3,a4,a5,a6出现的概率分别是0.4、0.2、0.12、0.15、0.1、0.03。试进行哈夫曼编码,并计算编码效率、压缩比、冗余度。,编码步骤: (1)初始化,根据符号概率的大小按由大到小顺序对符号进行排序,如图所示。 (2)把概率小的两个符号组成一个节点,如图4中的a5、a6组成节点P1。 (3)重复步骤2,得到节点P2、P3、P4、P5,形成一棵“树”,其中P5为根节点。 (4)从根节点P5开始到相应于每个符号的“树叶”,从上到下标上1(上枝)或者0(下枝),至于哪个为1哪个为0则无关紧要,最后的结果仅仅是分配的代码不同,而代码的平均长度是相同的。,最终编码结果为:a1 =1, a2 =000 , a3 =011, a4 =001, a5 =0100, a6 =0101,由公式(4-6)可求得图像信源熵是: H(X)= =-(0.4log20.4+0.2log20.2+0.12log20.12+ 0.15log20.15+0.1log20.1+0.03log20.03) =2.25 bit,根据哈夫曼编码过程图给出的结果,由公式(4-7)可求出它的平均码字长度: Lc=0.41+0.23+0.153+0.123+0.14+0.034 =2.33 由公式(4-9)得编码效率为:,压缩之前8个符号需要3个比特量化,经过压缩之后的平均码字长度为2.33,由公式(4-10)得其压缩比为:,由公式(4-8)得冗余度为: r = 1- = 3.4%,采用哈夫曼编码时有两个问题值得注意: (1)哈夫曼编码没有错误保护功能,在译码时,如果码串中没有错误,那么就能一个接一个的正确译出代码。但如果码串中有错误,哪怕仅是1位出现错误,不但这个码本身译错,更糟糕的是后面的译码可能全错,这种现象称为错误传播(Error Propagation)。 (2)哈夫曼编码是可变长度码,因此很难随意查找或调用压缩文件中间的内容,然后再译码,这就需要在存储代码之前加以考虑。,2算术编码,算术编码(arithmetic coding AC)是利用0和1之间的间隔来表示信源编码的一种方法,其编码值是间隔的上、下限包含的相同二进制。编码过程中的间隔决定了符号压缩后的输出。 算术编码用到两个基本的参数:符号的概率和它的编码间隔。 信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔,而这些间隔包含在0到1之间。 算术编码器的编码过程可用例2加以解释。,例2:假设信源符号为A, B, C, D,这些符号的概率分别为 0.1, 0.4, 0.2, 0.3 ,根据这些概率可把间隔0, 1分成4个子间隔:0, 0.1, 0.1, 0.5, 0.5, 0.7, 0.7, 1,其中x,y表示半开放间隔,即包含x不包含y,如表4-1所示。,表1 信源符号、概率和初始编码间隔,如果消息序列的输入为:CADACDB,其编码过程如下: 首先输入的符号是C,找到它的编码范围是0.5, 0.7; 由于消息中第2个符号A的编码范围是0, 0.1,因此它的间隔就取0.5, 0.7的第一个1/10作为新间隔0.5, 0.52;,编码第3个符号D时取新间隔为0.514, 0.52; 编码第4个符号A时,取新间隔为0.514, 0.5146,。,消息的编码输出可以是最后一个间隔中的任意数,整个编码过程如图1所示。最后在0.5143876,0.51442中选择一个数作为编码输出值:0.5143876。,解码时,解码器由编码输出值:0.5143876,可马上解得一个字符为C,然后依次得到唯一解A,D,A,C,D,B。,在算术编码中需要注意的几个问题: (1)由于实际的计算机的精度不可能无限长,运算中出现溢出是一个明显的问题,但多数机器都有16位、32位或者64位的精度,因此这个问题可使用比例缩放方法解决。 (2)算术编码器对整个消息只产生一个码字,这个码字是在间隔0, 1)中的一个实数,因此译码器在接受到表示这个实数的所有位之前不能进行译码。 (3)算术编码也是一种对错误很敏感的编码方法,如果有一位发生错误就会导致整个消息译错。,行程长度编码,是一个针对包含有顺序排列的多次重复的数据的压缩方案。其原理就是把一系列的重复值用一个单独的值再加上一个计数值来取代,行程长度就是连续且重复的单元数目。如果想得到原始数据,只需展开这个编码就可以了。 例如,计算机制作图像中,常常具有许多颜色相同的图块,而且在行上都具有相同的颜色,或者在一行上有许多连续的像素都具有相同的颜色值。这时,就不需要存储每一个像素的颜色值,而仅存储一个像素的颜色值以及具有相同颜色的像素数目就可以,或者存储一个像素的颜色值,以及具有相同颜色值的行数,这种压缩编码称为行程编码。具有相同颜色的连续的像素数目称为行程长度。,如图所示,假定一幅灰度图像,第n行的像素值为: 用RLE编码方法得到的代码为:3150841160。代码斜黑体表示的数字是行程长度,黑体字后面的数字代表像素的颜色值。例如黑体字50代表有连续50个像素具有相同的颜色值,它的颜色值是8。,对比RLE编码前后的代码数可以发现,在编码前要用73个代码表示这一行的数据,而编码后只要用10个代码表示代表原来的73个代码,压缩前后的数据量之比约为7:1,即压缩比为7:1。这说明RLE确实是一种压缩技术,而且编码技术实用。,RLE的性能好坏主要取决于图像本身的特点。RLE压缩编码尤其适用于计算机生成的图像,对减少图像文件的存储空间非常有效。然而,由于颜色丰富的自然图像在同一行上具有相同颜色的连续像素往往很少,而连续几行都具有相同颜色值的连续行数就更少,如果仍然使用RLE编码方法,不仅不能压缩图像数据,反而可能使原来的图像数据变得更大。,译码时按照与编码时采用的相同规则进行,还原后得到的数据与压缩前的数据完全相同。因此,RLE属于无损压缩技术。,人们通过对大量自然景物图像的统计分析发现,绝大部分图像信号在空间域中像素之间的相关性是很大的。它们经过正交变换以后,其能量主要集中在低频部分;而且经过正交变换后的变换系数之间的相关性大大降低。 变换编码的基本思路就是利用上述特点,在编码时略去某些能量很小的高频分量,或在量化时对方差较小的分量分配以较少的比特数,以降低码率。另外,变换编码还可以根据人眼对不同频率分量的敏感程度而对不同系数采用不同的量化台阶,以进一步提高压缩比。,变换编码,变换编码不是直接对空间域图像信号编码,而是首先将空间域图像信号映射变换到另一个正交矢量空间,产生一批变换系数,然后对这些变换系数进行编码处理。 下图显示了一个变换编码解码过程的示意图。,变换编码(续),变换编码的性能取决于子图像的大小、正交变换的类型、样本的选择和量化器的设计。,变换编解码系统通过发送端将原始图像分割成1到n个子图像块,每个子图像块送入到正交变换器作正交变换,变换器输出变换系数经过滤波、量化、编码后送到信道传输到接收端,接收端作解码、逆变换、综合拼接,恢复出空域图像。,1正交变换类型 从均方误差最小和主观图像质量两个观点来看,最好的变换类型是离散K-L变换。 但由于离散K-L变换的基核向量是不固定的,一般没有快速算法,因此只宜作理论分析和试验。 在数字信号处理技术中,傅里叶变换是应用最为广泛的一类正交变换,它不仅具有物理含义明确的优点,而且可以使用快速算法来减少运算量。但它应用在图像编码中时也有两个明显的弱点:一是要进行复数运算;二是收敛速度较慢。 变换压缩编码的基本依据是变换系数的方差比较集中。因此通常按系数方差大小作出变换系数的分布函数,以说明方差的集中程度。当原始图像为相关函数 的高斯型一阶马尔可夫过程时,离散余弦DCT可与最佳变换K-L媲美,因为DCT与K-L变换压缩性能和误差比较近,而且DCT也具有多种快速算法,因而在图像压缩编码中被广泛的应用。,1正交变换类型(续) DCT变换具有如下特点: DCT变换计算复杂度适中。 DCT变换域系数矩阵能量集中在直流和低频区。 DCT的直流系数近似满足瑞利分布,交流系数近似满足拉普拉斯分布。 DCT系数相关性很小。,在变换编码中,选择哪些变换系数进行量化编码,略去哪些系数不予传输,对变换压缩编码的性能有很大影响。原则上,应保留能量集中、方差大的变换系数予以编码传输。 系数选择通常有两种方法:区域取样和门限取样。,2样本选择与量化方案,门限取样:是把变换系数的方差和某个门限值比较,超过门限的会予以编码,否则舍弃。,区域取样:是对设定形状内的变换系数进行量化编码,略去区域外的变换系数。由于DCT变换域系数矩阵能量集中在直流和低频区,则在右图所示的DCT系数中能量将主要集中在左上角的系数上。为此,可只传左上角上的系数,并按图中的“之”字形扫描路径输出系数。,在选定了要编码传输的系数后,有几种方法可以对其量化: (1)对所有变换系数分配相同的比特数。在发送端先对各变换系数进行归一化,使它们变得有相同的方差,然后用一个统一的量化器对所有的系数进行量化及编码。在该方式下,由于接收端要把归一化的系数恢复回去,原来方差大的系数要乘大的倍数,因此量化误差大。 (2)对方差大的变换系数分配较多的比特数,使比特数正比于该系数方差的对数。可以证明,这样的分配方案可使量化造成的总均方误差最小。在该方式中,对不同的变换系数要用不同的量化器,它们之间不仅量化级数不同,判决电平和量化输出电平的变化规律也可以不同,以适合各自系数的分布规律。 (3)利用人眼视觉特性设计量化器。由于人眼对不同空间频率的失真敏感度不同,在比特分配时可对人眼较为敏感的变化系数分配较多的比特,而不太敏感的系数分配较少的比特。按这种方式设计的量化器可使变换编码系统总的主观图像质量较好。 变换编码中对变换域系数的量化是造成图像质量下降的主要原因,量化器设计的好坏将直接影响图像质量。变换编码中图像质量下降的主要表现形式是方块效应,也即在图像分块的边缘产生较易为人眼所察觉的误差。,3子图像大小选择 在变换编码系统中,考虑到矩阵变换所需的计算量、变换编码的性能和传输时误码的影响等因素,一般将图像分成若干小的子图像进行处理。 从变换编码的压缩特性来看:子图像尺寸n越大,所计入的相关像素越多,总的均方差性能越好。但根据对大量自然图像的统计分析结果,大多数图像仅在约20个相邻像素间有较大的相关性,n16后对性能的改善不大。变换编码对图像进行分块处理的另一特点,是可以将传输时误码造成的图像损伤限制在子图像范围内。显然,子图像尺寸越大误码造成的图像损伤范围越大;反之范围越小。综合考虑上述因素,一般子图像尺寸选为88或1616。,通常,图像中局部区域的像素是高度相关的,因此可以用先前像素的有关灰度知识来对当前像素的灰度进行估计,这就是预测。如果预测是正确的,则不必对每一个像素的灰度都进行压缩,而是把预测值与实际像素值之间的差值经过熵编码后发送到接收端,接收端通过预测值+差值信号来重建原像素。 预测编码可分为线性预测编码和非线性预测编码。前者常被称为差分脉冲编码调制(DPCM),其基本原理是基于图像中相邻像素之间的相关性,每个像素可通过与之相关的几个像素来进行预测,如下页图所示。,5 预测编码,预测编码可以获得比较高的编码质量,并且实现起来比较简单,因此被广泛地应用于 图像压缩编码系统。但是它的压缩比不高,而且精确的预测有赖于图像特性的大量的先验知识,并且必须进行大量的非线性运算,因此一般不单独使用,而是与其他方法结合起来使用。例如,在JPEG中使用了预测编码技术对DCT直流系数进行编码。,图中x(n)为采样的声音或图像数据, 为x(n)的预测值, 是实际值和预测值的差值, 是d(n)的量化值, 是引入量化误差的x(n)。,1模型编码 模型编码则是利用计算机视觉和计算机图形学的知识对图像信号进行分析与合成。 模型编码采用图像分析和描述的方法,将图像信号看成三维世界中的目标和景物投影到二维平面的产物,对图像的结构和特征进行分析,提取出图像的特征参数,如运动参数、形状参数等,并用某种模型加以描述,通过对模型参数的编码达到图像编码的目的。图像解码时,根据参数和模型先验知识用图像合成技术重建图像。由于编码的对象是特征参数,而不是原始图像,因此有可能实现比较大的压缩比。模型编码引入的误差主要是人眼视觉不太敏感的几何失真,因此重建图像非常自然和逼真。,其他编码方法,模型编码目前的研究目标主要集中于可视电话和会议电视的应用中。这是因为此类应用传送的图像中主要感兴趣的内容是人的头肩像,是一种基本固定的特定场景,因此可以预先建立人体头肩像的三维模型,从而进行模型编码。人的头肩像三维模型由人脸形状模型和脸部表情模型两部分组成。其形状模型可用许多小三角形的组合即“线框”(Wireframe)去逼近,脸部表情模型由“基本活动单元”(Action Unit)的线性组合来实现。 通信时首先要将被传输对象的基本特征传送到对方,以建立人的头肩像三维模型;通信开始后,当头部发生运动、脸部表情发生变化时,抽取这些运动和变化的参数并对其进行编码发送给对方;接收端用已知的三维模型和收到的参数,用图像合成技术重建图像。由于头部运动和脸部表情参数变化是一种非刚体运动,精确的运动估值是相当困难的。目前采用的是在一定约束条件下建立在预测和反馈技术上的运动跟踪算法。,2混合编码 用两种或两种以上的方法对图像进行编码称为混合编码,是今年来广泛采用的一种方法。 混合编码通常使用DCT等变换进行空间冗余度的压缩,用帧间预测或运动补偿预测进行时间冗余度的压缩,以达到对运动图像的更高的压缩率。后面要介绍的JPEG和MPEG都属于混合编码。 混合编码器有两种不同的结构,如图4-8所示,分别表示空/时压缩和时/空压缩两种不同的方案。图4-8是这两种方案的结构框图,其中T、IT代表正、反变换,Q、IQ代表正、反量化。方案I由于把变换部分放在预测环内,因此预测环本身工作在图像域内,便于使用性能优良、带有运动补偿的帧间预测,因而被广泛地应用于研究和使用;而方案II由于把变换部分放在预测环外,需要在变换域(频率域)进行预测,处理上不方便。方案I经过若干年的研究总结后,发展为带有运动补偿性质的帧间预测与DCT结合的方案。这一方案具有压缩性能高、编码技术成熟,以及编码延迟短等特点,目前已成为运动图像压缩的主流方案。,
展开阅读全文