图像与数字图像通信chapter-3

1、3.1 图像压缩编码的分类图像压缩编码的分类3.2 数据压缩与信息论基础数据压缩与信息论基础3.3 霍夫曼编码霍夫曼编码3.4 游程长度编码游程长度编码3.5 算术编码算术编码数字图象通常要求很大的比特数，这给图象的数字图象通常要求很大的比特数，这给图象的传输和存储带来相当大的困难。要占用很多的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。资源，花很高的费用。 如一幅如一幅512x512的黑白图象的比特数为的黑白图象的比特数为 512x512x8=。 再如一部再如一部90分钟的彩色电影，每秒放映分钟的彩色电影，每秒放映24帧。把它数字化，每帧帧。把它数字化，每帧512x512象素

2、，象素，每象素的每象素的 、 三分量分别占三分量分别占8 bit，总比，总比特数为特数为 90 x60 x24x3x512x512x8bit=。 如一张如一张CD光盘可存光盘可存600兆字节数据，这部兆字节数据，这部电影光图象（还有声音）就需要电影光图象（还有声音）就需要张张CD光光盘用来存储。盘用来存储。 对图象数据进行对图象数据进行压缩显得非常必要压缩显得非常必要。 本章讨论的问题：在满足一定条件下，能否本章讨论的问题：在满足一定条件下，能否减小图象减小图象bitbit数，以及用什么样的编码方法使之数，以及用什么样的编码方法使之减少。减少。图像压缩编码限失真编码无失真编码行程编码LZW编码

3、哈夫曼编码算术编码无损预测编码位平面编码有损预测编码分形编码模型编码子带编码神经网络编码变换编码K.L变换Haar变换Walsh.Hadamard变换离散余弦变换离散傅立叶变换斜变换小波变换1. 1.图象压缩是可能的图象压缩是可能的：n一般原始图象中存在很大的冗余度。一般原始图象中存在很大的冗余度。n用户通常允许图象失真。用户通常允许图象失真。n当信道的分辨率不及原始图象的分辨率当信道的分辨率不及原始图象的分辨率时，降低输入的原始图象的分辨率对输出时，降低输入的原始图象的分辨率对输出图象分辨率影响不大。图象分辨率影响不大。n用户对原始图象的信号不全都感兴趣，用户对原始图象的信号不全都感兴趣，可

4、用特征提取和图象识别的方法，丢掉大可用特征提取和图象识别的方法，丢掉大量无用的信息。提取有用的信息，使必须量无用的信息。提取有用的信息，使必须传输和存储的图象数据大大减少。传输和存储的图象数据大大减少。 n原始图象越有规则，各象素之间的相关性越原始图象越有规则，各象素之间的相关性越强，它可能压缩的数据就越多。强，它可能压缩的数据就越多。 值得指出的是：当前采用的编码方法得到值得指出的是：当前采用的编码方法得到的结果，离可能压缩的极限还相差很远，这的结果，离可能压缩的极限还相差很远，这说明图象数据压缩的潜力是很大的，直到目说明图象数据压缩的潜力是很大的，直到目前为止，它还是个正在继续研究的领域。

5、前为止，它还是个正在继续研究的领域。33K15K 图象数据压缩的图象数据压缩的目的目的是在满足一定图象质量是在满足一定图象质量条件下，用尽可能少的比特数来表示原始图条件下，用尽可能少的比特数来表示原始图象，以提高图象传输的效率和减少图象存储象，以提高图象传输的效率和减少图象存储的容量，在信息论中称为的容量，在信息论中称为信源编码信源编码。 信源编码可分为两大类，一类是信源编码可分为两大类，一类是无失真编无失真编码码，另一类是，另一类是有失真编码有失真编码或称或称限失真编码限失真编码。从从N个数选定一个数个数选定一个数s的概率为的概率为p(s)，且等概率，且等概率，p(s)=1/N。设信源符号表

