第8章 图像压缩（1）.ppt

《第8章 图像压缩（1）.ppt》由会员分享，可在线阅读，更多相关《第8章 图像压缩（1）.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第八章第八章 图像压缩图像压缩 8.1 图像压缩基础图像压缩基础 8.2 图像压缩模型图像压缩模型 8.4 无误差压缩无误差压缩 8.5 有损压缩有损压缩 8.6 图像压缩标准图像压缩标准 8.1 图像压缩基础图像压缩基础图像信息占据大量的存储容量图像信息占据大量的存储容量,所用传输信道也较宽所用传输信道也较宽.一幅一幅512512512512像素，像素，8b/8b/像素的灰度图像占据像素的灰度图像占据256KB256KB的磁盘空间；的磁盘空间；一一幅幅512512512512像像素素，每每分分量量8b/8b/像像素素的的彩彩色色图图像像则则占占据据32563256768KB768KB的的磁盘

2、空间；磁盘空间；如如果果以以每每秒秒2424帧帧传传送送此此彩彩色色图图像像，则则一一秒秒钟钟的的数数据据量量就就有有247682476818.5MB18.5MB，那么一张，那么一张680MB680MB容量的容量的CDCDROMROM仅能存储仅能存储3030多秒的原始数据。多秒的原始数据。对图像数据的压缩必不可少。对图像数据的压缩必不可少。8.1 图像压缩基础图像压缩基础相相同同数数量量的的信信息息可可以以用用不不同同数数量量的的数数据据表表示示.图图像像压压缩缩指指减减少少表表示示给给定定信息量所需的数据量信息量所需的数据量.数据冗余的量化数据冗余的量化:相对数据冗余：相对数据冗余：压缩率：

3、压缩率：在数字图像压缩中在数字图像压缩中,可以确定三种基本的数据冗余可以确定三种基本的数据冗余:编码冗余、像素间冗余和心理视觉冗余编码冗余、像素间冗余和心理视觉冗余.数据中存在信息冗余数据中存在信息冗余,就有可能对图像数据量进行压缩就有可能对图像数据量进行压缩,针对数据冗余的类针对数据冗余的类型不同型不同,可以有多种不同的数据压缩方法可以有多种不同的数据压缩方法.越大越大,压缩效果越好压缩效果越好8.1 图像压缩基础图像压缩基础编码冗余编码冗余:图像灰度可用不同的编码表示图像灰度可用不同的编码表示8.1 图像压缩基础图像压缩基础例例8.1变长编码的例子变长编码的例子编码编码2编码编码18.1

4、图像压缩基础图像压缩基础图图8.1 用变长编码的数据压缩基本原理的图表表示用变长编码的数据压缩基本原理的图表表示8.1 图像压缩基础图像压缩基础图图8.2 两幅图像和它们的灰度级直方图以及沿着某条线计算的归一化自相关系数两幅图像和它们的灰度级直方图以及沿着某条线计算的归一化自相关系数像素间冗余像素间冗余直方图直方图图像像素之间的相关性图像像素之间的相关性自相关系数自相关系数相邻像素之间具有相邻像素之间具有高度相关性高度相关性8.1 图像压缩基础图像压缩基础自相关系数的计算自相关系数的计算:另一种数据冗余形式另一种数据冗余形式:因为任何给定像素的值可以根据与这些像素相邻的像素进行适当的预测因为任

5、何给定像素的值可以根据与这些像素相邻的像素进行适当的预测,所以由单个像素携带的信息相对较少所以由单个像素携带的信息相对较少.单一像素对于一幅图像的多数视觉共享单一像素对于一幅图像的多数视觉共享是多余的是多余的;它的值可以通过相邻像素进行推测它的值可以通过相邻像素进行推测.8.1 图像压缩基础图像压缩基础例例8.2行程编码的简单说明行程编码的简单说明(a)(b)(c)(d)(a)原图原图(b)标记了线标记了线100的二值图像的二值图像(c)线状剖面和二线状剖面和二值化门限值化门限(d)行程编码行程编码8.1 图像压缩基础图像压缩基础1024343个像素个像素,每个像素用每个像素用1个比特表示个比

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

