第8章图像压缩1

《第8章图像压缩1》由会员分享，可在线阅读，更多相关《第8章图像压缩1（50页珍藏版）》请在金锄头文库上搜索。

1、 8.1 图像压缩基础图像压缩基础图像信息占据大量的存储容量图像信息占据大量的存储容量, ,所用传输信道也较宽所用传输信道也较宽. .一幅一幅512512512512像素，像素，8b/8b/像素的灰度图像占据像素的灰度图像占据256KB256KB的磁盘空间；的磁盘空间；一一幅幅512512512512像像素素，每每分分量量8b/8b/像像素素的的彩彩色色图图像像则则占占据据32563256768KB768KB的的磁盘空间；磁盘空间；如如果果以以每每秒秒2424帧帧传传送送此此彩彩色色图图像像，则则一一秒秒钟钟的的数数据据量量就就有有247682476818.5MB18.5MB，那么一张，那么一

2、张680MB680MB容量的容量的CDCDROMROM仅能存储仅能存储3030多秒的原始数据。多秒的原始数据。对图像数据的压缩必不可少。对图像数据的压缩必不可少。 8.1 图像压缩基础图像压缩基础相相同同数数量量的的信信息息可可以以用用不不同同数数量量的的数数据据表表示示. .图图像像压压缩缩指指减减少少表表示示给给定定信息量所需的数据量信息量所需的数据量. .数据冗余的量化数据冗余的量化:相对数据冗余：相对数据冗余：压缩率：压缩率： 在数字图像压缩中在数字图像压缩中,可以确定三种基本的数据冗余可以确定三种基本的数据冗余: 编码冗余、像素间冗余和心理视觉冗余编码冗余、像素间冗余和心理视觉冗余.

3、数据中存在信息冗余数据中存在信息冗余,就有可能对图像数据量进行压缩就有可能对图像数据量进行压缩,针对数据冗余的类针对数据冗余的类型不同型不同,可以有多种不同的数据压缩方法可以有多种不同的数据压缩方法.越大越大,压缩效果越好压缩效果越好8.1 图像压缩基础图像压缩基础编码冗余编码冗余: 图像灰度可用不同的编码表示图像灰度可用不同的编码表示8.1 图像压缩基础图像压缩基础例例8.1变长编码的例子变长编码的例子编码编码2编码编码18.1 图像压缩基础图像压缩基础图图8.1 用变长编码的数据压缩基本原理的图表表示用变长编码的数据压缩基本原理的图表表示8.1 图像压缩基础图像压缩基础图图8.2 两幅图像

4、和它们的灰度级直方图以及沿着某条线计算的归一化自相关系数两幅图像和它们的灰度级直方图以及沿着某条线计算的归一化自相关系数像素间冗余像素间冗余直方图直方图图像像素之间的相关性图像像素之间的相关性自相关系数自相关系数相邻像素之间具有相邻像素之间具有高度相关性高度相关性8.1 图像压缩基础图像压缩基础自相关系数的计算自相关系数的计算:另一种数据冗余形式另一种数据冗余形式: 因为任何给定像素的值可以根据与这些像素相邻的像素进行适当的预测因为任何给定像素的值可以根据与这些像素相邻的像素进行适当的预测,所以由单个像素携带的信息相对较少所以由单个像素携带的信息相对较少.单一像素对于一幅图像的多数视觉共享单一

5、像素对于一幅图像的多数视觉共享是多余的是多余的;它的值可以通过相邻像素进行推测它的值可以通过相邻像素进行推测.8.1 图像压缩基础图像压缩基础例例8.2行程编码的简单说明行程编码的简单说明(a)(b)(c)(d)(a)原图原图(b)标记了线标记了线100的二值图像的二值图像(c)线状剖面和二线状剖面和二值化门限值化门限(d)行程编码行程编码8.1 图像压缩基础图像压缩基础1024343个像素个像素,每个像素用每个像素用1个比特表示个比特表示12166个行程个行程,每个行程用每个行程用11比特表示比特表示8.1 图像压缩基础图像压缩基础心理视觉冗余：心理视觉冗余：在正常的视觉处理过程中在正常的视

6、觉处理过程中,各种信息的相对重要程度不同各种信息的相对重要程度不同.那些不重要的信息称那些不重要的信息称为心理视觉冗余为心理视觉冗余. 消除视觉冗余会导致一定量的信息丢失消除视觉冗余会导致一定量的信息丢失,这一过程常称为这一过程常称为”量化量化”例例8.3 通过量化进行压缩通过量化进行压缩(a)256个灰度级的原图像个灰度级的原图像(b)均匀量化为均匀量化为16个灰度级个灰度级(c)用用IGS量化为量化为16个灰度级个灰度级压缩比率为压缩比率为2出现假轮廓出现假轮廓8.1 图像压缩基础图像压缩基础心理视觉冗余：心理视觉冗余：IGS量化过程量化过程8.1 图像压缩基础图像压缩基础保真度准则：保真

7、度准则：图像的编码质量评价图像的编码质量评价定量分析丢失信息的性质和范围定量分析丢失信息的性质和范围, 包括包括(1) 客观保真度准则客观保真度准则 (2) 主观保真度准则主观保真度准则当信息损失的程度可以表示成初始图像或输入图像以及先被压缩而后被解压缩当信息损失的程度可以表示成初始图像或输入图像以及先被压缩而后被解压缩的输出图像的函数时的输出图像的函数时,就说这个函数是基于就说这个函数是基于客观保真度准则客观保真度准则的的.8.1 图像压缩基础图像压缩基础保真度准则：保真度准则：主观保真度准则主观保真度准则:8.2 图像压缩模型图像压缩模型信源信源编码编码信道信道编码编码信道信道信道信道解码

