多媒体通信技术四-修订

1、第四章第四章 视频信息压缩与处理视频信息压缩与处理第四章第四章 视频信息压缩与处理视频信息压缩与处理本章主要内容本章主要内容 图像信号的相关特点图像信号的相关特点 图像处理方法图像处理方法 各种实用编码各种实用编码 常见的图像压缩编码标准常见的图像压缩编码标准 图像信号的相关特点图像信号的相关特点 通常一幅图像中的各像素之间存在一定的通常一幅图像中的各像素之间存在一定的相关性。相关性。 在活动图像中，由于两幅相邻图像之间的时在活动图像中，由于两幅相邻图像之间的时间间隔很短，因此这两幅图像信息中包含大量间间隔很短，因此这两幅图像信息中包含大量相关信息。相关信息。 这些就是图像信息中的冗余。这些就

2、是图像信息中的冗余。 图像信号的相关特点图像信号的相关特点 多媒体数据压缩的目的就是要去除图像信多媒体数据压缩的目的就是要去除图像信息中的大量冗余，同时又能保证图像的质量。息中的大量冗余，同时又能保证图像的质量。 一般针对不同类型的冗余信息，采取不同的一般针对不同类型的冗余信息，采取不同的压缩方法。压缩方法。 1. 1.空间冗余空间冗余空间冗余是在图像数据中经常存在的一种冗余。空间冗余是在图像数据中经常存在的一种冗余。 在任何一幅图像中在任何一幅图像中： 均有许多灰度或颜色都均有许多灰度或颜色都相同的邻近像素相同的邻近像素组成的组成的局部区域局部区域，它们之间具有空间上的，它们之间具有空间上的

3、强相关性，在图像中就强相关性，在图像中就表现为空间冗余。表现为空间冗余。 1. 1.空间冗余空间冗余 颜色相同的区域颜色相同的区域 对空间冗余的压缩方法就是把这种对空间冗余的压缩方法就是把这种颜色都颜色都相相同的邻近像素组成的同的邻近像素组成的局部区域局部区域当作一个整体，当作一个整体，用极少的数据量来表示它，从而节省了存储空用极少的数据量来表示它，从而节省了存储空间。间。 这种压缩方法叫这种压缩方法叫空间压缩空间压缩或或帧内压缩帧内压缩。：视频信号和动画：视频信号和动画是基是基于时间轴的一组于时间轴的一组连续画面连续画面。 由于活动图像序列中的任意两幅相由于活动图像序列中的任意两幅相邻的图像

4、之间的时间间隔很短，因此两幅图像中邻的图像之间的时间间隔很短，因此两幅图像中存在大量的相关信息存在大量的相关信息 时间冗余时间冗余 相邻帧包含相同的背景和移动物体，只不过移相邻帧包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同动物体所在的空间位置略有不同 活动图像中的两幅相邻的图像有较大的相关活动图像中的两幅相邻的图像有较大的相关性，这反映为性，这反映为时间冗余时间冗余。 在前一幅图像的基础上，只需改变少量的数在前一幅图像的基础上，只需改变少量的数据，便可以表示出后一幅图像，达到数据压缩据，便可以表示出后一幅图像，达到数据压缩的目的。的目的。 这种压缩对活动图像往往能得到很高的压

5、缩比，这种压缩对活动图像往往能得到很高的压缩比，这也称为这也称为时间压缩时间压缩或或帧间压缩帧间压缩。3. 3.统计冗余统计冗余 空间冗余和时间冗余是将图像信号看作为随空间冗余和时间冗余是将图像信号看作为随机信号时所反映出的统计特征，因此有时把这机信号时所反映出的统计特征，因此有时把这两种冗余称为两种冗余称为统计冗余统计冗余。 4. 4.信息熵冗余信息熵冗余信息熵是针对数据的信息量而言的，它代表信息熵是针对数据的信息量而言的，它代表从图像信息源中发出的一个符号的平均信息量从图像信息源中发出的一个符号的平均信息量设某种编码的平均码长单位（符号）的设某种编码的平均码长单位（符号）的数据量数据量为为

