第三章图像压缩编码

第三章

图像压缩编码中国矿业大学信电学院主要内容

3.1图像编码理论分类

3.2数据压缩与信息论基础

3.3霍夫曼编码

3.4游程长度编码

3.5算术编码

3.6LZW字典编码

3.1图像压缩编码分类一般从信息论角度出发分为两大类：冗余度压缩方法信息量压缩方法1、冗余度压缩方法：也称无损压缩，信息保持编码或熵编码。具体讲为解码图像和压缩编码前图像严格相同，没有失真。冗余度压缩方法的核心是基于统计模型，减少或完全去除源数据流中的冗余，同时保持信息不变。可实现编码与解码互逆。(第3章压缩方法)2、信息量压缩方法：也称有损压缩，失真度编码或熵压缩编码。即解码图像和原始图像是有差别的，允许有一定失真。信息量压缩方法是以牺牲部分信息量为代价而换取缩短平均码长的编码压缩方法。由于在压缩过程中在允许前提下丢失一部分信息，所以图像还原后与压缩前不会完全一致。(第4、5章压缩方法)信息量压缩方法不能实现编码与解码互逆。压缩编码分类统计编码(无损编码)有损编码游程编码Huffman编码算术编码主要分两大类LZW字典编码预测编码变换编码DFTDCTK-L变换香农编码一、图像编码技术的必要性：1.信息传输方式发生了很大的改变

通信方式的改变

文字+语音图像+文字+语音

通信对象的改变

人与人人与机器，机器与机器要求图像的保真度和传输的实时性。3.2.1数据压缩与数据冗余3.2数据压缩与信息论基础

2.图像传输与存储需要的信息量空间：

如一部90分钟的彩色电影，每秒放映24帧。把它数字化，每帧512512像素，每像素的R、G、B三分量分别占8bit，则总比特数为90602435125128bit=97,200M。如一张CD光盘可存600兆字节数据，这部电影光图像（还有声音）就需要160张CD光盘用来存储。

因此，传输带宽、速度、存储器容量的限制使得对图象数据进行压缩显得非常必要。二、图像编码技术的可能性：1、从信息论观点来看，图像作为一信源，描述图像信源数据是有效信息量和冗余量两部分组成。去除冗余量可节省存储和传输中的开销，同时不损害图像信源中有效信息量。如果不同的方法表示给定量的信息用了不同的数据量，那么使用较多数据量的方法中，有些数据必然代表无用的信息，或者为重复地表示了其它数据已表示的信息，这为数据冗余的概念。什么是数据冗余呢？一幅图像中像素灰度出现的不均匀性。如果用同

样长度比特表示每一个灰度，则必然存在冗余。图像能量在变换域内分布的不均匀性，大部分能

量集中在低频部分，而小部分能量集中在高和较

高的频率部分。则高频能量为数据冗余。图像像素在时间和空间上的相关性造成信息冗余。空间冗余：邻近像素灰度分布的相关性很强。频间冗余：多谱段图像中各谱段图像对应像素之间

灰度相关性很强。时间冗余：序列图像帧间画面对应像素灰度的相关

性很强。视觉冗余：是指人眼不能感知或不敏感的那部分

图像信息。信息熵冗余：也称编码冗余，如果图像中平均每个

像素使用的比特数大于该图像的信息

熵，则图像中存在冗余。结构冗余：图像中存在很强的纹理结构或自相似性。知识冗余：在有些图像中还包含与某些先验知识

有关的信息。描述语言

1）“这是一幅2*2的图像，图像的第一个像素是红的，第二个像素是红的，第三个像素是红的，第四个像素是红的”。

2）“这是一幅2*2的图像，整幅图都是红色的”。由此我们知道，整理图像的描述方法可以达到压缩的目的。图像冗余无损压缩的原理RGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGB16RGB从原来的16*3*8=284bits压缩为：

(1+3)*8=32bits图像冗余有损压缩的原理34343434343434343434343434343434343434343434343434253436353434343434323434333730343434343434343435343431利用各种冗余信息，压缩编码技术能够很好地解决在将模拟信号转换为数字信号后所产生的带宽需求增加的问题，是使数字信号走上实用化的关键技术之一。表1几种常见应用的码率

2.应用环境允许图像有一定程度地失真：

接收端图像设备分辨率降低，则可降低图像分辨

率。

根据人的视觉特性对不敏感区进行降分辨率编码。

人眼对静态物体的敏感程度大于对动态物体敏感

