图像压缩(第14-16讲)

第5章图像压缩

Chapter5

ImageCompression

第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.3Huffman编码5.4算术编码5.5行程编码5.6本章小结5.1背景知识(1)空间冗余

在一幅图像中规则的物体和规则的背景具有很强的相关性。(4)视觉冗余

人眼的视觉系统对于图像的感知是非均匀和非线性的，对图像的变化并不都能察觉出来。(2)时间冗余电视图像序列中相邻两幅图像之间有较大的相关性。(3)结构冗余和知识冗余图像从大面积上看，常存在有纹理结构，称之为结构冗余。5.1背景知识通用的图像压缩与解压系统框图5.2基本概念信源中每个符号的平均信息量，称为信息的熵，可表示为定义1信息熵式中为灰度级出现的概率。5.2基本概念全部信息所占用的码子的平均长度，即定义2平均码长式中为灰度级对应的码长，为灰度级出现的概率。5.2基本概念若对原始图像数据的信息进行信源的无失真图像编码，压缩后平均码长存在一个下限，这个下限就是信息源信息熵，定理1Shannon无干扰信息保持编码定理式中为灰度级对应的码长，为灰度级出现的概率。5.2基本概念图像压缩后的冗余度定义3冗余度式中为信息熵，为平均码长5.2基本概念图像的编码效率定义4编码效率式中为信息熵，为平均码长5.2基本概念解压后的图像与原始图像不存在误差，称为无损压缩；解压后的图像与原始图像存在误差，称为有损压缩。定义4无损压缩与有损压缩5.3Huffman编码

Huffman于1952年提出基本思想：频率高的，赋给短码；频率低的，赋给长码；5.3Huffman编码

Huffman编码是最优的。换言之，若C*是Huffman编码，另有一个唯一可译码C’，不等式

L(C*)≤L(C’)恒成立。定理1Huffman编码的最优性提高：课后请同学证明，Huffman编码具有最优性解释：在给定信源符号的概率分布和码字母表的前提下，没有其他编码可以获得比Huffman编码更短的平均码长。5.3Huffman编码例1：设有编码输入，其频率分别为：求：1）、Huffman编码

2）、计算Huffman编码的平均码长5.3Huffman编码例1：第一次重排编码结果输入数据对应概率W10.4W20.3W30.1W40.1W50.06W60.040.40.30.10.10.10.40.30.20.10.40.30.30.60.4第二次重排第三次重排第四次重排01111110001000000000100110110100010101000101001011010110101001101101005.3Huffman编码例1（续）：Huffman编码步骤Step1:把信源符号按出现概率的值由大到小的顺序排列；Step2：然后把这两个概率相加作为一个新的辅助符号的概率；Step3：将新的辅助符号与其他符号一起重新按概率大小顺序排列；Step4：跳到第2步，直到出现2个为止；Step5：对最后两个分配以“0”和“15.3Huffman编码Step5:用线将符号连接起来，从而得到一个码树，树的N个端点对应N个信源符号；Step6：从最后一个概率为1的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“0”或“1”顺序排列起来，就是端点所对应的信源符号的码字。5.3Huffman编码例1（续）：输入数据W1W2W3W4W5W6概率0.40.30.10.10.060.04编码结果10001101000101001011码长1234555.3Huffman编码Huffman编码性质性质2：Huffman方法构造出来的码不是惟一的性质3：Huffman编码中，没有一个码字是另一个码字的前缀，因此，每个码字惟一可译。性质4：Huffman编码对不同的信源，其编码效率是不同的。性质1：Huffman编码具有最优性5.3Huffman编码例2：设有编码输入，其频率分别为：计算其Huffman编码和码长。问题：没有达到“高频短码，低频长码”的要求！5.3Huffman编码例3：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03计算其Huffman编码、码长和编码效率。问题：信源符号的概率严重不对称的情况下，Huffman编码恶化。Huffman编码：a 0b 11c 105.4算术编码（ArithmeticCoding）基本原理将待压缩的整段数据映射到实数半开区间[0，1）内，以某一区段的任一个数值作为数据段的唯一可译代码。015.4算术编码（ArithmeticCoding）从另一种角度对很长的信源符号序列进行有效编码对整个序列信源符号串产生一个唯一的标识（tag）不用对该长度所有可能的序列编码标识是[0,1)之间的一个数（二进制小数，可作为序列的二进制编码）5.4算术编码（ArithmeticCoding）编码函数为新子区间的起始位置为新子区间的结束位置为前子区间的起始位置为前子区间的长度为当前符号所在区间的左端为当前符号所在区间的右端5.5行程编码基本原理在给定的图像数据中寻找连续重复的数值，然后用两个字符值取代这些连续值。例子：计算aabbbbbbcccccdeee的行程编码。解答：2a6b5c1d3e5.6本章小结思考题1、平均码长、冗余度、编码效率的定义