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

第三章图像压缩编码

3.1图像压缩编码的分类

3.2数据压缩与信息论基础

3.3霍夫曼编码

3.4游程长度编码

3.5算术编码

图像压缩编码数字图象通常要求很大的比特数，这给图象的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。如一幅512x512的黑白图象的比特数为

512x512x8=2,097,152bit=256k。再如一部90分钟的彩色电影，每秒放映24帧。把它数字化，每帧512x512象素，每象素的R、G、B三分量分别占8bit，总比特数为图像压缩编码

90x60x24x3x512x512x8bit=97,200M。如一张CD光盘可存600兆字节数据，这部电影光图象（还有声音）就需要160张CD光盘用来存储。

对图象数据进行压缩显得非常必要。本章讨论的问题：在满足一定条件下，能否减小图象bit数，以及用什么样的编码方法使之减少。图像压缩编码的分类从信息论角度出发：（1）冗余度压缩方法

只降低或消除信源的冗余度，信息量没有减少。

又称：无损压缩，无失真编码，信息保持编码，熵编码。（2）信息量压缩

除降低或消除信源的冗余度外，进一步减少信源的信息量，有损压缩，限失真编码，信息非保持编码，熵压缩编码。较冗余度压缩具有更大的压缩比，具有更大的现实意义。图像压缩编码的分类图像压缩编码限失真编码无失真编码行程编码LZW编码哈夫曼编码算术编码无损预测编码位平面编码有损预测编码分形编码模型编码子带编码神经网络编码变换编码K.L变换Haar变换Walsh.Hadamard变换离散余弦变换离散傅立叶变换斜变换小波变换按压缩方法分类：数据压缩与信息论基础1.图象压缩是可能的：一般原始图象中存在很大的冗余度。用户通常允许图象失真。当信道的分辨率不及原始图象的分辨率时，降低输入的原始图象的分辨率对输出图象分辨率影响不大。用户对原始图象的信号不全都感兴趣，可用特征提取和图象识别的方法，丢掉大量无用的信息。提取有用的信息，使必须传输和存储的图象数据大大减少。数据压缩与信息论基础原始图象越有规则，各象素之间的相关性越强，它可能压缩的数据就越多。值得指出的是：当前采用的编码方法得到的结果，离可能压缩的极限还相差很远，这说明图象数据压缩的潜力是很大的，直到目前为止，它还是个正在继续研究的领域。数据压缩与信息论基础三种数据冗余：编码冗余；像素冗余；视觉心理冗余。1)编码冗余：如果一个图像的灰度级编码，使用了多于实际需要的编码符号，就称该图像包含了编码冗余。例：如果用8位表示该图像的像素，我们就说该图像存在着编码冗，因为该图像的像素只有两个灰度，用一位即可表示。数据压缩与信息论基础2)像素冗余：由于任何给定的像素值，原理上都可以通过它的邻居预测到，单个像素携带的信息相对是小的。对于一个图像，很多单个像素对视觉的贡献是冗余的。这是建立在对邻居值预测的基础上。例：原图像数据：234223231238235

压缩后数据：23411-8-73数据压缩与信息论基础3）视觉心理冗余：一些信息在一般视觉处理中比其它信息的相对重要程度要小，这种信息就被称为视觉心理冗余。33K15K数据压缩与信息论基础

图象数据压缩的目的是在满足一定图象质量条件下，用尽可能少的比特数来表示原始图象，以提高图象传输的效率和减少图象存储的容量，在信息论中称为信源编码。信源编码可分为两大类，一类是无失真编码，另一类是有失真编码或称限失真编码。数据压缩与信息论基础定义信息量：从N个数选定一个数s的概率为p(s)，且等概率，p(s)=1/N。熵：设信源符号表为s={s1,s2,…

,

sq}，其概率分布为P(s)={p(s1),p(s2),…,p(sq)}，则信源的熵为数据压缩与信息论基础s作为灰度，共q级，出现概率均等时，p(si)=1/q，

当灰度只有两级时，即si=0,1，且0出现概率为p1，1出现概率为p2=1-p1

，其熵数据压缩与信息论基础当p1=1/2，p2=1-p1=1/2时，H(s)=1为最大值。如图所示。数据压缩与信息论基础熵的性质：（1）熵是一个非负数，即总有H(s)≥0。（2）当其中一个符号sj的出现概率p(sj)=1时，其余符号si(i≠j)的出现概率p(si)