7、缩比率为2出现假轮廓出现假轮廓8.1 图像压缩基础图像压缩基础心理视觉冗余：心理视觉冗余：IGS量化过程量化过程8.1 图像压缩基础图像压缩基础保真度准则：保真度准则：图像的编码质量评价图像的编码质量评价定量分析丢失信息的性质和范围定量分析丢失信息的性质和范围,包括包括(1)客观保真度准则客观保真度准则(2)主观保真度准则主观保真度准则当信息损失的程度可以表示成初始图像或输入图像以及先被压缩而后被解压缩当信息损失的程度可以表示成初始图像或输入图像以及先被压缩而后被解压缩的输出图像的函数时的输出图像的函数时,就说这个函数是基于就说这个函数是基于客观保真度准则客观保真度准则的的.8.1 图像压缩基

8、础图像压缩基础保真度准则：保真度准则：主观保真度准则主观保真度准则:8.2 图像压缩模型图像压缩模型信源信源编码编码信道信道编码编码信道信道信道信道解码解码信源信源解码解码编码器编码器解码器解码器图图8.5 一个常用的图像压缩系统模型一个常用的图像压缩系统模型8.2 图像压缩模型图像压缩模型转换器转换器量化器量化器符号编码器符号编码器信道信道信道信道符号解码器符号解码器反向转换器反向转换器信源编码器信源编码器信源解码器信源解码器(a)信源编码器信源编码器 (b)信源解码器信源解码器信源编码器和信源解码器信源编码器和信源解码器8.2 图像压缩模型图像压缩模型信道编码器和解码器信道编码器和解码器如

9、果找到一个非零值如果找到一个非零值,则解码器只需简单地在校验字指出的位置补充码字比特则解码器只需简单地在校验字指出的位置补充码字比特.解码的解码的二进制二进制h3h5h6h7就能从纠正后的码字中提取出来就能从纠正后的码字中提取出来.信道带有噪声或易于出现错误信道带有噪声或易于出现错误,信道编码器和解信道编码器和解码器通过向信源编码数据中插入预制的冗余数码器通过向信源编码数据中插入预制的冗余数据来减少信道噪声的影响据来减少信道噪声的影响.设一个离散信源设一个离散信源设一个离散信源设一个离散信源X X X X：满足满足满足满足其概率分布：其概率分布：其概率分布：其概率分布：离散信源类型离散信源类型

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

11、 k,如果它出现的概率是如果它出现的概率是如果它出现的概率是如果它出现的概率是p pk k 信源熵信源熵信源熵信源熵H(X)H(X)x xk k的自信息量的自信息量的自信息量的自信息量 8.3 信息理论基础与熵编码信息理论基础与熵编码直观地理解自信息量的概念直观地理解自信息量的概念:一个概率小的符号出现将带来更大的信息量一个概率小的符号出现将带来更大的信息量.每个符号的平均自信息量每个符号的平均自信息量单位单位:比特比特/符号符号设设设设信源熵信源熵信源熵信源熵 则则则则,各各各各信源符号自信源符号自信源符号自信源符号自信息量：信息量：信息量：信息量：例例例例 8.48.48.48.4 编编编

12、编码码码码方方方方法法法法：a,b,c,da,b,c,d用用用用码码码码字字字字00,01,10,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,符符符符号号号号a a a a出

17、出出出现现现现的的的的概概概概率率率率为为为为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时时时时,H(p)=1,H(p)=1,H

18、(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 信息理论基础与熵编码信息理论基础与熵编码若把信息论中的熵值应用到图像信息源中若把信息论中的熵值应用到图像信息源中,若图像的灰度级为若图像的灰度级为0,L-1,则可以则可以通过直方图得到各灰度级

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

21、保持编码定理香农信息保持编码定理 香香农农信信息息论论已已证证明明,信信源源熵熵是是进进行行无无失失真真编编码码的的理理论论极极限限.低低于于此此极极限限的的无无失失真真编编码码方方法法是是不不存存在在的的,这这是是熵熵编编码码的的理理论论基基础础.而而且且可可以以证证明明,考考虑虑像像素素间间的的相相关关性性,使使用用高高阶阶熵熵一一定定可可以以获获得得更更高高的的压缩比压缩比.2)2)变长编码定理变长编码定理 n变变长长编编码码定定义义：对对于于一一个个无无记记忆忆离离散散信信源源中中每每一一个个符符号号,若若采采用用相相同同长长度度的的不不同同码码字字代代表表相相应应符符号号,就就叫叫做