6、式中，式中， 为分配给第为分配给第 符号的比特数，即符号的比特数，即二进制位数二进制位数niniiiiiSpSpSISpXH112)(log)()()()(niiiSlSpL1)()()(iSliS 由于实际中很难估算各符号出现的概率，我由于实际中很难估算各符号出现的概率，我们一般认为它们是等概率的，所以每个符号比们一般认为它们是等概率的，所以每个符号比特数相同。特数相同。 这种编码的符号的数据量这种编码的符号的数据量L L为最大。为最大。 但实际各符号出现的概率并不相同。但实际各符号出现的概率并不相同。 这样所得的这样所得的L L必然大于实际的信源熵必然大于实际的信源熵H H，由此，由此带来

7、的冗余我们称为带来的冗余我们称为信息熵冗余信息熵冗余或或编码冗余编码冗余。 )()()(21nSlSlSlniiiSlSpL1)()(总结总结： 数据中通常包含很大的冗余，数据的大小与所数据中通常包含很大的冗余，数据的大小与所携带的信息量的关系由下式给出：携带的信息量的关系由下式给出： L=H+R L=H+R H H：信源熵（信息量：信源熵（信息量/ /符号，代表最小比特数）、符号，代表最小比特数）、 L L：数据量（平均码长单位，即符号实际的比特：数据量（平均码长单位，即符号实际的比特数）数） R R：冗余量（即信息冗余量）：冗余量（即信息冗余量） R=L-HR=L-H5. 5.结构冗余结构

8、冗余 有些图像从整体上看存在着非常强的纹理结构。有些图像从整体上看存在着非常强的纹理结构。 下图为草席图像。下图为草席图像。是一种是一种规则有序排列的图形规则有序排列的图形，我们称它在结构上存在冗余我们称它在结构上存在冗余 。是一种结构冗余。是一种结构冗余。规则有序排列的图形规则有序排列的图形6. 6.知识冗余知识冗余 有些图像的理解与某些知识有相当大的相关有些图像的理解与某些知识有相当大的相关性。性。 比如人脸的图像有固定的结构：比如人脸的图像有固定的结构： 嘴的上方有鼻子、鼻子的上方有双眼睛，鼻嘴的上方有鼻子、鼻子的上方有双眼睛，鼻子位于正脸图像的中线上等等子位于正脸图像的中线上等等 这类

9、规律的结构可由先验知识和背景知识得这类规律的结构可由先验知识和背景知识得到，因此这类信息对一般人来说就是冗余信息。到，因此这类信息对一般人来说就是冗余信息。这就是知识冗余。这就是知识冗余。7. 7.视觉冗余视觉冗余 由于人眼的视觉特性有所限制，人类的视由于人眼的视觉特性有所限制，人类的视觉系统不能对图像画面的任何变化都能感觉到。觉系统不能对图像画面的任何变化都能感觉到。 举例：举例： 人眼视觉系统的一般分辨率为人眼视觉系统的一般分辨率为6464灰度等级灰度等级, ,而而一般图像的量化采用的是一般图像的量化采用的是256256的灰度等级。的灰度等级。 这种差别就是视觉冗余。这种差别就是视觉冗余。

10、 视频压缩编码方法及其分类视频压缩编码方法及其分类 图像压缩的基本目标就是减小数据量。图像压缩的基本目标就是减小数据量。 至于图像压缩到什么程度而又没有明显的失真至于图像压缩到什么程度而又没有明显的失真, ,则取决于图像数据的冗余度。则取决于图像数据的冗余度。所有的这些冗余所有的这些冗余度都可以被除去而不会引起显著的信息损失。度都可以被除去而不会引起显著的信息损失。空间冗余空间冗余和和时间冗余时间冗余是图像信号最常见的冗余是图像信号最常见的冗余。压缩编码分类压缩编码分类1. 1.按恢复的图像性质划分按恢复的图像性质划分 按恢复的图像性质按恢复的图像性质, ,数字图像压缩方法可以分为两数字图像压

11、缩方法可以分为两种种： 无损压缩编码无损压缩编码 有损压缩编码有损压缩编码 压缩编码分类压缩编码分类 无损压缩编码无损压缩编码： 也称为熵编码、可逆编码或无失真编码。也称为熵编码、可逆编码或无失真编码。 当系统采用此方法进行数据压缩时当系统采用此方法进行数据压缩时, ,在接收端所在接收端所获得的解码与原图像完全相同获得的解码与原图像完全相同。 无损压缩不能提供较高的压缩比。无损压缩不能提供较高的压缩比。 一般在一般在2:12:15:15:1。 压缩编码分类压缩编码分类 有损编码有损编码： 也称为不可逆编码、熵压缩编码或失真编码。也称为不可逆编码、熵压缩编码或失真编码。 由于压缩了熵，会减少信息

12、而不能再恢复。由于压缩了熵，会减少信息而不能再恢复。 这种压缩编码具有较高的压缩比。这种压缩编码具有较高的压缩比。 最大可达几百比一。最大可达几百比一。压缩编码分类压缩编码分类2. 2.按压缩方法的原理划分按压缩方法的原理划分 按压缩原理划分按压缩原理划分, ,数字图像压缩方法可以分为以数字图像压缩方法可以分为以下几种编码下几种编码: : 预测编码预测编码 变换编码变换编码 标量量化和矢量量化编码标量量化和矢量量化编码 信息熵编码信息熵编码 子带编码子带编码 结构编码结构编码 模型编码模型编码图像压缩编码图像压缩编码无损压缩无损压缩有损压缩有损压缩霍夫曼编码霍夫曼编码行程编码行程编码算术编码算

13、术编码L-Z编码编码预测编码预测编码:量化量化编码编码:模型编码模型编码:混合编码混合编码:变换编码变换编码:DPCM；运动补偿；运动补偿DCT；子带编码；子带编码分形编码；分形编码；知识知识基编码基编码JPEG；MPEG；H.26X编码编码采样编码；矢量量化编码采样编码；矢量量化编码图像压缩算法分类图像压缩算法分类压缩编码分类压缩编码分类（1 1）预测编码：）预测编码： 其典型的压缩方法有其典型的压缩方法有DPCMDPCM和和ADPCM.ADPCM.它们比它们比较适合于图像数据的压缩。较适合于图像数据的压缩。 它主要是减少图像数据在它主要是减少图像数据在空间上空间上和和时间上时间上的相的相关

14、性，从而达到数据压缩的目的，但这是一种关性，从而达到数据压缩的目的，但这是一种有失真的压缩方法。有失真的压缩方法。 压缩编码分类压缩编码分类（2 2）变换编码：）变换编码： 它是将图像它是将图像时域信号时域信号转换到转换到变换域变换域（系数空（系数空间、频域）上进行处理。间、频域）上进行处理。 在实际编码中，常常利用图像的统计特性和在实际编码中，常常利用图像的统计特性和人眼的视觉特性，只是选择部分变换系数来进人眼的视觉特性，只是选择部分变换系数来进行信息传输，因此恢复的图像中将存在一定的行信息传输，因此恢复的图像中将存在一定的失真。失真。 常用的正交变换有：离散傅氏变换常用的正交变换有：离散傅

15、氏变换DFTDFT、离、离散余弦变换散余弦变换DCTDCT、离散正弦变换、离散正弦变换DSTDST和和K-LK-L变换。变换。压缩编码分类压缩编码分类（3 3）标量量化和矢量量化编码：）标量量化和矢量量化编码： 标量量化指传统的量化，是将具有无限电平标量量化指传统的量化，是将具有无限电平的点样值，用有限电平数表示的方法，是一个的点样值，用有限电平数表示的方法，是一个样点、一个样点地进行量化编码样点、一个样点地进行量化编码。 这里量化器的设计是一个很关键的步骤。这里量化器的设计是一个很关键的步骤。 压缩编码分类压缩编码分类（3 3）标量量化和矢量量化编码：）标量量化和矢量量化编码： 矢量编码是相

16、对标量量化而提出的矢量编码是相对标量量化而提出的。 矢量编码中一次可以量化多个样点矢量编码中一次可以量化多个样点。 矢量量化也是一种有损压缩编码。矢量量化也是一种有损压缩编码。压缩编码分类压缩编码分类（4 4）信息熵编码：）信息熵编码： 信息熵编码是一种基于图像统计特性的编码信息熵编码是一种基于图像统计特性的编码方法。方法。 是一种无损压缩编码方法。是一种无损压缩编码方法。 压缩编码分类压缩编码分类（4 4）信息熵编码：）信息熵编码： 它是根据信息熵的原理它是根据信息熵的原理： 用最短的位数表示出现概率大的信息，而出现用最短的位数表示出现概率大的信息，而出现概率较小的信息则用较长的位数来表示，

17、以此概率较小的信息则用较长的位数来表示，以此达到压缩数据的目的。达到压缩数据的目的。 常见的熵编码有常见的熵编码有哈夫曼编码哈夫曼编码、游程编码游程编码和和算术算术编码编码。压缩编码分类压缩编码分类（5 5）子带编码：）子带编码： 在子带编码中，首先将图像数据转换到频在子带编码中，首先将图像数据转换到频域，然后按频率分成若干子带，对每个子带用域，然后按频率分成若干子带，对每个子带用不同的编码器进行抽样、量化和编码，并将各不同的编码器进行抽样、量化和编码，并将各子带输出数据合成为数据码流，从而获得压缩子带输出数据合成为数据码流，从而获得压缩数据。数据。 压缩编码分类压缩编码分类（6 6）结构编码

18、：）结构编码： 结构编码也称为第二代编码。结构编码也称为第二代编码。 编码时首先求出图像中的边界、轮廓、纹理编码时首先求出图像中的边界、轮廓、纹理等结构特征参数，然后保存这些参数信息，进等结构特征参数，然后保存这些参数信息，进行编码。行编码。 在解码时则根据这些结构和参数信息进行图在解码时则根据这些结构和参数信息进行图像合成，从而恢复出原图像。像合成，从而恢复出原图像。压缩编码分类压缩编码分类（7 7）模型编码：）模型编码： 这是一种基于知识的编码。这是一种基于知识的编码。 利用人们对自然知识的了解而形成一个规则利用人们对自然知识的了解而形成一个规则库，将人脸变化等特征用一系列参数来进行描库，

19、将人脸变化等特征用一系列参数来进行描述。述。 利用参数再加上模型就可以实现人脸的图像利用参数再加上模型就可以实现人脸的图像编码和解码，达到压缩图像数据的目的。编码和解码，达到压缩图像数据的目的。数据压缩技术的性能指标数据压缩技术的性能指标 1 1、压缩比、压缩比用来定义压缩性能。指压缩过程中输入数据用来定义压缩性能。指压缩过程中输入数据量与输出数据量之比。量与输出数据量之比。 设原图像的平均码长为设原图像的平均码长为Lc,Lc, 压缩后图像的平均码压缩后图像的平均码长为长为L L，则压缩比，则压缩比C C为为压缩比越大，说明数据压缩的程度越高。压缩比越大，说明数据压缩的程度越高。LLCC 冗余

20、度冗余度和和编码效率编码效率也是衡量信源特性以及编解码也是衡量信源特性以及编解码设备性能的重要指标，定义如下：设备性能的重要指标，定义如下：冗余度冗余度: :指冗余量在信息量中占的比例指冗余量在信息量中占的比例 L L为平均码字长度为平均码字长度 H(X)H(X)为信源熵。为信源熵。编码效率编码效率：指信息量在数据量中占的比例：指信息量在数据量中占的比例 1)(XHLRRLXH11)(数据压缩技术的性能指标数据压缩技术的性能指标2 2、重现质量：、重现质量： 恢复效果要好，要尽可能地恢复原始数据。恢复效果要好，要尽可能地恢复原始数据。 3 3、压缩和解压缩速度、压缩和解压缩速度无损图像压缩编码

21、方法无损图像压缩编码方法 无失真（无损）图像压缩编码就是指图像经无失真（无损）图像压缩编码就是指图像经过压缩、编码后恢复出的图像与原图像完全一过压缩、编码后恢复出的图像与原图像完全一样样, ,没有任何失真。没有任何失真。 无失真压缩编码无失真压缩编码-熵熵编码编码。 广泛应用于文本数据和特殊应用场合的图广泛应用于文本数据和特殊应用场合的图像数据（指纹图像、医学图像、卫星图像等）像数据（指纹图像、医学图像、卫星图像等）的压缩。的压缩。无损图像压缩编码方法无损图像压缩编码方法 香农信息论认为香农信息论认为, ,信源中或多或少地含有自信源中或多或少地含有自然冗余度。然冗余度。 这些冗余度既来自于信源

22、本身的相关性这些冗余度既来自于信源本身的相关性, ,又来又来自于信源概率分布的不均匀性中。自于信源概率分布的不均匀性中。 只要找到去除相关性或改变概率分布不均匀只要找到去除相关性或改变概率分布不均匀性的方法和手段性的方法和手段, ,也就找到了信息熵编码的方法。也就找到了信息熵编码的方法。 无损图像压缩编码方法无损图像压缩编码方法 例如例如： 在图像中存在着空间上的相关性在图像中存在着空间上的相关性 对运动图像而言存在着帧与帧之间在时间上的相对运动图像而言存在着帧与帧之间在时间上的相关性。关性。 这些都说明这些都说明存在着存在着颜色颜色的概率分布的不均匀性的概率分布的不均匀性。 无损图像压缩编码

23、方法无损图像压缩编码方法 信息熵编码所要解决的问题：信息熵编码所要解决的问题： 如何利用信息熵理论（香农信息论）减少数如何利用信息熵理论（香农信息论）减少数据在传输和存储时的冗余度据在传输和存储时的冗余度。香农信息论香农信息论 香农信息论认为：香农信息论认为： 信源所含有的信息熵就是进行无失真编码的信源所含有的信息熵就是进行无失真编码的理论极限。理论极限。 niniiiiiSpSpSISpXH112)(log)()()()(香农信息论香农信息论 低于此极限的无失真编码方法是找不到的低于此极限的无失真编码方法是找不到的, ,而只要不低于此极限而只要不低于此极限, ,那就总能找到某种适宜的那就总能

24、找到某种适宜的编码方法任意的逼近信息熵。编码方法任意的逼近信息熵。 熵编码的目的就是要使编码后的图像熵编码的目的就是要使编码后的图像平均码字平均码字长度（比特数）长度（比特数）L L近可能接近这个近可能接近这个信息熵信息熵H(x)H(x) niniiiiiSpSpSISpXH112)(log)()()()(无损图像压缩编码方法无损图像压缩编码方法根据：根据： L=H+R L=H+R H H：信源熵（信息量：信源熵（信息量/ /符号，代表符号的最小比特符号，代表符号的最小比特数）、数）、 L L：数据量（每个符号实际平均的比特数，也称：数据量（每个符号实际平均的比特数，也称码字长度码字长度） R

25、 R：冗余量（即信息冗余量）：冗余量（即信息冗余量） R=L-HR=L-H 无损数据压缩的本质：通过减少冗余量无损数据压缩的本质：通过减少冗余量R R，减少，减少数据量数据量L L，使之接近，使之接近H H。无损图像压缩编码方法无损图像压缩编码方法 无损图像压缩编码方法由于其中并没有考虑人无损图像压缩编码方法由于其中并没有考虑人眼的视觉特性眼的视觉特性, ,因此其所能达到的压缩比非常有因此其所能达到的压缩比非常有限。限。 常用的无失真图像压缩编码有：常用的无失真图像压缩编码有： 哈夫曼编码哈夫曼编码 游程编码（行程编码）游程编码（行程编码） 算术编码算术编码 无损图像压缩编码方法无损图像压缩编

26、码方法 在实际应用中在实际应用中, ,常将游程编码与哈夫曼编码结常将游程编码与哈夫曼编码结合起来使用合起来使用, ,例如在例如在H.261H.261、JPEGJPEG、MPEGMPEG等国际等国际标准中正是采用此种编码技术。标准中正是采用此种编码技术。 而在而在H.263H.263等国际标准中则采用算术编码技术。等国际标准中则采用算术编码技术。哈夫曼编码哈夫曼编码 哈夫曼哈夫曼(Huffman)(Huffman)编码方法于编码方法于19521952年问世年问世, ,迄今为迄今为止仍经久不衰止仍经久不衰, ,广泛应用于各种数据压缩技术中广泛应用于各种数据压缩技术中, ,且仍不失为熵编码中的最佳编

27、码方法。且仍不失为熵编码中的最佳编码方法。主要编码思路：主要编码思路： 对对出现频率较大出现频率较大的符号用的符号用较短的码较短的码来表示，来表示， 而对于而对于出现频率较小出现频率较小的符号则用的符号则用较长的码较长的码来表来表示。示。 这样的编码结果所获得的平均码字长度最短。这样的编码结果所获得的平均码字长度最短。哈夫曼编码哈夫曼编码 哈夫曼编码的码长是变化的，即可变长编码哈夫曼编码的码长是变化的，即可变长编码(VLC),(VLC),而且哈夫曼编码通常被称为最优码。而且哈夫曼编码通常被称为最优码。 最优的含义是：最优的含义是： 对于给定的符号集和概率模型，找不到任何其对于给定的符号集和概率

28、模型，找不到任何其它整数码比哈夫曼编码有更短的码长。它整数码比哈夫曼编码有更短的码长。 整数码整数码：指每个符号所对应的码字的位数都是指每个符号所对应的码字的位数都是整数。整数。哈夫曼编码哈夫曼编码具体编码过程：具体编码过程： 1 1、排序：按符号出现的概率从大到小进行排、排序：按符号出现的概率从大到小进行排列。列。 2 2、赋值：对排在最后的两个符号进行赋值，、赋值：对排在最后的两个符号进行赋值，概率大的赋概率大的赋“1”1”，概率小的赋，概率小的赋“0”0”。或相反。或相反。 3 3、合并：将上述最后的两个符号出现的概率、合并：将上述最后的两个符号出现的概率相加合成一个概率。相加合成一个概

29、率。哈夫曼编码哈夫曼编码 4 4、重新排序：将合成后的概率与其它符号概率、重新排序：将合成后的概率与其它符号概率一起进行重新排序（从大到小）。然后重复步一起进行重新排序（从大到小）。然后重复步骤骤2 2、3 3的内容，直至概率相加为的内容，直至概率相加为1 1为止。为止。 5 5、码字分配：从最后一步开始反向进行码字分、码字分配：从最后一步开始反向进行码字分配。从而形成一个码字。配。从而形成一个码字。哈夫曼编码的基本原理哈夫曼编码的基本原理例：例： aaaaaaaa bbbbbb cccc d d eeeeeeeeee ffffffffffffff 4 3 4 3 2 1 5 2 1 5 7

30、7 如果不进行特殊的编码，用字符方式如果不进行特殊的编码，用字符方式（ASCIIASCII码）传送，每个字符码）传送，每个字符8 8位，需要的位，需要的数据量为：数据量为： 2222* *8=8=176176 bit bit 哈夫曼编码的基本原理哈夫曼编码的基本原理cbafe7/227/225/225/224/224/222/222/2210f=11 e=01 a=00 b=101 c=1001 d=1000d1/221/223/223/226/226/2222/2222/2213/2213/229/229/223/223/2210101010哈夫曼编码哈夫曼编码哈夫曼编码的基本原理哈夫曼编码

31、的基本原理 aaaaaaaa bbbbbb cccc d d eeeeeeeeee ffffffffffffff 4 3 2 1 5 7 4 3 2 1 5 7按照哈夫曼编码的原理进行编码：按照哈夫曼编码的原理进行编码： a=00 b=101 c=1001 d=1000 e=01 f=11a=00 b=101 c=1001 d=1000 e=01 f=11需要的数据量为需要的数据量为 4 4* *2 2+3+3* *3 3+2+2* *4 4+1+1* *4 4+5+5* *2 2+7+7* *2 2= =5353bitbit比比2222* *8=176bit 8=176bit 少了少了123

32、123bitbit平均编码长度平均编码长度L L为为4 . 2)()(1niiiSLSPL哈夫曼编码的基本原理哈夫曼编码的基本原理例例 设信号源为设信号源为X= X= 、a a、e e、I I、m m、t t、c c、h h、rr。若传送一个字符串若传送一个字符串“I am a teacherI am a teacher”，对应的概，对应的概率为率为p=p=0.220.22、0.220.22、0.140.14、0.070.07、0.070.07、0.070.07、0.070.07、0.070.07、0.070.07, , 试给出该信源的霍夫曼编码方案。试给出该信源的霍夫曼编码方案。并计算压缩比

33、并计算压缩比C C、冗余度、冗余度R R和编码效率。和编码效率。 = =0101 a= a=0000 e= e=111111 I= I=11011101 m= m=11001100 t= t=10111011 c= c=10101010 h= h=10011001 r= r=10001000 出现出现3 3次，次，a a出现出现3 3次，次，e e出现出现2 2次，其它的各出现次，其它的各出现1 1次。次。 共需要共需要3 3* *2 2+3+3* *2 2+2+2* *3 3+6+6* *4 4= =4242bitbit分析分析: : 若传送一个字符串若传送一个字符串“I am a teac

34、her”“I am a teacher”，共，共1414个字个字符，其中包括符，其中包括9 9个不同的字符。个不同的字符。（1 1）若使用自然编码（等长二进制编码），该字）若使用自然编码（等长二进制编码），该字符串中有符串中有9 9个不同的符号，至少需要个不同的符号，至少需要4 4位二进制位二进制才能表示，这样传送该字符串也要才能表示，这样传送该字符串也要5656位。位。（2 2）HuffmanHuffman编码只需要编码只需要4242位位，平均编码长度为，平均编码长度为2.982.98。平均码字长度公式为：平均码字长度公式为：98. 24607. 0314. 02222. 0码长概率niii

35、SLSPL1)()(求压缩比、冗余度和编码效率求压缩比、冗余度和编码效率: : 压缩比压缩比C C： 14 14个字符，需个字符，需4 4位二进制数位二进制数 Lc=4 Lc=4 C=Lc/L=4/2.98= C=Lc/L=4/2.98= 1.34 :11.34 :1 冗余度冗余度R R=(L-H)/H=(2.98-2.97)/2.97=0.34%=(L-H)/H=(2.98-2.97)/2.97=0.34%编码效率编码效率符号/97. 207. 007. 0614. 0log14. 022. 0log22. 02)()()(22291bitligSISpXHiii%7 .9998. 297.

36、 2LH哈夫曼编码哈夫曼编码例：某信源符号及其对应的概率如下：例：某信源符号及其对应的概率如下： a1 a2 a3 a4 a5 a6a1 a2 a3 a4 a5 a6 0.4 0.2 0.12 0.15 0.1 0.03 0.4 0.2 0.12 0.15 0.1 0.03请完成哈夫曼编码，并计算压缩比、冗余度和编请完成哈夫曼编码，并计算压缩比、冗余度和编码效率。码效率。哈夫曼编码哈夫曼编码例：某信源符号及其对应的概率如下：例：某信源符号及其对应的概率如下： a1a1 a2a2 a3a3 a4a4 a5a5 a6a6 a7a7 a8a80.40 0.0.40 0.0404 0.1 0.1 0.

37、07 0.06 0. 0.1 0.1 0.07 0.06 0.1818 0.04 0.04请完成哈夫曼编码，并计算压缩比、冗余度和编请完成哈夫曼编码，并计算压缩比、冗余度和编码效率。码效率。a1:a1: 0 0 a2:a2: 1 11101100 0 a3:a3: 100 100 a4:a4: 1111 1111 a5:a5: 1011 1011 a6:a6: 1010 1010 a7:a7: 1 11101101 1 a8:a8: 110 110哈夫曼编码哈夫曼编码 特点：特点： （1 1）虽然哈夫曼码长可变虽然哈夫曼码长可变, ,但却不需要另附同步但却不需要另附同步码。码。 （2 2） 通

38、信双方只要均拥有预先编写的解释各种通信双方只要均拥有预先编写的解释各种代码意义的代码意义的词典词典( (即即码本码本), ),即可根据即可根据码本码本逐码译出。逐码译出。哈夫曼编码哈夫曼编码哈夫曼编码有几个问题值得注意哈夫曼编码有几个问题值得注意: :一、哈夫曼码没有错误保护功能。一、哈夫曼码没有错误保护功能。 如果码串中有错如果码串中有错, ,哪怕仅仅是哪怕仅仅是1 1位出错位出错, ,不但该码不但该码本身将会译错本身将会译错, ,更糟糕的是对后面的影响更糟糕的是对后面的影响, ,一错就一错就是一串是一串, ,一般称这种现象为错误传播。一般称这种现象为错误传播。 哈夫曼编码哈夫曼编码二、二、

39、不可调用中间的内容不可调用中间的内容 哈夫曼码是可变长度码，因此很难随意查找哈夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码或调用压缩文件中间的内容，然后再译码; ;三、接收端需保存一个与发送端相同的霍夫曼码表三、接收端需保存一个与发送端相同的霍夫曼码表 哈夫曼码还是得到广泛应用哈夫曼码还是得到广泛应用, ,哈夫曼编码毕竟属哈夫曼编码毕竟属于最佳编码方法。于最佳编码方法。游程编码游程编码RLCRLC 游程编码（行程编码）游程编码（行程编码）RLCRLC（RLE)RLE)是一种非是一种非常简单的数据压缩编码形式。它在某些场合是常简单的数据压缩编码形式。它在某些场合是非常

