第6章 图像编码.ppt

第六章第六章 图像编码图像编码 16.1 6.1 概概 述述2一般来说，图像数据中存在以下几种冗余：一般来说，图像数据中存在以下几种冗余：1、空间冗余：、空间冗余：2、时间冗余：、时间冗余：3、结构冗余：、结构冗余：4、信息熵冗余：、信息熵冗余：5、知识冗余：、知识冗余：6、视觉冗余：灰度等级，我们把这类冗余称为视觉冗、视觉冗余：灰度等级，我们把这类冗余称为视觉冗 既然图像数图像数据中存在信息冗余，就有可能对图像数既然图像数图像数据中存在信息冗余，就有可能对图像数据量进行压缩，针对数据冗余的类型不同，可以有多种不同的据量进行压缩，针对数据冗余的类型不同，可以有多种不同的数据压缩方法，本章将讨论各种压缩方法。数据压缩方法，本章将讨论各种压缩方法。3 常用的准则有均方误差、均方根误差、均方信噪比、常用的准则有均方误差、均方根误差、均方信噪比、基本信噪比和峰值信噪比基本信噪比和峰值信噪比 均方误差均方误差均方误差均方误差 均方根误差均方根误差均方根误差均方根误差客观评价准则客观评价准则客观评价准则客观评价准则4均方信噪比均方信噪比均方信噪比均方信噪比 令令令令 客观评价准则客观评价准则客观评价准则客观评价准则5基本信噪比基本信噪比基本信噪比基本信噪比 设设设设峰值信噪比峰值信噪比峰值信噪比峰值信噪比 客观评价准则客观评价准则客观评价准则客观评价准则6得分得分得分得分第一种评价标准第一种评价标准第一种评价标准第一种评价标准第二种评价标准第二种评价标准第二种评价标准第二种评价标准5 5优秀优秀优秀优秀没有失真的感觉没有失真的感觉没有失真的感觉没有失真的感觉4 4良好良好良好良好感感感感觉觉觉觉到到到到失失失失真真真真，但但但但没没没没有有有有不不不不舒舒舒舒服服服服的感觉的感觉的感觉的感觉3 3可用可用可用可用感觉有点没舒服感觉有点没舒服感觉有点没舒服感觉有点没舒服2 2较差较差较差较差感觉较差感觉较差感觉较差感觉较差1 1差差差差感觉非常不舒服感觉非常不舒服感觉非常不舒服感觉非常不舒服 对图像质量的主观评分标准对图像质量的主观评分标准对图像质量的主观评分标准对图像质量的主观评分标准主观评价准则主观评价准则主观评价准则主观评价准则7设每一种得分为设每一种得分为设每一种得分为设每一种得分为C C C Ci i i i，每一种得分的评分人数为每一种得分的评分人数为每一种得分的评分人数为每一种得分的评分人数为n n n ni i i i平均感觉分平均感觉分平均感觉分平均感觉分MOSMOS的主观评价可定义的主观评价可定义的主观评价可定义的主观评价可定义主观评价准则主观评价准则主观评价准则主观评价准则MOSMOSMOSMOS得分越高，解码后图像的主观评价好得分越高，解码后图像的主观评价好得分越高，解码后图像的主观评价好得分越高，解码后图像的主观评价好8则压缩比：则压缩比：压缩比压缩比压缩比压缩比设设n1为原始图像每个像素的平均比特数为原始图像每个像素的平均比特数 n2为编码后每个像素的平均比特数为编码后每个像素的平均比特数 压缩比越大压缩效果越好压缩比越大压缩效果越好压缩比越大压缩效果越好压缩比越大压缩效果越好 96.2 6.2 信息理论基础与熵编码信息理论基础与熵编码 10设一个离散信源设一个离散信源设一个离散信源设一个离散信源X X X X：满足满足满足满足其概率分布：其概率分布：其概率分布：其概率分布：离散信源类型离散信源类型离散信源类型离散信源类型 无记忆信源无记忆信源 有记忆信源有记忆信源 11考虑无记忆信源考虑无记忆信源考虑无记忆信源考虑无记忆信源X X ，某个信源符号某个信源符号某个信源符号某个信源符号x xk k，如果它出现的概率是如果它出现的概率是如果它出现的概率是如果它出现的概率是p pk k 信源熵信源熵信源熵信源熵H(X)H(X)x xk k的自信息量的自信息量的自信息量的自信息量 12设设设设信源熵信源熵信源熵信源熵 则，各信源符号自则，各信源符号自则，各信源符号自则，各信源符号自信息量：信息量：信息量：信息量：例例例例6 6 6 6。1 1 1 1 编编编编码码码码方方方方法法法法：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比特。比特。比特。比特。13设设设设信源熵信源熵信源熵信源熵 则，各信源符号自则，各信源符号自则，各信源符号自则，各信源符号自信息量：信息量：信息量：信息量：例例例例6 6 6 6。2 2 2 2 14例例例例6 6 6 6。2 2 2 2 两种编码方法：两种编码方法：两种编码方法：两种编码方法：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来编码来编码来编码来编码 平均码长：平均码长：平均码长：平均码长：平均码长大于信源的熵平均码长大于信源的熵平均码长大于信源的熵平均码长大于信源的熵 平均码长：平均码长：平均码长：平均码长：平均码长等于信源的熵平均码长等于信源的熵平均码长等于信源的熵平均码长等于信源的熵 15设设设设信源熵信源熵信源熵信源熵 则，各信源符号自则，各信源符号自则，各信源符号自则，各信源符号自信息量：信息量：信息量：信息量：例例例例6 6 6 6。3 3 3 3 用例用例用例用例7.27.27.27.2第二种编码方法第二种编码方法第二种编码方法第二种编码方法 ，平均码长平均码长平均码长平均码长1.851.851.851.85大于信源熵大于信源熵大于信源熵大于信源熵 16可得到几点提示可得到几点提示可得到几点提示可得到几点提示：信源的平均码长信源的平均码长信源的平均码长信源的平均码长l lavgavg=H(X)=H(X)；也就是说熵是无失真编码的下界。也就是说熵是无失真编码的下界。也就是说熵是无失真编码的下界。也就是说熵是无失真编码的下界。如果所有如果所有如果所有如果所有I(I(x xk k)都是整数，且都是整数，且都是整数，且都是整数，且l(l(x xk k)=I()=I(x xk k),可以使平均码长等于熵。可以使平均码长等于熵。可以使平均码长等于熵。可以使平均码长等于熵。对对对对非非非非等等等等概概概概率率率率分分分分布布布布的的的的信信信信源源源源，采采采采用用用用不不不不等等等等长长长长编编编编码码码码其其其其平平平平均均均均码码码码长长长长小小小小于于于于等等等等长长长长编编编编码码码码的平均码长。的平均码长。的平均码长。的平均码长。如如如如果果果果信信信信源源源源中中中中各各各各符符符符号号号号的的的的出出出出现现现现概概概概率率率率相相相相等等等等，信信信信源源源源熵熵熵熵值值值值达达达达到到到到最最最最大大大大，这这这这就就就就是是是是重重重重要的最大离散熵定理。要的最大离散熵定理。要的最大离散熵定理。要的最大离散熵定理。17考虑有记忆信源考虑有记忆信源考虑有记忆信源考虑有记忆信源X X（1 1 1 1阶马尔可夫信源阶马尔可夫信源阶马尔可夫信源阶马尔可夫信源 ）1 1 1 1阶熵阶熵阶熵阶熵 条件概率条件概率条件概率条件概率 条件概率条件概率条件概率条件概率 18对对对对mm阶马尔可夫信源，可以证明：阶马尔可夫信源，可以证明：阶马尔可夫信源，可以证明：阶马尔可夫信源，可以证明：结结结结论论论论：对对对对于于于于有有有有记记记记忆忆忆忆信信信信源源源源，如如如如果果果果符符符符号号号号序序序序列列列列中中中中前前前前面面面面的的的的符符符符号号号号知知知知道道道道得得得得越越越越多多多多，那那那那么么么么下下下下一一一一个个个个符符符符号号号号的的的的平平平平均均均均信信信信息息息息量量量量就就就就越越越越小小小小 191 1香农信息保持编码定理香农信息保持编码定理 n香香农农信信息息论论已已证证明明，信信源源熵熵是是进进行行无无失失真真编编码码的的理理论论极极限限。低低于于此此极极限限的的无无失失真真编编码码方方法法是是不不存存在在的的，这这是是熵熵编编码码的的理理论论基基础础。而而且且可可以以证证明明，考考虑虑像像素素间间的的相相关关性性，使使用用高高阶阶熵熵一一定定可可以以获获得得更高的压缩比。更高的压缩比。2 2变长编码定理变长编码定理 n变变长长编编码码定定义义：对对于于一一个个无无记记忆忆离离散散信信源源中中每每一一个个符符号号，若若采采用用相相同同长长度度的的不不同同码码字字代代表表相相应应符符号号，就就叫叫做做等等长长编编码码，例例如如中中国国4 4位位电电报报码码。若若对对信信源源中中的的不不同同符符号号，用用不不同同长长度度的的码码字字表表示示就就叫做不等长或变长编码。叫做不等长或变长编码。n与与定定长长编编码码相相比比，变变长长编编码码更更复复杂杂，除除唯唯一一可可译译码码（也也称称为为单单义义可译）的要求，还存在即时解码问题。可译）的要求，还存在即时解码问题。20变变长长编编码码定定理理：若若一一个个离离散散无无记记忆忆信信源源具具有有熵熵，并并有有个个码码元元符符号号集集，则则总总可可以以找找到到一一种种无无失失真真信信源源编编码码，构构成单义可译码，使其平均码长满足：成单义可译码，使其平均码长满足：当当当当r=2r=2213 3 3 3变长最佳编码定理变长最佳编码定理变长最佳编码定理变长最佳编码定理n n 在在在在变变变变长长长长编编编编码码码码中中中中，对对对对出出出出现现现现概概概概率率率率大大大大的的的的信信信信息息息息符符符符号号号号赋赋赋赋予予予予短短短短码码码码字字字字，而而而而对对对对于于于于出出出出现现现现概概概概率率率率小小小小的的的的信信信信息息息息符符符符号号号号赋赋赋赋予予予予长长长长码码码码字字字字。如如如如果果果果码码码码字字字字长长长长度度度度严严严严格格格格按按按按照照照照所所所所对对对对应应应应符符符符号号号号出出出出现现现现概概概概率率率率大大大大小小小小逆逆逆逆序序序序排排排排列列列列，则则则则编编编编码码码码结结结结果果果果平平平平均均均均码码码码字字字字长长长长度度度度一一一一定定定定小小小小于于于于任任任任何何何何其其其其他排列形式他排列形式他排列形式他排列形式.22n根据变长最佳编码定理，根据变长最佳编码定理，HuffmanHuffman编码编码步骤如下：步骤如下：n（1 1）将信源符号将信源符号将信源符号将信源符号x xi i按其出现的概率，由大到小顺序排列。按其出现的概率，由大到小顺序排列。按其出现的概率，由大到小顺序排列。按其出现的概率，由大到小顺序排列。n n（2 2 2 2）将将将将两两两两个个个个最最最最小小小小的的的的概概概概率率率率的的的的信信信信源源源源符符符符号号号号进进进进行行行行组组组组合合合合相相相相加加加加，并并并并重重重重复复复复这这这这一一一一步步步步骤骤骤骤，始始始始终终终终将将将将较较较较大大大大的的的的概概概概率率率率分分分分支支支支放放放放在在在在上上上上部部部部，直直直直到到到到只只只只剩剩剩剩下下下下一一一一个个个个信信信信源源源源符符符符号号号号且且且且概概概概率率率率达达达达到到到到1.01.01.01.0为止；为止；为止；为止；n n（3 3 3 3）对对对对每每每每对对对对组组组组合合合合的的的的上上上上边边边边一一一一个个个个指指指指定定定定为为为为1 1 1 1，下下下下边边边边一一一一个个个个指指指指定定定定为为为为0 0 0 0（或或或或相相相相反反反反：对上边一个指定为对上边一个指定为对上边一个指定为对上边一个指定为0 0 0 0，下边一个指定为，下边一个指定为，下边一个指定为，下边一个指定为1 1 1 1）；）；）；）；n n（4 4 4 4）画出由每个信源符号到概率）画出由每个信源符号到概率）画出由每个信源符号到概率）画出由每个信源符号到概率1.01.01.01.0处的路径，记下沿路径的处的路径，记下沿路径的处的路径，记下沿路径的处的路径，记下沿路径的1 1 1 1和和和和0 0 0 0；n n（5 5 5 5）对对对对于于于于每每每每个个个个信信信信源源源源符符符符号号号号都都都都写写写写出出出出1 1 1 1、0 0 0 0序序序序列列列列，则则则则从从从从右右右右到到到到左左左左就就就就得得得得到到到到非非非非等等等等长长长长的的的的HuffmanHuffmanHuffmanHuffman码。码。码。码。23n一一幅幅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.125 0.125。例例例例6 6 6 6。5 5 5 5 HuffmanHuffmanHuffmanHuffman编码过程示意图编码过程示意图编码过程示意图编码过程示意图24结果结果结果结果 图像熵图像熵图像熵图像熵 信源符号信源符号信源符号信源符号出现概率出现概率出现概率出现概率码字码字码字码字码长码长码长码长s10.401S20.1751113S30.151103S40.151013S50.1251003编码编码编码编码后均后均后均后均码长码长码长码长 25特点特点特点特点 HuffmanHuffmanHuffmanHuffman编码的特点是：编码的特点是：编码的特点是：编码的特点是：（1 1 1 1）HuffmanHuffmanHuffmanHuffman编编编编码码码码构构构构造造造造程程程程序序序序是是是是明明明明确确确确的的的的，但但但但编编编编出出出出的的的的码码码码不不不不是是是是唯唯唯唯一一一一的的的的，其其其其原原原原因因因因之之之之一一一一是是是是两两两两个个个个概概概概率率率率分分分分配配配配码码码码字字字字“0 0 0 0”和和和和“1 1 1 1”是是是是任任任任意意意意选选选选择择择择的的的的（大大大大概概概概率率率率为为为为“0 0 0 0”，小小小小概概概概率率率率为为为为“1 1 1 1”，或或或或者者者者反反反反之之之之）。第第第第二二二二原原原原因因因因是是是是在在在在排排排排序序序序过过过过程程程程中中中中两两两两个个个个概概概概率率率率相相相相等等等等，谁谁谁谁前前前前谁后也是随机的。这样编出的码字就不是唯一的。谁后也是随机的。这样编出的码字就不是唯一的。谁后也是随机的。这样编出的码字就不是唯一的。谁后也是随机的。这样编出的码字就不是唯一的。（2 2 2 2）HuffmanHuffmanHuffmanHuffman编编编编码码码码结结结结果果果果，码码码码字字字字不不不不等等等等长长长长，平平平平均均均均码码码码字字字字最最最最短短短短，效效效效率率率率最最最最高高高高，但但但但码码码码字字字字长长长长短短短短不不不不一一一一，实实实实时时时时硬硬硬硬件件件件实实实实现现现现很很很很复复复复杂杂杂杂（特特特特别是译码），而且在抗误码能力方面也比较差。别是译码），而且在抗误码能力方面也比较差。别是译码），而且在抗误码能力方面也比较差。别是译码），而且在抗误码能力方面也比较差。26特点特点特点特点 （3 3 3 3）HuffmanHuffmanHuffmanHuffman编编编编码码码码的的的的信信信信源源源源概概概概率率率率是是是是2 2 2 2的的的的负负负负幂幂幂幂时时时时，效效效效率率率率达达达达100%100%100%100%，但但但但是是是是对对对对等等等等概概概概率率率率分分分分布布布布的的的的信信信信源源源源，产产产产生生生生定定定定长长长长码码码码，效效效效率率率率最最最最低低低低，因因因因此此此此编编编编码码码码效效效效率率率率与与与与信信信信源源源源符符符符号号号号概概概概率率率率分分分分布布布布相相相相关关关关，故故故故HuffmanHuffmanHuffmanHuffman编编编编码码码码依依依依赖赖赖赖于于于于信信信信源源源源统统统统计计计计特特特特性性性性，编编编编码码码码前前前前必必必必须须须须有有有有信信信信源源源源这这这这方方方方面面面面的的的的先先先先验验验验知知知知识识识识，这这这这往往往往往往往往限限限限制制制制了了了了哈哈哈哈夫夫夫夫曼曼曼曼编编编编码码码码的应用。的应用。的应用。的应用。（4 4 4 4）HuffmanHuffmanHuffmanHuffman编编编编码码码码只只只只能能能能用用用用近近近近似似似似的的的的整整整整数数数数位位位位来来来来表表表表示示示示单单单单个个个个符符符符号号号号，而而而而不不不不是是是是理理理理想想想想的的的的小小小小数数数数，这这这这也也也也是是是是HuffmanHuffmanHuffmanHuffman编编编编码码码码无无无无法法法法达到最理想的压缩效果的原因。达到最理想的压缩效果的原因。达到最理想的压缩效果的原因。达到最理想的压缩效果的原因。27n根据变长最佳编码定理，根据变长最佳编码定理，Shannon-Shannon-FanoFano编码编码步骤如下：步骤如下：n（1 1）将信源中符号）将信源中符号xi按其出现的概率，由大到小顺序排列。按其出现的概率，由大到小顺序排列。n（2 2）将信源分成两部分，使两个部分的概率和尽可能接）将信源分成两部分，使两个部分的概率和尽可能接近。重复第（近。重复第（2 2）步直至不可再分，即每一个叶子只对应）步直至不可再分，即每一个叶子只对应一个符号。一个符号。n（3 3）从左到右次次为这两部分标记）从左到右次次为这两部分标记0 0，1 1。n（4 4）将各个部分标记的）将各个部分标记的0 0，1 1串接起来就得到各信源符号串接起来就得到各信源符号所对应的码字所对应的码字28例例例例6 6 6 6。6 6 6 6 Shannon-Shannon-Shannon-Shannon-FanoFanoFanoFano编码过编码过编码过编码过程示意程示意程示意程示意图图图图 29结果结果结果结果 编码编码编码编码后均后均后均后均码长码长码长码长 灰度级灰度级灰度级灰度级出现概率出现概率出现概率出现概率码字码字码字码字码长码长码长码长s10.4002S20.175012S30,15102S40.151103S50.125111330n n 算术编码不是将单个信源符号映射成一个码字，而是把整算术编码不是将单个信源符号映射成一个码字，而是把整算术编码不是将单个信源符号映射成一个码字，而是把整算术编码不是将单个信源符号映射成一个码字，而是把整个信源表示为实数线上的个信源表示为实数线上的个信源表示为实数线上的个信源表示为实数线上的0 0到到到到1 1之间的一个区间（之间的一个区间（之间的一个区间（之间的一个区间（IntervalInterval），），），），其其其其长度等于该序列的概率，再在该区间内选择一个代表性的小数，长度等于该序列的概率，再在该区间内选择一个代表性的小数，长度等于该序列的概率，再在该区间内选择一个代表性的小数，长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都转化为二进制作为实际的编码输出。消息序列中的每个元素都转化为二进制作为实际的编码输出。消息序列中的每个元素都转化为二进制作为实际的编码输出。消息序列中的每个元素都要缩短为一个区间。消息序列中元素越多，所得到的区间就越要缩短为一个区间。消息序列中元素越多，所得到的区间就越要缩短为一个区间。消息序列中元素越多，所得到的区间就越要缩短为一个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。采用小，当区间变小时，就需要更多的数位来表示这个区间。采用小，当区间变小时，就需要更多的数位来表示这个区间。采用小，当区间变小时，就需要更多的数位来表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。算术编码每个符号的平均编码长度可以为小数。算术编码每个符号的平均编码长度可以为小数。算术编码每个符号的平均编码长度可以为小数。31假设信源符号为假设信源符号为假设信源符号为假设信源符号为00,01,10,1100,01,10,1100,01,10,1100,01,10,11，这些符号的概率分别为，这些符号的概率分别为，这些符号的概率分别为，这些符号的概率分别为 0.1,0.4,0.2,0.3 0.1,0.4,0.2,0.3 0.1,0.4,0.2,0.3 0.1,0.4,0.2,0.3，根据这些概率可把间隔，根据这些概率可把间隔，根据这些概率可把间隔，根据这些概率可把间隔0,1)0,1)0,1)0,1)分成分成分成分成4 4 4 4个子间隔：个子间隔：个子间隔：个子间隔：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)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)。符号符号 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)0.7,1)如果二进制消息序列的输入为：如果二进制消息序列的输入为：如果二进制消息序列的输入为：如果二进制消息序列的输入为：10 00 11 00 10 11 0110 00 11 00 10 11 0110 00 11 00 10 11 0110 00 11 00 10 11 01。例例例例6 6。7 7 32例例例例6 6。7 7 算术编码过程示意图算术编码过程示意图算术编码过程示意图算术编码过程示意图 33步骤步骤步骤步骤 输入输入输入输入 符号编码间隔符号编码间隔符号编码间隔符号编码间隔 编码判决编码判决编码判决编码判决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,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.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.5143,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，从第从第从第从第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算术编码过程算术编码过程算术编码过程算术编码过程 34算术编码解码过程算术编码解码过程算术编码解码过程算术编码解码过程 步骤步骤步骤步骤 间隔间隔间隔间隔 译码符号译码符号译码符号译码符号 译码判决译码判决译码判决译码判决 1 0.5,0.7)10 0.514391 0.5,0.7)10 0.514391 0.5,0.7)10 0.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.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)的第的第的第的第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.51442)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 0.51439,0.5143948)01 0.514397 0.51439,0.5143948)01 0.514397 0.51439,0.5143948)01 0.514397 0.51439,0.5143948)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 0135n n行行行行程程程程编编编编码码码码（Run Run Length Length EncodingEncoding）是是是是一一一一种种种种利利利利用用用用空空空空间间间间冗冗冗冗余余余余度度度度压压压压缩缩缩缩图图图图像像像像的的的的方方方方法法法法，对对对对某某某某些些些些相相相相同同同同灰灰灰灰度度度度级级级级成成成成片片片片连连连连续续续续出出出出现现现现的的的的图图图图形形形形，行行行行程程程程编编编编码码码码也也也也是是是是一一一一种种种种高高高高效效效效的的的的编编编编码码码码方方方方法法法法。特特特特别别别别是是是是对对对对二值图像，效果尤为显著。二值图像，效果尤为显著。二值图像，效果尤为显著。二值图像，效果尤为显著。n n具有相同颜色并且是连续的象素数目称为行程长度。具有相同颜色并且是连续的象素数目称为行程长度。具有相同颜色并且是连续的象素数目称为行程长度。具有相同颜色并且是连续的象素数目称为行程长度。36一行图像行程编码示意图一行图像行程编码示意图一行图像行程编码示意图一行图像行程编码示意图 376.3 LZW6.3 LZW算法算法 38LZWLZW编码算法的具体执行步骤如下：编码算法的具体执行步骤如下：步步步步骤骤骤骤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=C(P=C(即现在的即现在的P P仅包含一个字符仅包含一个字符C);C);步骤步骤4 4：判断输入字符流中是否还有码字要编码判断输入字符流中是否还有码字要编码(1)(1)如果如果“是是”，就返回到步骤，就返回到步骤2 2；(2)(2)如果如果“否否”把当前前缀把当前前缀P P的码字输出到码字流的码字输出到码字流;结束。结束。39位置位置位置位置 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 CA B B A B A B A CA B B A B A B A CA B B A B A B A C 步骤步骤步骤步骤 位置位置位置位置 词典词典词典词典 输出输出输出输出 (1)(1)(1)(1)A A A 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 (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)例例例例6 6。8 8406.4 6.4 预测编码预测编码 41无损预测编码系统无损预测编码系统无损预测编码系统无损预测编码系统 42预测误差预测误差预测误差预测误差 线性预测线性预测线性预测线性预测 是预测系数是预测系数是预测系数是预测系数 43n在在图像数据压缩中，常用如下几种线性预测方案：图像数据压缩中，常用如下几种线性预测方案：n（1 1）前值预测，即）前值预测，即n（2 2）一维预测，即用同一扫描行的前面几个采样值预测。一维预测，即用同一扫描行的前面几个采样值预测。n（3 3）二二维维预预测测，即即不不但但用用同同一一扫扫描描行行的的前前面面几几个个采采样样值值，还要用前几行中的采样值一起来预测。还要用前几行中的采样值一起来预测。44对对对对LenaLenaLenaLena图像进行无损的一阶预测编码和解码图像进行无损的一阶预测编码和解码图像进行无损的一阶预测编码和解码图像进行无损的一阶预测编码和解码 例例例例6 6。9 9预测误差图像预测误差图像预测误差图像预测误差图像 45（b)b)b)b)原图直方图原图直方图原图直方图原图直方图 （c c c c）预测误差直预测误差直预测误差直预测误差直 例例例例6 6。9 946有损预测编码系统有损预测编码系统有损预测编码系统有损预测编码系统 47考虑一维预测考虑一维预测考虑一维预测考虑一维预测前值预测器前值预测器前值预测器前值预测器 48n n 德德德德尔尔尔尔塔塔塔塔调调调调制制制制是是是是一一一一种种种种简简简简单单单单的的的的有有有有损损损损预预预预测测测测编编编编码方法，其预测器和量化器定义如下：码方法，其预测器和量化器定义如下：码方法，其预测器和量化器定义如下：码方法，其预测器和量化器定义如下：49例例例例6 6。1111预测误差图像预测误差图像预测误差图像预测误差图像 解码后图像解码后图像解码后图像解码后图像rmesrmesrmesrmes=25.5558=25.5558=25.5558=25.5558 50级248isitisitisiti10.7071.1020.3950.5040.22221.8101.1810.78532.2851.57642.9941.4141.0870.731单位方差拉普拉斯概率密度的单位方差拉普拉斯概率密度的单位方差拉普拉斯概率密度的单位方差拉普拉斯概率密度的Lloyd-MaxLloyd-MaxLloyd-MaxLloyd-Max量化器量化器量化器量化器 51三种量化器的效果比较三种量化器的效果比较三种量化器的效果比较三种量化器的效果比较 预测编码的效果图预测编码的效果图预测编码的效果图预测编码的效果图 预测误差图预测误差图预测误差图预测误差图预测编码的误差图预测编码的误差图预测