图片处理技术4

1、本章重点：本章重点：图像编码与压缩的基本概念、理论及其编码分图像编码与压缩的基本概念、理论及其编码分类。类。常用的无损压缩方法。常用的无损压缩方法。常用的有损压缩方法。常用的有损压缩方法。第第4章章 图像编码与压缩图像编码与压缩4.1 图像编码的必要性与可能性图像编码的必要性与可能性 4.2 图像编码分类图像编码分类 4.3 图像编码评价准则图像编码评价准则 4.4 图像编码模型图像编码模型 4.5 无损压缩无损压缩 4.6 有损压缩有损压缩 4.7 JPEG图像编码压缩标准图像编码压缩标准 4.8 MPEG视频编码压缩标准视频编码压缩标准 4.9 小结小结第第4章章 图像编码与压缩图像编码与

2、压缩4.1 图像编码的必要性与可能性图像编码的必要性与可能性4.1.1图像编码的必要性图像编码的必要性 数字图像的庞大数据对计算机的处理速度、存储容量都提数字图像的庞大数据对计算机的处理速度、存储容量都提出过高的要求。因此必须把数据量压缩。出过高的要求。因此必须把数据量压缩。 各种媒体信息(特别是动态视频)数据量非常之大。 以一幅10241024分辨率的24位真彩色图像为例，数据量为： 1024 1024 8 3/8=3MB； 若以30帧/秒播放，每秒数据量为： 3 30=90MB 陆地卫星LandSat-3分辨率为2340 3240，四波段，采样精度7位，则一幅图像的数据量为： 2340 3

3、240 7 4=212Mb 按每天传输30幅计,每天数据量为: 21230=6.36Gb=795MB 可见，没有图像编码与压缩技术的发展，大容量图像信息的存储与传输是难以实现的。 从传送图像的角度来看，则更要求数据量压缩。在信从传送图像的角度来看，则更要求数据量压缩。在信道带宽、通信链路容量一定的前提下，采用编码压缩道带宽、通信链路容量一定的前提下，采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段技术，减少传输数据量，是提高通信速度的重要手段 。4.1.2图像编码的可能性图像编码的可能性 图像、声音这些媒体确实又具有很大的图像、声音这些媒体确实又具有很大的压缩潜力。压缩潜力。 以目前

4、常用的位图格式的图像存储方以目前常用的位图格式的图像存储方式为例，像素与像素之间无论是在行方式为例，像素与像素之间无论是在行方向还是在列方向都具有很大的相关性，向还是在列方向都具有很大的相关性，因而整体上数据的冗余度很大，在允许因而整体上数据的冗余度很大，在允许一定限度失真的前提下，能够对图像数一定限度失真的前提下，能够对图像数据进行很大程度的压缩。据进行很大程度的压缩。 这里所说的失真一般都是在人眼允许的误差范围之内，压缩前后的图像如果不做非常细致的对比是很难觉察出两者的差别的。因此，数据压缩技术是多媒体系统中一项十分关键的技术。 数据之所以能够压缩是基于原始信源的数据存在着很大的冗余度。

5、图像数据冗余图像数据冗余q 空间冗余q 时间冗余q 结构冗余q 知识冗余q 视觉冗余q 图像区域的相同性冗余q 纹理的统计冗余空间冗余空间冗余 同一景物表面上各采样点之间的颜色（亮度）之间往往存在着空间相关性。 基于离散象素的表示方式通常没有利用景物表面颜色（亮度）的这种空间相关性，从而产生了空间冗余。 大部分区域所有像大部分区域所有像素值相同。素值相同。时间冗余时间冗余 主要指视频相邻帧之间的冗余。 结构冗余结构冗余 有些图像的纹理区，图象像素值之间存在着明显的分布模式，称之为结构冗余。知识冗余知识冗余 某些图像的理解与某些知识有相当大的相关性。如人脸有固定的结构。视觉冗余视觉冗余 人的视觉

6、系统对图像场的敏感性是非均匀和非线性的，然而，在记录原始图像数据时，通常假定视觉系统是线性的和均匀的，对视觉敏感和不敏感部分同等对待，从而产生视觉冗余。 如对亮度和色彩的敏感度不同。图像区域的相同性冗余图像区域的相同性冗余 指在图像中的两个或对应的所有像素相同或相近，从而产生的数据重复性存储，即图像区域的相似性冗余。 纹理的统计冗余纹理的统计冗余 图像纹理在统计意义上服从某一分布规律。利用这种性质可以减少表示图像的数据量。4.2图像编码分类图像编码分类 根据解压重建后的图像和原始图像之间是否具有误差，根据解压重建后的图像和原始图像之间是否具有误差，可以将图像编码与压缩方法分为无误差可以将图像编

7、码与压缩方法分为无误差(亦称无失真、亦称无失真、无损、信息保持无损、信息保持)编码和有误差编码和有误差(有失真或有损有失真或有损)编码两编码两大类。大类。 根据编码作用域划分，图像编码分为空间域编码和变根据编码作用域划分，图像编码分为空间域编码和变换域编码两大类。换域编码两大类。 若从具体编码技术来考虑，又可分为预测编码、变换若从具体编码技术来考虑，又可分为预测编码、变换编码、统计编码、轮廓编码、模型编码等。编码、统计编码、轮廓编码、模型编码等。多媒体数据编码多媒体数据编码 脉冲编码调制(PCM) 预测编码 变换编码 统计编码（熵编码） 混合编码 静态图像编码 动态图像编码 其他编码4.3 图