程度，可减少表示动态物体bit数；

人眼对图像中心信息敏感程度大于对图像边缘信

息敏感程度，可对边缘信息少分配bit数。

应用方关心图像区域有限，可对其余部分图像可

采用空间和灰度级上的粗化。

对于识别，图像特征抽取和描述也是数据压缩。3.2.2图像压缩编码系统的基本构成3.2数据压缩与信息论基础图像信息源信源编码器信道编码器信道信道解码器信源解码器图像输出编码器解码器信源编码功能是将信源编码输出一系列二进制数字序列信道编码功能是将输入二进制序列形成能够在信道中传输的码，具有检错纠错3.2.2图像压缩编码系统的基本构成3.2数据压缩与信息论基础编码器构成输入图像变换器量化器符号编码器信道反变换器符号解码器输出图像3.2.3信息论基础3.2数据压缩与信息论基础一、图像的信息熵：熵是信息量的度量方法,表达一个信源平均信息量的大小。它表示某一事件出现的消息越多,事件发生的可能性越小,数学上为概率越小.

出现概率小的事件（符号）比出现概率大的事件能提供更多的信息量。

设数字图像X中包含的像素的分布灰度级的集合为A={ai|i=1,2,…,m}，ai在统计上是无关的，且ai出现概率为p(ai),则定义各灰度级ai所包含信息I(ai)为：如果对数字图像X像素分布各灰度级作平均度量，则可得平均信息量：则称H(X)为数字图像X的熵，单位为bit/像素。可看出，图像的熵H是表示其各个灰度级比特数的统计平均值。例如：有一幅40个像素组成的灰度图像，灰度共有5级，分别用A、B、C、D、E表示。40个像素中出现灰度A的像素数有15个；出现灰度B的像素数有7个；出现灰度C的像素数有7个等等，如下表所示。灰度等级ABCDE像素数157765概率15/407/407/406/405/40假设每个像素占3位表示，则编码这幅图像共需403=120位。求这幅图象的熵为：这就是说每个像素用2.196位表示，40个像素需要用87.84位。可看出，通过求图像的熵对图像编码，可起到压缩图像数据作用。二、无失真编码理论(可变长最佳编码定理)等长编码：对于每个符号，如经过量化后的图像数据，如果对它们每个值都是以相同长度的二进制码表示的，称之为等长编码或均匀编码。可变长编码：对于每个符号，表示符号的码字的长度不是固定不变的，而是随符号出现概率而变化：对出现概率高的符号分配较短码字，对出现概率低的符号分配较长码字。等长编码是将所有符号当作等概率事件处理的。定理2：在变字长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平均码字长度为最小。定理1：若编码时，对出现概率较大的符号用较少比特数(短码)表示，对出现概率较小的符号用较多比特数(长码)表示，则其平均码字长度L要比等长编码时所需码字少。在非均匀符号概率分布情况下，变长编码效率高于等长编码。三、描述图像压缩性能的指标：压缩比：一般情况下压缩比c1，c愈大则压缩程度愈高。平均码字长度R：k为数字图像第k个码字Ck的长度；pk为数字图像第k个码字Ck相应出现概率。编码效率：H为原始图像的熵；R是实际编码的平均码字长度。冗余度r：如果编码效率100%，说明还有冗余信息存在。r越小，说明可压缩的余地越小。统计编码统计编码是一种无损编码，是建立在图像的统计特性基础之上的压缩编码。信源统计编码方法关键在于去除冗余度。统计编码(无损编码)游程编码Huffman编码算术编码LZW字典编码香农编码3.3霍夫曼编码(HuffmanCoding)这为Huffman于1952年提出的一种编码方法，是一种最佳编码方法。所谓最佳编码方法是指采用Huffman编码方法得到的单元像素的比特数最接近图像的实际熵值。而熵为进行无失真编码的理论极限。Huffman编码是根据可变长最佳编码定理，应用哈夫曼算法而产生的一种编码方法。1、Huffman编码方法⑴概率统计(如对一幅图像作灰度信号统计)，得到n个不同概率的灰度信息符号；⑵将n个灰度信息符号出现的概率由大到小排序，概率相同的可以任意放；⑶将两个最小概率相加(概率个数减为n-1个),形成新的概率集合；再按第⑵步方法重排，如此重复直到仅有两个概率为止；⑷分配码字。原则为从最后一步开始反向进行，以二进制码元(0,1)赋值，构成Huffman码字；注意：码字分配从最后一步开始反向进行。对最后两个概率一个赋予“0”码，一个赋予“1”码，这里赋予0和1完全随机，不影响结束。2、举例1：设有一图像序列，含8个灰度级x1，x2，,x8，概率分别为：P1=0.04，P2=0.06，P3=0.10，P4=0.10，P5=0.07，P6=0.18，P7=0.05，P8=0.40。

