1、2022-12-71多媒体技术多媒体技术22022-12-7第第6章章 多媒体数据压缩多媒体数据压缩常用的无损数据压缩方法常用的无损数据压缩方法6.3常用的有损数据压缩方法常用的有损数据压缩方法6.4多媒体数据压缩概述多媒体数据压缩概述 6.1数据压缩的技术基础数据压缩的技术基础 6.232022-12-76.1 多媒体数据压缩概述多媒体数据压缩概述v6.1.1 多媒体数据压缩的必要性多媒体数据压缩的必要性 原始采样的媒体数据量巨大原始采样的媒体数据量巨大 有效利用存储器存储容量有效利用存储器存储容量 提高通信线路的传输效率提高通信线路的传输效率 消除计算机系统处理视频消除计算机系统处理视频I
2、/O瓶颈瓶颈42022-12-76.1 多媒体数据压缩概述多媒体数据压缩概述v6.1.2 多媒体数据压缩的可能性多媒体数据压缩的可能性 常见的图像数据冗余种类：常见的图像数据冗余种类：空间冗余空间冗余 时间冗余时间冗余 结构冗余结构冗余 知识冗余知识冗余 视觉冗余视觉冗余52022-12-7空间冗余空间冗余v在任何一幅图像中，均有由许多在任何一幅图像中，均有由许多灰度或颜灰度或颜色色都相同的邻近像素组成的区域，它们形都相同的邻近像素组成的区域，它们形成了一个性质相同的集合块，即它们相互成了一个性质相同的集合块，即它们相互之间具有空间上的强相关性，在图像中就之间具有空间上的强相关性，在图像中就表
3、现为空间冗余。表现为空间冗余。例如，一块表面颜色均匀的区域中所有点的光强和色彩以及饱和度都是相同的，这就是空间冗余。62022-12-7时间冗余时间冗余v这是序列图像（电视图像、运动图像）表这是序列图像（电视图像、运动图像）表示中经常包含的冗余。图像示中经常包含的冗余。图像序列中两幅相序列中两幅相邻的图像有较大的相关邻的图像有较大的相关，这反映为时间冗，这反映为时间冗余。余。运动图像的相邻帧往往包含相同的背景和移动物体，只不过物体所在的位置略有不同，由于相邻帧记录了相邻时刻的同一场景，所以称为时间冗余。72022-12-7结构冗余结构冗余v在有些图像的纹理区，在有些图像的纹理区，图像的像素值图
4、像的像素值存在存在着明显的分布模式。着明显的分布模式。例如，方格状的板图案等，我们称此为结构冗例如，方格状的板图案等，我们称此为结构冗余。已知分布模式，可以通过某一过程生成图余。已知分布模式，可以通过某一过程生成图像。像。82022-12-7知识冗余知识冗余v有些有些图像的理解与某些知识图像的理解与某些知识有相当大的有相当大的相相关关性。例如：狗的图像有固定的结构，狗性。例如：狗的图像有固定的结构，狗有四条腿，头部有眼、鼻、耳朵，有尾巴有四条腿，头部有眼、鼻、耳朵，有尾巴等。这类规律性的结构可由先验知识和背等。这类规律性的结构可由先验知识和背景知识得到，我们称此类冗余为知识冗余。景知识得到，我
5、们称此类冗余为知识冗余。92022-12-7视觉冗余视觉冗余v人类的视觉系统对图像场的人类的视觉系统对图像场的敏感度敏感度是非均是非均匀的。但是，在记录原始的图像数据时，匀的。但是，在记录原始的图像数据时，通常假定视觉系统近似线性的和均匀的，通常假定视觉系统近似线性的和均匀的，对视觉敏感和不敏感的部分同等对待，从对视觉敏感和不敏感的部分同等对待，从而产生比理想编码（即把视觉敏感和不敏而产生比理想编码（即把视觉敏感和不敏感的部分区分开来的编码）更多的数据，感的部分区分开来的编码）更多的数据，这就是视觉冗余。这就是视觉冗余。人类视觉系统的一般分辨能力估计为人类视觉系统的一般分辨能力估计为26灰度灰
6、度等等级，而一般图像的量化采用的是级，而一般图像的量化采用的是28的灰度的灰度等级。等级。这也被称之为视觉冗余。这也被称之为视觉冗余。102022-12-76.1 多媒体数据压缩概述多媒体数据压缩概述v6.1.3 多媒体数据压缩的原理多媒体数据压缩的原理v1.1.图像数据压缩的主要依据有两个图像数据压缩的主要依据有两个 一是图像数据中有许多一是图像数据中有许多重复的数据重复的数据，使用数学，使用数学方法来表示这些重复数据就可以减少数据量；方法来表示这些重复数据就可以减少数据量；另一个依据是另一个依据是人眼睛对图像细节和颜色的辨认人眼睛对图像细节和颜色的辨认有一个有一个极限极限，把超过极限的部分
7、去掉，这也就，把超过极限的部分去掉，这也就达到了数据压缩的目的。达到了数据压缩的目的。基于数据冗余基于数据冗余的压缩技术是的压缩技术是无损压缩技术无损压缩技术基于人眼视觉特基于人眼视觉特性的压缩技术是性的压缩技术是有损压缩技术有损压缩技术112022-12-76.1.3 多媒体数据压缩的原理多媒体数据压缩的原理v2.图像压缩说明图像压缩说明 视频压缩与语音相比，语音的数据量较小，且视频压缩与语音相比，语音的数据量较小，且基本压缩方法已经成熟，目前的数据压缩研究基本压缩方法已经成熟，目前的数据压缩研究主要集中于图像和视频信号的压缩方面。主要集中于图像和视频信号的压缩方面。压缩处理过程有两个过程，
8、编码过程是将原始压缩处理过程有两个过程，编码过程是将原始数据经过编码进行压缩，以便存储与传输；解数据经过编码进行压缩，以便存储与传输；解码过程是对编码数据进行解码，还原为可以使码过程是对编码数据进行解码，还原为可以使用的数据。用的数据。122022-12-76.1.3 多媒体数据压缩的原理多媒体数据压缩的原理v3.与压缩相关的指标与压缩相关的指标 衡量一种数据压缩技术的好坏有四个重要的指衡量一种数据压缩技术的好坏有四个重要的指标：标：压缩比大：即压缩前后所需要的信息存储量之比压缩比大：即压缩前后所需要的信息存储量之比要大。要大。算法简单：实现压缩的算法简单，压缩、解压速算法简单：实现压缩的算法
9、简单，压缩、解压速度快，尽可能地做到实时压缩解压。度快，尽可能地做到实时压缩解压。恢复效果好：恢复效果好，要尽可能地恢复原始恢复效果好：恢复效果好，要尽可能地恢复原始数据。数据。压缩能否用硬件实现。压缩能否用硬件实现。132022-12-76.1.3 多媒体数据压缩的原理多媒体数据压缩的原理142022-12-76.1.3 多媒体数据压缩的原理多媒体数据压缩的原理v 冗余压缩法冗余压缩法 也称无损压缩法，是指使用压缩后的数据可以也称无损压缩法，是指使用压缩后的数据可以解压缩，且解压之后的数据与原来的数据完全解压缩，且解压之后的数据与原来的数据完全相同。它利用数据的统计冗余进行压缩，可完相同。它
10、利用数据的统计冗余进行压缩，可完全恢复原始数据而不引入任何失真，但压缩率全恢复原始数据而不引入任何失真，但压缩率受到数据统计冗余度的理论限制，一般为受到数据统计冗余度的理论限制，一般为2:1到到5:1。152022-12-76.1.3 多媒体数据压缩的原理多媒体数据压缩的原理v 熵压缩法熵压缩法 也称有损压缩法，有失真压缩，是指使用压缩也称有损压缩法，有失真压缩，是指使用压缩后的数据进行解压缩，解压之后的数据与原来后的数据进行解压缩，解压之后的数据与原来的数据有所不同，但不会让人对原始资料表达的数据有所不同，但不会让人对原始资料表达的信息造成误解。的信息造成误解。162022-12-76.1.
11、3 多媒体数据压缩的原理多媒体数据压缩的原理v 熵压缩法与冗余压缩法的比较熵压缩法与冗余压缩法的比较 在图像压缩系统组成中，变换和编码是无损耗在图像压缩系统组成中，变换和编码是无损耗的，而量化是有损耗的。无损压缩方法仅利用的，而量化是有损耗的。无损压缩方法仅利用了统计冗余，而没有利用量化器。有损压缩方了统计冗余，而没有利用量化器。有损压缩方法既利用了统计冗余又采用了量化器，利用了法既利用了统计冗余又采用了量化器，利用了心理视觉冗余。心理视觉冗余。172022-12-76.1.4 数据压缩方法的分类数据压缩方法的分类v1.根据编、解码后数据根据编、解码后数据是否一致是否一致来进行分来进行分类，数
12、据压缩的方法一般被划分为两类：类，数据压缩的方法一般被划分为两类：可逆编码（无损编码）可逆编码（无损编码）。此种方法的解码图像。此种方法的解码图像与原始图像严格相同，压缩比大约在与原始图像严格相同，压缩比大约在2:15:1之之间。主要编码有间。主要编码有Huffman编码编码、算术编码算术编码、行行程长度编码程长度编码等。等。不可逆编码（有损编码）不可逆编码（有损编码）。此种方法的解码图。此种方法的解码图像与原始图像存在一定的误差，但视觉效果一像与原始图像存在一定的误差，但视觉效果一般可以接受，压缩比可以从几倍到上百倍调节。般可以接受，压缩比可以从几倍到上百倍调节。常用的编码有常用的编码有变换
13、编码变换编码和和预测编码预测编码。182022-12-76.1.4 数据压缩方法的分类数据压缩方法的分类v2.根据压缩方法的原理，可将其具体划分根据压缩方法的原理，可将其具体划分为以下几种：为以下几种：量化与向量量化编码量化与向量量化编码 预测编码预测编码 变换编码变换编码 信息熵编码信息熵编码 混合编码混合编码 变换编码与预测编码相结合变换编码与预测编码相结合192022-12-7量化与向量量化编码量化与向量量化编码v对像元点进行量化时，除了每次仅量化一对像元点进行量化时，除了每次仅量化一个点的方法外，也可以考虑一次量化多个个点的方法外，也可以考虑一次量化多个点的做法，这种方法称为向量量化。
14、即利点的做法，这种方法称为向量量化。即利用相邻数据间的相关性，将数据系列分组用相邻数据间的相关性，将数据系列分组进行量化。进行量化。202022-12-7预测编码预测编码v预测编码预测编码 预测编码是根据离散信号之间存在着一定关联预测编码是根据离散信号之间存在着一定关联性的特点，利用前面一个或多个信号预测下一性的特点，利用前面一个或多个信号预测下一个信号进行，然后对实际值和预测值的差（预个信号进行，然后对实际值和预测值的差（预测误差）进行编码。如果预测比较准确，误差测误差）进行编码。如果预测比较准确，误差就会很小。在同等精度要求的条件下，就可以就会很小。在同等精度要求的条件下，就可以用比较少的
15、比特进行编码，达到压缩数据的目用比较少的比特进行编码，达到压缩数据的目的。的。如：增量调制（如：增量调制（DM）、差分脉冲编码调制）、差分脉冲编码调制（DPCM）、自适应增量调制（）、自适应增量调制（ADPCM）等。）等。主要用于声音编码。主要用于声音编码。212022-12-7变换编码变换编码v变换编码变换编码 将图像将图像时域信号转换为频域信号时域信号转换为频域信号进行处理。数进行处理。数据处理时可以将主要的注意力集中在相对较小据处理时可以将主要的注意力集中在相对较小的区域，从而实现数据压缩。的区域，从而实现数据压缩。一般采用正交变换，如：离散余弦变换（一般采用正交变换，如：离散余弦变换（
16、DCT）、）、离散傅立叶变换（离散傅立叶变换（DFT）222022-12-7信息熵编码信息熵编码v信息熵原理信息熵原理 让出现概率大的信号用较短的码字表示，反之让出现概率大的信号用较短的码字表示，反之用较长的码字表示。用较长的码字表示。v常见的编码方法常见的编码方法 Huffman编码编码 Shannon编码编码 算术编码算术编码232022-12-76.2 数据压缩的技术基础数据压缩的技术基础v6.2.1 熵的概念熵的概念 表示一条信息中真正需要编码的信息量，即数表示一条信息中真正需要编码的信息量，即数据压缩的理论极限。据压缩的理论极限。对于任何一种无损数据压缩，最终的数据量一对于任何一种无
17、损数据压缩，最终的数据量一定大于信息熵，数据量越接近于熵值，说明其定大于信息熵，数据量越接近于熵值，说明其压缩效果越好。压缩效果越好。242022-12-76.2 数据压缩的技术基础数据压缩的技术基础v6.2.2 信息熵的计算信息熵的计算 1.信息量信息量 信息量是指从信息量是指从N个等概率事件中选出一个事件所需个等概率事件中选出一个事件所需要的信息含量。要的信息含量。设从设从N个数中选定任一个数个数中选定任一个数xj的概率为的概率为p(xj)，假定选，假定选定任意一个数的概率都相等，即定任意一个数的概率都相等，即p(xj)1/N，因此定，因此定义信息量如下：义信息量如下：)()(log1lo
18、glog)(222jjjxpIxpNNxI概率相等概率相等概率不等概率不等252022-12-76.2.2 信息熵的计算信息熵的计算v2.信息熵信息熵:平均信息量平均信息量 信源信源X发出的发出的xj（j=1,2,n）共共n个随机事件，个随机事件，每个事件产生的平均信息量为：每个事件产生的平均信息量为：H(X)称为信源称为信源X的的“熵熵”，即信源，即信源X发出任意发出任意一个随机变量的平均信息量。一个随机变量的平均信息量。其中：等概率事件的熵最大，假设有其中：等概率事件的熵最大，假设有N个事件，则个事件，则此时熵为：此时熵为：njjjjxPxPxIEXH12)(log)()()(NNNXHN
19、j221log1log1)(最大熵最大熵概率概率信息量信息量262022-12-76.2.3 信息熵的范围信息熵的范围v当当P(x1)1时，时，P(x2)P(x3)P(xj)0，则此时熵为：则此时熵为：v由上可得熵的范围为：由上可得熵的范围为：0)(log)()(121xPxPXHNXH2log)(0最小熵最小熵272022-12-76.2.4 平均码长平均码长v在编码中用在编码中用熵值熵值来衡量是否为最佳编码。若来衡量是否为最佳编码。若以以Lc表示编码器输出码字的平均码长，则当表示编码器输出码字的平均码长，则当 LcH(X)有冗余，不是最佳。有冗余，不是最佳。LcH(X)不可能。不可能。Lc
20、H(X)最佳编码（最佳编码（Lc稍大于稍大于H(X)）。）。熵值为平均码长熵值为平均码长Lc的下限。的下限。v平均码长平均码长Lc的计算公式为：的计算公式为：njjjcxLxPL1)()(（j=1,2,n）其中：其中：P(xj)是信源是信源X发出发出xj的概率，的概率，L(xj)为为xj的编码长。的编码长。282022-12-76.2.5 冗余度、编码效率与压缩比冗余度、编码效率与压缩比 v在数字图像通信系统中，在数字图像通信系统中，冗余度冗余度、编码效编码效率率与与压缩比压缩比是是衡量信源特性衡量信源特性以及以及编解码设编解码设备性能备性能的重要指标。的重要指标。设原图像的平均码长为设原图像
21、的平均码长为L，熵为熵为H(X)，压缩后压缩后图像的平均码长为图像的平均码长为Lc，则编码效率为：则编码效率为：冗余度为：冗余度为：1-压缩比为：压缩比为：1)(XHLRRLXH11)(cLLC LcRLXH11)(292022-12-76.3 常用的无损数据压缩方法常用的无损数据压缩方法v6.3.1 Huffman编码编码v6.3.2 算术编码算术编码v6.3.3 行程行程RLE编码编码v6.3.4 词典编码词典编码302022-12-76.3.1 Huffman编码编码v基本原理基本原理 依据信源字符出现的概率大小来构造代码，对依据信源字符出现的概率大小来构造代码，对出现概率较大出现概率较
22、大的信源字符，的信源字符，给予较短码长给予较短码长，而，而对于对于出现概率较小出现概率较小的信源字符，给予的信源字符，给予较长的码较长的码长长，最后使得编码的平均码字最短。，最后使得编码的平均码字最短。312022-12-76.3.1 Huffman编码编码v具体的编码步骤具体的编码步骤 将信源出现的概率由大到小排序。将信源出现的概率由大到小排序。将两处最小概率组合相加，形成新概率。将两处最小概率组合相加，形成新概率。将新概率与未编码的字符一起重新排序。将新概率与未编码的字符一起重新排序。重复步骤重复步骤2、3，直到出现的概率和为，直到出现的概率和为1。分配代码分配代码 代码分配从最后一步开始
23、反向进行，对最后两个概代码分配从最后一步开始反向进行，对最后两个概率率一个赋予一个赋予0代码，一个赋予代码，一个赋予1代码代码。记录下从树的。记录下从树的根到每个信源符号终节点的根到每个信源符号终节点的0和和1序列。序列。至于哪个为至于哪个为“1”哪个哪个为为“0”则无关紧要，则无关紧要，最后的结果仅仅是分最后的结果仅仅是分配的代码不同，而代配的代码不同，而代码的平均长度是相同码的平均长度是相同的。的。322022-12-76.3.1 Huffman编码编码vHuffman编码中求平均码长的方法：编码中求平均码长的方法：概率概率码长码长332022-12-76.3.1 Huffman编码编码v
24、Huffman编码练习一编码练习一:设输入图像的灰度级设输入图像的灰度级a1,a2,a3,a4,a5,a6出现的出现的概率分别是概率分别是0.4、0.2、0.12、0.15、0.1、0.03。试进行哈夫曼编码，并计算试进行哈夫曼编码，并计算平均码字长度平均码字长度。342022-12-76.3.1 Huffman编码编码vHuffman编码练习二编码练习二:信源符号的概率如下，请按要求作答：信源符号的概率如下，请按要求作答：画出其画出其Huffman编码的编码树编码的编码树 给出各信源符号的码字与码长给出各信源符号的码字与码长 计算该信源的平均码长。计算该信源的平均码长。（说明：大概率符号赋予
25、（说明：大概率符号赋予0，小概率符号赋予，小概率符号赋予l，相，相同概率情况下上面的是同概率情况下上面的是0，下面的是，下面的是1。）。）XX1X2X3X4X5X6P(X)0.35 0.25 0.200.10.05 0.05352022-12-7Huffman编码练习一答案编码练习一答案最终编码结果为：最终编码结果为：a1=1,a2=011,a3=001,a4=010,a5=0001,a6=00001010010362022-12-7Huffman编码练习一答案编码练习一答案v据公式图像信源熵为：据公式图像信源熵为：H(X)=-(0.4log20.4+0.2log20.2+0.12log20.
26、12+0.15log20.15+0.1log20.1+0.03log20.03)=2.25 bit v根据哈夫曼编码结果，平均码字长度：根据哈夫曼编码结果，平均码字长度：Lc=0.41+0.23+0.153+0.123+0.14+0.034=2.33v编码效率、压缩比和冗余度分别为：编码效率、压缩比和冗余度分别为：96.6%、1.2、3.4%njjjxPxP12)(log)(%6.9633.225.2LHc2.133.23Cr=1-=3.4%372022-12-7Huffman编码练习二答案编码练习二答案382022-12-76.3.1 Huffman编码编码vHuffman编码注意事项编码注
27、意事项 哈夫曼编码没有错误保护功能，在译码时，如哈夫曼编码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个的正果码串中没有错误，那么就能一个接一个的正确译出代码。但如果码串中有错误，哪怕仅是确译出代码。但如果码串中有错误，哪怕仅是1位出现错误，不但这个码本身译错，后面的位出现错误，不但这个码本身译错，后面的译码可能全错，这种现象称为译码可能全错，这种现象称为错误传播错误传播（Error Propagation）。）。哈夫曼编码是可变长度码，很难随意查找或调哈夫曼编码是可变长度码，很难随意查找或调用压缩文件中间的内容，然后再译码，这就需用压缩文件中间的内容，然后再译码，这就需要
28、在存储代码之前加以考虑。要在存储代码之前加以考虑。392022-12-76.3.2 算术编码算术编码v算术编码（算术编码（arithmetic coding AC）是利用）是利用0和和1之间的间隔来表示信源编码的一种方法，之间的间隔来表示信源编码的一种方法，其编码值是间隔的上、下限包含的相同二其编码值是间隔的上、下限包含的相同二进制。编码过程中的间隔决定了符号压缩进制。编码过程中的间隔决定了符号压缩后的输出。后的输出。v算术编码用到两个基本的参数算术编码用到两个基本的参数 符号的概率和它的编码间隔。符号的概率和它的编码间隔。v信源符号的信源符号的概率决定概率决定压缩编码的压缩编码的效率效率，也
29、，也决定编码过程中信源符号的决定编码过程中信源符号的间隔间隔，而这些，而这些间隔包含在间隔包含在0到到1之间。之间。402022-12-76.3.2 算术编码算术编码v编码过程编码过程:设信源符号为设信源符号为A,B,C,D，其概率分别为，其概率分别为 0.1,0.4,0.2,0.3，按概率可把间隔，按概率可把间隔0,1分成分成4个子个子间隔：间隔：0,0.1),0.1,0.5),0.5,0.7),0.7,1，其，其中中x,y)表示半开放间隔，即包含表示半开放间隔，即包含x不包含不包含y，如，如下表所示。下表所示。符号符号ABCD概率概率0.10.40.20.3初始编码间初始编码间隔隔0,0.
30、1)0.1,0.5)0.5,0.7)0.7,1412022-12-76.3.2 算术编码算术编码v如果消息序列的输入为：如果消息序列的输入为：CADACDB，其，其编码过程如下：编码过程如下：首先输入的符号是首先输入的符号是C，找到它的编码范围是，找到它的编码范围是0.5,0.7)；由于消息中第由于消息中第2个符号个符号A的编码范围是的编码范围是0,0.1)，因此它的间隔就取因此它的间隔就取0.5,0.7)的第一个的第一个1/10作为作为新间隔新间隔0.5,0.52)；编码第编码第3个符号个符号D时取新间隔为时取新间隔为0.514,0.52)；编码第编码第4个符号个符号A时，取新间隔为时，取新
31、间隔为0.514,0.5146)，。422022-12-76.3.2 算术编码算术编码符号符号ABCD概率概率0.10.40.20.3初始编码间初始编码间隔隔0,0.1)0.1,0.5)0.5,0.7)0.7,1432022-12-76.3.2 算术编码算术编码v消息的编码输出可以是最后一个间隔中的任消息的编码输出可以是最后一个间隔中的任意数，整个编码过程如下图所示。最后在意数，整个编码过程如下图所示。最后在0.5143876,0.514402)中选择一个数作为编码中选择一个数作为编码输出值：输出值：0.51439。v解码时，解码器由编码输出值：解码时，解码器由编码输出值：0.51439，可，
32、可马上解得一个字符为马上解得一个字符为C，然后依次得到唯一，然后依次得到唯一解解A,D,A,C,D,B。442022-12-76.3.2 算术编码算术编码步步骤骤译码间隔译码间隔译译码码10.51439在间隔 0.5,0.7)1020.51439在间隔 0.5,0.7)的第1个1/100030.51439在间隔0.5,0.52)的第7个1/101140.51439在间隔0.514,0.52)的第1个1/100050.51439在间隔0.514,0.5146)的第5个1/101060.51439在间隔0.5143,0.51442)的第7个1/101170.51439在间隔0.51439,0.51
33、43948)的第1个1/10018译码消息：10 00 11 00 10 11 01 译码过程如下：译码过程如下：452022-12-76.3.2 算术编码算术编码v在算术编码中需要注意的几个问题：在算术编码中需要注意的几个问题：由于计算机精度不可能无限长，运算中容易出现由于计算机精度不可能无限长，运算中容易出现溢出，但多数机器都有溢出，但多数机器都有16位、位、32位或者位或者64位的精位的精度，因此可使用比例缩放方法解决。度，因此可使用比例缩放方法解决。算术编码器对整个消息只产生一个码字，这个码算术编码器对整个消息只产生一个码字，这个码字是在间隔字是在间隔0,1)中的一个实数，因此译码器在
34、中的一个实数，因此译码器在接受到所有位之前不能进行译码。接受到所有位之前不能进行译码。算术编码也是一种对错误很敏感的编码方法，如算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。果有一位发生错误就会导致整个消息译错。462022-12-76.3.2 算术编码算术编码v算术编码练习一算术编码练习一:假设有假设有4个符号的信源，它门的概率如下表所个符号的信源，它门的概率如下表所示：示：输入序列为输入序列为Xn:a2,a1,a3,。试画出它的编码过程试画出它的编码过程 信源符号信源符号aia1a2a3a4概率概率PiP10.5P20.25P30.125P40.125初始
35、编码间隔初始编码间隔0,0.5)0.5,0.75)0.75,0.875)0.875,1)472022-12-76.3.2 算术编码算术编码v算术编码练习二：算术编码练习二：假设信源符号为假设信源符号为1,0，如果消息序列的输入为，如果消息序列的输入为1101。这些符号的概率分别为。这些符号的概率分别为:v画出其编码过程！画出其编码过程！信源信源01概率概率1/43/4编码间编码间隔隔0,1/4)1/4,1482022-12-7算术编码练习一答案算术编码练习一答案492022-12-7算术编码练习二答案算术编码练习二答案502022-12-76.3.3 行程长度编码行程长度编码 vRLE（Run
36、-Length Encoding）是一个针对）是一个针对包含有顺序排列的多次重复的数据的压缩包含有顺序排列的多次重复的数据的压缩方案。其原理就是把一系列的重复值用一方案。其原理就是把一系列的重复值用一个单独的值再加上一个计数值来取代，个单独的值再加上一个计数值来取代，行行程长度程长度就是就是连续且重复的单元连续且重复的单元数目。如果数目。如果想得到原始数据，只需展开这个编码就可想得到原始数据，只需展开这个编码就可以了。以了。512022-12-76.3.3 行程长度编码行程长度编码v例如，计算机制作图像中，不需要存储每例如，计算机制作图像中，不需要存储每一个像素的颜色值，而一个像素的颜色值，而
37、仅存储一个像素的仅存储一个像素的颜色值以及具有相同颜色的像素数目颜色值以及具有相同颜色的像素数目就可就可以，以，或者存储一个像素的颜色值，以及具或者存储一个像素的颜色值，以及具有相同颜色值的行数有相同颜色值的行数，这种压缩编码称为这种压缩编码称为行程编码。具有相同颜色的连续的像素数行程编码。具有相同颜色的连续的像素数目称为行程长度。目称为行程长度。522022-12-76.3.3 行程长度编码行程长度编码v如图所示，假定一幅灰度图像，第如图所示，假定一幅灰度图像，第n行的像行的像素值为：素值为：v用用RLE编码方法得到的代码为：编码方法得到的代码为：3150841160。代码。代码红色斜体红色
38、斜体表示的数字是表示的数字是行程长度，后面的数字代表像素的颜色值。行程长度，后面的数字代表像素的颜色值。例如例如红色斜体红色斜体字字50代表有连续代表有连续50个像素具个像素具有相同的颜色值，它的颜色值是有相同的颜色值，它的颜色值是8。532022-12-76.3.3 行程长度编码行程长度编码v对比对比RLE编码前后的代码数可以发现，在编码前后的代码数可以发现，在编码前要用编码前要用73个代码表示这一行的数据，个代码表示这一行的数据，而编码后只要用而编码后只要用10个代码表示代表原来的个代码表示代表原来的73个代码，压缩前后的数据量之比约为个代码，压缩前后的数据量之比约为7:1，即压缩比为即压
39、缩比为7:1。这说明这说明RLE确实是一种压确实是一种压缩技术，而且编码技术实用缩技术，而且编码技术实用。542022-12-76.3.3 行程长度编码行程长度编码vRLE的性能好坏主要取决于图像本身的特的性能好坏主要取决于图像本身的特点。点。RLE压缩编码尤其适用于计算机生成压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常的图像，对减少图像文件的存储空间非常有效。有效。v然而，由于颜色丰富的自然图像在同一行然而，由于颜色丰富的自然图像在同一行上具有相同颜色的连续像素往往很少，上具有相同颜色的连续像素往往很少，而而连续几行都具有相同颜色值的连续行数就连续几行都具有相同颜色值的连
40、续行数就更少，如果仍然使用更少，如果仍然使用RLE编码方法，不仅编码方法，不仅不能压缩图像数据，反而可能使原来的图不能压缩图像数据，反而可能使原来的图像数据变得更大。像数据变得更大。552022-12-76.3.3 行程长度编码行程长度编码v译码时按照与编码时采用的相同规则进行，译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相还原后得到的数据与压缩前的数据完全相同。因此，同。因此，RLE属于无损压缩技术。属于无损压缩技术。v它被用于它被用于BMP、JPEG/MPEG、TIFF和和PDF等编码之中，还被用于传真机。等编码之中，还被用于传真机。562022-12-76.3
41、.4 词典编码词典编码v词典编码属于词典编码属于无损压缩技术无损压缩技术，其根据是，其根据是数数据本身包含有重复代码序列据本身包含有重复代码序列这个特性。词这个特性。词典编码的种类较多，归纳起来有两类。典编码的种类较多，归纳起来有两类。第一类词典编码第一类词典编码 LZ77、LZSS 第二类词典编码第二类词典编码 LZ78、LZW572022-12-7第一类词典编码第一类词典编码v第一类词典编码的基本思想是第一类词典编码的基本思想是查找正在压查找正在压缩的字符序列是否在前面输入的数据中出缩的字符序列是否在前面输入的数据中出现过现过，如果是，则用指向早期出现过的字，如果是，则用指向早期出现过的字
42、符串的符串的“指针指针”替代重复的字符串。替代重复的字符串。582022-12-7第一类词典编码第一类词典编码v这里所指的这里所指的“词典词典”是指是指用以前处理过的用以前处理过的数据来表示编码过程中遇到的重复部分数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以这类编码中的所有算法都是以Abraham Lempel和和Jakob Ziv在在1977年开发和发表的称年开发和发表的称为为LZ77算法算法为基础的。为基础的。LZSS算法算法LZ77的改进方法的改进方法592022-12-7LZ77算法算法v输入数据流输入数据流(input stream):待压缩的字符序列待压缩的字符序
43、列v字符字符(character):输入数据流中的基本单元。输入数据流中的基本单元。v编码位置编码位置(coding position):输入数据流中当前输入数据流中当前要编码的字符位置，要编码的字符位置，前向缓冲器前向缓冲器的开始字符。的开始字符。v前向缓冲器前向缓冲器(lookahead buffer):存放从编码位置存放从编码位置到输入数据流结束的字符序列的存储器。到输入数据流结束的字符序列的存储器。v窗口窗口(Window):包含包含W个字符的窗口，字符从个字符的窗口，字符从编码位置开始向后数。编码位置开始向后数。v指针指针(Pointer):指向窗口中的匹配串且含长度。指向窗口中的匹
44、配串且含长度。602022-12-7LZ77算法算法vLZ77编码算法的核心是查找编码算法的核心是查找从前向缓冲器从前向缓冲器开开始的最长的匹配串。具体执行步骤如下：始的最长的匹配串。具体执行步骤如下：把编码位置设置到输入数据流的开始。把编码位置设置到输入数据流的开始。查找窗口中最长的匹配串。查找窗口中最长的匹配串。输出输出(Pointer，Length)Characters，其中，其中Pointer是指向窗口中匹配串的指针，是指向窗口中匹配串的指针，Length表示匹配字表示匹配字符的长度，符的长度，Characters是前向缓冲器中第是前向缓冲器中第1个不匹个不匹配的字符。配的字符。如果前
45、向缓冲器不是空的，则把编码位置和窗口如果前向缓冲器不是空的，则把编码位置和窗口向前移向前移Length+1个字符，然后返回到步骤个字符，然后返回到步骤2。612022-12-7LZ77算法算法待编码的待编码的数据流数据流 位置位置1 2 3 4 5 6 7 8 9 10 字符字符 A A B C B B A B CC编码过程编码过程 步骤步骤 位置位置 匹配串匹配串 字符字符输出输出1 1-A(0，0)A 2 2 A B(1，1)B 34-C(0，0)C 45 B B(2，1)B 57 A B C C(5，3)C 告诉译码告诉译码器回退器回退5个个字符字符,然后然后拷贝拷贝3个字个字符符“AB
46、C”622022-12-7LZ77算法算法v“步骤步骤”栏表示编码步骤。栏表示编码步骤。v“位置位置”栏表示编码位置。栏表示编码位置。v“匹配匹配”栏表示窗口中找到的最长的匹配串。栏表示窗口中找到的最长的匹配串。v“字符字符”栏表示匹配之后在前向缓冲器中的第栏表示匹配之后在前向缓冲器中的第1个字个字符符v“输出输出”栏以栏以(Back_chars，Chars_length)Explicit_character格式输出。格式输出。其中其中(Back_chars，Chars_length)是指指向匹配串的指针，是指指向匹配串的指针，告诉译码器告诉译码器“在这个窗口中向后退在这个窗口中向后退Back
47、_chars个字符然后拷个字符然后拷贝贝Chars_length个字符到输出个字符到输出”，Explicit_character是真实是真实字符。字符。例如，输出例如，输出“(5，2)C”告诉译码器回退告诉译码器回退5个字符，然后拷贝个字符，然后拷贝2个字符个字符“AB”632022-12-7LZ77算法算法v解压算法解压算法 解码解码 当碰到编码字符串时，解压算法使用当碰到编码字符串时，解压算法使用，和，和，字段将编码替换成实际的正文字符串。，字段将编码替换成实际的正文字符串。642022-12-7LZ77 算法练习算法练习v给定一个报文给定一个报文:abcdbbccaaabaeaaabae
48、e，请用请用LZ77算法对该报文序列进行编码！算法对该报文序列进行编码！652022-12-7LZSS算法算法vLZ77冗余信息冗余信息 空指针空指针和和编码器可能输出额外的字符编码器可能输出额外的字符，这种字，这种字符可能包含在下一个匹配串中。符可能包含在下一个匹配串中。vLZSS算法以比较有效的方法解决这个问题，算法以比较有效的方法解决这个问题，它的思想是它的思想是如果匹配串的长度比指针本身如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字的长度长就输出指针，否则就输出真实字符。符。指针长度为指针长度为2662022-12-7LZSS算法算法v把编码位置置于输入数据流的开始位置
49、。把编码位置置于输入数据流的开始位置。v在前向缓冲存储器中查找与窗口中最长的匹配串在前向缓冲存储器中查找与窗口中最长的匹配串 Pointer：=匹配串指针。匹配串指针。Length：=匹配串长度。匹配串长度。v判断匹配串长度判断匹配串长度是否大于等于是否大于等于最小匹配串长度最小匹配串长度 如果如果“是是”：输出指针，然后把编码位置向前移动：输出指针，然后把编码位置向前移动Length个字符。个字符。如果如果“否否”：输出前向缓冲存储器中的第：输出前向缓冲存储器中的第1个字符，然个字符，然后把编码位置向前移动一个字符。后把编码位置向前移动一个字符。v如前向缓冲存储器不是空的，就返回到步骤如前向
50、缓冲存储器不是空的，就返回到步骤2。672022-12-7LZSS算法举例算法举例待编码的待编码的数据流数据流 位置位置1 2 3 4 5 6 7 8 9 1011 字符字符 A A B B C B B A ABC编码过程编码过程 步骤步骤位置位置 匹配串匹配串输出输出1 1-A 2 2 A A 33-B 44 B B 55-C 66BB(3,2)78AAB(7,3)811CC682022-12-7LZSS解码解码v与与LZ77一样完全可逆一样完全可逆692022-12-7LZSS算法算法v在相同的计算机环境下，在相同的计算机环境下，LZSS算法比算法比LZ77可获得比较高的压缩比，而译码同样