8、像编码评价准则图像编码评价准则 在图像压缩编码中，解码图像与原始图像可能会有差在图像压缩编码中，解码图像与原始图像可能会有差异，因此，需要评价压缩后图像的质量。异，因此，需要评价压缩后图像的质量。 描述解码图像相对原始图像偏离程度的测度一般称为描述解码图像相对原始图像偏离程度的测度一般称为保真度保真度(逼真度逼真度)准则。准则。 常用的准则可分为两大类：客观保真度准则和主观保常用的准则可分为两大类：客观保真度准则和主观保真度准则。真度准则。4.3.1 客观保真度准则客观保真度准则 最常用的客观保真度准则是原图像和解码图像之间的最常用的客观保真度准则是原图像和解码图像之间的均方根误差和均方根信噪

9、比两种。均方根误差和均方根信噪比两种。 均方根误差均方根误差 : :1 2211001( , )( , )MNrmsxyef x yf x yMN均方信噪比均方信噪比: : 2111120000( , )( , )( , )MNMNmsxyxySNRf x yf x yf x y对上式求平方根，就得到均方根信噪比。对上式求平方根，就得到均方根信噪比。 （4-2） （4-3） 4.3.2主观保真度准则主观保真度准则 具有相同客观保真度的不同图像，人的视觉可能产生具有相同客观保真度的不同图像，人的视觉可能产生不同的视觉效果。这是因为客观保真度是一种统计平不同的视觉效果。这是因为客观保真度是一种统计

10、平均意义下的度量准则，对于图像中的细节无法反映出均意义下的度量准则，对于图像中的细节无法反映出来。来。 一种常用的方法是对一组一种常用的方法是对一组(不少于不少于20人人)观察者显示图像，观察者显示图像，并将他们对该图像的评分取平均，用来评价一幅图像并将他们对该图像的评分取平均，用来评价一幅图像的主观质量。的主观质量。 例如可用例如可用-3-3，-2-2，-1-1，0 0 ，1 1，2 2，33来代表主观评价来代表主观评价 很差，很差，较差，稍差，相同，稍好，较好，很好较差，稍差，相同，稍好，较好，很好 。评分评价说明1优秀图像质量非常好，如同人能想象出的最好质量2良好图像质量高，观看舒服，有

11、干扰但不影响观看3可用图像质量可以接受，有干扰但不太影响观看4刚可看图像质量差，干扰有些妨碍观看，观察者希望改进5差图像质量很差，几乎无法观看6不能用图像质量极差，不能使用表表4.1 4.1 电视图像质量评价尺度电视图像质量评价尺度4.4 图像编码模型图像编码模型 一个图像压缩系统包括两个不同的结构块：一个图像压缩系统包括两个不同的结构块： 编码器和解码器。编码器和解码器。 图像图像f（x，y）输入到编码器中，编码器可以根据输入）输入到编码器中，编码器可以根据输入数据生成一组符号。在通过信道进行传输之后，将经数据生成一组符号。在通过信道进行传输之后，将经过编码的表达符号送入解码器，经过重构后，

12、生成输过编码的表达符号送入解码器，经过重构后，生成输出图像。出图像。 f(x,y)信源编码信道编码信道信道解码信源解码f(x,y)一个常用于图像压缩系统模型一个常用于图像压缩系统模型4.4.1信源编码器和信源解码器信源编码器和信源解码器 信源编码器的任务是减少或消除输入图像中的编码冗信源编码器的任务是减少或消除输入图像中的编码冗余、像素间冗余或心理视觉冗余。余、像素间冗余或心理视觉冗余。 从原理来看主要分为三个阶段从原理来看主要分为三个阶段:v 第一阶段将输入数据转换为可以减少输入图像中像素第一阶段将输入数据转换为可以减少输入图像中像素间冗余的数据的集合。间冗余的数据的集合。v 第二阶段设法去

13、除原图像信号的相关性第二阶段设法去除原图像信号的相关性 。v 第三阶段是找一种更近于熵，又利于计算机处理的编第三阶段是找一种更近于熵，又利于计算机处理的编码方式码方式 。 信源解码器包含两部分：符号解码器和反向转换器。信源解码器包含两部分：符号解码器和反向转换器。编码器模型编码器模型 f(x,y)转换器量化器 符号编码器信道信道符 号 解 码器反 向 转 换器f(x,y)（a）信源编码器）信源编码器（b）信源解码器）信源解码器4.4.2信道编码器和解码器信道编码器和解码器 当信道带有噪声或易于出现错误时，信道编码器和解当信道带有噪声或易于出现错误时，信道编码器和解码器就在整个译码解码处理中扮演

14、了重要的角色。信码器就在整个译码解码处理中扮演了重要的角色。信道编码器和解码器通过向信源编码数据中插入预制的道编码器和解码器通过向信源编码数据中插入预制的冗余数据来减少信道噪声的影响。冗余数据来减少信道噪声的影响。 最有用的一种信道编码技术是由最有用的一种信道编码技术是由RwHamming提提出的。这种技术是基于这样的思想，即向被编码数据出的。这种技术是基于这样的思想，即向被编码数据中加入足够的位数以确保可用的码字间变化的位数最中加入足够的位数以确保可用的码字间变化的位数最小。小。 信源编码器与信源解码器信源编码器与信源解码器信源编码器的任务是减少或消除图象中的编码冗余、像素间冗余或心理视觉冗

15、余。映射映射 映射的目的是使原信号经过映射后更有利于编码，既映射后的数据可用较少的比特来编码。 如DPCM中的差分。量化器量化器 把映射后的值进行量化。 可以有均匀量化和非均匀量化。数据压缩编码中的量化处理数据压缩编码中的量化处理 不是指指 A/D 变换时的量化，而是指变换时的量化，而是指在熵编码之前，对该值进行的量化处理。 量化处理把某个范围内的一批输入，量化到一量化处理把某个范围内的一批输入，量化到一个输出级上，因此是个输出级上，因此是多对一的映射，过程一的映射，过程不可逆，有信息丢失，会引起，有信息丢失，会引起量化误差(量化噪声)。 量化方法和量化特性量化方法量化方法标量量化矢量量化均匀