试进行Huffman编码，并计算编码效率、压缩比及冗余度。符号概率p80.40p60.18p30.10p40.10p50.07p20.06p70.05p10.040.400.180.100.100.070.090.060.400.180.130.100.100.090.400.180.190.130.100.400.230.190.180.400.370.230.600.4010111111000000统一：概率大的赋予码字为“0”，概率小的赋予码字为“1”。分配码字x1x2x3x4x5x6x7x8码长0001101010110000010000100010154344351则有：则其平均码字长度为：则其熵为：则其编码效率为：则其冗余度为：如果压缩前8个符号需要3个比特量化，经压缩后平均码字长度为2.61，则压缩比为：3.讨论：试对图像字符序列aaaa

bbb

cc

d

eeeee

fffffff进行Huffman编码。解：对该图像字符序列中不同字符进行概率统

计，有：P(a)=4/22P(b)=3/22P(c)=2/22

P(d)=1/22P(e)=5/22P(f)=7/22则进行Huffman编码过程为：统一：概率大的赋予码字为“1”，概率小的赋予码字为“0”。则赋予码字时得：a=00b=100c=1011d=1010e=01f=11（或第2种答案：a=00b=101c=1001d=1000e=01f=11）4、Huffman编码在图像压缩中的实现我们知道，对一幅图像进行编码时，如果图像的大小大于256时，这幅图像的不同的码字就有可能是很大，例如极限为256个不同的码字。对整幅图直接进行Huffman编码时，小分布的灰度值，就有可能具有很长的编码。如：100位以上，这样不但达不到压缩的效果反而会使数据量加大，应该如何处理？常用的且有效的方法是：

将图像分割成若干的小块，对每块进行独立的Huffman编码。例如：分成的子块，就可以大大降低不同灰度值的个数（最多是64而不是256）。3.4香农编码是一种可变长编码，码字长度由符号出现概率决定。1、基本原理(求可变长度最佳编码的平均码字长度)设进行可变长度最佳编码时，被编码的信息符号总数为N，所用码元进制为D，第i个符号出现的概率为Pi，与其对应码字长度为ti，则可证明这种编码结果的平均码字长度R落在下列区间内：式中H为信息熵。由此可引导出对某一个信息符号(码字)的长度存在如下关系式：对二进制进一步简化为：可见，码字长度ti是根据信息符号出现概率Pi决定的。2、香农编码步骤：将输入图像灰度级（信息符号）按出现概率由大到小顺序排列(相等者可任意颠倒排列位置)。按式子(1)或式子(2)计算各概率对应的码字长度ti

。

计算各概率对应的累加概率ai

：(4)把各个累加概率由十进制小数转换成二进制小数，保留最高的ti位，去掉小数点，即获得各个与累加概率相对应的信息符号的码字。3、举例1：仍采用上面Huffman例子进行香农编码：设有一图像序列，含8个灰度级x1，x2，,x8，概率分别为：P1=0.04，P2=0.06，P3=0.10，P4=0.10，P5=0.07，P6=0.18，P7=0.05，P8=0.40。

试进行香农编码，计算平均码字长度和编码效率。解：计算ti：当P1=0.04，有：ti=5依次类推，得：符号概率x80.4020000x60.1830.4001100011x30.1040.58100101001x40.1040.68101001010x50.0740.78110001100x20.0650.85110110011011x70.0550.91111010011101x10.0450.96111101011110计算ti计算ai十变二

进制去掉多余ti尾数(码字)则其平均码字长度为：则其熵为：则其编码效率为：可见，香农编码要比Huffman编码的编码效率略低一些。3.5行程长度编码（游程编码）行程编码又称行程长度编码（RunLengthEncoding，RLE），是一种熵编码。行程：对于图像编码，可定义沿特定方向上具有相同灰度值的相邻像元为一轮，其延续长度称之为延续的行程，简称为“行程”。基本原理：将具有相同灰度值的连续串用其串长（行程长度）和一个代表灰度值来代替。将行程长度和代表灰度值组合在一起构成行程对，作为输入的码元进行编码。在二值图像中，每一扫描行总由若干段连着的黑像素（灰度值为0）和连着的白像素（灰度值为1）组成，它们分别称为“黑行程”和“白行程”，且交替出现(全白或全黑扫描行除外)。对于不同的行程长度根据其概率分布分配相应的码字，可以得到较好的压缩。通常行程编码比较适合于二值图像的编码。例如有一扫描线自左向右线段组成如下所示：线段序号线段性质线段组成线段长度