=0，H(s)=0。（3）当各个si出现的概率相同时，则最大平均信息量为log2

q。（4）熵值总有H(s)≤log2

q。数据压缩与信息论基础无失真编码定理可以证明，在无干扰的条件下，存在一种无失真的编码方法，使编码的平均长度与信源的熵H(s)任意地接近，即L=H(s)+ε，其中ε为任意小的正数，但以H(s)为其下限，即L≥H(s)，这就是香农(Shannon)无干扰编码定理。

数据压缩与信息论基础熵与相关性、冗余度的关系对于无失真图象的编码，原始图象数据的压缩存在一个下限，即平均码组长度不能小于原始图象的熵，而理论上的最佳编码的平均码长无限接近原始图象的熵。

原始图象冗余度定义为：数据压缩与信息论基础将编码效率定义为：

冗余度接近于0，或编码效率接近于1的编码称为高效码。数据压缩与信息论基础设：n1和n2是在两个表达相同信息的数据集中，所携 带的单位信息量。压缩率（压缩比）：——描述压缩算法性能

CR=n1/n2

其中，n1是压缩前的数据量，n2是压缩后的数据量.相对数据冗余：

RD=1–1/CR

例：CR=20;RD=19/20数据压缩与信息论基础

数字图像通信系统的组成：其中，信源编码器：完成原数据的压缩。信道编码：为了抗干扰，增加一些容错、校验位、版权保护，实际上是增加冗余。信道：如Internet、广播、通讯、可移动介质数据压缩与信息论基础

信源数据编码与解码的模型信源数据编码的模型信源数据解码的模型符号解码器反向映射器映射器量化器符号编码器数据压缩与信息论基础信源数据编码与解码的模型中，映射器：减少像素冗余，如使用RLE编 码。或进行图像变换。量化器：减少视觉心理冗余，仅用于有损压缩。符号编码器：减少编码冗余，如使用哈夫曼编码霍夫曼编码等字长编码

每个抽样值都以相同长度的二进制码表示。

编码简单，但编码效率低

→PCM变字长编码每个抽样值用不同长度的二进制码表示。每个符号的平均码长：

设图像信源有K种符号（例如K种灰度等

级），,且它们出现的概率为,那么，不考

虑信源符号的相关性，对每个符号编码时，

其平均码长为：

霍夫曼编码

其中li为ai的码字长度，L为平均码长若编码时，对概率大的符号用短码，概率小的符号用长码，则L会比等长编码所需的码字短。→较等长编码效率高。霍夫曼编码构成不等长编码的方法有许多，Huffman于1952年提出一种最佳不等长编码，是图像编码中常用的无损压缩编码。1、定理

如果码字长度严格按照符号出现概率大小逆序排列，则平均码字长度最小。→概率大的用短码，概率小的用长码。

霍夫曼编码2、编码方法

（1）对信源符号按其出现的概率进行递减排序。

（2）将两个最小的概率相加，其和作为新符号的概率，并按（1）重新排序。

（3）重复（1）（2），直到概率之和达到1为止。

（4）每次合并符号时，将被合并的符号赋予1和0或0和1。

（5）寻找从概率1处到每个信源符号的路径，记录下路径上的0，1序列，该序列即为信源符号的码字（编码）。

霍夫曼编码

举例：信号源s={s1,s2,s3,s4,s5,s6}，其概率分布为p1=0.4p2=0.3p3=0.1p4=0.1p5=0.06p6=0.04，求最佳Huffman码。方法：将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。霍夫曼编码重复上述做法，直到最后剩下两个概率为止。从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码元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*0.04=2.2bit压缩比：η＝3/2.2＝1.36静态编码：在压缩之前就建立好一个概率统计表和编码树。算法速度快，但压缩效果不是最好；动态编码：对每一个图像，临时建立概率统计表和编码树。算法速度慢，但压缩效果最好。霍夫曼编码霍夫曼解码设接收端收到的码流是101001000，如何判断应“断”在何处，即哪几个比特应对应一个码字？也就是说如何解码？下面介绍两种方法。1）树形解码。解码器先进高位，并根据该位是1还是0判断由根向下走向，若走到树叶，说明至此为止的码串部分对应一个码字，从而解出对应的符号；

