第11章-图像压缩编码20160830.

第十一章图像压缩编码Chapter112Contents信息论基础图像压缩基本概念与模型统计编码变换编码预测编码图像压缩编码国际标准3信息论基础信息论基础：信息论是图像编码的基础。信息论认为可以将信息的产生模拟成一个概率事件，可以用随机过程描述信息论中的信源模型。–信息熵：随机变量的熵是描述随机变量不确定度的统计量，设随机变量X的概率密度函数为，，，熵H(X)定义为，–式中，称为自信息。–通常在二元概率空间中规定等概率时的熵为单位熵，对数底为2时，熵的单位为比特(bit)；以e为底时，熵的单位为奈特(nat)；以10为底时，熵的单位为哈特利(Hartley)。–随机变量X的熵函数H(X)具有如下的基本性质：1.(非负性)；2.H(X)是X的凹函数(凹性)；3.当随机变量X服从均匀分布时，其熵达到最大值，其中，m为X可能取值的个数。4信息论基础–相对熵：设随机变量的概率分布服从均匀分布，即所有取值的概率相等，，则有，式中，表示两个概率分布和之间的相对熵，给出的是两个随机变量概率分布之间距离的度量。二元概率空间的熵函数5信息论基础–香农(Shannon)定理：关于随机变X的信源编码C是从X的取值空间到的一个映射，其中表示D进制码元表中有限长度的符号序列所构成的集合。设C表示x的码字，表示的码字的长度，信源编码C的期望长度L(C)定义为，–若编码将X的取值空间中的每一个元素映射到不同的编码序列，则称这个编码是非奇异的。非奇异码可以保证了X取值的明确性，但只有在两个码字之间添加间断码，才能确保其可译性。–编码C的扩展C*是从中有限长度的符号序列到D进制码元表中有限长码元序列的映射，。若一个编码的扩展编码是非奇异的，则称该编码是惟一可译码。若码中无任何码字是其他码字的前缀，则称该编码为前缀码。–香农第一定理(最优前缀码定理)：设是关于信源概率分布的D进制编码的一组最优码字长度，L*为最优码的期望长度()，则有。–最优编码就是使码字长度L(C)接近下界。若L(C)远大于，则效率过低；若，则必然丢失信息。6图像压缩基本概念与模型图像压缩基本概念与模型：图像信息具有直观、形象的优点，但数据量庞大。图像压缩的目的是消减图像数据中的冗余信息，从而更加有效地传输和存储图像。–图像熵与编码效率：将像素的灰度看作随机变量X，其概率分布率为，为灰度级，k=0,1,…,L-1，L为灰度级数。根据信息论中熵的定义，图像熵H(X)定义为，–通常采用编码效率和冗余度来度量图像压缩编码方法的性能，编码效率定义为，；冗余度与编码效率之间的关系为，。–压缩率通常用于度量图像编码的数据压缩程度。设源图像的比特数为No，压缩数据的比特数为Nc，图像编码的压缩率定义为，。7图像压缩基本概念与模型–图像信息的冗余：数字图像的冗余包括空间冗余、时间冗余、信息熵冗余、结构冗余和心理视觉冗余等。–空间冗余和时间冗余统称为统计冗余。空间冗余是指，由于同一物体上各采样点的颜色之间通常在空间上是均匀的、连续的，因此大量相邻像素的数值是相同或相近的，存在着空间连贯性。时间冗余是指序列图像中的相邻帧之间的相关性所引起的数据冗余。–信息熵冗余是从编码技术的角度在图像编码时由于编码效率不高所引起的数据冗余，也称为编码冗余。–结构冗余是指图像中存在重复出现的相同或相似的纹理结构。–人类视觉系统对图像的敏感性是非均匀和非线性的，在正常的视觉处理过程中，各种信息的相对重要程度不同，由此就产生了心理视觉冗余，包括：(1)人眼对亮度变化敏感，而对色度变化相对不敏感；(2)人眼的辨别能力与物体周围的背景亮度成反比；(3)人眼对图像中灰度发生急剧变化的边缘区域敏感，而对非边缘区域相对不敏感；(4)人眼对整体结构敏感，而对局部细节相对不敏感；(5)大多数情况下灰度图像采用8位表示、共28种灰度，彩色图像采用24位表示、共224种颜色，而人眼至多可以辨认出26级灰度和216种颜色。8图像压缩基本概念与模型–保真度准则：保真度是指图像压缩系统编解码器的输出信号再现输入信号的相似程度，分主观与客观两方面。–主观保真度准则：取决于人类的视觉感受，采用由人来评价的主观方法。通过向观察者呈现重构图像，然后将观察者的评分进行平均，以此作为图像质量的主观评价。–人是图像和视频的最终观察者，因此主观评价是最直接、最可靠的方法；其问题是需多次重复实验，耗时费力，易受观察者个人因素的影响，且无法将主观评价方法嵌入到应用系统中。值等级描述1极好图像质量极高2好图像质量高，感觉良好，干扰可以接受3过得去图像质量可以接受，干扰不是不可接受4勉强可以图像质量较低，希望能加以改善，在某种程度上难以接受干扰5差图像质量很差，尚能观看，具有明显不可接受的干扰6不可用图像质量非常差，无法观看电视图像的绝对等级量表9图像压缩基本概念与模型–客观保真度准则：以压缩编码前后图像的误差来度量的，采用由算法评价的客观方法。–源图像与重构图像间的误差可表为，–设源图像和重构图像的尺寸为M×N，均方误差MSE定义为图像总体平方误差的平均值，可表示为，–若将源图像与重构图像之间的误差看作是噪声，则重构图像可表示为，，信噪比SNR定义为图像信号功率与噪声功率之比，可表示为，–由于大多数信号具有很宽的动态范围，通常以对数尺度来表示信噪比，单位为分贝。在这种情况下，信噪比SNRdB的定义为，10图像压缩基本概念与模型图像压缩系统：图像压缩系统是由编码器和解码器两个部分组成。编码器是对源数据经过编码进行压缩，由信源编码器和信道编码器组成；解码器是对编码生成的压缩数据进行解压缩，由与编码器相对应的信道解码器和信源解码器组成。–信源编码器和信源解码器：信源编码器用于减少或消除输入信号的数据冗余，包含了映射器、量化器和符号编码器3个级联的操作；信道编码器用于增强信源编码器输出符号的抗噪能力。–信道编码器和信道解码器：当信道中含有噪声或容易产生误差时，信道编码通过将可控制的冗余加入信源编码的码字以减少信道噪声的影响，提高信息传输时的抗干扰能力。映射器量化器符号编码器f(x;y)源图像位数据流符号解码器反向映射器^f(x;y)位数据流重构图像信源编码器信源解码器信源编码器信道编码器信道解码器信源解码器编码器解码器信道f(x;y)^f(x;y)源图像重构图像图像压缩系统11统计编码统计编码：统计编码是利用数据的统计冗余进行的可变码字长度编码，也称为熵编码。由源符号映射到可变长度的码字称为可变码字长度编码，如赫夫曼编码。当待编码的符号集合较大时，为了降低编解码器的复杂度，采用准变长编码，如香农-费诺编码。–对于信源符号的D进制前缀码，设是关于信源概率分布p的一组最优码长，码长为的编码称为香农码，步骤如下：1.统计每一个信源符号出现的概率，将信源符号按其概率以递减的顺序排列，即：2.计算各个概率对应的码字长度：3.计算累积概率：4.将累积概率由十进制小数转换成二进制小数；5.截取二进制小数点后的前位作为对应信源符号的码字。信源符号概率码长累积概率的二进制表示码字x30.4375200.0000000000x50.250020.43750.0111000001x40.187530.68750.10110000101x20.0625４0.8750.111000001110x10.062540.93750.111100001111香农-费诺编码的过程12统计编码–费诺提出了一种构造信源编码的次优方法—二分法香农-费诺编码方法，期望码字长度可以达到，具体编码步骤如下：1.统计每一个信源符号出现的概率，将信源符号按其概率以递减顺序排列，，选取k使得最小；2.从位置k将信源符号集合划分为概率总和相等或近似相等的两个子集，对概率较大的子集中的符号，加入0，对于概率较小的，加入1编码；3.对每一个划分出来的子集合重复2，直至子集中只剩余单个信源符号；4.依次连接每一个信源符号所属子集的二进制编码，组成所对应的码字。灰度值xix3x5x4x2x1概率pi0.43750.25000.18750.06250.0625第1次编码01第2次编码01第3次编码01第4次编码01信源符号概率码长码字x30.43710x50.250021x40.18753110x20.062541110x10.062541111二分法香农-费诺编码的过程13统计编码–赫夫曼编码方法：赫夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。设根节点为0层，为m个叶节点对应的权值，从根节点到叶节点的路径长度为叶节点的层数，则树的带权路径长度的计算式为，–赫夫曼编码包括构造赫夫曼树和分配码字两步骤。–构造赫夫曼树步骤如下：1.统计每一个信源符号出现的概率，并按其概率以递减的顺序排列；2.将最小概率的两个符号合并成为一个节点，并将它们的概率之和作为该节点的概率，参与下一次的排序；3.按概率递减顺序重新排列新的节点，并重复2直至合并为一个总根节点。–分配码字步骤如下：对于每一个节点的分支，对概率大的符号0，对概率小的符号加入1编码，从根节点到叶节点路径分支上分配的编码依次连接组成所对应信源符号的码字。14统计编码BDE10100A00000000110010001C01p3=0:18p2=0:22p6=0:04p5=0:08p4=0:16p1=0:32pc=0:40pb=0:28pa=0:12pd=0:60pe=1x3x2x6x5x4x1赫夫曼树构造和码字分配过程赫夫曼编码的码字信源符号概率码长码字x10.32200x40.22210x50.1811x60.163000x20.0840000x30.044000115统计编码–有关赫夫曼编码的评论：1.赫夫曼编码的实现问题：赫夫曼编码在实际中存在的以下若干问题：1)当硬件实现时，概率值的最小存储单元为1bit，不能精确到小数后多位，这样会引起概率匹配不准确以及编码效率的下降；2)由于码字长度可变，因此赫夫曼编码与解码过程耗时；3)一幅灰度图像一般达到256个灰度级，当对整幅图像直接进行赫夫曼编码时，就会产生很多不同的码字，且小概率分布的灰度值可能有很长的编码，这样不仅达不到数据压缩的目的反而会使数据量和复杂度增大。2.赫夫曼编码与香农码：对于某个特定的符号，使用码字长度为的香农码，可能比最优码更差。例如，考虑两个符号，其中一个符号发生的概率为0.9999，而另一个为0.0001。若使用香农码，则它们的码字长度分别为1bit和14bit。然而，这两个符号的赫夫曼编码的最优码长都是1bit。因而，在香农编码中，不经常发生的符号的码字长度一般比最优码的码字更长。对于单个符号来说，不论是香农码还是赫夫曼码都可能有更短的码字长度，但从平均意义上讲，赫夫曼编码具有更短的期望码字长度。另外，从期望码字长度衡量，香农码和赫夫曼码的差别不超过1bit，两者的期望码字长度均在H(X)与H(X)+1之间。16统计编码–算术编码：算术编码将信源序列用0与1之间的小数进行编码，可以用分数比特来表示单个信源符号。当信源序列的长度增加时，表示信源序列的编码区间减小，信源序列表示该编码区间所需的位数就会增加。–具体来讲，赫夫曼编码每一次对一个符号进行编码，将单个信源符号映射成一个整数位的码字，而算术编码将信源符号的整个序列映射成一个单独的浮点数，给整个符号序列分配一个单一的码字。–在算术编码中，根据信源中的每一个符号的概率来细分编码区间，每输入一个符号，将编码区间缩小至当前输入符号的间隔。根据输入信源符号的概率减小编码区间[0,1)，信源符号的概率愈大对应于间隔愈宽，需要使用较短的码字表示；信源符号的概率愈小对应于间隔愈窄，需要用较长的码字表示。设一个离散无记忆信源X的符号集合为，信源符号及其概率分布如表所示,信源的熵为1.5219bit。在算术编码的开始，编码区间为整个半开区间[0,1)，初始时根据每一个信源符号的概率将其划分成3个间隔，符号x1对应于间隔[0,0.4)，符号x2对应于间隔[0.4,0.6)，符号x3对应于间隔[0.6,1)。17统计编码0x1x3x2x2x1x1x3x