1白游程0003

2黑游程1113

3白游程000005

4黑游程11114

5白游程000005则游程长度进行统计为：3个0，3个1，5个0，4个0，5个1(含义为3个白，3个黑，5个白，4个黑，5个白)。游程长度编码的信息符号集由长度为1,2,…,N等各种游程长度组成。这里N是一条扫描线上的像素总数。例如，有一字符串“aabbbcddddd”，则经行程长度编码后，该字符串可以只用“2a3b1c5d”来表示。

aa

bbb

c

ddddd

(共11*8=88bits)

2a3b1c5d(共8*8=64bits)1.一维行程编码例如：图像中某行灰度值40，40，40，40，40，232，232，232，232，232，0，0，0，0，0，0，0，0，93，93，93，93，56，93，93，93，93，93序号灰度值行程长度灰度行程对1405（5，40）22325（5，232）308（8，0）4934（4，90）5561（1，56）6935（5，93）总数据量为：28×8=224bit则得到行程编码的码流为：5，40，5，232，8，0，4，93，1，56，5，93规则：行程长度编码用3位二进制数灰度值用8位二进制数8=7+15，40，5，232，7，0，1，0，4，93，1，56，5，93行程编码所需用的比特位数为：7×3+7×8=77bit压缩率为：2.二维行程编码关键是进行二维排序，使像素之间关系变成一维的邻接关系此排序方法主要用于DCT系数的压缩编码。对以下二维图象进行行程长度编码原图象数据大小为：64×8=512bit行程长度编码图象数据大小为：3×41+8×41=451bit游程长度编码本质上说就是计算图像信号出现行程长度，然后将行程长度转换为代码。如果不区分黑、白游程进行统一游程长度编码，并设Pi为长度为i的游长的概率。则：游长的熵H平均游长L游程长度的熵

