第十五讲 图像的编码与压缩

Lecture15

ImageCodingand

CompressionPurpose

图像压缩的概念、目的和意义图像的霍夫曼编码、香农编码、算术编码、行程编码方法ExplainContents

了解图像压缩的目的和意义，熟悉图像保真度准则掌握图像霍夫曼编码、香农编码、算术编码、行程编码方法

图像压缩(ImageCompression)的概念

数据压缩的研究内容包括数据的表示、传输、变换和编码方法，目的是减少存储数据所需的空间和传输所用的时间。

图像压缩就是在一个可以接受的还原状况的前提下用尽可能少的比特数来表示源信号，即把需要存储或传输的图像数据的比特数减少到最少程度。图像压缩是通过编码实现的。

概述

图像数据压缩的必要性

图像数据的特点之一是信息量大。海量数据需要巨大的存储空间。如多媒体中的海量图像数据，不进行编码压缩处理，一张600M字节的光盘，只能存放20秒左右的640×480像素的图像。没有编码压缩，多媒体信息保存有多么困难是可想而知的。在现代通信中，图像传输已成为重要内容之一。采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段。可见，没有图像编码与压缩技术的发展，大容量图像信息的存储与传输是难以实现的，多媒体、信息高速公路等新技术在实际中的应用会遇到很大困难。概述

图像数据压缩的可能性概述

从信息论观点看，描述图像信源的数据由有用数据和冗余数据两部分组成。信息量数据量冗余量

冗余量是可以压缩的，在实际应用中应尽量保证去除冗余量而不会减少信息量，即压缩数据在一定条件可以近似恢复。数据冗余(DataRedundancy)

编码冗余(CodingRedundancy)等长编码平均码长为3变长编码平均码长为2.7数据冗余

像素间冗余(InterpixelRedundancy)

图像是由按一定规则排列起来的像素组成，图像中相邻像素的灰度往往相同或相近，这就称为像素间冗余或空间冗余。数据冗余

心理视觉冗余(PsychovisualRedundancy)175K1.46M

受生理和心理上的影响，人眼对黑白和彩色信息的分辨率是有限的。光学上不一致的图像在视觉上可能是一样。图像压缩系统模型信源信源编码器信道编码器通信线路或存储介质信源解码器信道解码器信宿压缩的有效性编码的可靠性图像保真度准则描述解码图像相对原始图像偏离程度的测度一般称为保真度。常用的保真度准则可分为两大类：客观保真度准则和主观保真度准则。客观保真度准则最常用的客观保真度准则是原图像和解码图像之间的均方根误差和均方根信噪比两种。主观保真度准则

很多解压图最终是供人观看的，一种常用的方法是让一组（不少于20人）观察者观察图像并给该图像评分，将他们对该图像的评分取平均，作为这幅图像的质量。信息论要素(ElementsofInformationTheory)

熵(Entropy)根据Shannon无干扰信息保持编码定理，若对原始图像数据的信息进行无失真图像编码，压缩后平均码长存在一个下限，这个下限是图像信息熵H。理论上最佳信息保持编码的平均码长可以无限接近图像信息熵H。但总是大于或等于图像的熵H。

平均码长(AverageCodeLength)平均信息量度，图像中各灰度级比特数的统计平均值。M:灰度级数Pk:灰度级Wk出现的概率

编码效率CodingEfficiency

冗余度Redundancy熵编码目的：使R尽量减少至H

信息论要素(ElementsofInformationTheory)例题设一离散信源如下：

信源概率编码求信源X的熵、平均码长和编码效率。解：

比特平均码长：编码效率：比特

变长最佳编码定理

对概率大的消息符号赋予短码字，而对概率小的信息符号赋予长码字，则编码的平均码长一定最短。

如：WmWnPm<PnPm：概率低Pn：概率高

tm>tntm：长码tn：短码符合定理的平均码长不符合定理的平均码长

唯一可译编码

所编码字序列能唯一地译出来。单义性、非续长码是唯一可译编码。单义性代码：任意一个有限长的码字序列只能被唯一地分割成一个个码字。非续长代码：集合中的码字不能由其他码字在后面添加码元构成。如：信源概率码I码II码III码IVW11/20000W21/4011001W31/8100110011W41/810111110111码I：非单义性、续长码如：00110W1W2W3W4W1W1W3W3W1W1W1W3W3W2码II：非单义性、续长码如：