8、解码信源信源解码解码编码器编码器解码器解码器图图8.5 一个常用的图像压缩系统模型一个常用的图像压缩系统模型8.2 图像压缩模型图像压缩模型转换器转换器量化器量化器符号编码器符号编码器信道信道信道信道符号解码器符号解码器反向转换器反向转换器信源编码器信源编码器信源解码器信源解码器(a) 信源编码器信源编码器 (b) 信源解码器信源解码器信源编码器和信源解码器信源编码器和信源解码器8.2 图像压缩模型图像压缩模型信道编码器和解码器信道编码器和解码器如果找到一个非零值如果找到一个非零值,则解码器只需简单地在校验字指出的位置补充码字比特则解码器只需简单地在校验字指出的位置补充码字比特.解码的解码的二

9、进制二进制h3h5h6h7就能从纠正后的码字中提取出来就能从纠正后的码字中提取出来.信道带有噪声或易于出现错误信道带有噪声或易于出现错误,信道编码器和解信道编码器和解码器通过向信源编码数据中插入预制的冗余数码器通过向信源编码数据中插入预制的冗余数据来减少信道噪声的影响据来减少信道噪声的影响.设一个离散信源设一个离散信源设一个离散信源设一个离散信源X X X X：满足满足满足满足其概率分布：其概率分布：其概率分布：其概率分布：离散信源类型离散信源类型离散信源类型离散信源类型 无记忆信源无记忆信源 信源的当前输出与以前的输出无关信源的当前输出与以前的输出无关 有记忆信源有记忆信源 8.3 信息理论

10、基础与熵编码信息理论基础与熵编码信息理论是图像编码的主要理论依据之一信息理论是图像编码的主要理论依据之一,它给出无失真编码所需比特数的下限它给出无失真编码所需比特数的下限,为逼近这些下限提出了一系列熵编码算法为逼近这些下限提出了一系列熵编码算法.(1) 离散信源的熵表示离散信源的熵表示:一般分成两种情况来考虑一般分成两种情况来考虑:考虑无记忆信源考虑无记忆信源考虑无记忆信源考虑无记忆信源X X, , , ,某个信源符号某个信源符号某个信源符号某个信源符号x xk k, , , ,如果它出现的概率是如果它出现的概率是如果它出现的概率是如果它出现的概率是p pk k 信源熵信源熵信源熵信源熵H(X

11、)H(X) x xk k的自信息量的自信息量的自信息量的自信息量 8.3 信息理论基础与熵编码信息理论基础与熵编码直观地理解自信息量的概念直观地理解自信息量的概念: 一个概率小的符号出现将带来更大的信息量一个概率小的符号出现将带来更大的信息量.每个符号的平均自信息量每个符号的平均自信息量单位单位: 比特比特/符号符号设设设设信源熵信源熵信源熵信源熵 则则则则, , , ,各信源符号自信息量：各信源符号自信息量：各信源符号自信息量：各信源符号自信息量：例例例例 8.4 8.4 8.4 8.4 编编编编码码码码方方方方法法法法：a,b,c,da,b,c,d用用用用码码码码字字字字00,01,10,

12、1100,01,10,1100,01,10,1100,01,10,11来来来来编编编编码码码码, , , ,每每每每个个个个符符符符号号号号用用用用2 2 2 2个个个个比比比比特特特特. .平均码长也是平均码长也是平均码长也是平均码长也是2 2 2 2比特比特比特比特. . 8.3 信息理论基础与熵编码信息理论基础与熵编码设设设设信源熵信源熵信源熵信源熵 则则则则, , , ,各信源符号自信息量：各信源符号自信息量：各信源符号自信息量：各信源符号自信息量：例例例例8.58.58.58.5 8.3 信息理论基础与熵编码信息理论基础与熵编码 可以有两种编码方法：可以有两种编码方法：可以有两种编码

13、方法：可以有两种编码方法： 2 2、 a,b,c,da,b,c,d分别用码字分别用码字分别用码字分别用码字0,10,110,1110,10,110,1110,10,110,1110,10,110,111来编码来编码来编码来编码 1 1、a,b,c,da,b,c,d用码字用码字用码字用码字00,01,10,1100,01,10,1100,01,10,1100,01,10,11来编码来编码来编码来编码 平均码长：平均码长：平均码长：平均码长：平均码长大于信源的熵平均码长大于信源的熵平均码长大于信源的熵平均码长大于信源的熵 平均码长：平均码长：平均码长：平均码长： 平均码长等于信源的熵平均码长等于信

14、源的熵平均码长等于信源的熵平均码长等于信源的熵 8.3 信息理论基础与熵编码信息理论基础与熵编码设设设设信源熵信源熵信源熵信源熵 则则则则, , , ,各信源符号自信息量各信源符号自信息量各信源符号自信息量各信源符号自信息量：例例例例8.68.68.68.6 用例用例用例用例8.58.58.58.5第二种编码方法第二种编码方法第二种编码方法第二种编码方法 , , , ,平均码长为平均码长为平均码长为平均码长为1.85,1.85,1.85,1.85,大于信源熵大于信源熵大于信源熵大于信源熵 8.3 信息理论基础与熵编码信息理论基础与熵编码可得到几点提示可得到几点提示可得到几点提示可得到几点提示：

15、信源的平均码长信源的平均码长信源的平均码长信源的平均码长l lavgavg=H(X)=H(X)；也就是说熵是无失真编码的下界也就是说熵是无失真编码的下界也就是说熵是无失真编码的下界也就是说熵是无失真编码的下界. .如果所有如果所有如果所有如果所有I(xI(xk k) )都是整数都是整数都是整数都是整数, ,且且且且l(xl(xk k)=)=I(xI(xk k) ), , , ,可以使平均码长等于熵可以使平均码长等于熵可以使平均码长等于熵可以使平均码长等于熵. .对对对对非非非非等等等等概概概概率率率率分分分分布布布布的的的的信信信信源源源源, ,采采采采用用用用不不不不等等等等长长长长编编编编

