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

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

周三例会报告 26/11 /2014

数字图像处理—图像压缩

上海大学

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

OUTLINE:图像压缩1.香农信息论 2.数据压缩原理 3.数据冗余 4.无损压缩 5.有损压缩

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_香农信息论1、香农信息论 例生活实例 第一句话：我有一个师兄叫“**”。 第二句话：我有一个舍友叫“**”。 直观的感受一下这两句话所携带的未知信息量。 说明：一个消息若能传达给我们许多原来 未知的内容，我们就认为这个信息很有意义，

信息量大；反之，一个消息传达给我们的是已知确定的东西，则这个传达就失去了意义。

信息量 在信息论中：信息使用不确定的度量来确定的，一个消息的可能性越小，其信息含量越大；消息

的可能性越大，其信息含量越小。设某消息 xi 发生的概率为 p xi ,则该消息携载的信息量为：I xi log a p xi 1)当 a 2 时，则单位为比特(bit);

2)当 a e 时，则单位为奈特(nat);

3)当 a 10时，则单位为哈特(hat)。一般以2为底取对数，由此定义的信息量等于描述该信息所用的最少比特数。

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_香农信息论信息熵 若信源有 n个字符，对应字符 xi 的概率为 p xi ,则该信源的平均信息量就称为信息熵，既：

H p xi log 2 p xi i 0

L 1

L 1

ni n log 2 i n i 0 n

具体到数字图像中，称 H 为图像信息熵。它给出了描述一幅图像携载信息量的最少比特数。

Shannon无失真编码定理 基于图像信息熵，存在一种无失真的编码方法，使编码的平均码长与信息熵无限的接 近。既：

Lavg H , 0但以 H 为下限，既 Lavg H 。这就是Shannon的无失真编码定理。 R 1 100% 1 H Lavg H D Lavg Lavg 无失真编码性能的几个指标：

1)编码效率

H Lavg

RD 1

n n n2 1 1 2 1 CR n1 n1

2)冗余度

RD 1 100% 或CR m Lavg

RD 1

1 CR

3)压缩比

或

CR

n1 n2

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_图像压缩原理2、图像压缩原理1)数据压缩的对象是数据，大的数据量并不代表含有大的信息量。 2)图像压缩就是除去图像中多余的数据而对信息没有本质的影响。 3)图像压缩是以图像编码的形式实现的，用较少的比特数表示出现概率较大的灰度级，用较多的 比特数表示出现概率较小的灰度级，从而使平均码长更接近于信息熵。

图像编码 码本：编码所用符号的集合称为码本。 如 A a0 , a1 , a2 , a3 , a4 , a5 , a6 码字：对每个码本的每个符号所赋的符号序列称为码字。如 a0 01011 码字长度：每个码字里的符号个数称为码字长度。数字图像：码长 = 二进制数长度。

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_数据冗余3、数据冗余1)信息熵冗余：也称编码冗余，如果图像中平均比特数大于该图像的信息熵，则图像中存 在冗余，这种冗余称为信息熵冗余。 2)空间冗余：也称为像素间冗余或几何冗余，是图像内部相邻像素之间存在较强的相关性 所造成的冗余。 3)时间冗余：视频图像序列中的不同帧之间的相关性所造成的冗余。 4)视觉冗余：是指人眼不能感知或不敏感的那部分图像信息。 5)结构冗余：是指图像中存在很强的纹理结构或自相似性。 6)知识冗余：是指有些图像还包含与某些先验知识有关的信息。

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_无损压缩4、无损编码常用的无损编码方法有霍夫曼编码、香农—费诺编码、算术编码、游程编码和无损预测编码等。 1)Huffman编码 霍夫曼编码法是消除编码冗余最常用的方法。 假设有一个信源为 A a0 , a1 , a2 , a3 , a4 , a5 , a6 ,其概率分布为： 符号 概率a0 a1 a2 a3 a4 a5 a6

0.16

0.4

0.12

0.04

0.02

0.2

0.06

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_无损压缩

1

0.4 1 0.2 000 0.16 001 0.12 010 0.06 0110 0.06 0111

0.4 1 0.2 000 0.16 001 0.12 010 0.12 011

0.4 1

0.4 1

0.6 0

000 001

0.24 010.2 000 0.16 001

0.36 000.24 01

0.4

1

010

011001110 01111

霍弗曼编码示意图

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_无损压缩符号a0 a1 a2 a3 a4 a5 a6

概率霍弗曼编码 (码字) 二进制编码 (码字)

0.16001 000

0.41 001

0.12010 010

0.0401110 011

0.0201111 100

0.2000 101

0.060110 1103 1.26 2.380

Huffman编码效率 信源信息熵为：H P ak log 2 p ak 2.325k 0 7 1

压缩比： CR m Lavg

二进制编码效率为： H 2.325 100% 100% 77.5% m 3

霍弗曼编码平均码长 Lavg 为：Lavg Bk Pkk 0 N 1

3 0.16 1 0.4 3 0.12 5 0.04 5 0.02 3 0.2 4 0.06 2.380