16、量化非均匀量化自适应量化 标量量化：对PCM数据一个数一个数地进行量化。 矢量量化：对这些数据先分组, 每组 K 个数构成一个 K 维矢量，然后以矢量为单位，逐个矢量进行量化。可有效提高压缩比。 矢量量化的编码与解码矢量量化的编码与解码输入量输入量：待编码的K维矢量(如一个尺寸nn图象块中的n2个象素)码本码本C：一个具有L个K维矢量的集合(实际上是一个长度为L的表， 这个表的每一个分量是一个K维矢量y，称其为码字)。矢量量化编码过程：矢量量化编码过程： 从码本 C 中搜索一个与输入矢量最接近的码字 yi(i=1,2,L)的过程。 传输时并不传送码字yi本身，只传送其下标号 i 。 下标所需比

17、特数仅log2L,故该图象块一个象素仅需比特数 * log2L1K矢量量化的关键问题矢量量化的关键问题 设计一个良好的码本。设计一个良好的码本。编码器编码器 编码器的输入为编码器的输入为wi,若若wi可取可取M个值个值w1,w2 ,wm 之一，之一， 其输出码应该是二进制码子其输出码应该是二进制码子ci。 编码器不会引入误差。编码器不会引入误差。 设计编码器应该使设计编码器应该使M个可能输入都能分配一个唯一的个可能输入都能分配一个唯一的二进制码字。二进制码字。 例如，用不等长码对例如，用不等长码对w1,w2 ，w3 分别赋予一个码字分别赋予一个码字c1=0,c2=1,c3=01， 则对于比特流

18、则对于比特流0011，既可译为：，既可译为：c1c1c2c2，也可译为也可译为c1c3c2，不唯一。不唯一。 若赋予一个码字若赋予一个码字c1=0,c2=10,c3=11， 则对于比特流则对于比特流0011，可唯一译为，可唯一译为c1,c1,c3。 能实用的码都应该是唯一的。能实用的码都应该是唯一的。 信源解码器包含两个部分：符号解码器和反向信源解码器包含两个部分：符号解码器和反向映射器。映射器。反向映射符号解码信道4.5无损压缩无损压缩 无损压缩可以精确无误地从压缩数据中恢复出原始数无损压缩可以精确无误地从压缩数据中恢复出原始数据。据。 常见的无损压缩技术包括：基于统计概率的方法和基常见的无

19、损压缩技术包括：基于统计概率的方法和基于字典的技术。于字典的技术。 基于统计概率的方法是依据信息论中的变长编码定理基于统计概率的方法是依据信息论中的变长编码定理和信息熵有关知识，用较短代码代表出现概率大的符和信息熵有关知识，用较短代码代表出现概率大的符号，用较长代码代表出现概率小的符号，从而实现数号，用较长代码代表出现概率小的符号，从而实现数据压缩。据压缩。 统计编码方法中具有代表性的是利用概率分布特性的统计编码方法中具有代表性的是利用概率分布特性的著名的霍夫曼著名的霍夫曼(Huffman)编码方法编码方法 ,另一种是算术编码。另一种是算术编码。 基于字典技术的数据压缩技术有两种：基于字典技术

20、的数据压缩技术有两种： 一种是游程编码一种是游程编码(Running Length Coding)，简称为，简称为RLC ，适用于灰度级不多、数据相关性很强的图像数，适用于灰度级不多、数据相关性很强的图像数据的压缩。但最不适用于每个像素都与它周围的像素据的压缩。但最不适用于每个像素都与它周围的像素不同的情况。不同的情况。 另一种称之为另一种称之为LZW编码编码 ， LZW在对数据文件进行编在对数据文件进行编码的同时，生成了特定字符序列的表以及它们对应的码的同时，生成了特定字符序列的表以及它们对应的代码。代码。 4.5.1霍夫曼编码霍夫曼编码 一个事件集合一个事件集合x1, x2,xn,处于一个