16、码码码码其其其其平平平平均均均均码码码码长长长长小小小小于于于于等等等等长长长长编编编编码码码码的的的的平平平平均均均均码码码码长长长长. .如如如如果果果果信信信信源源源源中中中中各各各各符符符符号号号号的的的的出出出出现现现现概概概概率率率率相相相相等等等等, ,信信信信源源源源熵熵熵熵值值值值达达达达到到到到最最最最大大大大, ,这这这这就就就就是是是是重重重重要要要要的的的的最最最最大大大大离离离离散散散散熵定理熵定理熵定理熵定理. .例例例例: : : :对对对对于于于于二二二二元元元元信信信信源源源源X=a,b,N=2,X=a,b,N=2,X=a,b,N=2,X=a,b,N=2,符

17、符符符号号号号a a a a出出出出现现现现的的的的概概概概率率率率为为为为p,p,p,p,那那那那么么么么符符符符号号号号b b b b出出出出现现现现的的的的概概概概率率率率为为为为1-1-1-1-p,p,p,p,其熵为其熵为其熵为其熵为H(p)=-p*logH(p)=-p*logH(p)=-p*logH(p)=-p*log2 2 2 2(p)+(1-p)*log(p)+(1-p)*log(p)+(1-p)*log(p)+(1-p)*log2 2 2 2(1-p).(1-p).(1-p).(1-p). 当当当当p=1/N=0.5p=1/N=0.5p=1/N=0.5p=1/N=0.5时时时时

18、,H(p)=1,H(p)=1,H(p)=1,H(p)=1,取得最大值取得最大值取得最大值取得最大值 当当当当p=0p=0p=0p=0或或或或p=1p=1p=1p=1时时时时,H(p)=0,H(p)=0,H(p)=0,H(p)=0,即是确定性事件集即是确定性事件集即是确定性事件集即是确定性事件集. . . . 离离离离散散散散无无无无计计计计机机机机信信信信源源源源的的的的冗冗冗冗余余余余度度度度寓寓寓寓于于于于信信信信源源源源符符符符号号号号的的的的非非非非等等等等概概概概率率率率分分分分布布布布之之之之中中中中, , , ,因因因因此此此此, , , ,要要要要想想想想压压压压缩缩缩缩数据数

19、据数据数据, , , ,就要设法改变信源的概率分布就要设法改变信源的概率分布就要设法改变信源的概率分布就要设法改变信源的概率分布, , , ,使其尽可能非均匀使其尽可能非均匀使其尽可能非均匀使其尽可能非均匀. . . .8.3 信息理论基础与熵编码信息理论基础与熵编码考虑有记忆信源考虑有记忆信源考虑有记忆信源考虑有记忆信源X X（1 1 1 1阶马尔可夫信源阶马尔可夫信源阶马尔可夫信源阶马尔可夫信源 ）1 1 1 1阶熵阶熵阶熵阶熵 条件概率条件概率条件概率条件概率 联合概率联合概率联合概率联合概率 8.3 信息理论基础与熵编码信息理论基础与熵编码若把信息论中的熵值应用到图像信息源中若把信息论

20、中的熵值应用到图像信息源中,若图像的灰度级为若图像的灰度级为0,L-1,则可以则可以通过直方图得到各灰度级概率通过直方图得到各灰度级概率ps(sk),那么此时图像的熵为那么此时图像的熵为:对对对对mm阶马尔可夫信源阶马尔可夫信源阶马尔可夫信源阶马尔可夫信源, ,可以证明：可以证明：可以证明：可以证明：结结结结论论论论：对对对对于于于于有有有有记记记记忆忆忆忆信信信信源源源源, , , ,如如如如果果果果符符符符号号号号序序序序列列列列中中中中前前前前面面面面的的的的符符符符号号号号知知知知道道道道得越多得越多得越多得越多, , , ,那么下一个符号的平均信息量就越小那么下一个符号的平均信息量就

21、越小那么下一个符号的平均信息量就越小那么下一个符号的平均信息量就越小 8.3 信息理论基础与熵编码信息理论基础与熵编码1)1)香农信息保持编码定理香农信息保持编码定理 w香香农农信信息息论论已已证证明明, ,信信源源熵熵是是进进行行无无失失真真编编码码的的理理论论极极限限. .低低于于此此极极限限的的无无失失真真编编码码方方法法是是不不存存在在的的, ,这这是是熵熵编编码码的的理理论论基基础础. .而而且且可可以以证证明明, ,考考虑虑像像素素间间的的相相关关性性, ,使使用用高高阶阶熵熵一一定定可可以以获获得得更更高高的的压缩比压缩比. . 2)2)变长编码定理变长编码定理 n变变长长编编码

22、码定定义义：对对于于一一个个无无记记忆忆离离散散信信源源中中每每一一个个符符号号, ,若若采采用用相相同同长长度度的的不不同同码码字字代代表表相相应应符符号号, ,就就叫叫做做等等长长编编码码, ,例例如如中中国国4 4位位电电报报码码. .若若对对信信源源中中的的不不同同符符号号, ,用用不不同同长长度度的的码码字字表表示示就就叫叫做做不等长不等长或或变长编码变长编码. .n与与定定长长编编码码相相比比, ,变变长长编编码码更更复复杂杂, ,除除唯唯一一可可译译码码（也也称称为为单单义义可可译）的要求译）的要求, ,还存在即时解码问题还存在即时解码问题. .8.3 信息理论基础与熵编码信息理