6、为设信源符号表为 s=s1, s2, , sq ，其概率分布为其概率分布为P(s)=p(s1), p(s2), , p(sq) ，则信源的，则信源的为为)()(log1loglog)(222spIspNNsIqiiiqiiispIspspspH112)()()(log)()(ss作为灰度，共作为灰度，共q级级，出现概率均等时，出现概率均等时，p(si)=1/q， 当灰度只有两级时，即当灰度只有两级时，即si = = 0, 1，且，且0出现出现概率为概率为p1，1出现概率为出现概率为p2=1- p1 ，其熵，其熵qqqHqi212log1log1)(s12112111log)1 (1log)(p

7、pppHs当当p1=1/2， p2=1- p1 =1/2时，时， H(s)=1为最大值。如图所示。为最大值。如图所示。（1 1）熵是一个非负数，即总有）熵是一个非负数，即总有H(s)0。（2 2）当其中一个符号）当其中一个符号sj的出现概率的出现概率p(sj)=1时，时，其余符号其余符号si(ij)的出现概率的出现概率p(si) =0，H(s)=0。（3 3）当各个）当各个si出现的概率相同出现的概率相同时时，则最大平，则最大平均信息量为均信息量为log2 q。（4 4）熵值总有）熵值总有H(s) log2 q。无失真编码定理无失真编码定理 可以证明，在无干扰的条件下，存在一种无可以证明，在无

8、干扰的条件下，存在一种无失真的编码方法，使编码的平均长度失真的编码方法，使编码的平均长度 与与信源信源的熵的熵H(s)任意地接近，即任意地接近，即L=H(s)+，其中，其中为任意小的正数，但以为任意小的正数，但以H(s)为其下限，即为其下限，即LH(s)，这就是，这就是香农香农(Shannon)无干扰编无干扰编码定理码定理。L)(sHL)(sHL 熵与相关性、冗余度的关系熵与相关性、冗余度的关系 对于无失真图象的编码，原始图象数据的压对于无失真图象的编码，原始图象数据的压缩存在一个下限，即平均码组长度不能小于原缩存在一个下限，即平均码组长度不能小于原始图象的熵，而理论上的最佳编码的平均码长始图

9、象的熵，而理论上的最佳编码的平均码长无限接近原始图象的熵。无限接近原始图象的熵。 原始图象原始图象定义为：定义为：1)(1sHLr原始图象的熵原始图象平均码长将将定义为：定义为：rLsH11)( 冗余度接近于冗余度接近于0，或编码效率接近于，或编码效率接近于1的编的编码称为码称为。 数字图像通信系统的组成数字图像通信系统的组成：其中，其中，信源编码器：完成原数据的压缩。信源编码器：完成原数据的压缩。信道信道 编编 码：为了抗干扰，增加一些容错、校验码：为了抗干扰，增加一些容错、校验位、版权保护，实际上是增加冗余。位、版权保护，实际上是增加冗余。信信 道：如道：如Internet、广播、通讯、可

10、移动介质、广播、通讯、可移动介质符号符号解码器解码器反向反向映射器映射器映射器映射器量化器量化器符号符号编码器编码器等字长编码等字长编码 每个抽样值都以相同长度的二进制码表示。每个抽样值都以相同长度的二进制码表示。 编码简单，但编码效率低编码简单，但编码效率低 PCM变字长编码变字长编码n每个抽样值用不同长度的二进制码表示。每个抽样值用不同长度的二进制码表示。n每个符号的平均码长：每个符号的平均码长：设图像信源有设图像信源有K种符号（例如种符号（例如K种灰度等种灰度等级），级）， ,且它们出现的概率为且它们出现的概率为 ,那么，不考那么，不考虑信源符号的相关性，对每个符号编码时，虑信源符号的相

11、关性，对每个符号编码时，其平均码长为：其平均码长为：其中其中li为为ai的码字长度，的码字长度，L为平均码长为平均码长若编码时，对概率大的符号用短码，概率小若编码时，对概率大的符号用短码，概率小的符号用长码，则的符号用长码，则L L会比等长编码所需的码会比等长编码所需的码字短。字短。 较等长编码效率高。较等长编码效率高。i1(a )kiiLpl构成不等长编码的方法有许多，构成不等长编码的方法有许多，Huffman于于1952年提出一种最佳不等长编码，是图像编年提出一种最佳不等长编码，是图像编码中常用的无损压缩编码。码中常用的无损压缩编码。 1、定理、定理 如果码字长度严格按照符号出现概率大小如

12、果码字长度严格按照符号出现概率大小逆序排列，则平均码字长度最小。逆序排列，则平均码字长度最小。概率大概率大的用短码，概率小的用长码。的用短码，概率小的用长码。2、编码方法、编码方法 （1）对信源符号按其出现的概率进行递减排）对信源符号按其出现的概率进行递减排序。序。 （2）将两个最小的概率相加，其和作为新符）将两个最小的概率相加，其和作为新符号的概率，并按（号的概率，并按（1）重新排序。）重新排序。 （3）重复（）重复（1）（）（2），直到概率之和达到），直到概率之和达到1为止。为止。 （4）每次合并符号时，将被合并的符号赋予）每次合并符号时，将被合并的符号赋予1和和0或或0和和1。 （5）寻

13、找从概率）寻找从概率1处到每个信源符号的路径，处到每个信源符号的路径，记录下路径上的记录下路径上的0，1序列，该序列即为信源符序列，该序列即为信源符号的码字（编码）。号的码字（编码）。 举例：举例：信号源信号源 s=ss=s1 1, s, s2 2, s, s3 3, s, s4 4, s, s5 5, s, s6 6 ，其概率，其概率分布为分布为p p1 1=0.4 p=0.4 p2 2=0.3 p=0.3 p3 3=0.1 p=0.1 p4 4=0.1 =0.1 p p5 5=0.06 p=0.06 p6 6=0.04=0.04，求最佳，求最佳HuffmanHuffman码。码。i. i.

14、 将信源符号按出现概率从大到小排成一列将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成，然后把最末两个符号的概率相加，合成一个概率。一个概率。ii. ii. 把这个符号的概率与其余符号的概率按从把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。率加起来，合成一个概率。 ii. ii. 重复上述做法，直到最后剩下两个概率为重复上述做法，直到最后剩下两个概率为止。止。iii.iii.从最后一步剩下的两个概率开始逐步向前从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一进行

15、编码。每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码元个二进制码，如对概率大的赋予码元0，对概率小的赋予码元对概率小的赋予码元1。输入输入S1S2S3S4S5S6输入概率输入概率0.40.30.10.10.060.04第一步第一步0.40.30.10.10.1第二步第二步0.40.30.20.1第三步第三步0.40.30.3第四步第四步0.60.40101010101S1=1S2=00S3=011S4=0100S5=01010S6=01011压缩前，等长编码：每个符号压缩前，等长编码：每个符号3bit压缩后，压缩后， =1*0.4+2*0.3+3*0.1+4*0.1+5*0.06+5

16、*0.04=2.2bit压缩比：压缩比：3/2.21.36静态编码静态编码：在压缩之前就建立好一个概率统计：在压缩之前就建立好一个概率统计表和编码树。算法速度快，但压缩效果不是最表和编码树。算法速度快，但压缩效果不是最好；好；动态编码动态编码：对每一个图像，临时建立概率统计：对每一个图像，临时建立概率统计表和编码树。算法速度慢，但压缩效果最好。表和编码树。算法速度慢，但压缩效果最好。霍夫曼解码霍夫曼解码设接收端收到的码流是设接收端收到的码流是101001000，如何，如何判断应判断应“断断”在何处，即哪几个比特应对应在何处，即哪几个比特应对应一个码字？也就是说如何解码？下面介绍两一个码字？也就

17、是说如何解码？下面介绍两种方法。种方法。1）树形解码。树形解码。解码器先进高位，并根据该位是解码器先进高位，并根据该位是1还是还是0判断判断由根向下走向，若走到树叶，说明至此为止由根向下走向，若走到树叶，说明至此为止的码串部分对应一个码字，从而解出对应的的码串部分对应一个码字，从而解出对应的符号；符号；重新从树根开始解码，若未走到树叶，则继重新从树根开始解码，若未走到树叶，则继续进一位，至到走到树叶。续进一位，至到走到树叶。 2）并行解码。）并行解码。 用树形解码时需一位一位读入和判断，当码用树形解码时需一位一位读入和判断，当码表较长时，速度太慢。特别是对活动图像解表较长时，速度太慢。特别是对

18、活动图像解码时，难以用硬件实现。而并行解码，可一码时，难以用硬件实现。而并行解码，可一次解出一个码字，易于硬件实现，解码速度次解出一个码字，易于硬件实现，解码速度快。快。游程编码游程编码是一种简单的无损压缩的方法。是一种简单的无损压缩的方法。概念：概念：行程行程：具有相同灰度值的像素序列。：具有相同灰度值的像素序列。编码思想：编码思想：去除像素冗余。去除像素冗余。用行程的灰度和行程的长度代替行程本身。用行程的灰度和行程的长度代替行程本身。例：设重复次数为例：设重复次数为 iC, 重复像素值为重复像素值为 iP编码为：编码为：iCiP iCiP iCiP 编码前：编码前：aaaaaaabbbbb

19、bcccccccc 编码后：编码后：7a6b8c基本方法：基本方法： 使用一新字符序列代取原始数据中相同的字使用一新字符序列代取原始数据中相同的字 符序列，来实现数据压缩。（压缩原始符序列，来实现数据压缩。（压缩原始数据数据中相同的字符序列）中相同的字符序列）把沿着扫描行的象素序列把沿着扫描行的象素序列x1, x2, xN映射映射为行程序列为行程序列(g1, l1), (g2, l2), (gk, lk) gi灰度级灰度级 ligi的行程长度的行程长度因为象素序列可以根据行程序列来重建，故行因为象素序列可以根据行程序列来重建，故行程映射变换是可逆的。因它包含灰度鉴别和行程映射变换是可逆的。因它

20、包含灰度鉴别和行程计数，故它是非线性的。程计数，故它是非线性的。分析：分析：对于有大面积色块的图像，压缩效果很对于有大面积色块的图像，压缩效果很好好对于纷杂的图像，压缩效果不好，最坏对于纷杂的图像，压缩效果不好，最坏情况下，会加倍图像情况下，会加倍图像例如一个数据字符串为例如一个数据字符串为RTTTTTTTTABBC KGHJK用一新的字符串：用一新的字符串：#8T，代替，代替8个个T。#为特殊标识符，表示行程编码。为特殊标识符，表示行程编码。8代表其后字符重复的次数代表其后字符重复的次数；T为重复的字符。为重复的字符。则行程编码后的字符串为：则行程编码后的字符串为：R8TABBC K GHJ

21、K压缩前总字符数压缩前总字符数 18压缩后总字符数压缩后总字符数 13其压缩比：其压缩比：= 18/13 = 1.38几点说明几点说明： 1、如果原始数据字符串包含了、如果原始数据字符串包含了“#”符符号，则用两个号，则用两个“#”符号替换原始数据字符串符号替换原始数据字符串中的中的“#”符号。符号。2、原始数据字符串中重复字符数少于、原始数据字符串中重复字符数少于4个，个，则行程编码无效。则行程编码无效。3、压缩对象可以是重复的单个字符序列，也、压缩对象可以是重复的单个字符序列，也可以是重复的多个字符序列。对于后者，必可以是重复的多个字符序列。对于后者，必须标识一个字符序列的长度或者结束标志

22、。须标识一个字符序列的长度或者结束标志。算术编码：越来越流行（在很多标准中被算术编码：越来越流行（在很多标准中被采用）采用）适合的场合：适合的场合：小字母表：如二进制信源小字母表：如二进制信源概率分布不均衡概率分布不均衡建模与编码分开建模与编码分开算术编码算术编码：对整个序列信源符号串产生一个唯一的对整个序列信源符号串产生一个唯一的标识（标识（ tag ）直接对序列进行编码（不是码字的串直接对序列进行编码（不是码字的串联）：非分组码联）：非分组码不用对该长度所有可能的序列编码不用对该长度所有可能的序列编码标识是标识是0,1)之间的一个数（二进制小之间的一个数（二进制小数，可作为序列的二进制编码