霍夫曼编码重新从树根开始解码，若未走到树叶，则继续进一位，至到走到树叶。2）并行解码。

用树形解码时需一位一位读入和判断，当码表较长时，速度太慢。特别是对活动图像解码时，难以用硬件实现。而并行解码，可一次解出一个码字，易于硬件实现，解码速度快。

游程长度编码游程编码是一种简单的无损压缩的方法。概念：行程：具有相同灰度值的像素序列。编码思想：去除像素冗余。用行程的灰度和行程的长度代替行程本身。例：设重复次数为iC,重复像素值为iP编码为：iCiPiCiPiCiP

编码前：aaaaaaabbbbbbcccccccc

编码后：7a6b8c游程长度编码基本方法：

使用一新字符序列代取原始数据中相同的字

符序列，来实现数据压缩。（压缩原始

数据中相同的字符序列）把沿着扫描行的象素序列x1,x2,…,xN映射为行程序列(g1,l1),

(g2,l2),…,(gk,lk)

gi—灰度级li—gi的行程长度因为象素序列可以根据行程序列来重建，故行程映射变换是可逆的。因它包含灰度鉴别和行程计数，故它是非线性的。游程长度编码分析：

对于有大面积色块的图像，压缩效果很好

对于纷杂的图像，压缩效果不好，最坏情况下，会加倍图像游程长度编码举例:例如一个数据字符串为RTTTTTTTTABBCKGHJK用一新的字符串：#8T，代替8个T。#为特殊标识符，表示行程编码。8代表其后字符重复的次数；T为重复的字符。则行程编码后的字符串为：R＃8TABBCKGHJK压缩前总字符数18压缩后总字符数13其压缩比：η=18/13=1.38

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

算术编码算术编码：越来越流行（在很多标准中被采用）适合的场合：小字母表：如二进制信源概率分布不均衡建模与编码分开算术编码算术编码：对整个序列信源符号串产生一个唯一的标识（tag）直接对序列进行编码（不是码字的串联）：非分组码不用对该长度所有可能的序列编码标识是[0,1)之间的一个数（二进制小数，可作为序列的二进制编码）算术编码算术编码中，信源符号与码字之间不存在一一对应的关系。一个码字不是赋给某个信源符号，而是赋给整个消息序列。这个码字本身定义一个介于0和1之间的实数区间，该区间中的任何一个实数就代表要编码的消息序列。当消息中的符号数目增加时，用于描述消息的间隔变得更小，而表示间隔所需要的信息单元（如编码位数）变得更多了。算术编码定义一一映射：ak

[FX(k-1),FX(k)],k=1..m,FX(0)=0[FX(k-1),FX(k)]区间内的任何数字表示ak对2字母序列akaj编码对ak

，选择[FX(k-1),FX(k)]然后将该区间按比例分割并选取第j个区间：算术编码方法：1.产生标识将[0,1)分为m个区间：算术编码考虑对a1a2a3编码：A={a1,a2,a3},P={0.7,0.1,0.2)映射：a11,a22,a33cdf:FX(1)=0.7,FX(2)=0.8,FX(3)=1 .0算术编码A={a1,a2,…,am}对公平掷骰子的例子：{1,2,3,4,5,6}映射成数字算术编码字符串的词典顺序：其中表示“在字母顺序中，y在x的前面”n

为序列的长度算术编码考虑两轮连续的骰子：输出={11,12,…,16,21,22,…,26,…,61,62,…,66}注意：为了产生13的标识，我们不必对产生其他标识但是，为了产生长度为n的字符串的标识，我们必须知道比其短的字符串的概率这与产生所有的码字一样繁重！应该想办法来避免此事算术编码区间构造包含某个标识的区间与所有其他标识的区间不相交基本思想递归：将序列的下/上界视为更短序列的界的函数上述骰子的例子：考虑序列：322

令u(n),l(n)

为长度为n序列的上界和下界，则

u(1)=FX(3),l(1)=FX(2) u(2)=FX(2)(32),l(2)=FX(2)(31)算术编码算术编码算术编码产生标识：通常，对任意序列x=x1x2…xn只需知道信源的cdf，即信源的概率模型算术编码：编码和解码过程都只涉及算术运算（加、减、乘、