23、论基础与熵编码变长编码定理：变长编码定理：若一个离散无记忆信源具有熵若一个离散无记忆信源具有熵H(X),H(X),并有并有r r个码元符个码元符号集号集, ,则总可以找到一种无失真信源编码则总可以找到一种无失真信源编码, ,构成单义可译码构成单义可译码, ,使其使其平均码长满足：平均码长满足：当当当当r=2r=28.3 信息理论基础与熵编码信息理论基础与熵编码例例编码编码A是可以即时解码的是可以即时解码的,而编码而编码B是有惟一解码的是有惟一解码的,却不是即时的却不是即时的.如收到码串如收到码串01,要等下一个比特到来要等下一个比特到来.给定一个无记忆离散信源给定一个无记忆离散信源,意味着其统

24、计特性已知意味着其统计特性已知,则则信源的熵已确定信源的熵已确定,那么那么,信信源的单义可译码长源的单义可译码长L的下界的下界也就随之确定了也就随之确定了.3)3)3)3)变长最佳编码定理变长最佳编码定理变长最佳编码定理变长最佳编码定理w w在在在在变变变变长长长长编编编编码码码码中中中中, , , ,对对对对出出出出现现现现概概概概率率率率大大大大的的的的信信信信息息息息符符符符号号号号赋赋赋赋予予予予短短短短码码码码字字字字, , , ,而而而而对对对对于于于于出出出出现现现现概概概概率率率率小小小小的的的的信信信信息息息息符符符符号号号号赋赋赋赋予予予予长长长长码码码码字字字字. . .

25、 .如如如如果果果果码码码码字字字字长长长长度度度度严严严严格格格格按按按按照照照照所所所所对对对对应应应应符符符符号号号号出出出出现现现现概概概概率率率率大大大大小小小小逆逆逆逆序序序序排排排排列列列列, , , ,则则则则编编编编码码码码结结结结果果果果平平平平均均均均码码码码字字字字长长长长度度度度一一一一定定定定小于任何其他排列形式小于任何其他排列形式小于任何其他排列形式小于任何其他排列形式. . . .8.3 信息理论基础与熵编码信息理论基础与熵编码1 1 1 1霍夫曼编码霍夫曼编码霍夫曼编码霍夫曼编码8.4 无误差压缩无误差压缩根据变长最佳编码定理根据变长最佳编码定理,Huffma

26、nHuffman编码编码步骤如下：步骤如下：（1 1）将信源符号将信源符号将信源符号将信源符号x xi i按其出现的概率按其出现的概率按其出现的概率按其出现的概率, , , ,由大到小顺序排列由大到小顺序排列由大到小顺序排列由大到小顺序排列. . . .（2 2 2 2）将将将将两两两两个个个个最最最最小小小小的的的的概概概概率率率率的的的的信信信信源源源源符符符符号号号号进进进进行行行行组组组组合合合合相相相相加加加加, , , ,并并并并重重重重复复复复这这这这一一一一步步步步骤骤骤骤, , , ,始始始始终终终终将将将将较较较较大大大大的的的的概概概概率率率率分分分分支支支支放放放放在在

27、在在上上上上部部部部, , , ,直直直直到到到到只只只只剩剩剩剩下下下下一一一一个个个个信信信信源源源源符符符符号号号号且且且且概概概概率率率率达达达达到到到到1.01.01.01.0为止；为止；为止；为止；（3 3 3 3）对对对对每每每每对对对对组组组组合合合合的的的的上上上上边边边边一一一一个个个个指指指指定定定定为为为为1,1,1,1,下下下下边边边边一一一一个个个个指指指指定定定定为为为为0 0 0 0（或或或或相相相相反反反反：对对对对上上上上边一个指定为边一个指定为边一个指定为边一个指定为0,0,0,0,下边一个指定为下边一个指定为下边一个指定为下边一个指定为1 1 1 1）；

28、）；）；）；（4 4 4 4）画出由每个信源符号到概率）画出由每个信源符号到概率）画出由每个信源符号到概率）画出由每个信源符号到概率1.01.01.01.0处的路径处的路径处的路径处的路径, , , ,记下沿路径的记下沿路径的记下沿路径的记下沿路径的1 1 1 1和和和和0 0 0 0；（5 5 5 5）对对对对于于于于每每每每个个个个信信信信源源源源符符符符号号号号都都都都写写写写出出出出1 1 1 1、0 0 0 0序序序序列列列列, , , ,则则则则从从从从右右右右到到到到左左左左就就就就得得得得到到到到非非非非等等等等长长长长的的的的 HuffmanHuffmanHuffmanHuf

29、fman码码码码. . . .w一一幅幅20202020的的图图像像共共有有5 5个个灰灰度度级级：s1,s2,s3,s4,s1,s2,s3,s4,和和 s5s5，它们的概率依次为它们的概率依次为0.4,0.175,0.15,0.150.4,0.175,0.15,0.15和和 0.1250.125。例例例例8.78.78.78.7HuffmanHuffmanHuffmanHuffman编码过程示意图编码过程示意图编码过程示意图编码过程示意图8.4 无误差压缩无误差压缩编码结果编码结果编码结果编码结果 图像熵图像熵图像熵图像熵 信源符号信源符号信源符号信源符号出现概率出现概率出现概率出现概率码字

30、码字码字码字码长码长码长码长s10.401S20.1751113S30.151103S40.151013S50.1251003编码编码后均后均后均后均码长码长 8.4 无误差压缩无误差压缩HuffmanHuffmanHuffmanHuffman编码的特点是：编码的特点是：编码的特点是：编码的特点是：（1 1 1 1）HuffmanHuffmanHuffmanHuffman编编编编码码码码构构构构造造造造程程程程序序序序是是是是明明明明确确确确的的的的，但但但但编编编编出出出出的的的的码码码码不不不不是是是是唯唯唯唯一一一一的的的的，其其其其原原原原因因因因之之之之一一一一是是是是两两两两个个个

