图像压缩(第14-16讲)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,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,背景知识,(1),空间冗余,在一幅图像中规则的物体和规则的背景具有很强的相关性。,(4),视觉冗余,人眼的视觉系统对于图像的感知是非均匀和非线性的，对图像的变化并不都能察觉出来。,(2),时间冗余,电视图像序列中相邻两幅图像之间有较大的相关性。,(3),结构冗余和知识冗余,图像从大面积上看，常存在有纹理结构，称之为结构冗余。,5.1,背景知识,通用的图像压缩与解压系统框图,5.2,基本概念,信源中每个符号的平均信息量，称为信息的熵，可表示为,定义,1,信息熵,式中 为灰度级 出现的概率。,5.2,基本概念,全部信息所占用的码子的平均长度 ，即,定义,2,平均码长,式中 为灰度级 对应的码长，为灰度级 出现的概率。,5.2,基本概念,若对原始图像数据的信息进行信源的无失真图像编码，压缩后平均码长 存在一个下限，这个下限就是信息源信息熵 ，,定理,1,Shannon,无干扰信息保持编码定理,式中 为灰度级 对应的码长，为灰度级 出现的概率。,5.2,基本概念,图像压缩后的冗余度,定义,3,冗余度,式中 为信息熵，为平均码长,5.2,基本概念,图像的编码效率,定义,4,编码效率,式中 为信息熵，为平均码长,5.2,基本概念,解压后的图像与原始图像不存在误差，称为无损压缩；,解压后的图像与原始图像存在误差，称为有损压缩。,定义,4,无损压缩与有损压缩,5.3,Huffman,编码,Huffman,于,1952,年提出,基本思想：频率高的，赋给短码；,频率低的，赋给长码；,5.3,Huffman,编码,Huffman,编码是最优的。换言之，若,C*,是,Huffman,编码，另有一个唯一可译码,C,，不等式,L(C*)L(C),恒成立。,定理,1,Huffman,编码的最优性,提高：课后请同学证明，,Huffman,编码具有最优性,解释：在给定信源符号的概率分布和码字母表的前提下，没有其他编码可以获得比,Huffman,编码更短的平均码长。,5.3,Huffman,编码,例,1,：,设有编码输入 ，其频率分别为：,求：,1,）、,Huffman,编码,2,）、计算,Huffman,编码的平均码长,5.3,Huffman,编码,例,1,：,第一次重排,编码,结果,输入,数据,对应,概率,W,1,0.4,W,2,0.3,W,3,0.1,W,4,0.1,W,5,0.06,W,6,0.04,0.4,0.3,0.1,0.1,0.1,0.4,0.3,0.2,0.1,0.4,0.3,0.3,0.6,0.4,第二次重排,第三次重排,第四次重排,0,1,1,1,1,1,1,00,01,00,00,00,00,010,011,011,0100,0101,0100,01010,01011,01011,01010,011,011,0100,5.3,Huffman,编码,例,1,（续）：,Huffman,编码步骤,Step1:,把,信源符号 按出现概率的值由大到小的顺序排列；,Step2,：然后把这两个概率相加作为一个新的辅助符号的概率；,Step3,：将新的辅助符号与其他符号一起重新按概率大小顺序排列；,Step4,：跳到第,2,步，直到出现,2,个为止；,Step5,：,对最后两个分配以“,0”,和“,1,5.3,Huffman,编码,Step5:,用线将符号连接起来，从而得到一个码树，树的,N,个端点对应,N,个信源符号；,Step6,：从最后一个概率为,1,的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“,0”,或“,1”,顺序排列起来，就是端点所对应的信源符号的码字。,5.3,Huffman,编码,例,1,（续）：,输入数据,W,1,W,2,W,3,W,4,W,5,W,6,概率,0.4,0.3,0.1,0.1,0.06,0.04,编码结果,1,00,011,0100,01010,01011,码长,1,2,3,4,5,5,5.3,Huffman,编码,Huffman,编码性质,性质,2,：,Huffman,方法构造出来的码不是惟一的,性质,3,：,Huffman,编码中，没有一个码字是另一个码,字的前缀，因此，每个码字惟一可译。,性质,4,：,Huffman,编码对不同的信源，其编码效率是,不同的。,性质,1,：,Huffman,编码具有最优性,5.3,Huffman,编码,例,2,：,设有编码输入 ，其频率分别为：,计算其,Huffman,编码和码长。,问题：没有达到“高频短码，低频长码”的要求！,5.3,Huffman,编码,例,3,：,A=a,b,c,P(a)=0.95,P(b)=0.02,P(c)=0.03,计算其,Huffman,编码、码长和编码效率。,问题：,信源符号的概率严重不对称的情况下，,Huffman,编码恶化。,Huffman,编码：,a0,b11,c10,5.4,算术编码（,Arithmetic Coding,）,基本原理,将待压缩的整段数据映射到实数半开区间,0,，,1,）内，以某一区段的任一个数值作为数据段的唯一可译代码。,0,1,5.4,算术编码（,Arithmetic Coding,）,从另一种角度对很长的信源符号序列进行有效编码,对整个序列信源符号串产生一个唯一的标识（,tag,）,不用对该长度所有可能的序列编码,标识是,0,1),之间的一个数（二进制小数，可作为序列的二进制编码）,5.4,算术编码,（,Arithmetic Coding,）,编码函数,为新子区间的起始位置,为新子区间的结束位置,为前子区间的起始位置,为前子区间的长度,为当前符号所在区间的左端,为当前符号所在区间的右端,5.5,行程编码,基本原理,在给定的图像数据中寻找连续重复的数值，然后用两个字符值取代这些连续值。,例子：,计算,aabbbbbbcccccdeee,的行程编码。,解答：,2a6b5c1d3e,5.6,本章小结,思考题,1,、,平均码长、冗余度、编码效率的定义,2,、,Huffman,编码的基本原理是什么？如何求解,Huffman,编码？,3,、算术编码的基本原理是什么？,4,、行程编码的基本原理是什么？如何求解行程编码？,我的联系方式：,手机：,13950109178,办公室：信息管理与信息系统,Email,：,谢谢！,