40、有效的一种无损压缩编码方法。非常有效的一种无损压缩编码方法。 游程编码游程编码RLCRLC 游程编码编码原则游程编码编码原则: : 连续重复的数据值序列（或称为连续重复的数据值序列（或称为“流流”）用一）用一个重复次数和单个数据值来代替。个重复次数和单个数据值来代替。比如：得到的字符串为比如：得到的字符串为AAAAAAAAABCDDDDDDDDAAABCDDDDDDDDD DBBBBBBBBBBBBBBBB 可压缩为可压缩为* *6 6ABCABC* *9 9D D* *8 8B B 颜色相同的区域颜色相同的区域游程编码游程编码RLCRLC 不需要存储每一个像素的颜色值，而仅存储不需要存储每一

41、个像素的颜色值，而仅存储一个像素的颜色值以及具有相同颜色的像素数一个像素的颜色值以及具有相同颜色的像素数目。目。 或者存储一个像素的颜色值，以及具有相同颜或者存储一个像素的颜色值，以及具有相同颜色值的行数。色值的行数。 这种压缩编码称为这种压缩编码称为游程编码游程编码或或行程编码行程编码。游程编码游程编码RLCRLC 游程编码多用于游程编码多用于黑白黑白图像图像或图形或图形的压缩。的压缩。 具有相同具有相同灰度等级灰度等级的连续的像素数目称为的连续的像素数目称为游游程程长度长度RLRL。 图像中具有相同灰度的图像块越大越多，压缩图像中具有相同灰度的图像块越大越多，压缩的效果就越好。的效果就越好