31、个概概概概率率率率分分分分配配配配码码码码字字字字“0”“0”“0”“0”和和和和“1”“1”“1”“1”是是是是任任任任意意意意选选选选择择择择的的的的（大大大大概概概概率率率率为为为为“0”“0”“0”“0”，小小小小概概概概率率率率为为为为“1”“1”“1”“1”，或或或或者者者者反反反反之之之之）。第第第第二二二二原原原原因因因因是是是是在在在在排排排排序序序序过过过过程程程程中中中中两两两两个个个个概概概概率率率率相相相相等等等等，谁谁谁谁前前前前谁谁谁谁后后后后也也也也是是是是随随随随机机机机的的的的。这这这这样样样样编编编编出出出出的的的的码码码码字字字字就就就就不不不不是是是是

32、唯唯唯唯一一一一的。的。的。的。（2 2 2 2）HuffmanHuffmanHuffmanHuffman编编编编码码码码结结结结果果果果，码码码码字字字字不不不不等等等等长长长长，平平平平均均均均码码码码字字字字最最最最短短短短，效效效效率率率率最最最最高高高高，但但但但码码码码字字字字长长长长短短短短不不不不一一一一，实实实实时时时时硬硬硬硬件件件件实实实实现现现现很很很很复复复复杂杂杂杂（特特特特别别别别是是是是译译译译码码码码），而而而而且且且且在在在在抗抗抗抗误码能力方面也比较差。误码能力方面也比较差。误码能力方面也比较差。误码能力方面也比较差。（3 3 3 3）HuffmanHuf

33、fmanHuffmanHuffman编码的信源概率是编码的信源概率是编码的信源概率是编码的信源概率是2 2 2 2的负幂时，效率达的负幂时，效率达的负幂时，效率达的负幂时，效率达100%100%100%100%，但是对等，但是对等，但是对等，但是对等概率分布的信源，产生定长码，效率最低，因此编码效率与信源符概率分布的信源，产生定长码，效率最低，因此编码效率与信源符概率分布的信源，产生定长码，效率最低，因此编码效率与信源符概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故号概率分布相关，故号概率分布相关，故号概率分布相关，故HuffmanHuffmanHuffmanHu

34、ffman编码依赖于信源统计特性，编码前必须编码依赖于信源统计特性，编码前必须编码依赖于信源统计特性，编码前必须编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了哈夫曼编码的应用。有信源这方面的先验知识，这往往限制了哈夫曼编码的应用。有信源这方面的先验知识，这往往限制了哈夫曼编码的应用。有信源这方面的先验知识，这往往限制了哈夫曼编码的应用。（4 4 4 4）HuffmanHuffmanHuffmanHuffman编码只能用近似的整数位来表示单个符号，而不是理编码只能用近似的整数位来表示单个符号，而不是理编码只能用近似的整数位来表示单个符号，而不是理编码只能用近似的整数位来表

35、示单个符号，而不是理想的小数，这也是想的小数，这也是想的小数，这也是想的小数，这也是HuffmanHuffmanHuffmanHuffman编码无法达到最理想的压缩效果的原因。编码无法达到最理想的压缩效果的原因。编码无法达到最理想的压缩效果的原因。编码无法达到最理想的压缩效果的原因。8.4 无误差压缩无误差压缩 算术编码不是将单个信源符号映射成一个码字，而是把整个信源表算术编码不是将单个信源符号映射成一个码字，而是把整个信源表算术编码不是将单个信源符号映射成一个码字，而是把整个信源表算术编码不是将单个信源符号映射成一个码字，而是把整个信源表示为实数线上的示为实数线上的示为实数线上的示为实数线上

36、的0 0 0 0到到到到1 1 1 1之间的一个区间（之间的一个区间（之间的一个区间（之间的一个区间（IntervalIntervalIntervalInterval），其长度等于该序列），其长度等于该序列），其长度等于该序列），其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要缩短为一个区间。消息序列中的编码输出。消息序列中的每个元素都要缩短为一

37、个区间。消息序列中的编码输出。消息序列中的每个元素都要缩短为一个区间。消息序列中的编码输出。消息序列中的每个元素都要缩短为一个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。表示这个区间。采用算术编码每个

38、符号的平均编码长度可以为小数。2.算术编码算术编码8.4 无误差压缩无误差压缩假设信源符号为假设信源符号为假设信源符号为假设信源符号为00,01,10,11,00,01,10,11,00,01,10,11,00,01,10,11,这些符号的概率分别为这些符号的概率分别为这些符号的概率分别为这些符号的概率分别为 0.1,0.4, 0.1,0.4, 0.1,0.4, 0.1,0.4, 0.2,0.3,0.2,0.3,0.2,0.3,0.2,0.3,根据这些概率可把间隔根据这些概率可把间隔根据这些概率可把间隔根据这些概率可把间隔0,1)0,1)0,1)0,1)分成分成分成分成4 4 4 4个子间隔：

39、个子间隔：个子间隔：个子间隔：0,0.1), 0,0.1), 0,0.1), 0,0.1), 0.1,0.5), 0.5,0.7), 0.7, 1).0.1,0.5), 0.5,0.7), 0.7, 1).0.1,0.5), 0.5,0.7), 0.7, 1).0.1,0.5), 0.5,0.7), 0.7, 1).符号符号 00 01 10 11 00 01 10 11 概率概率 0.1 0.4 0.2 0.3 0.1 0.4 0.2 0.3 初始编码间隔初始编码间隔 0, 0.1) 0.1, 0.5) 0.5, 0.7) 0.7, 1)0, 0.1) 0.1, 0.5) 0.5, 0.7)