21、基本概率空间，其处于一个基本概率空间，其相应概率为相应概率为p1, p2,pn，且，且p1+ p2+pn=1。每一个信息。每一个信息的信息量为的信息量为: 如定义在概率空间中每一事件的概率不相等时的平均如定义在概率空间中每一事件的概率不相等时的平均不肯定程度或平均信息量叫作熵不肯定程度或平均信息量叫作熵H，则：，则：)(log)(kakpxInkkaknkkkkppxIpxIEH11log)()(1.理论基础理论基础 （4-9） （4-10） 图象熵：图象熵： 设数字图像像素灰度级集合为设数字图像像素灰度级集合为(W1,W2,WM)，其对其对应的概率分别为应的概率分别为P1,P2,PM,则数字

22、图像的信息熵则数字图像的信息熵H为：为： H=nkkakPP1log a取取2时，时，H的单位为比特。的单位为比特。 a取取e时，时，H的单位的单位为奈特。图像编码中为奈特。图像编码中a取取2。 一幅图像的信息熵就是这幅图像的平均信息量，一幅图像的信息熵就是这幅图像的平均信息量，即表示图像中各个灰度级比特数的统计平均值。即表示图像中各个灰度级比特数的统计平均值。 等概率事件的熵最大。等概率事件的熵最大。 信息熵是进行无失真编码理论的极限。低于此极限的无失真编码方法是不存在的。例例 :设设8个随机变量具有同等概率为个随机变量具有同等概率为18，计算信，计算信息熵息熵H。 解解 :根据公式根据公式

23、4-10可得：可得：H=8*-1/8*(log2(1/8)=8*-1/8*(-3)=3 编码效率编码效率在一般情况下，编码效率往往用下列简单公式表在一般情况下，编码效率往往用下列简单公式表示：示： =H/R%H为信息熵，为信息熵，R为平均码字长度。为平均码字长度。 平均码字长度平均码字长度 设设 k为数字图像第为数字图像第k个码字个码字Ck的长度（二进制的长度（二进制代码的位数），其相应出现的概率为代码的位数），其相应出现的概率为Pk，则则该数字图像所赋予的码字平均码长该数字图像所赋予的码字平均码长R为为: R=nkkkP1 根据信息熵编码理论，可以证明在根据信息熵编码理论，可以证明在R H条

24、件下，条件下，总可以设计出某种无失真编码方法。总可以设计出某种无失真编码方法。 若编码结果远大于若编码结果远大于H，表明这种编码效率很低，表明这种编码效率很低，占用的比特数太多。占用的比特数太多。 若编码结果使若编码结果使R等于或接近于等于或接近于H，这种状态的这种状态的编码方法称为最佳编码。编码方法称为最佳编码。 若要求编码结果使若要求编码结果使RH，则必然丢失信息而引则必然丢失信息而引起图像失真。这就是在允许失真条件下的一些起图像失真。这就是在允许失真条件下的一些失真编码方法。失真编码方法。图像熵编码方法图像熵编码方法 熵编码的目的就是要使编码后的图像平均比特熵编码的目的就是要使编码后的图

25、像平均比特数数R尽可能接近图象熵尽可能接近图象熵H。一般根据图像灰度。一般根据图像灰度级数出现的概率赋予不同长度的码字，概率大级数出现的概率赋予不同长度的码字，概率大的灰度级用短码字，反之，用长码字。的灰度级用短码字，反之，用长码字。 可以证明：这样的编码结果所获得的平均码字可以证明：这样的编码结果所获得的平均码字长度最短。长度最短。常用的熵编码方法：常用的熵编码方法： Huffman编码编码 Fano-shannon编码编码 游程编码游程编码 算术编码算术编码 Huffman编码是编码是1952年由年由Huffman提出的一种编码方提出的一种编码方法。法。 这种编码方法根据信源数据符号发生的

26、概率进行编码。这种编码方法根据信源数据符号发生的概率进行编码。在信源数据中出现概率越大的符号，相应的码越短；在信源数据中出现概率越大的符号，相应的码越短；出现概率越小的符号，其码长越长，从而达到用尽可出现概率越小的符号，其码长越长，从而达到用尽可能少的码符号表示源数据。能少的码符号表示源数据。 它在变长编码方法中是最佳的。它在变长编码方法中是最佳的。2. Huffman编码编码 设信源设信源A的信源空间为：的信源空间为：其中其中 ，现用，现用r个码符号的码符号集个码符号的码符号集 对信源对信源A中的每个符号（中的每个符号（i1，2，N)进行编码。进行编码。具体编码的方法是具体编码的方法是:(1

27、) 把信源符号按其出现概率的大小顺序排列起来；把信源符号按其出现概率的大小顺序排列起来；(2) 把最末两个具有最小概率的元素之概率加起来；把最末两个具有最小概率的元素之概率加起来；(3) 把该概率之和同其余概率由大到小排队，然后再把两个最小概率把该概率之和同其余概率由大到小排队，然后再把两个最小概率加起来，再重新排队；加起来，再重新排队；(4) 重复重复(2)直到最后只剩下两个概率为止。直到最后只剩下两个概率为止。1212:( ):()()()NNAaaaA PP AP aP aP a1( )1NiiP a12:,rXxxxHuffman编码具体方法：编码具体方法：例例1 :设有编码输入设有编

28、码输入 。其频率分布分别。其频率分布分别为为 ，现求其最佳霍夫曼编码现求其最佳霍夫曼编码 。 解解 :Huffman编码过程下图所示：编码过程下图所示： 123456,Xx xx xx x12( )0.4, ()0.3P xP x3()0.1,P x456()0.1, ()0.06, ()0.04P xP xP x123456,Ww w w w w w符号 概率 x1 0.4x2 0.3x3 0.1x4 0.1x5 0.06x6 0.041 0.40.30.10.10.120.40.30.20.130.40.30.340.60.4本例中对本例中对0.6赋予赋予0，对，对0.4赋予赋予1，0.4

29、传递到传递到x1，所以，所以x1的的编码便是编码便是1。0.6传递到前一级是两个传递到前一级是两个0.3相加，大值是单独相加，大值是单独一个元素一个元素x2的概率，小值是两个元素概率之和，每个概率的概率，小值是两个元素概率之和，每个概率都小于都小于0.3，所以，所以x2赋予赋予0，0.2和和0.1求和的求和的0.3赋予赋予1。所以。所以x2的编码是的编码是00，而剩余元素编码的前两个码应为，而剩余元素编码的前两个码应为01。0.1赋予赋予1，0.2赋予赋予0。以此类推，最后得到诸元素的编码如。以此类推，最后得到诸元素的编码如下：下： 元素元素x1x1x2x3x4x5x6概概 率率P(x1)0.

30、40.30.10.10.060.04编码编码w110001101000101001011 经霍夫曼编码后，平均码长为：经霍夫曼编码后，平均码长为： = =0.41+0.302+0.13+0.14+0.065+0.045=2.20(bit) 该信源的熵为该信源的熵为H=2.14 bit，编码后计算的平均码长为，编码后计算的平均码长为2.2 bit,非常接近于熵。可见非常接近于熵。可见Huffman编码是一种较好的编码。编码是一种较好的编码。B61()iiPn例2：Huffman编码举例Huffman码字的构成3用二叉树方法实现用二叉树方法实现Huffman编码方法较为便利，因此这种编码方编码方法

31、较为便利，因此这种编码方法用于计算机数据结构的转换中。法用于计算机数据结构的转换中。Huffman编码是最佳的编码是最佳的 ，其构造出来的码不唯一，但其平均码，其构造出来的码不唯一，但其平均码长相同长相同 ，不影响编码效率和数据压缩性能。，不影响编码效率和数据压缩性能。 由于由于Huffman码的码长参差不齐，因此，存在一个输入、输出速码的码长参差不齐，因此，存在一个输入、输出速率匹配问题。解决的办法是设置一定容量的缓冲存储器率匹配问题。解决的办法是设置一定容量的缓冲存储器 Huffman码在存储或传输过程中，如果出现误码，可能会引起误码在存储或传输过程中，如果出现误码，可能会引起误码的连续传

32、播码的连续传播 Huffman编码对不同信源其编码效率也不尽相同。编码对不同信源其编码效率也不尽相同。 Huffman编码应用时，均需要与其他编码结合起来使用，才能进编码应用时，均需要与其他编码结合起来使用，才能进一步提高数据压缩比。一步提高数据压缩比。 Huffman编码方法传输时，需要同时传输Huffman编码表。Huffman编码需要多次排序。4.5.2 香农费诺编码香农费诺编码 由于霍夫曼编码法需要多次排序，当很多时十分不便，由于霍夫曼编码法需要多次排序，当很多时十分不便，为此费诺为此费诺(Fano)和香农和香农(Shannon)分别单独提出类似的分别单独提出类似的方法，使编码更简单。

33、具体编码方法如下：方法，使编码更简单。具体编码方法如下： 把把 按概率由大到小、从上到下排成一列，然后按概率由大到小、从上到下排成一列，然后把把 分成两组分成两组 ， ，并使得，并使得 把两组分别按把两组分别按0，1赋值。赋值。 然后分组、赋值，不断反复，直到每组只有一种输入然后分组、赋值，不断反复，直到每组只有一种输入为止。将每个所赋的值依次排列起来就是费诺为止。将每个所赋的值依次排列起来就是费诺香农香农编码。编码。 nxx ,.,1nxx ,.,1kxx ,.,1nkxx,.,111()()knijijkPxPx 以前面哈夫曼编码的例子进行香农费诺编码以前面哈夫曼编码的例子进行香农费诺编码

34、 ：输入概率 x10.4 o 0 x20.310 10 x30.1100 1100 x40.11 1101x50.0610 1110 x60.041 1111理论上，用Huffman方法对源数据流进行编码可达到最佳编码效果。但由于计算机中存储、处理的最小单位是“位”，因此，在一些情况下，实际压缩比与理论压缩比的极限相去甚远。例如源数据流由X和Y两个符号构成，它们出现的概率分别为23和13。根据字符X的熵确定的最优码长为：H(X)=0.588bitH(Y)=1.58bit若要达到最佳编码效果，相应于字符若要达到最佳编码效果，相应于字符X的码长为的码长为0.58位；字符位；字符Y的码长为的码长为1

35、.58位。位。计算机中不可能有非整数位出现。硬件的限制使得计算机中不可能有非整数位出现。硬件的限制使得编码只能按编码只能按“位位”进行。用进行。用Huffman方法对这两个字方法对这两个字符进行编码，得到符进行编码，得到x、y的代码分别为的代码分别为0和和1。显然，对于概率较大的字符显然，对于概率较大的字符x不能给予较短的代码。不能给予较短的代码。这就是实际编码效果不能达到理论压缩比的原因所这就是实际编码效果不能达到理论压缩比的原因所在。在。4.5.3 算术编码算术编码 算术编码没有延用数据编码技术中用一个特定的代码代替一算术编码没有延用数据编码技术中用一个特定的代码代替一个输入符号的一般做法

36、，它把要压缩处理的整段数据映射到个输入符号的一般做法，它把要压缩处理的整段数据映射到一段实数半开区间一段实数半开区间0，1内的某一区段，构造出小于内的某一区段，构造出小于1且大于且大于或等于或等于0的数值。这个数值是输入数据流的唯一可译代码。的数值。这个数值是输入数据流的唯一可译代码。 算术编码把一个信源集合表示为实数轴上的算术编码把一个信源集合表示为实数轴上的0到到1之间的一个区间。信源集合中的每个元素都要用来缩之间的一个区间。信源集合中的每个元素都要用来缩短这个区间。信源集合的元素越多，所得到的区间就短这个区间。信源集合的元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这

37、个越小，当区间变小时，就需要更多的数位来表示这个区间，这就是区间作为代码的原理。算术编码首先假区间，这就是区间作为代码的原理。算术编码首先假设一个信源的概率模型，然后用这些概率来缩小表示设一个信源的概率模型，然后用这些概率来缩小表示信源集的区间。信源集的区间。 算术编码的编码方法算术编码的编码方法初始化子区间为初始化子区间为 0,1,预设一个大概率预设一个大概率 Pe 和小概率和小概率 Qe ,信源中的每个符号信源中的每个符号(0或或1)对应一个概率对应一个概率,然后对被编然后对被编码信源比特流符号码信源比特流符号(0或或1)依次进行判断。依次进行判断。QePe01设置两个专用寄存器设置两个专

38、用寄存器 C, A，存贮符号到来之前子存贮符号到来之前子区间的状态参数，令：区间的状态参数，令： C = 子区间的起始位置，子区间的起始位置， A = 子区间的宽度，子区间的宽度，初始化时，初始化时，C=0, A=1.随着被编码信源数据比特流符号随着被编码信源数据比特流符号0,1的输入，的输入，C和和A按以下方法进行修正：按以下方法进行修正：当低概率符号到来时，当低概率符号到来时， C C A A Qe 当高概率符号到来时，当高概率符号到来时， C C + A Qe A A Pe 新的子区间为新的子区间为C, C+A, , 以此类推，直到一以此类推，直到一组信源符号结束为止。算术编码的结果落在

39、最组信源符号结束为止。算术编码的结果落在最后的子区间之内，为子区间头、尾之间的取值。后的子区间之内，为子区间头、尾之间的取值。 题题 己知信源己知信源 X = 试对试对 1011 进行算术编码。进行算术编码。0 11/4 3/4 解 (1) 对二进制信源只有两个符号“0” 和“1”，设置小概率Qe =1/4，大概率 Pe = 1 Qe = 3/4. (2) 设 C 为子区间的左端起始位置，A 为子区间的宽度，符号“0”的子区间为0,1/4), 符号“1”的子区间为1/4, 1)(3) 初始子区间为初始子区间为0, 1), C=0, A=1,子区间按以子区间按以下各步依次缩小：下各步依次缩小：步