010011W1W2W3W4W1W2W1W1W4

W1W2W1W3W2W2W1W2W1W1W2W2码III：单义性、非续长码如：010110111W1W2W3W4码IV：单义性、续长码如：0010110111W1W2W3W4单义非续长代码平均码长最短单义代码的充要条件：

D：代码中的码元种类；n：代码中的码字个数；ti：第i个码字的码长；如上例：图像编码压缩的分类图像压缩无损编码有损编码霍夫曼编码行程编码算术编码预测编码变换编码其它编码根据解压重建后的图像和原始图像之间是否具有误差，图像编码压缩分为无损（亦称无失真、无误差、信息保持）编码和有损（有失真或有误差）编码两大类。Huffman编码是1952年由Huffman提出的一种编码方法。这种编码方法是根据信源数据符号发生的概率进行编码的。霍夫曼编码(HuffmanCoding)思想：在信源数据中出现概率越大的符号，编码以后相应的码长越短；出现概率越小的符号，其码长越长，从而达到用尽可能少的码符表示信源数据。它在无损变长编码方法中是最佳的。把输入符号按出现的概率从大到小排列起来,接着把概率最小的两个符号的概率求和;把它（概率之和）同其余符号概率由大到小排序,然后把两个最小概率求和;重复2,直到最后只剩下两个概率为止。在上述工作完毕之后，从最后两个概率开始逐步向前进行编码。对于概率大的消息赋予0，小的赋予1。在反向进行的过程中，若概率不变，保留原码字；若概率分裂为两个，前几位保留原码字，最后一位一个赋“0”，另一个赋“1”码。

编码方法：符号集x1x2x3x4x5x6概率分布0.400.200.120.110.090.08Huffman编码符号集经排序的概率分布第一次合并后排序第二次合并后排序第三次合并后排序第四次合并后排序第五次合并后排序x10.400.400.400.400.601x20.200.200.230.370.40x30.120.170.200.23x40.110.120.17x50.090.11x60.08符号集经排序的概率分布第一次合并后排序第二次合并后排序第三次合并后排序第四次合并后排序第五次合并后排序x10.400.400.400.400.601x20.200.200.230.370.40x30.120.170.200.23x40.110.120.17x50.090.11x60.0801100010100000111100000000101001101001100100011符号集x1x2x3x4x5x6概率分布0.400.200.120.110.090.08Huffman编码100001001100100011

用二叉树方法实现Huffman编码方法也较为便利。

计算该信源的熵、编码后的平均码长，并思考对于同一图像采用Huffman编码，编码是否唯一？？0.230.4

x10.6

0.11

x4

10

100.37

0.20

x2

0.08

x60.09

x50.17

10

10

100.12

x3香农编码(ShannonCoding)编码方法：1、将输入灰度级按出现的概率由大到小排列；2、按计算各概率对应的码长；3、计算各灰度级对应的累加概率：

4、把各个累加概率由十进制数转换成二进制数：转换规则：乘2取整，先取的整数为高位，后取的整数为低位。5、将二进制表示的累加概率去掉多于ti的尾数，即得Wi对应的码字。算术编码(ArithmeticCoding)思想：

按照符号序列的出现概率区间分割，用一个实数代表一个数据流的输入符号，再将这个实数转化为一定位数的二进制代码。对于较长的消息，二进制代码的位数也会增加。它们是通过算术运算逐步形成码字的，因而得名。

设四阶Markov信源符号集为｛a,b,c,d｝，其概率分布为｛0.2,0.2,0.4,0.2｝。（1）若对该信源进行Huffman编码，可得其平均码长为2.0比特/字符（2）若信源发出序列为｛b,c,a,c,d｝，算数编码过程如下：各个数据符号在半封闭实数区间[0，1）内按概率进行赋值范围设定为数据流bcacd编码区间[0.2,0.4）[0.28,0.36）[0.28,0.296）[0.2864,0.2928）[0.29152,0.2928）区间长度0.20.080.0160.00640.00128新子区间左端＝前一子区间左端＋新子区间左边累加概率×前子区间长度新子区间长度＝当前区间概率×前子区间长度行程编码(Run-