40、 0.7, 1) 如果二进制消息序列的输入为：如果二进制消息序列的输入为：如果二进制消息序列的输入为：如果二进制消息序列的输入为：10 00 11 00 10 11 01.10 00 11 00 10 11 01.10 00 11 00 10 11 01.10 00 11 00 10 11 01.例例例例8.8 8.8 8.4 无误差压缩无误差压缩步骤步骤步骤步骤 输入输入输入输入 符号编码间隔符号编码间隔符号编码间隔符号编码间隔 编码判决编码判决编码判决编码判决1 10 0.5, 0.7) 1 10 0.5, 0.7) 1 10 0.5, 0.7) 1 10 0.5, 0.7) 符号的间隔范

41、围符号的间隔范围符号的间隔范围符号的间隔范围0.5, 0.7) 0.5, 0.7) 0.5, 0.7) 0.5, 0.7) 2 00 0.5, 0.52) 0.5, 0.7)2 00 0.5, 0.52) 0.5, 0.7)2 00 0.5, 0.52) 0.5, 0.7)2 00 0.5, 0.52) 0.5, 0.7)间隔的第一个间隔的第一个间隔的第一个间隔的第一个1/101/101/101/103 11 0.514, 0.52) 0.5, 0.52)3 11 0.514, 0.52) 0.5, 0.52)3 11 0.514, 0.52) 0.5, 0.52)3 11 0.514, 0.

42、52) 0.5, 0.52)间隔的最后间隔的最后间隔的最后间隔的最后3 3 3 3个个个个1/101/101/101/104 00 0.514, 0.5146) 0.514, 0.52)4 00 0.514, 0.5146) 0.514, 0.52)4 00 0.514, 0.5146) 0.514, 0.52)4 00 0.514, 0.5146) 0.514, 0.52)间隔的第一个间隔的第一个间隔的第一个间隔的第一个1/101/101/101/105 10 0.5143, 0.51442) 0.514, 0.5146)5 10 0.5143, 0.51442) 0.514, 0.5146

43、)5 10 0.5143, 0.51442) 0.514, 0.5146)5 10 0.5143, 0.51442) 0.514, 0.5146)间隔的第五个间隔的第五个间隔的第五个间隔的第五个1/101/101/101/10开始，开始，开始，开始， 二个二个二个二个1/101/101/101/106 11 0.514384, 0.51442) 0.5143, 0.51442)6 11 0.514384, 0.51442) 0.5143, 0.51442)6 11 0.514384, 0.51442) 0.5143, 0.51442)6 11 0.514384, 0.51442) 0.5143

44、, 0.51442)间隔的最后间隔的最后间隔的最后间隔的最后3 3 3 3个个个个1/101/101/101/107 01 0.5143836, 0.514402)0.514384, 0.51442)7 01 0.5143836, 0.514402)0.514384, 0.51442)7 01 0.5143836, 0.514402)0.514384, 0.51442)7 01 0.5143836, 0.514402)0.514384, 0.51442)间隔的间隔的间隔的间隔的4 4 4 4个个个个1/101/101/101/10， 从第从第从第从第1 1 1 1个个个个1/101/101/1

45、01/10开始开始开始开始8 8 8 8 从从从从0.5143876, 0.5144020.5143876, 0.5144020.5143876, 0.5144020.5143876, 0.514402中选择一个数作为输出：中选择一个数作为输出：中选择一个数作为输出：中选择一个数作为输出：0.51438760.51438760.51438760.5143876算术编码过程算术编码过程算术编码过程算术编码过程 8.4 无误差压缩无误差压缩low = low+range * range_low range和和low为上一个被编码符号的范围和低端值为上一个被编码符号的范围和低端值;high = lo

46、w + range * range_high rang_low 和和range_high为被编码符号已给定的出为被编码符号已给定的出 现概率范围的低端值和高端值现概率范围的低端值和高端值.算术编码过程示意图算术编码过程示意图算术编码过程示意图算术编码过程示意图 8.4 无误差压缩无误差压缩算术编码解码过程算术编码解码过程算术编码解码过程算术编码解码过程 步骤步骤步骤步骤 间隔间隔间隔间隔 译码符号译码符号译码符号译码符号 译码判决译码判决译码判决译码判决 1 0.5, 0.7) 10 0.514391 0.5, 0.7) 10 0.514391 0.5, 0.7) 10 0.514391 0.

47、5, 0.7) 10 0.51439在间隔在间隔在间隔在间隔 0.5, 0.7)0.5, 0.7)0.5, 0.7)0.5, 0.7)2 0.5, 0.52) 00 0.514392 0.5, 0.52) 00 0.514392 0.5, 0.52) 00 0.514392 0.5, 0.52) 00 0.51439在间隔在间隔在间隔在间隔 0.5, 0.7)0.5, 0.7)0.5, 0.7)0.5, 0.7)的第的第的第的第1 1 1 1个个个个1/101/101/101/103 0.514, 0.52) 11 0.514393 0.514, 0.52) 11 0.514393 0.514

48、, 0.52) 11 0.514393 0.514, 0.52) 11 0.51439在间隔在间隔在间隔在间隔0.5, 0.52)0.5, 0.52)0.5, 0.52)0.5, 0.52)的第的第的第的第7 7 7 7个个个个1/101/101/101/104 0.514, 0.5146) 00 0.514394 0.514, 0.5146) 00 0.514394 0.514, 0.5146) 00 0.514394 0.514, 0.5146) 00 0.51439在间隔在间隔在间隔在间隔0.514, 0.52)0.514, 0.52)0.514, 0.52)0.514, 0.52)的第

49、的第的第的第1 1 1 1个个个个1/101/101/101/105 0.5143, 0.51442) 10 0.514395 0.5143, 0.51442) 10 0.514395 0.5143, 0.51442) 10 0.514395 0.5143, 0.51442) 10 0.51439在间隔在间隔在间隔在间隔0.514, 0.5146)0.514, 0.5146)0.514, 0.5146)0.514, 0.5146)的第的第的第的第5 5 5 5个个个个1/101/101/101/106 0.514384, 0.51442) 11 0.514396 0.514384, 0.514