40、序步序 符号符号 C A1 1 0+1*1/4=1/4 1*3/4=3/4 2 0 1/4 3/4*1/4=3/163 1 1/4+3/16*1/4=19/64 3/16*3/4=9/644 1 19/64+9/64*1/4=85/256 9/64*3/4=27/25601/4119/6485/25610117/16112/256最后的子区间左端最后的子区间左端(起始位置起始位置) C = ( 85/256)d = (0.01010101)b最后的子区间右端最后的子区间右端(终止位置终止位置) C+A = (112/256) d = (0.01110000) b 编码结果为子区间头、尾之间取值

41、，其值为编码结果为子区间头、尾之间取值，其值为0.011, 可编码为可编码为011，原来，原来4个符号个符号1011现被压缩现被压缩为三个符号为三个符号011。 解码 解码时，是编码的逆过程。解码时，是编码的逆过程。 首先将区间首先将区间 0 , 1) 按按 Qe 靠近靠近 0 侧、侧、 Pe 靠近靠近 1 侧分割成两个子区间，判断被解码的码字落侧分割成两个子区间，判断被解码的码字落在哪个子区间，赋以对应符号，然后调整子区在哪个子区间，赋以对应符号，然后调整子区间间 C, A 的值。的值。 按此法多次重复，便可依次得到串中各符号。按此法多次重复，便可依次得到串中各符号。4.5.4游程编码游程编

