数字图像处理——图像压缩.

1、 周三例会报告周三例会报告 26/11 /2014 上海大学上海大学 数字图像处理数字图像处理图像压缩图像压缩 OUTLINE:OUTLINE: 图像压缩图像压缩 1.香农信息论香农信息论 2.数据压缩原理数据压缩原理 3.数据冗余数据冗余 4.无损压缩无损压缩 5.有损压缩有损压缩 3 图像压缩图像压缩_ _香农信息论香农信息论 1 1、香农信息论、香农信息论 说明：一个消息若能传达给我们许多原来 未知的内容，我们就认为这个信息很有意义， 信息量大；反之，一个消息传达给我们的是已 知确定的东西，则这个传达就失去了意义。 生活实例生活实例 第一句话：我有一个师兄叫“*”。 第二句话：我有一个舍

2、友叫“*”。 直观的感受一下这两句话所携带的未知信息量。 例例 信息量信息量 在信息论中：信息使用不确定的度量来确定的，一个消息的可能性越小，其信息含量越大；消息 的可能性越大，其信息含量越小。设某消息 发生的概率为 ，则该消息携载的信息量为： 1）当 时，则单位为比特（bit）； 2）当 时，则单位为奈特（nat）； 3）当 时，则单位为哈特（hat）。 一般以2为底取对数，由此定义的信息量等于描述该信息所用的最少比特数。 log i ia I xp x i x i p x 2a ae 10a 信息熵信息熵 若信源有 个字符，对应字符 的概率为 ，则该信源的平均信息量就称为信息熵，既： 具体

3、到数字图像中，称 为图像信息熵。它给出了描述一幅图像携载信息量的最少比特数。 图像压缩图像压缩_ _香农信息论香农信息论 11 22 00 loglog i LL ii i ii nn Hp xp x nn n i x i p x H Shannon Shannon无失真编码定理无失真编码定理 基于图像信息熵，存在一种无失真的编码方法，使编码的平均码长与信息熵无限的接 近。既： 但以 为下限，既 。这就是Shannon的无失真编码定理。 无失真编码性能的几个指标： 1 1）编码效率）编码效率 2 2）冗余度）冗余度 或 3 3）压缩比）压缩比 或 ,0 avg LH H avg LH a v

4、g H L 1100% D R R avg m C L 1 2 R n C n 1 1 D R R C 212 11 1100%1 1 11 avg D avgavg D R LH H R LL nnn R Cnn 5 图像压缩图像压缩_ _图像压缩原理图像压缩原理 2 2、图像压缩原理图像压缩原理 1）数据压缩的对象是数据，大的数据量并不代表含有大的信息量。 2）图像压缩就是除去图像中多余的数据而对信息没有本质的影响。 3）图像压缩是以图像编码的形式实现的，用较少的比特数表示出现概率较大的灰度级，用较多的 比特数表示出现概率较小的灰度级，从而使平均码长更接近于信息熵。 图像编码图像编码 码本

5、：码本：编码所用符号的集合称为码本。 如 码字：码字：对每个码本的每个符号所赋的符号序列称为码字。如 码字长度：码字长度：每个码字里的符号个数称为码字长度。数字图像：码长 = 二进制数长度。 0123456 A,aa aa aa a 0 01011a 6 图像压缩图像压缩_ _数据冗余数据冗余 3 3、数据冗余、数据冗余 1)1)信息熵冗余：信息熵冗余：也称编码冗余，如果图像中平均比特数大于该图像的信息熵，则图像中存 在冗余，这种冗余称为信息熵冗余。 2)2)空间冗余：空间冗余：也称为像素间冗余或几何冗余，是图像内部相邻像素之间存在较强的相关性 所造成的冗余。 3)3)时间冗余：时间冗余：视频