50、42) 11 0.514396 0.514384, 0.51442) 11 0.514396 0.514384, 0.51442) 11 0.51439在间隔在间隔在间隔在间隔0.5143, 0.51442)0.5143, 0.51442)0.5143, 0.51442)0.5143, 0.51442)的第的第的第的第7 7 7 7个个个个1/101/101/101/107 7 7 70.51439, 0.5143948) 01 0.514390.51439, 0.5143948) 01 0.514390.51439, 0.5143948) 01 0.514390.51439, 0.51439

51、48) 01 0.51439在间隔在间隔在间隔在间隔0.514384, 0.51442)0.514384, 0.51442)0.514384, 0.51442)0.514384, 0.51442)的第的第的第的第1 1 1 1个个个个 1/101/101/101/108 8 8 8 解码后消息序列：解码后消息序列：解码后消息序列：解码后消息序列：10 00 11 00 10 11 0110 00 11 00 10 11 0110 00 11 00 10 11 0110 00 11 00 10 11 018.4 无误差压缩无误差压缩首先计算首先计算valuek+1 = (valuek range

52、_lowk ) /rangek然后判断然后判断valuek+1 位于哪个范围位于哪个范围,则得到对应编码则得到对应编码.译码判决方法译码判决方法:算术编码的特点算术编码的特点算术编码的特点算术编码的特点: : : : 1. 1. 1. 1. 实际的计算机精度有限实际的计算机精度有限实际的计算机精度有限实际的计算机精度有限, , , ,会产生溢出问题会产生溢出问题会产生溢出问题会产生溢出问题; ; ; ; 2. 2. 2. 2. 对整个消息只产生一个编码对整个消息只产生一个编码对整个消息只产生一个编码对整个消息只产生一个编码, , , ,因此译码器必须接受到这个实数后因此译码器必须接受到这个实数

53、后因此译码器必须接受到这个实数后因此译码器必须接受到这个实数后 才能译码才能译码才能译码才能译码; ; ; ; 3. 3. 3. 3. 对错误很敏感对错误很敏感对错误很敏感对错误很敏感. . . .8.4 无误差压缩无误差压缩n n行行行行程程程程编编编编码码码码（Run Run Run Run Length Length Length Length EncodingEncodingEncodingEncoding）是是是是一一一一种种种种利利利利用用用用空空空空间间间间冗冗冗冗余余余余度度度度压压压压缩缩缩缩图图图图像像像像的的的的方方方方法法法法，对对对对某某某某些些些些相相相相同同同同灰

54、灰灰灰度度度度级级级级成成成成片片片片连连连连续续续续出出出出现现现现的的的的图图图图形形形形，行行行行程程程程编编编编码码码码也也也也是是是是一一一一种高效的编码方法。特别是对二值图像，效果尤为显著。种高效的编码方法。特别是对二值图像，效果尤为显著。种高效的编码方法。特别是对二值图像，效果尤为显著。种高效的编码方法。特别是对二值图像，效果尤为显著。n n具有相同灰度值并且是连续的像素数目称为行程长度。具有相同灰度值并且是连续的像素数目称为行程长度。具有相同灰度值并且是连续的像素数目称为行程长度。具有相同灰度值并且是连续的像素数目称为行程长度。3. 行程编码行程编码8.4 无误差压缩无误差压缩

55、一行图像行程编码示意图一行图像行程编码示意图一行图像行程编码示意图一行图像行程编码示意图 8.4 无误差压缩无误差压缩每一行图像都由每一行图像都由k段长度为段长度为lk、灰度值为、灰度值为gi的片段组成，那么该行图像就可以由一系的片段组成，那么该行图像就可以由一系列的偶对列的偶对(gi,li)来表示。每个偶对就是一个灰度级行程。来表示。每个偶对就是一个灰度级行程。8.4 无误差压缩无误差压缩4. LZW编码编码一种处理图像的像素间冗余的无误差压缩技术一种处理图像的像素间冗余的无误差压缩技术.对信源符号的可变长度序列分配固定长度的码字对信源符号的可变长度序列分配固定长度的码字,且不需要了解有关被

56、编码符号且不需要了解有关被编码符号的出现概率的知识的出现概率的知识.基本思想是基本思想是: 建立一个编码表建立一个编码表,将输入字符串映射成定长的码字输出将输入字符串映射成定长的码字输出,通常码长设通常码长设为为12比特比特,则可容纳则可容纳4096个码字个码字.如果将图像当做一个一维的比特串如果将图像当做一个一维的比特串,编码图像也视编码图像也视为一个一维的比特串为一个一维的比特串,算法在产生输出串的同时更新编码表算法在产生输出串的同时更新编码表,这样编码表可以更好这样编码表可以更好地适应所压缩图像的特殊性质地适应所压缩图像的特殊性质.LZWLZW编码算法的具体执行步骤如下：编码算法的具体执

57、行步骤如下：步步步步骤骤骤骤1 1 1 1： 将将词词典典初初始始化化为为包包含含所所有有可可能能的的单单字字符符，当当前前前前缀缀P P初初始始化化为空；为空；步骤步骤2 2： 当前字符当前字符C C 的内容为输入字符流中的下一个字符；的内容为输入字符流中的下一个字符；步骤步骤3 3： 判断判断P+CP+C是否在词典中是否在词典中(1) (1) 如果如果“是是”， 则用则用C C扩展扩展P P，即让，即让P=PP=PC C；(2) (2) 如果如果“否否”，则，则 输出当前前缀输出当前前缀P P的码字到码字流；的码字到码字流； 将将P PC C添加到词典中；添加到词典中； 令前缀令前缀P =