23、）数，可作为序列的二进制编码） 算术编码中，信源符号与码字之间不存在一一算术编码中，信源符号与码字之间不存在一一对应的关系。一个码字不是赋给某个信源符对应的关系。一个码字不是赋给某个信源符号，而是赋给整个消息序列。这个码字本身号，而是赋给整个消息序列。这个码字本身定义一个介于定义一个介于0和和1之间的实数区间，该区间之间的实数区间，该区间中的任何一个实数就代表要编码的消息序列中的任何一个实数就代表要编码的消息序列。当消息中的符号数目增加时，用于描述消。当消息中的符号数目增加时，用于描述消息的间隔变得更小，而表示间隔所需要的信息的间隔变得更小，而表示间隔所需要的信息单元（如编码位数）变得更多了。

24、息单元（如编码位数）变得更多了。定义一一映射：定义一一映射：ak FX(k-1), FX(k), k = 1.m, FX(0) = 0FX(k-1), FX(k)区间内的任何数字表示区间内的任何数字表示 ak对对2字母序列字母序列ak aj编码编码对对ak ，选择，选择FX(k-1), FX(k)然后将该区间按比例分割并选取第然后将该区间按比例分割并选取第j个区间：个区间： 11,111XXXXXXXXFjFjFkFkFkFkFkFk算术编码方法：算术编码方法：1.产生标识将0, 1)分为m个区间： 00,.1,1XXXFmiiFiF考虑对考虑对a1a2a3编码编码：A = a1, a2, a