42、。 宽度：宽度：263 263 宽度：宽度：263263 高度：高度：300 300 高度：高度：300 300 灰度灰度：4 4 灰度灰度：8 8 游程编码游程编码RLCRLC RLCRLC特点：特点： 编码简单直观，编码编码简单直观，编码/ /解码速度快解码速度快，只需要简只需要简单地复制字符若干遍即可以了。单地复制字符若干遍即可以了。 BMPBMP、TIFFTIFF、AVIAVI等格式文件的压缩均采用此方等格式文件的压缩均采用此方法。在法。在PDFPDF文件格式中也得到应用文件格式中也得到应用。 存在着不同的实现技术和文件格式。存在着不同的实现技术和文件格式。游程编码游程编码RLCRLC

43、的构成的构成在在RLCRLC中用中用3 3个字节表示一个字符串：个字节表示一个字符串：由一个指示符、一个重复次数字节和一个被重复的由一个指示符、一个重复次数字节和一个被重复的字符构成的字符构成的3 3字节码字节码 思考：思考：RL RL ? ? 时，数据压缩才用意义时，数据压缩才用意义3游程编码游程编码RLCRLC方法方法例如例如: :字符串字符串 RTAAAASDEEEEERTAAAASDEEEEE经经RLERLE压缩后为：压缩后为： RT RT* *4ASD4ASD* *5E 5E “* *4A” 4A” 代替了代替了“AAAA”“AAAA” “ “* *5E” 5E” 代替代替“EEEE