58、 C (P = C (即现在的即现在的P P仅包含一个字符仅包含一个字符C);C);步骤步骤4 4： 判断输入字符流中是否还有码字要编码判断输入字符流中是否还有码字要编码(1) (1) 如果如果“是是”，就返回到步骤，就返回到步骤2 2；(2) (2) 如果如果“否否” 把当前前缀把当前前缀P P的码字输出到码字流的码字输出到码字流; ; 结束。结束。 8.4 无误差压缩无误差压缩位置位置位置位置 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9字符字符字符字符 A B B A B A B A C A

59、 B B A B A B A C A B B A B A B A C A B B A B A B A C 步骤步骤步骤步骤 位置位置位置位置 词典词典词典词典 输出输出输出输出 (1) A (1) A (1) A (1) A (2) B (2) B (2) B (2) B (3) C (3) C (3) C (3) C 1 1 (4)A B (1) 1 1 (4)A B (1) 1 1 (4)A B (1) 1 1 (4)A B (1) 2 2 (5)B B (2) 2 2 (5)B B (2) 2 2 (5)B B (2) 2 2 (5)B B (2) 3 3 (6) B A (2) 3 3

60、 (6) B A (2) 3 3 (6) B A (2) 3 3 (6) B A (2) 4 4 (7)A B A (4) 4 4 (7)A B A (4) 4 4 (7)A B A (4) 4 4 (7)A B A (4) 5 6 (8)A B A C (7) 5 6 (8)A B A C (7) 5 6 (8)A B A C (7) 5 6 (8)A B A C (7) 6 - - - 6 - - - 6 - - - 6 - - - (3)(3)(3)(3)例例例例8.98.98.4 无误差压缩无误差压缩5. 5. 无损预测编码无损预测编码8.4 无误差压缩无误差压缩 预测编码数据压缩技术

61、建立在信号预测编码数据压缩技术建立在信号(语音、图像等语音、图像等)数据的相关性上。数据的相关性上。根据某一模型根据某一模型,利用以前的样本值对新样本进行预测利用以前的样本值对新样本进行预测,以此减少数据在时以此减少数据在时间和空间上的相关性间和空间上的相关性,从而达到压缩的目的从而达到压缩的目的. 实际进行预测时实际进行预测时,一般基于估计理论一般基于估计理论. 基本思想是通过对每个像基本思想是通过对每个像素中新增的信息进行提取和编码素中新增的信息进行提取和编码,以此来消除空间上较为接近的像素以此来消除空间上较为接近的像素之间的冗余之间的冗余. 新增信息是指像素值与预测值之间的差异新增信息是

62、指像素值与预测值之间的差异. 相邻像素之间具有较强的相关性相邻像素之间具有较强的相关性,因此可以根据以前已知的几个像素来因此可以根据以前已知的几个像素来估计、猜测，即预测估计、猜测，即预测.无损预测编码系统无损预测编码系统无损预测编码系统无损预测编码系统 8.4 无误差压缩无误差压缩编码器编码器解码器解码器编码器和解码器中的预测编码器和解码器中的预测器是相同的器是相同的预测误差预测误差预测误差预测误差 8.4 无误差压缩无误差压缩误差通过符号编码器编码成压缩数据流的一个元素误差通过符号编码器编码成压缩数据流的一个元素.解压时解压时,通过解码器解码后得到的通过解码器解码后得到的en序列与解码端的

63、预测值相加序列与解码端的预测值相加,再现序列再现序列fn由于预测误差的方差大大小于输入序列的方差由于预测误差的方差大大小于输入序列的方差,因此可以用较低的码率进行编码因此可以用较低的码率进行编码.线性预测线性预测线性预测线性预测 是预测系数是预测系数是预测系数是预测系数 8.4 无误差压缩无误差压缩round为四舍五入函数为四舍五入函数如果预测方案中的预测系数是固定不变的常数，则称为线性预测。如果预测方案中的预测系数是固定不变的常数，则称为线性预测。m称为线性预测器的阶。称为线性预测器的阶。不能对前不能对前m个像素预测，需要用其他方式编码，称为预测编码的额外开销。个像素预测，需要用其他方式编码

64、，称为预测编码的额外开销。如果如果不是上式所示的线性组合关系，而是非线性关系，则称为非线性预测。不是上式所示的线性组合关系，而是非线性关系，则称为非线性预测。在图像数据压缩中，常用如下几种线性预测方案：在图像数据压缩中，常用如下几种线性预测方案：（1 1）前值预测，即）前值预测，即（2 2）一维预测，即用同一扫描行的前面几个采样值预测。）一维预测，即用同一扫描行的前面几个采样值预测。（3 3）二二维维预预测测，即即不不但但用用同同一一扫扫描描行行的的前前面面几几个个采采样样值值，还还要要用用前前几几行行中的采样值一起来预测。中的采样值一起来预测。8.4 无误差压缩无误差压缩二维预测示意图二维预

65、测示意图8.4 无误差压缩无误差压缩考虑一维预测考虑一维预测考虑一维预测考虑一维预测前值预测器前值预测器前值预测器前值预测器 对于数字图像：对于数字图像：xy8.4 无误差压缩无误差压缩无损预测编码得到的压缩量与输入图像映射到预测误无损预测编码得到的压缩量与输入图像映射到预测误差序列后熵减少有直接的关系。因为通过预测和差分差序列后熵减少有直接的关系。因为通过预测和差分处理，消除了大量的像素间的冗余，因此，预测误差处理，消除了大量的像素间的冗余，因此，预测误差的概率分布在零处有一个很高的峰值，并且与输入灰的概率分布在零处有一个很高的峰值，并且与输入灰度值相比其方差较小。度值相比其方差较小。原图的标准方差为：原图的标准方差为：52.8775预测误差图像的标准方差为：预测误差图像的标准方差为：13.5670