(即平均每个像素的熵)当根据各游长的概率，利用Huffman编码时，则每个游程的平均码长满足下列不等式：若不等式两边同除以平均游长L，可得每个像素的平均码长n的估值：则每个像素的熵h即为游长编码可达到的最小比特率的估值。3.6算术编码为了解决计算机中必须以整数位进行编码问题，提出算术编码方法。1、基本原理假设一个信源的概率模型。根据该信源的概率模型，一般把一个信源集合表示为实数线上的0至1间的一个区间。这集合中每个元素用来缩短这个区间。信源集合的元素越多,信息越长,编码表示所得区间间隔越小,表示这一间隔所需二进制位就越多,码字越长。这就是区间作为代码的原理。2、编码方法：(举例讲解）设图像信源编码用a，b，c，d4个符号表示，符号a，b，c，d分别出现概率为：P(a)=0.4，P(b)=0.2,P(c)=0.2,P(d)=0.2假设各数据符号在[0,1内赋值范围设定:试对源数据集{dacab}进行算术编码。a=[0,0.4]，b=[0.4,0.6]，c=[0.6,0.8]，d=[0.8,1.0]解：给出一组关系式为：

StartN=StartB+LeftCLEndN=StartB

+RightCL式中StartN

为新子区间的起始位置；

EndN

为新子区间的结束位置；

StartB

为前子区间的起始位置；

LeftC

为当前符号的区间左端；

RightC

为当前符号的区间右端；

L

为前子区间长度。第一个被压缩符号为“d”，

则前符号区间为[0,1，而d为[0.8，1.0

StartN=0+0.81=0.8

EndN=0+1.01=1.0

代码“d”编码区间为[0.8,1.0，宽度为0.2第二个被压缩符号为“a”，

前符号区间为[0.8，1.0，“a”为[0，0.4)，则“a”取值范围应在前符号区间[0.8，1.0的范围之内，则：

StartN=0.8+00.2=0.8

EndN=0.8+0.40.2=0.88

代码“a”编码区间为[0.8，0.88，宽度为0.08

第三个被压缩符号为“c”，

前符号区间[0.8，0.88)，c为[0.6，0.8)

StartN

=0.8+0.60.08=0.848

EndN

=0.8+0.80.08=0.864

“c”实际编码区间为[0.848，0.864，宽度为0.016第四个被压缩符号为“a”，

前符号区间[0.848，0.864)，a为[0，0.4)

StartN=0.848+00.016=0.848

EndN

=0.848+0.40.016=0.8544

“a”实际编码区间为[0.848，0.8544，宽度为0.0064第五个被压缩符号为“b”，

前符号区间[0.848，0.8544)，b为[0.4，0.6)

StartN=0.848+0.40.0064=0.85056

EndN

=0.848+0.60.0064=0.85184

“b”实际编码区间为[0.85056，0.85184至此，数据串{dacab}已经被描述成一个编码实数区间为[0.85056，0.85184。或者说在此区间内任一实数值都唯一对应该数据序列。把该十进制实数区间用二进制表示为：[0.110110011011，0.110110100001。把该十进制实数区间用二进制表示为：

[0.110110011011，0.110110100001。但从这个区间可以看出，0.1101101位于这个区间内并且其编码最短，故把其作为数据序列{dacab}的编码输出。考虑到算术编码中任一数据序列的编码都含有“0.”，所以编码时可以不考虑“0.”。最后所得的码点值“1101101”(忽视小数点)就是对{dacab}进行算术编码的结果。所以“dacab”的编码区间为[0.85056，0.85184]“dacab”的编码值为1101101信源熵为：平均码长：编码效率：3.7LZW编码LZW编码又称字串表编码，属于无损编码。

基本思想:

在编码过程中，将所遇到的字符串建立一个字符串表，表中的每个字符串都对应一个索引，编码时用该字符串在字串表中的索引来代替原始的数据串。字符串表是在压缩过程中动态生成的，不必将它保存在压缩文件里，因为解压缩时字符串表可以由压缩文件中的信息重新生成。

编码方法(举例讲解)

设有一来源于4色（以a、b、c、d表示）图像的数据流aabcabbbbd，现对其进行LZW编码。编码过程如下：①设S1、S2为两个存放字符串的临时变量。

LZW_CLEAR为字符表初始化标志。

LZW_EOI为字符表编码结束标志。②根据图像中使用颜色数初始化一个字串表，每个颜色对应字串表中一个索引。由于图像中只有四种颜色，仅用4比特表示字符串表中每个字符串索引。建立初始化字符串表如下所示。字符串索引a0Hb1Hc2Hd3HLZW_CLEAR4HLZW_EOI5H表中前四项代表4种颜色，

后两项分别表示初始化和图像结束标志。把S1和S2初始化为空（即NULL），输出LZW_CLEAR的在字符串表中的索引值4H，接下来是对图像数据的编码。③从图像数据流的第一个字符开始，每次读取一个字符，将其赋给字符串变量S2。则读取的图像数据流的第一个字符为“a”，赋给S2。④判断“S1+S2”是否存在于字符串表中，如果字符串表中存在“S1+S2”，则S1=S1+S2，不输出任何结果；否则，输出S1在字符串表中索引，并且在字符串表末尾为“S1+S2”添加索引，同时S1=S2。读取第一个字符为“a”赋给S2，则有S1+S2=“a”。而“a”存在于字符串表中，对应索引值为0H，则不输出任何结果，只使S1=S1+S2。接着读入下一个字符“a”赋给S2，因S1+S2=“aa”不存在于字串表中，所以对应输出结果为输出S1=“a”的索引0H，同时在字符串表末尾添加新字符串“aa”的索引6H，并使S1=S2=“a”。

接着读入第三个字符“b”赋给S2,因S1+S2=“ab”不存在于字串表中，所以对应输出结果为输出S1=“a”的索引0H，同时在字符串表末尾添加新字符串“ab”的索引7H，并使S1=S2=“b”。

依次读取数据流中的每个字符，如果S1+S2没有出现在字符串表中，则输出S1中的字符串的索引作为输出结果，并在字符串表末尾为新字符串S1+S2添加索引，并使S1=S2；否则，不输出任何结果，只是使S1=S1+S2。最终，直到所有字符读完为止。所有字符处理完毕后，输出S1中的字符串的索引，最后输出结束标志LZW_EOI的索引。至此，编码完毕，图像数据流aabcabbbbd完整编码过程如下表：输入数据S2S1+S2输出结果S1生成新字符串及索引NULLNULL4HNULLaaaaaa0Haaa<6H>bab0Hbab<7H>cbc1Hcbc<8H>aca2Haca<9H>bababbabb7Hbabb<AH>bbb1Hbbb<BH>bbbbbdb