44、E”“EEEEE” 指示符采用特殊字符指示符采用特殊字符* *： 指出一个指出一个RLCRLC编码的开始，后面的数字表示重编码的开始，后面的数字表示重复的次数，数字后的单个字符是被重复的字符。复的次数，数字后的单个字符是被重复的字符。游程编码游程编码RLCRLC方法方法例例: : 设有数据设有数据“AAAAAAA ABBBBCCCCCBBBBCCCCCCCCCDAAAAAADAAAAAA”试计算该数据的行程编码。试计算该数据的行程编码。解：解：A A重复重复4 4次，次，B B重复重复4 4次，次，C C重复重复7 7次，次，D D不重复，不重复，A A重复重复6 6次，次， RLC RLC数

45、据流为：数据流为：“# #4 4A#4B#A#4B#7 7CD#6ACD#6A”，其中，其中# #为指示符。总共占用为指示符。总共占用1313个字节，而源数据占用个字节，而源数据占用2222个字节。个字节。游程编码游程编码也可以也可以不用指示符不用指示符: : 重复与否相同对待，相应的重复与否相同对待，相应的RLCRLC为为“3A4B5C1D6A3A4B5C1D6A”占用占用1010个字节。个字节。游程编码游程编码RLCRLC方法方法 例：例： aaaaaaaa bbbbbb cccc d d eeeeeeeeee ffffffffffffff ( (共共2222* *8=176 bit)8=