霍夫曼编码效率为 ： H 2.325 100% 100% 97.7% Lavg 2.3809

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_无损压缩2)香农-费诺编码 由于霍夫曼编码法中的信源缩减过程复杂，当信源符号个数较多时十分不便。为此Shannon和 Fano提出了一种类似的变长编码方法，相对于霍夫曼编码法更方便、快捷。 假设有一个信源为 A a0 , a1 , a2 , a3 , a4 , a5 , a6 ,其概率分布为： 符号 概率 具体步骤如下： a)将信源符号按出现的概率 p ai 由大到小排列； b)将信源A分成两个子集 a0 A1 p a0 a1 ak ak 1 和 A2 p ak p ak 1 ak 2 an p an a0 a1 a2 a3 a4 a5 a6

0.16

0.4

0.12

0.04

0.02

0.2

0.06

p a1 n

p ak 2

并且保证

p a p a i 0 i j k 1 j

k

成立或差不多成立；

c)给两个子集赋

不同的码元值； d)重复(2)、(3),既对每个子集再一分为二，并赋予不同的码元值，直到每个子集仅含一 个符号为止。

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_无损压缩计算香农-费诺编码平均码长为：Lavg Bk Pkk 0 N 1

1 0..4 3 0.2 3 0.16 3 0.12 4 0.06 5 0.04 5 0.02 2.380

0

0 0 01

100 101 11011110

0

01 1 1

11110

01

11111

香农-费诺编码示意图

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_无损压缩3)算术编码例如：I xi log2 p xi 1.732

算术编码法和霍夫曼编码法都是一种变长编码。但霍夫曼编码必须分配整数位码字，而算数编 码可以分配带有小数的比特数目信符，并且算术编码给整个信源符号序列分配一个单一的算术码字。 假设有一信源为 A b,c,a,d,c ,信源中各符号出现的概率分别为：p(a) 0.2 p(b) 0.3 p(c) 0.4 p(d) 0.1

算术编码具体步骤如下： a)“当前区间”初始化[0,1);

b)对于输入信源中的每个符号，依次执行如下两个步骤：①将“当前区间”分成子区间，该子区间的长度正比于符号的概率；②选择下一个信符对应的子区间，并使它成为新的“当前区间”; c)将整个信源的所有符号处理完后，在最后一个“当前区间”中任找一个数作为算数编码的输 入码。

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_无损压缩A b,c,a,d,c

算术编码示意图

输出区间[0.3728,0.37376)

[0.01011111011,0.01011111101)

取位数最少的一个数: 0.010111111 不考虑“0.”,则编码输出为:010111111

算数编码法： L

avg

9 1.8比特 / 字符 5

霍夫曼编码法：Lavg 1.9比特 / 字符

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_无损压缩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 1

游程编码：(5,6)(7,5)(3,3)(2,4)(1,7)游程编码适合于二值图像编码，只有黑白出现。规定“0”游程开始。 例如：对于一个二元序列：0000001111100011001,对应的又称序列为：653221。然后根据不同 长度段发生的概率来分配不同长度的码字。

5)无损预测编码无损预测编码跟有损预测编码一起讲解。

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_有损压缩5、有损编码常用的有损编码方法有预测编码、变换编码

1)预测编码 预测编码是通过消除紧邻像素在空间和时间上的冗余来实现的，它仅对每个像素中的新信息进 行提取并代替原图像进行编码。新信息=实际值-预测值,既预测误差。

差分脉冲编码调制(Differential Pulse Code Modulation ,DPCM)。

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_有损压缩

DPCM系统原理框图

误

差信号：

en fn f n

量化器误差： qn en en 接收端输出： f f e n n n

可以推出：

e f f e e e q f n f n f n f n n n n n n n n

a)当 qn 0 时，无损预测编码 b)当 qn 0 时，有损预测编码。 问题：如何使误差尽可能小？ 最优预测？

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_有损压缩最佳预测器 预测器选择要满足两个要求： a)使均方预测误差最小，既： n E e2 n E f n f

2

和 f n = i f n i i 1 m

b)约束条件： n e n f n f n f n e n f

常用的几种线性预测方案①前值预测： f xm , yn af xm 1 , yn ②一维预测： f xm , yn ai f xi , yn i 0 m 1

③二维预测： f xm , yn ai f xi , yn b j f x j , yn 1 i 0 j 0

m 1

M 1

④三位预测：也叫帧间预测，主要用于视频压缩。

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_有损压缩2)变换编码 变换编码是采用一种可逆线性变换(正交变换),把图像从空间域映射到变换域的系数集合， 然后对这些变换系数进行量化和编码。 区别：变换编码是在变换域内进行编码。

变换编码方法编码、解码示意图

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

图像压缩_有损压缩第一步：子图像分解 将一副大小为 M N 的输入图像分解成大小为 n n 的子图像。 8×8 16×16 原因： ①距离远的像素之间的相关性比较差； ②小块图像的变换比较容易。

第二步：正交变换将一副图像从空间域映射到变换域的系数集合。 正交变换的特点：①不会丢失信息； ②去除部分相关性； ③能量(信息)集中 第三步：量化大的系数→能量多→低频 小的系数→能量小→高频

系数选择(滤波):区域法和阈值法量化：小数系数变成整数 第四步：编码 变长编码法

数字图像处理,图像压缩,图像编码,霍夫曼编码,香浓-费诺编码,游程编码,预测编码

Acknoledgement

Thanks for Your Attention!

谢谢大家！

本文来源：https://www.bwwdw.com/article/pdp1.html