6、图像序列中的不同帧之间的相关性所造成的冗余。 4)4)视觉冗余：视觉冗余：是指人眼不能感知或不敏感的那部分图像信息。 5)5)结构冗余：结构冗余：是指图像中存在很强的纹理结构或自相似性。 6) 6)知识冗余：知识冗余：是指有些图像还包含与某些先验知识有关的信息。 图像压缩图像压缩_ _无损压缩无损压缩 4 4、无损编码、无损编码 常用的无损编码方法有霍夫曼编码霍夫曼编码、香农香农费诺编码费诺编码、算术编码算术编码、游程编码游程编码和无损预测编码无损预测编码等。 1 1）HuffmanHuffman编码编码 霍夫曼编码法是消除编码冗余最常用的方法。 假设有一个信源为 ，其概率分布为： 01234

7、56 A,a a a a a a a 符号 概率0.160.40.120.040.020.20.06 0 a 1 a 2 a 3 a 4 a 5 a 6 a 图像压缩图像压缩_ _无损压缩无损压缩 0.4 0.2 0.16 0.12 0.06 0.06 0.4 0.2 0.16 0.12 0.12 0.4 0.24 0.2 0.16 0.4 0.36 0.24 0.6 0.4 0 1 0 0 1 0 1 1 01 00 001 0 001 010 0110 01110 000000 11 000 001001 010 010 0110110 0111 1 01111 霍弗曼编码示意图 9 图像

8、压缩图像压缩_ _无损压缩无损压缩 符号 概率0.160.40.120.040.020.20.06 0 a 1 a 2 a 3 a 4 a 5 a 6 a 霍弗曼编码 （码字） 001101001110011110000110 二进制编码 （码字） 000001010011100101110 二进制编码效率为： 2.325 100%100%77.5% 3 H m Huffman Huffman编码效率编码效率 信源信息熵为： 霍弗曼编码平均码长 为： 霍夫曼编码效率为 ： avg L 7 1 2 0 log2.325 kk k HP ap a 2.325 100%100%97.7% 2.380

9、 avg H L 1 0 3 0.161 0.43 0.125 0.045 0.023 0.24 0.06 2.380 N avgkk k LB P 压缩比： 3 1.26 2.380 R avg m C L 图像压缩图像压缩_ _无损压缩无损压缩 2）香农）香农- -费诺编码费诺编码 由于霍夫曼编码法中的信源缩减过程复杂，当信源符号个数较多时十分不便。为此Shannon和 Fano提出了一种类似的变长编码方法，相对于霍夫曼编码法更方便、快捷。 假设有一个信源为 ，其概率分布为： 0123456 A,a a a a a a a 符号 概率0.160.40.120.040.020.20.06 0

10、 a 1 a 2 a 3 a 4 a 5 a 6 a 具体步骤如下： a）将信源符号按出现的概率 由大到小排列； b）将信源A分成两个子集 并且保证 成立或差不多成立； c）给两个子集赋不同的码元值； d）重复（2）、（3），既对每个子集再一分为二，并赋予不同的码元值，直到每个子集仅含一 个符号为止。 01k 12 12 0112 AA kkn kkkn aaaaaa p ap ap ap ap ap a 和 01 kn ij ij k p ap a i p a 图像压缩图像压缩_ _无损压缩无损压缩 0 1 0 1 0 1 1 1 1 0 0 0 0 100 101 110 1110 111

11、10 11111 香农-费诺编码示意图 计算香农-费诺编码平均码长为： 1 0 1 0.430.230.1630.1240.0650.0450.02 2.380 N avgkk k LB P 图像压缩图像压缩_ _无损压缩无损压缩 3）算术编码）算术编码 算术编码法和霍夫曼编码法都是一种变长编码。但霍夫曼编码必须分配整数位码字，而算数编 码可以分配带有小数的比特数目信符，并且算术编码给整个信源符号序列分配一个单一的算术码字。 假设有一信源为 ，信源中各符号出现的概率分别为： Ab,c,a,d,c (a)0.2(b)0.3(c)0.4(d)0.1pppp 算术编码具体步骤如下： a）“当前区间”