22、做等等长长编编码码,例例如如中中国国4 4位位电电报报码码.若若对对信信源源中中的的不不同同符符号号,用用不不同同长长度度的的码码字字表表示示就就叫叫做做不等长不等长或或变长编码变长编码.n与与定定长长编编码码相相比比,变变长长编编码码更更复复杂杂,除除唯唯一一可可译译码码（也也称称为为单单义义可可译）的要求译）的要求,还存在即时解码问题还存在即时解码问题.8.3 信息理论基础与熵编码信息理论基础与熵编码变长编码定理：变长编码定理：若一个离散无记忆信源具有熵若一个离散无记忆信源具有熵H(X),H(X),并有并有r r个码元符个码元符号集号集,则总可以找到一种无失真信源编码则总可以找到一种无失真

23、信源编码,构成单义可译码构成单义可译码,使其使其平均码长满足：平均码长满足：当当当当r=2r=28.3 信息理论基础与熵编码信息理论基础与熵编码信源符号概率编码A编码Ba1/200B1/41001C1/8110011d1/8111111例例编码编码A是可以即时解码的是可以即时解码的,而编码而编码B是有惟一解码的是有惟一解码的,却不是即时的却不是即时的.如收到码串如收到码串01,要等下一个比特到来要等下一个比特到来.给定一个无记忆离散信源给定一个无记忆离散信源,意味着其统计特性已知意味着其统计特性已知,则则信源的熵已确定信源的熵已确定,那么那么,信信源的单义可译码长源的单义可译码长L的下界的下界

24、也就随之确定了也就随之确定了.3)3)3)3)变长最佳编码定理变长最佳编码定理变长最佳编码定理变长最佳编码定理在在在在变变变变长长长长编编编编码码码码中中中中,对对对对出出出出现现现现概概概概率率率率大大大大的的的的信信信信息息息息符符符符号号号号赋赋赋赋予予予予短短短短码码码码字字字字,而而而而对对对对于于于于出出出出现现现现概概概概率率率率小小小小的的的的信信信信息息息息符符符符号号号号赋赋赋赋予予予予长长长长码码码码字字字字.如如如如果果果果码码码码字字字字长长长长度度度度严严严严格格格格按按按按照照照照所所所所对对对对应应应应符符符符号号号号出出出出现现现现概概概概率率率率大大大大小小

25、小小逆逆逆逆序序序序排排排排列列列列,则则则则编编编编码码码码结结结结果果果果平平平平均均均均码码码码字字字字长长长长度度度度一一一一定定定定小于任何其他排列形式小于任何其他排列形式小于任何其他排列形式小于任何其他排列形式.8.3 信息理论基础与熵编码信息理论基础与熵编码1 1 1 1霍夫曼编码霍夫曼编码霍夫曼编码霍夫曼编码8.4 无误差压缩无误差压缩根据变长最佳编码定理根据变长最佳编码定理,HuffmanHuffman编码编码步骤如下：步骤如下：（1 1）将信源符号将信源符号将信源符号将信源符号x xi i按其出现的概率按其出现的概率按其出现的概率按其出现的概率,由大到小顺序排列由大到小顺序

26、排列由大到小顺序排列由大到小顺序排列.（2 2 2 2）将将将将两两两两个个个个最最最最小小小小的的的的概概概概率率率率的的的的信信信信源源源源符符符符号号号号进进进进行行行行组组组组合合合合相相相相加加加加,并并并并重重重重复复复复这这这这一一一一步步步步骤骤骤骤,始始始始终终终终将将将将较较较较大大大大的的的的概概概概率率率率分分分分支支支支放放放放在在在在上上上上部部部部,直直直直到到到到只只只只剩剩剩剩下下下下一一一一个个个个信信信信源源源源符符符符号号号号且且且且概概概概率率率率达达达达到到到到1.01.01.01.0为止；为止；为止；为止；（3 3 3 3）对对对对每每每每对对对对