46、176 bit) 4a3b2c1d5e7f 4a3b2c1d5e7f ( (共共1212* *8=96 bit)8=96 bit) 压缩率为：压缩率为：176/96=1.83:1176/96=1.83:1游程编码游程编码 游程编码的压缩率不高，但编码、解码的速度游程编码的压缩率不高，但编码、解码的速度快，仍被得到广泛的应用。快，仍被得到广泛的应用。 特别是在特别是在变换编码变换编码后再进行后再进行游程编码游程编码，有很好的，有很好的效果。在效果。在图像图像数据压缩标准数据压缩标准( (JPEGJPEG) )中扮演重要中扮演重要角色。角色。 算术编码算术编码 算术编码产生于算术编码产生于2020

47、世纪世纪6060年代初年代初, ,在图像数据在图像数据压缩标准中算术编码扮演了重要的角色。能有压缩标准中算术编码扮演了重要的角色。能有效地压缩信源冗余度，属于熵编码的一种。效地压缩信源冗余度，属于熵编码的一种。 该方法实现较为复杂，常与其它有损压缩编该方法实现较为复杂，常与其它有损压缩编码结合使用，在码结合使用，在视频视频数据压缩标准数据压缩标准( (如如H.263H.263) )中中扮演重要角色。扮演重要角色。 算术编码算术编码 算术编码与哈夫曼编码一样，也是对概率较大算术编码与哈夫曼编码一样，也是对概率较大的符号采用短码，对概率较小的符号采用长码。的符号采用短码，对概率较小的符号采用长码。

