第7章 图像编码与压缩

1、 7.1 概述 7.2 图像保真度准则 7.3 图像的统计编码方法 7.4 预测编码 7.5 变换编码第七章 图像编码与压缩7 7.1 .1 概述概述一、图像数据压缩的必要性与可能性一、图像数据压缩的必要性与可能性 数据压缩的研究内容包括数据的表示、传输、变换和编码方法，目的是减少存储数据所需的空间和传输所用的时间。 图像编码与压缩就是对图像数据按一定的规则进行变换和组合，达到以尽可能少的代码（符号）来表示尽可能多的图像信息。为什么要对图像进行压缩？图像数据的特点之一：数据量大为什么能对图像进行压缩？图像中存在着冗余数据二、数据冗余类别二、数据冗余类别(1) 编码冗余 与灰度分布的概率特性有关

2、(2) 象素间冗余空间冗余，几何冗余(3) 心理视觉冗余与主观感觉有关 减少/消除其中的一种/多种冗余，就能取得数据压缩的效果 1. 1. 编码冗余编码冗余 编码：用符号表达图像 对图像编码需建立码本来表达图像数据。码本：码本：用来表达一定量的信息或一组事件所 需的一系列符号（如字母、数字等）码字：码字：对每个信息或事件所赋的码符号序列码字的长度（字长）：码字的长度（字长）：每个码字里的符号个数图象中灰度出现的概率：不同灰度出现的概率不同。 设用来表示Sk每个数值的比特数是 ，则表示每个像素所需要的平均比特数为：平均比特数为：10avg)()(LkkskspslL1 , , 1 , 0)(Lk

3、nnspkks)(ksl如果编码时所用的码本不能使上式达到最小，说明存在编码冗余。变长编码：变长编码：用较少的比特数表示出现概率较大的灰度级，用较多的比特数表示出现概率较小的灰度级。思考：该图像的熵是多少？思考：该图像的熵是多少？2.77(bit)2.77(bit)（2 2） 象素间冗余象素间冗余图像内部相邻像素之间存在较强的相关性所造成的冗余00.81051015202500.810510152025规则 冗余大不规则冗余小（3 3）心理视觉冗余心理视觉冗余主观：因人而异，因应用要求而异其存在与人观察图象的方式有关 眼睛对某些视觉信息更敏感 人对某些视觉信

4、息更关心心理视觉冗余与实在的视觉信息有联系心理视觉冗余丢掉后，不能找回，即信息会丢失。 图像数据到底能压缩多少，除了和图像本身存在的冗余度大小有关外，还取决于对图像质量的要求，如 广播电视 压缩比31 可视电话 压缩比15001 三、图像编码压缩的分类三、图像编码压缩的分类 根据解压重建后的图像和原始图像之间是否具有误差，图像编码压缩分为：l 无损编码l 有损编码 根据编码作用域划分，图像编码分为：l 空间域编码l 变换域编码 图像压缩无损编码有损编码霍夫曼编码行程编码算术编码预测编码变换编码其它编码图1 图像编码压缩分类图像保真度准则：描述解码图像相对于原始图像偏离 程度的测度。常用的保真度

5、准则可分为两大类：l 客观保真度准则：客观保真度准则：用编码输入图与解码输出图的某个确定函数表示损失的信息量， 便于计算或测量l 主观保真度准则：主观保真度准则：主观测量图象的质量，因人而异7 7.2 .2 图像保真度准则图像保真度准则一、客观保真度准则一、客观保真度准则 最常用的客观保真度准则是原图像和解码图像之间的均方根误差和均方根信噪比两种。 点误差图误差均方根误差解压图像的均方信噪比),(),(),(yxfyxfyxe 1010),(),( MxNyyxfyxf21 10102 rms),(),( 1 MxNyyxfyxfMNe 10102 10102),(),( ),( MxNyMx

6、NymsyxfyxfyxfSNR令 1010),( 1MxNyyxfMNf 10102 10102 ),(),( ),( lg10MxNyMxNyyxfyxffyxfSNR10102 2max),(),(lg10MxNyyxfyxffMNPSNR实际使用中，常将SNRrms归一化，并用分贝(dB)表示。令令 ，则得峰值信噪比，则得峰值信噪比yxff,maxmax（归一化）信噪比信噪比：二、主观保真度准则二、主观保真度准则 很多解压图最终是供人观看的，一种常用的方法是让一组（不少于20人）观察者观察图像并给该图像评分，将他们对该图像的评分取平均，作为这幅图像的质量。 表1 电视图象质量评价尺度

7、评分评价说 明1优秀图象质量非常好，如同人能想象出的最好质量。2良好图象质量高，观看舒服，有干扰但不影响观看。3可用图象质量可接受，有干扰但不太影响观看。4刚可看图象质量差，干扰有些妨碍观看，观察者希望改进。5差图象质量很差，妨碍观看的干扰始终存在，几乎无法观看。6不能用图象质量极差，不能使用。一、图像冗余度和编码效率一、图像冗余度和编码效率7.3 7.3 统计编码方法统计编码方法 根据信源的概率分布特性分配可变长码，使平均码长非常接近于熵，这种压缩编码称为统计编码。统计编码。 根据Shannon无干扰信息保持编码定理，若对原始图像数据的信息进行无失真图像编码，压缩后平均码长存在一个下限，这个

8、下限是图像信息熵H。理论上最佳信息保持编码的平均码长可以无限接近图像信息熵H，但总是大于或等于图像的熵H。 iLiippH210log信息熵压缩后平均码长 10LiiipB是灰度级i的编码长度，pi是灰度级i出现的概率i编码效率为：1HBrrBH11冗余度定义为： 当经过编码压缩后，图像信息的冗余度接近于零，或编码效率接近于1，这类编码方法称为高效编码。二、霍夫曼二、霍夫曼(Huffman)(Huffman)编码编码 霍夫曼编码是1952年由Huffman提出的一种编码方法，是一种无损编码方法。这种编码方法是根据信源数据各信号发生的概率进行编码的。 思想：在信源数据中出现概率越大的符号，编码以

9、后相应的码长越短；出现概率越小的符号，其码长越长，从而达到用尽可能少的码符表示信源数据。 在无损变长编码方法中是最佳的。霍夫曼编码实例： 设输入信源为 ，其频率分布分别为求其霍夫曼编码。 654321,aaaaaaa 654321,wwwwwwW 3 . 004. 01 . 006. 04 . 01 . 0654321iiapaaaaaaa霍夫曼编码步骤：霍夫曼编码步骤：(1) 缩减信源符号数量 将信源符号按出现概率从大到小排列，然后将概率最小的相加，再重新排序，重复，直到剩下两个概率为止。0.10.060.00.40.

10、1234a12a5a3a6a4a初始信源信源的消减步骤符号概率(2)对每个信源符号赋值从（消减到）最小的信源开始向前进行编码，逐步回到初始信源。0.10.060.00.40.61234a12a5a3a6a4a初始信源对消减信源的赋值符号概率10001101000101100010011100010110001101000101001011码字思考：思考：计算该信源的熵、编码后的平均码长及编码效率。霍夫曼编码结果霍夫曼编码结果 平均码长 信源熵 编码效率2 . 2)543(1 . 02

11、3 . 014 . 010LkiipB14. 2log112LiiiPPH973. 02 . 214. 2BH霍夫曼编码的计算量霍夫曼编码的计算量信源：N个符号信源消减次数：N -2码赋值次数：N -2最优的变长编码方法牺牲编码效率来换取编码速度对于同一图像采用霍夫曼编码，编码是否唯一？霍夫曼编码的特点：（1）编码值不是唯一的；（2）当图像灰度值分布不均匀时，霍夫曼编码效率 高；当概率分布比较均匀时，编码效率低；（3）不能使用某种数学模型建立信源符号与编码之 的关系，而必须通过查表方法建立它们之间 的对应关系。 利用霍夫曼编码需要对图像扫描两遍，第一遍获取图像每个灰度级出现的概率，进行霍夫曼编

12、码，获取编码表；第二遍扫描图像是根据编码表对原图像各像素编码，生成压缩文件。Huffman Huffman 编码结果？编码结果？自然码平均码长：自然码平均码长：3思考思考Huffman编码输入输入01234567输入概率输入概率0.020.050.000.220.16排序排序输入输入65743210输入概率输入概率90.050.02Huffman编码第第1步步90.07输入输入65743210概率概率90.050.02第第2步步0.2

13、60.140.12第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42Huffman编码第第1步步90.07输入输入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.4201010101

14、010101Huffman编码第第1步步90.07输入输入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101016=10Huffman编码第第1步步90.07输入输入65743210概率概率

15、90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101015=11Huffman编码第第1步步90.07输入输入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5

16、步步0.420.320.26第第6步步0.580.42010101010101017=000Huffman编码第第1步步90.07输入输入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101014=010Huffman编码第第1步步90.

17、07输入输入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101013=011Huffman编码第第1步步90.07输入输入65743210概率概率90.050.02第第2步步2第第3步步0.

18、260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101012=0010Huffman编码第第1步步90.07输入输入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101011=

19、00110Huffman编码第第1步步90.07输入输入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101010=00111编码结果代码代码001110011000100110101110000码长码长55433223输入输入01234567输入概率输入概率0.020.050.09

20、00.220.16平均码长：平均码长：2.81也可用二叉树二叉树实现Huffman编码方法。（1）统计出每个元素出现的频率；（2）从左到右把上述频率按从大到小的顺序排列；（3）选出频率最小的两个值，作为二叉树的两个叶子 节点，将其和作为它们的根节点，两个叶子节点 不再参与排序，新的根节点同其余元素出现的频 率排序；（4）重复（3），直到最后得到和为1的根节点；（5）将形成的二叉树的子节点概率大的为0，概率小 的为1。把最上面的根节点到最小面的叶子节点 途中遇到的0，1序列串起来，就得到了各个元素 的编码。 0.2霍夫曼编码： 10 00 0110 010 0111 11原

21、始信源： a1 a2 a3 a4 a5 a6 2 . 004. 015. 006. 035. 02 . 0654321iiapaaaaaaaa2 0.35 1 0a6 a1 0.2 a4 0.15 a3 0.06 a5 0.04 00.60 0 1 1 00 10 1主要步骤为：(1) 将信源符号依其概率从大到小排列；(2) 将信源符号分成概率和接近的两部分；(3) 分别给两部分的信源符号组合赋值；(4) 如果两部分均只有一个信源符号，编码结束，否则返回(2)继续进行。三、费诺三、费诺- -仙农编码仙农编码 3 . 004. 01 . 006. 04 . 01 . 0654

22、321iiapaaaaaaa输入概率a20.41a60.300a10.1100a40.11a30.0610a50.0411000100010101100111编码编码四、算术编码四、算术编码l 算术编码是一种从整个符号序列出发，采用递推形式连续编码的方法。l 算术编码中，源符号和码字间的一一对应关系并不存在。一个算术码字要赋给整个信源符号序列。l 算术编码的结果是在0到1之间的一个实数。只用到加法和移位运算，所以称为算术编码。算术编码示例：算术编码示例： 有1个由4-符号信源a1, a2, a3, a4组成的符号序列：b1b2b3b4b5 = a1a2a3a3a40.067 520.068 8

23、100.200.080.040.0720.0560.062 4编码序列b =22a1b =a1b =3a3b =3a44ab =53aa1a12a2a3a3a3aa12a2a2a3aa1a14a4a4a4a4a0.068各符号出现的概率：P(a1)=0.2 p(a2)=0.2 p(a3)=0.4 p(a4)=0.2解码过程：0.067 520.068 8100.200.080.040.0720.0560.062 4编码序列b =22a1b =a1b =3a3b =3a44ab =53aa1a12a2a3a3a3aa12a2a2a3aa1a14a4a4a4a4a各符号出现的概率：P(a1)=0.

24、2 p(a2)=0.2 p(a3)=0.4 p(a4)=0.8解码解码0.040.080.160.0680.0480.0560.0720.05920.06240.06880.063880.06496五、行程编码五、行程编码 简称RLE（Run-Length-Encoding）压缩方法，也称游程编码，是一种建立在统计特性基础上的无损压缩编码方式，是最简单的图像压缩方式之一。 分为：l 一维行程编码l 二维行程编码 行程编码在处理包含大量重复信息的数据时可以获得很好的压缩效率。 在一个逐行存储的图象中，具有相同灰度值的一些象素组成的序列称为一个行程。编码时，对于每个行程只存储一个

25、灰度值及个数。这种按照行程进行的编码被称为行程编码（Run Length Encoding）。 如“aaabbbbccccddddedddaaa”经过行程编码为：3a4b4c4d1e3d3a。 l 一维行程编码一维行程编码只考虑消除行内像素间的相关性。l 二维行程编码二维行程编码 利用图像的二维信息的强相关性，按照一定的扫描路径遍历所有的像素形成一维的序列，对序列进行一维行程编码的方法。 对一幅灰度图像进行二维行程编码，首先将图像分为一定大小的子块，然后对每个子块按照一定的扫描路径遍历所有的像素形成一维的序列，进行一维行程编码，所有子块的编码就是图像的二维行程编码。图 二维行程编码数据排列方式

26、例：例：130130130129134133129130130130130129134133130130130130130129132132130130129130130129130130129129127128127129131 129131 130127128127128127128132132125126129129127129133132127125128128126130131131f数据量：数据量：6464* *8=512(bit)8=512(bit)如果按照行扫描的顺序排列的话，数据分布为：130，130，130，129，134，133，129，130； 130，130，130，

27、129，134，133，130，130； 130，130，130，129，132，132，130，130；129，130，130，129，130，130，129，129； 127，128，127，129，131，129，131，130；127，128，127，128，127，128，132，132； 125，126，129，129，127，129，133，132；127，125，128，128，126，130，131，131行程编码为行程编码为: :（3，130），（），（1，129），（），（1，134），（），（1，133），（），（1，129），（），（4，130），），（1，129），

28、（），（1，134），（），（1，133），（），（5，130），（），（1，129），（），（2，132），），（2，130），（），（1，129），（），（2，130），（），（1，129），（），（2，130），（），（2，129），），（1，127），（），（1，128），（），（1，127），（），（1，129），（），（1，131），（），（1，129），），（1，131），（），（1，130），（），（1，127），（），（1，128），（），（1，127），（），（1，128），），（1，127），（），（1，128），（），（2，132），（），（1，125），（），（1，1

29、26），（），（2，129），），（1，127），（），（1，129），（），（1，133），（），（1，132），（），（1，127），（），（1，125），），（2，128），（），（1，126），（），（1，130），（），（2，131）数据量为数据量为:46:46* *（3+83+8）=506(bit) (98.83%)=506(bit) (98.83%)如果按照列扫描的顺序排列的话，数据分布为：130，130，130，129，127，127，125，127； 130，130，130，130，128，128，126，125； 130，130，130，130，127，127，129，12

30、8；129，129，129，129，129，128，129，128； 134，134，132，130，131，127，127，126；133，133，132，130，129，128，129，130； 129，130，130，129，131，132，133，131；130，130，130，129，130，132，132，131行程编码为行程编码为: :数据量为数据量为:42:42* *（3+83+8）=462(bit) (92.03%)=462(bit) (92.03%)（3，130），（），（1，129），（），（2，127），（），（1，125），（），（1，127），（），（4， 130）

31、，），（2，128），（），（1，126），（），（1，125），（），（4，130），（），（2，127），（），（1，129），），（1，128），（），（5，129），（），（1，128），（），（1，129），（），（1，128），（），（2， 134），），（1，132），（），（1，130），（），（1，131），（），（2，127），（），（1，126），（），（2，133），），（1，132），（），（1，130），（），（1，129），（），（1，128），（），（1，129），（），（1，130），）， （1，129），（），（2，130），（），（1，129），（），（1

32、，131），（），（1，132），（），（1，133），），（1，131），（），（3，130），（），（1，129），（），（1，130），（），（2，132），（），（1，131）如果按照方式(a)扫描的顺序排列的话，数据分布为：130，130，130，130，130，130，130，130，130；129，129，129，129，130，130，129；127，128，127，129，131，130，132，134，134；133，133，132，130，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129

33、，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127行程编码为行程编码为: :数据量为数据量为:43:43* *（3+83+8）=473(bit) (94.22%)=473(bit) (94.22%)（7，130），（），（2，130），（），（4，129），（），（2，130），（），（1，129）；（）；（1，127），），（1，128），（），（1，127），（），（1，129），（），（1，131），（），（1，130），（），（1，132），），（2，134），（），（2，133），（），（1

34、，132），（），（1，130），（），（1，129），（），（1，128），），（1，127），（），（1，128），（），（1，127），（），（1，128），（），（1，127），（），（1，125），），（1，126），（），（2，129），（），（1，127），（），（1，129），（），（1，133），（），（1，132），），（1，131），（），（1，129），（），（2，130），（），（1，129），（），（3，130），（），（1，129），），（1，130），（），（2，132），（），（2，131），（），（1，130），（），（1，126），（），（2，128），）

35、，（2，127）7.4 7.4 预测编码预测编码空域方法，消除象素间的冗余预测编码的基本思想：通过仅提取每个像素中的新信息并对它们编码来消除像素间的冗余。预测编码分为：一、无损预测编码 信息保存型二、有损预测编码 信息损失型一、无损预测编码无损预测编码系统无损预测编码系统编码器 + + 解码器（有相同的预测器）无损预测编码系统无损预测编码过程无损预测编码过程输入序列： fn (n = 1, 2, )预测输出： （舍入成整数）预测误差：误差编码：在符号编码器中用变长码编误差解压序列：哪里取得了压缩？nnnffennnfefnf（消除了象素间冗余）（消除了象素间冗余） 预测编码中，关键预测编码中，

36、关键：如何进行预测如何进行预测？最常用的方法是线性预测最常用的方法是线性预测m 阶线性预测： miininfaf 1round 式中，m 是线性预测器的阶，ai为预测系数，round为舍入函数。 1-D线性预测：miinyixfayxf 1)(round )(,即1-D线性预测是当前行扫描到的先前像素的函数一阶(m=1)1-D线性预测：)1(round )(yxafyxfn,eee2exp21)(eep的均方差是误差ee预测误差的概率密度函数：也称为前值预测。二、有损预测编码系统二、有损预测编码系统增加了1个量化器，预测器放在1个反馈环中 有损预测编码系统有损预测编码系统有损预测编码系统输入序

37、列： fn (n = 1, 2, )量化输出：预测输入：解压序列：编码误差：哪里又又取得了压缩？nnnfef nnnfef （量化，减少了（量化，减少了 心理视觉冗余）心理视觉冗余） )(nneqe nnff德尔塔调制（DM）是一种简单的有损预测编码方法，其预测器与量化器分别如下： 预测器 量化器预测系数 a 1，常数 c 0 1 nnfaf其它对cecenn0 DM编码举例 取a=1,c=6.5 1 nnfaf其它对cecenn0 7.5 7.5 变换编码变换编码变换编码的基本原理：利用可逆的线性变换将图像从空间域中转换为变换域中的一组系数，然后对变换系数进行量化、编码，达到压缩数据的目的。频域方法，非信息保