25、3, P = 0.7, 0.1, 0.2)映射：映射：a1 1, a2 2, a3 3cdf: FX(1) = 0.7, FX(2) = 0.8, FX(3) = 1.0A = a1, a2, , am对公平掷骰子的例子：1, 2, 3, 4, 5, 66.161kforkXP iXPiFiXPkXPaTXikiX2112111 25. 022112XPXPTX 75. 0521541XPkXPTkX映射成数字映射成数字字符串的词典顺序：字符串的词典顺序：其中其中 表示表示“在字母顺序中，在字母顺序中，y在在x的前面的前面”n 为序列的长度为序列的长度 ( ):12inXiiTPPy y xx

26、yxxy 考虑两轮连续的骰子：考虑两轮连续的骰子：输出输出 = 11, 12, , 16, 21, 22, , 26, , 61, 62, , 66 469. 07251321121113xPxPxPTXv注意：注意：为了产生为了产生13的标识，我们不必对产生其他标识的标识，我们不必对产生其他标识=但是，为了产生长度为但是，为了产生长度为n的字符串的标识，我的字符串的标识，我们必须知道比其短的字符串的概率们必须知道比其短的字符串的概率这与产生所有的码字一样繁重！这与产生所有的码字一样繁重！应该想办法来避免此事应该想办法来避免此事区间构造区间构造包含某个标识的区间与所有其他标识的区间不相交包含某