27、组组组组合合合合的的的的上上上上边边边边一一一一个个个个指指指指定定定定为为为为1,1,1,1,下下下下边边边边一一一一个个个个指指指指定定定定为为为为0 0 0 0（或或或或相相相相反反反反：对对对对上上上上边一个指定为边一个指定为边一个指定为边一个指定为0,0,0,0,下边一个指定为下边一个指定为下边一个指定为下边一个指定为1 1 1 1）；）；）；）；（4 4 4 4）画出由每个信源符号到概率）画出由每个信源符号到概率）画出由每个信源符号到概率）画出由每个信源符号到概率1.01.01.01.0处的路径处的路径处的路径处的路径,记下沿路径的记下沿路径的记下沿路径的记下沿路径的1 1 1 1

28、和和和和0 0 0 0；（5 5 5 5）对对对对于于于于每每每每个个个个信信信信源源源源符符符符号号号号都都都都写写写写出出出出1 1 1 1、0 0 0 0序序序序列列列列,则则则则从从从从右右右右到到到到左左左左就就就就得得得得到到到到非非非非等等等等长长长长的的的的 HuffmanHuffmanHuffmanHuffman码码码码.一一幅幅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

29、.125。例例例例8.78.78.78.7HuffmanHuffmanHuffmanHuffman编码过程示意图编码过程示意图编码过程示意图编码过程示意图8.4 无误差压缩无误差压缩编码结果编码结果编码结果编码结果 图像熵图像熵图像熵图像熵 信源符号信源符号信源符号信源符号出现概率出现概率出现概率出现概率码字码字码字码字码长码长码长码长s10.401S20.1751113S30.151103S40.151013S50.1251003编码编码编码编码后均后均后均后均码长码长码长码长 8.4 无误差压缩无误差压缩HuffmanHuffmanHuffmanHuffman编码的特点是：编码的特点是：编

30、码的特点是：编码的特点是：（1 1 1 1）HuffmanHuffmanHuffmanHuffman编编编编码码码码构构构构造造造造程程程程序序序序是是是是明明明明确确确确的的的的，但但但但编编编编出出出出的的的的码码码码不不不不是是是是唯唯唯唯一一一一的的的的，其其其其原原原原因因因因之之之之一一一一是是是是两两两两个个个个概概概概率率率率分分分分配配配配码码码码字字字字“0”0”0”0”和和和和“1”1”1”1”是是是是任任任任意意意意选选选选择择择择的的的的（大大大大概概概概率率率率为为为为“0”0”0”0”，小小小小概概概概率率率率为为为为“1”1”1”1”，或或或或者者者者反反反反之

31、之之之）。第第第第二二二二原原原原因因因因是是是是在在在在排排排排序序序序过过过过程程程程中中中中两两两两个个个个概概概概率率率率相相相相等等等等，谁谁谁谁前前前前谁谁谁谁后后后后也也也也是是是是随随随随机机机机的的的的。这这这这样样样样编编编编出出出出的的的的码码码码字字字字就就就就不不不不是是是是唯唯唯唯一一一一的。的。的。的。（2 2 2 2）HuffmanHuffmanHuffmanHuffman编编编编码码码码结结结结果果果果，码码码码字字字字不不不不等等等等长长长长，平平平平均均均均码码码码字字字字最最最最短短短短，效效效效率率率率最最最最高高高高，但但但但码码码码字字字字长长长长

32、短短短短不不不不一一一一，实实实实时时时时硬硬硬硬件件件件实实实实现现现现很很很很复复复复杂杂杂杂（特特特特别别别别是是是是译译译译码码码码），而而而而且且且且在在在在抗抗抗抗误码能力方面也比较差。误码能力方面也比较差。误码能力方面也比较差。误码能力方面也比较差。（3 3 3 3）HuffmanHuffmanHuffmanHuffman编码的信源概率是编码的信源概率是编码的信源概率是编码的信源概率是2 2 2 2的负幂时，效率达的负幂时，效率达的负幂时，效率达的负幂时，效率达100%100%100%100%，但是对等，但是对等，但是对等，但是对等概率分布的信源，产生定长码，效率最低，因此编码效