42、码 游程编码游程编码(RLC)是一种利用空间冗余度压缩图像的方是一种利用空间冗余度压缩图像的方法法 ，属于统计编码类，属于统计编码类 。 设图像中的某一行或某一块像素经采样或经某种变换设图像中的某一行或某一块像素经采样或经某种变换后的系数为后的系数为 ： 某一行或某一块内像素值某一行或某一块内像素值可分为可分为k段，长度为段，长度为 的连续串，每个串具有相同的值，的连续串，每个串具有相同的值，那么，该图像的某一行或某一块可由下面偶对那么，该图像的某一行或某一块可由下面偶对 来表示来表示： 其中其中 为每个串内的代表值，为每个串内的代表值， 为串的长度。串长就是为串的长度。串长就是游程长度游程长

43、度(Runlength)，简写为，简写为RL，即由灰度值构成，即由灰度值构成的数据流中各灰度值重复出现而形成的长度。如果给的数据流中各灰度值重复出现而形成的长度。如果给出了灰度值、对应长度及位置，就能很容易地恢复出出了灰度值、对应长度及位置，就能很容易地恢复出原来的数据流。原来的数据流。 12( ,)Mxxx121122( ,)(,),(,),(,)Mkkxxxglglgligil(,),1iiglik ilRL的基本结构的基本结构 游程编码分为定长游程编码和变长游程编码两类。游程编码分为定长游程编码和变长游程编码两类。v定长游程编码是指编码的游程所使用位数是固定的，即定长游程编码是指编码的游

44、程所使用位数是固定的，即RL位数是固定的。如果灰度连续相同的个数超过了固定位数所位数是固定的。如果灰度连续相同的个数超过了固定位数所能表示的最大值，则进入下一轮游程编码。能表示的最大值，则进入下一轮游程编码。变长游程编码是指对不同范围的游程使用不同位数的编码，变长游程编码是指对不同范围的游程使用不同位数的编码，即表示即表示RL位数是不固定的。位数是不固定的。X SC RL串字符串位置串长游程编码一般不直接应用于多灰度图像，但比较适合游程编码一般不直接应用于多灰度图像，但比较适合 于二于二值图像的编码。值图像的编码。 为了达到较好的压缩效果，有时游程编码和其他一些编码方为了达到较好的压缩效果，有

45、时游程编码和其他一些编码方法混合使用。法混合使用。RLC比较适合二值图像数据序列，其原因是在比较适合二值图像数据序列，其原因是在二值序列中，只有二值序列中，只有“0”和和“1”两种符号；这些符号的连续出两种符号；这些符号的连续出现，就形成了现，就形成了“0”游程：游程：L(0)，“1”游程：游程：L(1)。 定义了游程和游程长度之后，就可以把任何二元序列变换成定义了游程和游程长度之后，就可以把任何二元序列变换成游程长度的序列，简称游程序列。这一变换是可逆的，一一游程长度的序列，简称游程序列。这一变换是可逆的，一一对应的。对应的。 4.5.5 无损预测编码无损预测编码 一幅二维静止图像，设空间坐