27、个标识的区间与所有其他标识的区间不相交基本思想基本思想递归：将序列的下递归：将序列的下/上界视为更短序列的界的上界视为更短序列的界的函数函数上述骰子的例子：上述骰子的例子：考虑序列：考虑序列：3 2 2 令令u(n), l(n) 为长度为为长度为n序列的上界和下界，则序列的上界和下界，则 u(1) = FX(3), l(1) = FX(2)u(2) = FX(2)(32), l(2) = FX(2)(31) (2)32(11).(16)(21).(26)(31)(32)XFPPPPPPxxxxxx6661212112111,iiiPkiP xk xiP xkP xiP xkwherex xxx

28、(2)1132(1)(2)(31)(32)(2)(31)(32)XXFP xP xPPFPPxxxx1221(31)(32)(3)(1)(2)(3)(2)XPPP xP xP xP xFxx)2()3()3(1XXFFxP)2()2()3()2(32)2(XXXXXFFFFF)2()1()1()1()2(XFlulu ) 1 ()2()3()2(31)2(XXXXXFFFFF) 1 ()1()1()1()2(XFlull()()(3)( )(3)( )322 ,32133XXuFlF=()()(3)(2)(2)(2)322(31)(32)(31)(2)XXXXXFFFFF=+-()()(3)(

29、2)(2)(2)321(31)(32)(31)(1)XXXXXFFFFF=+-)2()2()2()2()3(XFlulu) 1 ()2()2()2()3(XFlull)2()2()3()2(32)2(XXXXXFFFFF)2()1()1()1()2(XFlulu产生标识：产生标识：通常，对任意序列通常，对任意序列x = x1x2xn ( )( )2nnXulTx( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl只需知道信源的只需知道信源的cdfcdf，即信源的概率模型，即信源的概率模型算术编码：编码和解码过程都只涉及算术运算（加、算术编码

30、：编码和解码过程都只涉及算术运算（加、减、乘、除）减、乘、除）考虑随机变量考虑随机变量X(ai) = i 对序列对序列1 3 2 1编码：编码：3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX1, 0)0()0(ul8 . 0) 1 (0)0()0()0()0()1()0()0()0()1(XXFluluFlull18 . 0)3(656. 0)2()1()1()1()2()1()1()1()2(XXFluluFlull1377408. 0)2(7712. 0) 1 ()2()2()2()3()2()2()2()3(XXFluluFlull132()()(4)(1)(3)(3)(4)(3)(3)(3)( )0.7712(1)0.7735040XXllulFululF=+-=+-=1321(4)(4)13210.7723522XulT( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl算术编码的唯一性和有效性算术编码的唯一性和有效性上述产生的标识可以唯一表示一个序列，上述产生的标识可以唯一表示一个序列，这意味着该标识的二进制表示为序列的唯这意味着该标识的二进制