48、 它突破了哈夫曼编码每个符号只能按整数比特它突破了哈夫曼编码每个符号只能按整数比特来逼近信源熵的限制来逼近信源熵的限制: : 每个符号的平均编码长度可以按每个符号的平均编码长度可以按小数比特小数比特来逼来逼近信源熵。近信源熵。算术编码基本思想算术编码基本思想 算术编码不是将单个信源符号映射成一个码算术编码不是将单个信源符号映射成一个码字。字。 而是把而是把整个信源整个信源表示为实数线上的表示为实数线上的0 0到到1 1之间的之间的一个区间，其长度等于该一个区间，其长度等于该信源信源的概率。的概率。 再在该区间内选择一个代表性的小数，转化再在该区间内选择一个代表性的小数，转化为二进制作为实际的编

49、码输出。为二进制作为实际的编码输出。算术编码基本步骤算术编码基本步骤 将编码的消息表示成实数将编码的消息表示成实数0 0和和1 1之间的一之间的一个区间。个区间。 消息序列中的每个元素都要用来缩短这个消息序列中的每个元素都要用来缩短这个区间。区间。 消息序列中元素越多，所得到的区间就越小，消息序列中元素越多，所得到的区间就越小，当区间变小时，表示这一区间所需的二进制位当区间变小时，表示这一区间所需的二进制位就越多。就越多。 消息结束时就最后所得到区间的下边界值表消息结束时就最后所得到区间的下边界值表示该消息。示该消息。 给定符号序列的算术编码步骤如下：给定符号序列的算术编码步骤如下： （1 1

50、）初始化：初始化： 编码器开始时将编码器开始时将“当前区间当前区间” ” 设置为一。设置为一。 为为0 0，1) 1) （2 2）按消息（按消息（符号序列符号序列）中符号的顺序：）中符号的顺序： 对每一符号，编码器按步骤对每一符号，编码器按步骤（a a）和和（b b）重复进重复进行处理行处理 给定符号序列的算术编码步骤如下：给定符号序列的算术编码步骤如下： （a a）编码器将编码器将“当前区间当前区间”分为分为子区间子区间，每一，每一个符号分配一个子区间。一个子区间的大小与个符号分配一个子区间。一个子区间的大小与符号的概率成比例。符号的概率成比例。 （b b）对应于一个确切发生的符号，编码器选

51、择对应于一个确切发生的符号，编码器选择其子区间，并使它成为其子区间，并使它成为新的新的“当前区间当前区间”。 这也称为重新归一化。这也称为重新归一化。给定符号序列的算术编码步骤如下：给定符号序列的算术编码步骤如下： （3 3）最后一个符号对应有最后输出的）最后一个符号对应有最后输出的“当前区当前区间间” ” 。 最后输出的最后输出的“当前区间当前区间”的下边界就是该给定的的下边界就是该给定的整个符号序列的算术编码。整个符号序列的算术编码。算术编码方法算术编码方法算术编码用到两个基本的参数：符号的概率和它算术编码用到两个基本的参数：符号的概率和它的累积概率。的累积概率。累积概率（累积概率（下下边