46、标一幅二维静止图像，设空间坐标(i，j)像素点的实际灰度为像素点的实际灰度为f(i,j)， 是根据以前已出现的像素点的灰度对该点的预测灰是根据以前已出现的像素点的灰度对该点的预测灰度，也称预测值或估计值，计算预测值的像素，可以是同一度，也称预测值或估计值，计算预测值的像素，可以是同一扫描行的前几个像素，或者是前几行上的像素，甚至是前几扫描行的前几个像素，或者是前几行上的像素，甚至是前几帧的邻近像素。实际值和预测值之间的差值，以下式表示：帧的邻近像素。实际值和预测值之间的差值，以下式表示： ),(jif),(),(),(jifjifjie（4-13） 由图像的统计特性可知，相邻像素之间有着较强的

47、相由图像的统计特性可知，相邻像素之间有着较强的相关性。因此，其像素的值可根据以前已知的几个像素关性。因此，其像素的值可根据以前已知的几个像素来估计，即预测。来估计，即预测。 预测编码是根据某一模型，利用以往的样本值对于新预测编码是根据某一模型，利用以往的样本值对于新样本值进行预测，然后将样本的实际值与其预测值相样本值进行预测，然后将样本的实际值与其预测值相减得到一个误差值，对于这一误差值进行编码。减得到一个误差值，对于这一误差值进行编码。 如果模型足够好且样本序列在时间上相关性较强，那如果模型足够好且样本序列在时间上相关性较强，那么误差信号的幅度将远远小于原始信号。么误差信号的幅度将远远小于原

48、始信号。 对差值信号不进行量化而直接编码就称之为无损预测对差值信号不进行量化而直接编码就称之为无损预测编码。编码。 无损预测编码器的工作原理图无损预测编码器的工作原理图 如下：如下：预测器源图像熵编码器编码表压缩源图像 由先前三点预测可以定义为：由先前三点预测可以定义为： 其中其中a1，a2, a3称预测系数，都是待定参数。如果预测称预测系数，都是待定参数。如果预测器中预测系数是固定不变的常数，称之为线性预测。器中预测系数是固定不变的常数，称之为线性预测。 预测误差：预测误差： ),(jif), 1() 1, 1() 1,(),(321jifajifajifajif),(),(),(jifji

49、fjie), 1() 1, 1() 1,(),(321jifajifajifajif（4-14） （4-15） 设设a=f(i,j-1)，b=f(i-1,j), c=f(i-1,j-1)， 的预测方法如的预测方法如右图所示，可有右图所示，可有8种选择方法：种选择方法： ),(jif选择方法预测值0非预测1acb 2b ax3c4a+b-c5a+(b-c)/26B+(a-c)/27 (a+b)/2),(yxf例：设有一幅图像，例：设有一幅图像，f(i-1,j-1),f(i-1,j), f(i,j-1), f(i,j)的灰度值的灰度值分别为分别为253,252,253,255，用图，用图4-8第四

50、种选择方法预测第四种选择方法预测f(i,j)的灰度值，并计算预测误差。的灰度值，并计算预测误差。 解：解： =a+b-c= f(i,j-1)+ f(i-1,j)- f(i-1,j-1)=252+253-253=252 预测误差预测误差 =255-252=3显然，预测误差显然，预测误差e(i,j)=3比像素的实际值比像素的实际值f(i,j)=255小的小的多，对多，对2进行编码比对进行编码比对255直接编码将占用更少的比特直接编码将占用更少的比特位。位。 ),(jif),(),(),(jifjifjie4.6有损压缩有损压缩 有损编码是以丢失部分信息为代价来换取高压缩比。有损编码是以丢失部分信息

51、为代价来换取高压缩比。 有损压缩方法主要有有损预测编码方法、变换编码方有损压缩方法主要有有损预测编码方法、变换编码方法等。法等。4.6.1有损预测编码有损预测编码 在预测编码中，对差值信号进行量化后再进行编码就在预测编码中，对差值信号进行量化后再进行编码就称之为有损预测编码。称之为有损预测编码。 有 损 预 测 方 法 有 多 种 ， 其 中 差 分 脉 冲 编 码 调 制有 损 预 测 方 法 有 多 种 ， 其 中 差 分 脉 冲 编 码 调 制(Differential Pulse Code Modulation，简称，简称DPCM)，是，是一种具有代表性的编码方法。一种具有代表性的编码

52、方法。 DPCM系统由编码器和解码器组成，它们各有一个相系统由编码器和解码器组成，它们各有一个相同的预测器。同的预测器。DPCM系统的工作原理如下图所示系统的工作原理如下图所示:量化器编码器预测器信道传输解码器输入输出预测器( , )f i j( , )e i j( , )e i j( , )fi j( , )fi j( , )fi j( , )e i j( , )fi j 系统包括发送、接收和信道传输三个部分。发送端由系统包括发送、接收和信道传输三个部分。发送端由编码器、量化器、预测器和加减法器组成；接收端包编码器、量化器、预测器和加减法器组成；接收端包括解码器和预测器等；信道传送以虚线表示

53、。图中输括解码器和预测器等；信道传送以虚线表示。图中输入信号入信号f(i,j)是坐标是坐标(i,j) 处的像素的实际灰度值，处的像素的实际灰度值， 是由已出现先前相邻像素点的灰度值对该像素的预测是由已出现先前相邻像素点的灰度值对该像素的预测灰度值。灰度值。 e(i,j)是预测误差。是预测误差。 DPCM包含量化器，这时编码器对编码，量化器导致包含量化器，这时编码器对编码，量化器导致了不可逆的信息损失，这时接收端经解码恢复出的灰了不可逆的信息损失，这时接收端经解码恢复出的灰度信号不是真正的度信号不是真正的f(i,j)，而是重建信号。可见引入量，而是重建信号。可见引入量化器会引起一定程度的信息损失

54、，使图像质量受损。化器会引起一定程度的信息损失，使图像质量受损。但是可以利用人眼的视觉特性，丢失不易觉察的图像但是可以利用人眼的视觉特性，丢失不易觉察的图像信息，不会引起明显失真信息，不会引起明显失真 。),(jif4.6.2变换编码变换编码 变换编码不是直接对空域图像信号编码，而是首先将图变换编码不是直接对空域图像信号编码，而是首先将图像数据经过某种正交变换（如傅立叶变换（像数据经过某种正交变换（如傅立叶变换（DFT），离），离散余弦变换（散余弦变换（DCT），），K-L变换等等）另一个正交矢量变换等等）另一个正交矢量空间空间(称之为变换域称之为变换域)，产生一批变换系数，然后对这些变，产生

55、一批变换系数，然后对这些变换系数进行编码处理，从而达到压缩图像数据的目的。换系数进行编码处理，从而达到压缩图像数据的目的。 变换编码的原理变换编码的原理 如下图：如下图： 图像数据经过正交变换后，空域中的总能量在变换域图像数据经过正交变换后，空域中的总能量在变换域中得到保持，但像素之间的相关性下降，能量将会重中得到保持，但像素之间的相关性下降，能量将会重新分布，并集中在变换域中少数的变换系数上，因此，新分布，并集中在变换域中少数的变换系数上，因此，选择少数选择少数F(u,v)来重建图像就可以达到压缩数据的目来重建图像就可以达到压缩数据的目的，并且重建图像仅引入较小误差。的，并且重建图像仅引入较

56、小误差。 变换多采用正交函数为基础的变换。变换多采用正交函数为基础的变换。 f(x,y)重建f(x,y)图象正交变换样本选择量化编码F(u,v)( , )F u v( , )F u v( , )F u v 卡胡南卡胡南-列夫变换（列夫变换（K-L）对于对于N N的矩阵的矩阵T，有，有N个标量个标量i，i=1,2,N,能使能使|T-iI|=0 则则i叫做矩阵叫做矩阵T的特征值。另外，的特征值。另外，N个满足个满足 的向量的向量Vi叫做叫做T的特征向量，这些特征向量的特征向量，这些特征向量构成一个正交基集。构成一个正交基集。 设设X是一个是一个N 1的随机向量，也就是说，的随机向量，也就是说，X的

57、每个的每个分量都是分量都是xi随机变量。随机变量。X的均值（平均向量）可以由的均值（平均向量）可以由L个样本向量来估计向量个样本向量来估计向量Mx： iiiVTVLllxXLM11（4-32） Mx协方差矩阵可以由协方差矩阵可以由来估计。协方差矩阵是实对称的。对角元素是个随机来估计。协方差矩阵是实对称的。对角元素是个随机变量的方差，非对角元素是它们的协方差。变量的方差，非对角元素是它们的协方差。定义一个线性变换定义一个线性变换T，它可由任何，它可由任何X向量产生一个新向量产生一个新向量向量Y： 式中式中，T的各行是的各行是Mx的特征向量，即的特征向量，即T的行向量就是的行向量就是Mx的特征向量

58、。的特征向量。LlTllTllTxxMxMMXXLMXMXE11)()(xMXTY（4-33） （4-34） 变换得到的变换得到的Y是期望为零的随机向量。是期望为零的随机向量。Y的协方差矩的协方差矩阵可以由阵可以由X的协方差矩阵决定：的协方差矩阵决定： 因为因为T的各行是的各行是x的特征向量，故的特征向量，故y是一个对角阵，是一个对角阵，对角元素是的对角元素是的x特征值。因此特征值。因此 这些也是的这些也是的x特征值。特征值。 随机向量随机向量Y是由互不相关的随机变量组成的，因此线是由互不相关的随机变量组成的，因此线性变换性变换T起到了消除变量间的相关性的作用。起到了消除变量间的相关性的作用。

59、 TXYTTx1 1 0 00 0 N N （4-35） 特征向量变换是可逆的。特征向量变换是可逆的。 要实现对信号进行要实现对信号进行KL变换，首先要求出矢量变换，首先要求出矢量x的协的协方差矩阵方差矩阵x，再求协方差矩阵，再求协方差矩阵x的特征值的特征值i，然后，然后求求对应的对应的x的特征向量，再用的特征向量，再用x的特征向量构成正的特征向量构成正交矩阵交矩阵T。 例例 :若已知随机矢量若已知随机矢量x的协方差矩阵为的协方差矩阵为 求其正交矩阵求其正交矩阵T？ x x6 2 06 2 02 2 2 2 1 10 0 1 11 11) 按按 , 求求x的特征值的特征值i : 得得: 则可解

60、得则可解得: =6.854 =2 =0.146 2) 求求i对应的特征向量。将对应的特征向量。将1，2，3代入代入(4-31)中分中分别求得如下三个特征向量：别求得如下三个特征向量： = = =0|xI011012202600000001101220261231V2V3V0.9180.3920.0670.3330.6670.6670.2170.6340.742用用V1，V2，V3的转置向量作为正交矩阵的转置向量作为正交矩阵T的行向量，的行向量，那么，对于任一向量那么，对于任一向量X=(2，1，-0.1)的的K-L变换为变换为 :则则Y的协方差矩阵的协方差矩阵y为为: Y=TX=0.918 0.