第五章 图像压缩(第14-16讲)

1、第5章 图像压缩 Chapter5 Image Compression 第14周周三34节2016年05月30日第15周周二34节2016年06月06日第16周周二34节2016年06月13日 JMU 2009 All Right Reserved本章的主要内容5.1 背景知识5.2 基本概念5.3 Huffman编码5.4 算术编码5.5 行程编码5.6 本章小结5.1 背景知识 在一幅图像中规则的物体和规则的背景具有很强的相关性。 人眼的视觉系统对于图像的感知是非均匀和非线性的，对图像的变化并不都能察觉出来。 电视图像序列中相邻两幅图像之间有较大的相关性。 图像从大面积上看，常存在有纹理结

2、构，称之为结构冗余。5.1 背景知识通用的图像压缩与解压系统框图5.2 基本概念信源中每个符号的平均信息量，称为信息的熵，可表示为H102logLiiiPPH式中 为灰度级 出现的概率。iPi5.2 基本概念 全部信息所占用的码子的平均长度 ，即B10LiiiPB式中 为灰度级 对应的码长， 为灰度级 出现的概率。iiiiP5.2 基本概念 若对原始图像数据的信息进行信源的无失真图像编码，压缩后平均码长 存在一个下限，这个下限就是信息源信息熵 ，BH10210logLiiiLiiiPPHPB式中 为灰度级 对应的码长， 为灰度级 出现的概率。iiiiP5.2 基本概念 图像压缩后的冗余度r1H

3、Br式中 为信息熵， 为平均码长HB5.2 基本概念 图像的编码效率BH式中 为信息熵， 为平均码长HB5.2 基本概念解压后的图像与原始图像不存在误差，称为无损压缩；解压后的图像与原始图像存在误差，称为有损压缩。其它编码变换编码预测编码有损压缩行程编码算术编码编码无损压缩图像压缩技术Huffman5.3 Huffman编码 Huffman于1952年提出 基本思想：频率高的，赋给短码； 频率低的，赋给长码；5.3 Huffman编码 Huffman编码是最优的。换言之，若C*是Huffman编码，另有一个唯一可译码C，不等式 L(C*) L(C)恒成立。提高：课后请同学证明，Huffman编

4、码具有最优性解释：在给定信源符号的概率分布和码字母表的前提下，没有其他编码可以获得比Huffman编码更短的平均码长。5.3 Huffman编码例例1 1：设有编码输入设有编码输入 ，其频率分别为：，其频率分别为：654321,wwwwwwW , 4 . 01wP, 3 . 02wP, 1 . 03wP, 1 . 04wP,06. 05wP,04. 06wP求：求：1 1）、）、HuffmanHuffman编码编码 2 2）、计算）、计算HuffmanHuffman编码的平均码长编码的平均码长5.3 Huffman编码例例1 1：第一次重排编码编码结果结果输入输入数据数据对应对应概率概率W10

5、.4W20.3W30.1W40.1W50.06W60.00.60.4第二次重排第三次重排第四次重排01111110001000000000100110110100010101000101001011010110101001101101005.3 Huffman编码例1（续）：Huffman编码步骤Step1 : 把信源符号 按出现概率的值由大到小的顺序排列；iWStep2：然后把这两个概率相加作为一个新的辅助符号的概率；Step3：将新的辅助符号与其他符号一起重新按概率大小顺序排列；Step4：跳到第2步，直到出现2个为

6、止；Step5：对最后两个分配以“0”和“15.3 Huffman编码Step5 : 用线将符号连接起来，从而得到一个码树，树的N个端点对应N个信源符号；Step6：从最后一个概率为1的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“0”或“1”顺序排列起来，就是端点所对应的信源符号的码字。5.3 Huffman编码例例1 1（续）：（续）：输入数据输入数据W1W2W3W4W5W6概率概率0.10.060.04编码结果编码结果10001101000101001011码长码长1234552 . 204. 0506. 051 . 041 . 033 . 024 . 011

7、0LiiiPB1436. 2)04. 0log04. 006. 0log06. 01 . 0log1 . 01 . 0log1 . 03 . 0log3 . 04 . 0log4 . 0(log222222102LiiiPPH5.3 Huffman编码Huffman编码性质性质2：Huffman方法构造出来的码不是惟一的性质3：Huffman编码中，没有一个码字是另一个码 字的前缀，因此，每个码字惟一可译。性质4：Huffman编码对不同的信源，其编码效率是 不同的。性质1：Huffman编码具有最优性5.3 Huffman编码例2：设有编码输入 ，其频率分别为：21,wwW ,321wP,3

8、12wP计算其Huffman编码和码长。问题：没有达到“高频短码，低频长码”的要求！bitH91829. 052832. 038997. 0)31(log31)32(log32221311321B08898. 0191829. 011HBr5.3 Huffman编码例3：A = a, b, c, P(a) = 0.95, P(b) = 0.02, P(c) = 0.03计算其Huffman编码、码长和编码效率。问题：信源符号的概率严重不对称的情况下， Huffman编码恶化。335. 01518. 01129. 00703. 0)03. 0(log03. 0)02. 0(log02. 0)95

9、. 0(log95. 0222H05. 103. 0202. 0295. 01B1343. 21335. 005. 11HBrHuffman编码：a0b11c105.4 算术编码（Arithmetic Coding）基本原理基本原理 将待压缩的整段数据映射到实数半开区间0，1）内，以某一区段的任一个数值作为数据段的唯一可译代码。013421aaaa3112aaaa5.4 算术编码（Arithmetic Coding）n 从另一种角度对很长的信源符号序列进行有效编码n 对整个序列信源符号串产生一个唯一的标识（ tag ）n 不用对该长度所有可能的序列编码n 标识是0,1)之间的一个数（二进制小数，可作为序列的二进制编码）5.4 算术编码（Arithmetic Coding）编码函数编码函数LCFNLCFNrselss为新子区间的起始位置为新子区间的起始位置为新子区间的结束位置为新子区间的结束位置为前子区间的起始位置为前子区间的起始位置为前子区间的长度为前子区间的长度为当前符号所在区间的左端为当前符号所在区间的左端为当前符号所在区间的右端为当前符号所在区间的右端sNeNsFLlCrC5.5 行程编码基本原理 在给定的图像数据中寻找连续重复的数值，然后用两个字符值取代这些连续值。例子： 计算 aabbbb