52、界值）：边界值）： 设信源符号集为设信源符号集为 A=A=a a0 0, , a a1 1, , a a2 2, , , a am-1m-1 相应的概率为相应的概率为Pi Pi， i=0 i=0， 1 1， 2 2， ， m-1 m-1。 各符号的累积概率各符号的累积概率P Pr r为为: :a a0 0的累积概率为的累积概率为0 0， a a1 1的累积概率为的累积概率为P P0 0 ， a a2 2的累积的累积概率为概率为 P P0 0 + P + P1 1irirpP10算术编码示例：算术编码示例： 符号符号 S1 S1、 S2 S2、 S3 S3、 S4 S4 十进制概率十进制概率 1

53、/8 1/4 1/2 1/8 1/8 1/4 1/2 1/8 二进制概率二进制概率P Pi i 0.001 0.01 0.1 0.001 0.001 0.01 0.1 0.001 累积概率累积概率P Pr r 0 0.001 0.011 0.1110 0.001 0.011 0.111 0 1/8 3/8 0 1/8 3/8 7/8 7/8 1 1 0 0.001 0.011 0.111 0 0.001 0.011 0.111 1 1 现在以符号序列：现在以符号序列：s3s3 s3s3 s2s2 s4 s4 为例来解释编码过程为例来解释编码过程算术编码的基本法则归纳如下算术编码的基本法则归纳如

54、下: : (1) (1) 初始状态初始状态 区间起始点区间起始点C=0C=0, , 区间宽度区间宽度A=1.0A=1.0。 (2)(2)新区间起点新区间起点C C= =原起点原起点C+C+原区间宽度原区间宽度A AP Pr r, , 新区间宽度新区间宽度A A= =原区间宽度原区间宽度A APi Pi 其中其中P Pr r为所编符号为所编符号si si对应的对应的累积概率累积概率 Pi Pi为所编符号为所编符号si si对应的对应的概率概率。对序列对序列s3s3 s3s3 s2s2 s4s4 进行编码的过程如下进行编码的过程如下: :初始起点初始起点C=0 C=0 初始区间宽度初始区间宽度A=

55、1A=1第第1 1个符号个符号s3s3: :新区间起点：新区间起点： C C=0+1=0+10.0110.011=0.011=0.011新区间宽度新区间宽度： A A=1=10.10.1=0.1 =0.1 区间终点为区间终点为0.1110.111新的新的当前区间当前区间范围为：范围为：0.011-0.011-0.1110.111第第2 2个符号个符号s3s3: : 新区间起点：新区间起点： C C =0.011+0.1 =0.011+0.10.011=0.10010.011=0.1001新区间宽度新区间宽度： A A=0.1=0.10.10.1=0.01 =0.01 区间终点区间终点0.110

56、10.1101新的新的当前区间当前区间为：为：0.1001-0.1001- -0.11010.1101 第第3 3个符号个符号s2s2: : 新区间起点：新区间起点：C C=0.1001+0.01=0.1001+0.010.0010.001=0.10011=0.10011新区间宽度：新区间宽度： A A=0.01=0.010.010.01=0.0001 =0.0001 新的新的当前区间当前区间为：为：0.10011-0.10011- -0.101010.10101 第第4 4个符号个符号s4:s4: 新区间起点：新区间起点：C C = 0.10011+0.0001= 0.10011+0.000

57、10.1110.111= = 0.10100110.1010011新区间宽度：新区间宽度：A A = 0.0001 = 0.00010.0010.001 = 0.0000001= 0.0000001取最后符号的当前区间的下边界作为序列的算术编取最后符号的当前区间的下边界作为序列的算术编码码所以最终编完的码字是所以最终编完的码字是 0.1010011 0.1010011算数编码的代码长度算数编码的代码长度L L为多少？为多少？根据信源熵：根据信源熵：得出，算数编码的代码长度得出，算数编码的代码长度L L： N N 代表出现的符号数量代表出现的符号数量 代表代表大于大于X X的的最小最小整数。整数

58、。 代码取其值小数点后的代码取其值小数点后的L L位。若有尾数，就进位位。若有尾数，就进位到第到第L L位。位。niniiiiiSpSpSISpXH112)(log)()()()( X)(XHNL如：如： 则取则取 L= L=3 3 如果最后符号的下边界为如果最后符号的下边界为0.101100010.10110001 取：取：c=0.11c=0.110 0 传输的二进制代码序列是传输的二进制代码序列是11110 08 . 2L刚才例题最终编完的码字刚才例题最终编完的码字0.10100110.1010011传输传输s3s3 s3s3 s2s2 s4s4共共4 4个符号，得个符号，得取取7 7位位

59、所以传输的码流为所以传输的码流为10100111010011压缩率为：压缩率为：4 42/7=8/7=1.14:12/7=8/7=1.14:1符号/75. 12log5 . 04log25. 08log125. 02)()()(22241bitSISpXHiii 775. 14)(XHNL算术编码解码过程算术编码解码过程 在解码器中在解码器中, ,当收到码字串当收到码字串0.1010.10100001111时时, , 这个码字串指向子区间这个码字串指向子区间0.011,0.011, 0.111)0.111), , 解出的第一个符号应为解出的第一个符号应为s3s3 0 0.001 0.011 0

60、 0.001 0.011 0.111 0.111 1.01.0 算术编码解码过程算术编码解码过程 之后之后采取与编码过程相反的步骤：采取与编码过程相反的步骤： 即即：从码字串中减去从码字串中减去已解符号已解符号的的累积概率累积概率, ,并将并将差差值值除以除以概率值概率值, ,则得到新码字串。则得到新码字串。 (0.10100111(0.10100111- -0.011)0.011)(0.1)=(0.1)=0.1000110.100011。 新码字串仍落在新码字串仍落在0.011,0.111)0.011,0.111)区间之内区间之内, , 解出的第解出的第2 2个符号仍为个符号仍为s3s3。