33、率与信源符概率分布的信源，产生定长码，效率最低，因此编码效率与信源符概率分布的信源，产生定长码，效率最低，因此编码效率与信源符概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故号概率分布相关，故号概率分布相关，故号概率分布相关，故HuffmanHuffmanHuffmanHuffman编码依赖于信源统计特性，编码前必须编码依赖于信源统计特性，编码前必须编码依赖于信源统计特性，编码前必须编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了哈夫曼编码的应用。有信源这方面的先验知识，这往往限制了哈夫曼编码的应用。有信源这方面的先验知识，这往往限制了哈夫曼编

34、码的应用。有信源这方面的先验知识，这往往限制了哈夫曼编码的应用。（4 4 4 4）HuffmanHuffmanHuffmanHuffman编码只能用近似的整数位来表示单个符号，而不是理编码只能用近似的整数位来表示单个符号，而不是理编码只能用近似的整数位来表示单个符号，而不是理编码只能用近似的整数位来表示单个符号，而不是理想的小数，这也是想的小数，这也是想的小数，这也是想的小数，这也是HuffmanHuffmanHuffmanHuffman编码无法达到最理想的压缩效果的原因。编码无法达到最理想的压缩效果的原因。编码无法达到最理想的压缩效果的原因。编码无法达到最理想的压缩效果的原因。8.4 无误差

35、压缩无误差压缩 算术编码不是将单个信源符号映射成一个码字，而是把整个信源表算术编码不是将单个信源符号映射成一个码字，而是把整个信源表算术编码不是将单个信源符号映射成一个码字，而是把整个信源表算术编码不是将单个信源符号映射成一个码字，而是把整个信源表示为实数线上的示为实数线上的示为实数线上的示为实数线上的0 0 0 0到到到到1 1 1 1之间的一个区间（之间的一个区间（之间的一个区间（之间的一个区间（IntervalIntervalIntervalInterval），），），），其长度等于该序列其长度等于该序列其长度等于该序列其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进

36、制作为实际的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要缩短为一个区间。消息序列中的编码输出。消息序列中的每个元素都要缩短为一个区间。消息序列中的编码输出。消息序列中的每个元素都要缩短为一个区间。消息序列中的编码输出。消息序列中的每个元素都要缩短为一个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来元素越多，所得到的区间就越小，当

37、区间变小时，就需要更多的数位来元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。2.算术编码算术编码8.4 无误差压缩无误差压缩假设信源符号为假设信源符号为假设信源符号为假设信源符号为00,01,10,11,00,01,10,11,00,01,10,11,00,01,10,11,这些符号的概率分别为这些符号的概率分别为这些符号的概率分别为这些符号

38、的概率分别为 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个子间隔：个子间隔：个子间隔：个子间隔：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

39、 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)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 无误差压缩无误差压缩步骤步骤步骤步骤

40、输入输入输入输入 符号编码间隔符号编码间隔符号编码间隔符号编码间隔 编码判决编码判决编码判决编码判决1 10 0.5,0.7)1 10 0.5,0.7)1 10 0.5,0.7)1 10 0.5,0.7)符号的间隔范围符号的间隔范围符号的间隔范围符号的间隔范围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

41、,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.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.

42、5143,0.51442)0.514,0.5146)5 10 0.5143,0.51442)0.514,0.5146)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.5

43、143,0.51442)6 11 0.514384,0.51442)0.5143,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，

44、从第从第从第从第1 1 1 1个个个个1/101/101/101/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为上一个被编码符号的范围和低端值为上一个

45、被编码符号的范围和低端值;high=low+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

46、.514391 0.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,0.52)11 0.5

47、14393 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)的第的第的第的第1 1 1 1个个个个1/101/101/101/1

48、05 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.51442)11 0.514396 0.514384,0.51442)11 0.514396 0.5

49、14384,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.5143948)01 0.51439在间隔在间隔在间隔在间隔0.514384,0.51442)0.514384,0.51442)0.51

50、4384,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_lowk)/rangek然后判断然后判断valuek+1 位于哪个范围位于哪个范围,则得到对应编码则得到对应编码.译码判决方法译码判决方法