12、初始化0,1）； b）对于输入信源中的每个符号，依次执行如下两个步骤：将“当前区间”分成子区间，该子 区间的长度正比于符号的概率；选择下一个信符对应的子区间，并使它成为新的“当前区间”； c）将整个信源的所有符号处理完后，在最后一个“当前区间”中任找一个数作为算数编码的输 入码。 2 log1.732 ii I xp x 例如： 图像压缩图像压缩_ _无损压缩无损压缩 算术编码示意图 输出区间0.3728,0.37376） 0.01011111011,0.01011111101） 取位数最少的一个数: 0.010111111 不考虑“0.”，则编码输出为:010111111 算数编码法： 霍夫

13、曼编码法： 9 1.8/ 5 avg L比特字符 1.9/ avg L比特 字符 Ab,c,a,d,c 图像压缩图像压缩_ _无损压缩无损压缩 4）游程编码）游程编码 游程：游程：是指字符序列中各个字符连续重复出现而形成字符串的长度。 游程编码（行程编码）：游程编码（行程编码）：就是将字符串序列映射成字符串的长度和串的位子的标志序列。 例如：一个字符串5 5 5 5 5 5 7 7 7 7 7 3 3 3 2 2 2 2 1 1 1 1 1 1 15 5 5 5 5 5 7 7 7 7 7 3 3 3 2 2 2 2 1 1 1 1 1 1 1 游程编码：（5,6）（7,5）（3,3）（2,4

14、）（1,7） 游程编码适合于二值图像编码，只有黑白出现。规定“0”游程开始。 例如：对于一个二元序列：00000011111000110010000001111100011001，对应的又称序列为：653221。然后根据不同 长度段发生的概率来分配不同长度的码字。 5）无损预测编码）无损预测编码 无损预测编码跟有损预测编码一起讲解。 图像压缩图像压缩_ _有损压缩有损压缩 1 1）预测编码）预测编码 预测编码是通过消除紧邻像素在空间和时间上的冗余来实现的，它仅对每个像素中的新信息进 行提取并代替原图像进行编码。新信息=实际值-预测值,既预测误差。 差分脉冲编码调制（Differential P

15、ulse Code Modulation，DPCM）。 5 5、有损编码、有损编码 常用的有损编码方法有预测编码预测编码、变换编码变换编码 图像压缩图像压缩_ _有损压缩有损压缩 DPCM系统原理框图 误差信号： 量化器误差： 接收端输出： 可以推出： a）当 时，无损预测编码 b）当 时，有损预测编码。 问题：如何使误差尽可能小？ 最优预测？ nnn eff nnn qe e nnn ffe nnnnnnnnnnn ffffeffeeeq 0 n q 0 n q 图像压缩图像压缩_ _有损压缩有损压缩 最佳预测器最佳预测器 预测器选择要满足两个要求： a)使均方预测误差最小，既： b)约束条

16、件： 2 2 E enEf nf n 1 = m i i fne nf ne nf nf nfnf ni 和 常用的几种线性预测方案 前值预测： 一维预测： 二维预测： 三位预测：也叫帧间预测，主要用于视频压缩。 1 , mnmn f xyaf xy 1 0 , m mniin i f xya f x y 11 1 00 , mM mniinjjn ij f xya f x yb f xy 图像压缩图像压缩_ _有损压缩有损压缩 2 2）变换编码）变换编码 变换编码是采用一种可逆线性变换（正交变换），把图像从空间域映射到变换域的系数集合， 然后对这些变换系数进行量化和编码。 区别：变换编码是在变换域内进行编码。 变换编码方法编码、解码示意图 图像压缩图像压缩_ _有损压缩有损压缩 第一步：子图像分解第一步：子图像分解 将一副大小为 的输入图像分解成大小为