多媒体通信技术四修订

会计学1多媒体通信技术四修订多媒体通信技术四修订第四章第四章 视频信息压缩与处理视频信息压缩与处理本章主要内容本章主要内容图像信号的相关特点图像信号的相关特点图像处理方法图像处理方法各种实用编码各种实用编码常见的图像压缩编码标准常见的图像压缩编码标准 图像信号的相关特点图像信号的相关特点 通常一幅图像中的各像素之间存在一通常一幅图像中的各像素之间存在一定的相关性。定的相关性。在活动图像中，由于两幅相邻图像之间在活动图像中，由于两幅相邻图像之间的时间间隔很短，因此这两幅图像信息中的时间间隔很短，因此这两幅图像信息中包含大量相关信息。包含大量相关信息。这些就是图像信息中的冗余。这些就是图像信息中的冗余。图像信号的相关特点图像信号的相关特点 多媒体数据压缩的目的就是要去除多媒体数据压缩的目的就是要去除图像信息中的大量冗余，同时又能保证图图像信息中的大量冗余，同时又能保证图像的质量。像的质量。一般针对不同类型的冗余信息，采取一般针对不同类型的冗余信息，采取不同的压缩方法。不同的压缩方法。图像信息中存在的冗余分类图像信息中存在的冗余分类 1 1 空间冗余空间冗余 规则物体的物理相关规则物体的物理相关性性2 2 时间冗余时间冗余 视频与动画画面间的相关性视频与动画画面间的相关性3 3 统计冗余统计冗余 具有空间冗余和时间冗余具有空间冗余和时间冗余6 6 视觉冗余视觉冗余 视觉、听觉敏感度和非线性感觉视觉、听觉敏感度和非线性感觉7 7 知识冗余知识冗余 凭借经验识别凭借经验识别4 4 结构冗余结构冗余 规则纹理、相互重叠的结构表面规则纹理、相互重叠的结构表面 5 5 信息熵冗余信息熵冗余 编码冗余，数据与携带的信编码冗余，数据与携带的信息息1011 0001 11001011 0001 11001011 0001 11001011 0001 11000101 1010 10100101 1010 10101011 11001011 11000101 1111 10100101 1111 10102 22424色色2 28 8色色 1.1.空间冗余空间冗余空间冗余是在图像数据中经常存在的一种冗余。空间冗余是在图像数据中经常存在的一种冗余。在任何一幅图像中：在任何一幅图像中：均有许多灰度或颜色都均有许多灰度或颜色都相同的邻近像素相同的邻近像素组成的组成的局部区域局部区域，它们之间具有空间上的强，它们之间具有空间上的强相关性，在图像中就相关性，在图像中就表现为空间冗余。表现为空间冗余。1.1.空间冗余空间冗余 颜色相同的区域 对空间冗余的压缩方法就是把这种对空间冗余的压缩方法就是把这种颜色都颜色都相同相同的邻近像素组成的的邻近像素组成的局部区域局部区域当作一个整体，用极当作一个整体，用极少的数据量来表示它，从而节省了存储空间。少的数据量来表示它，从而节省了存储空间。这种压缩方法叫这种压缩方法叫空间压缩空间压缩或或帧内压缩帧内压缩。时间冗余时间冗余：视频信号和动画是基于时间轴的一组：视频信号和动画是基于时间轴的一组连续画面。连续画面。由于活动图像序列中的任意两幅相邻由于活动图像序列中的任意两幅相邻的图像之间的时间间隔很短，因此两幅图像中存的图像之间的时间间隔很短，因此两幅图像中存在大量的相关信息在大量的相关信息 时间冗余 相邻帧包含相同的背景和移动物体，只不相邻帧包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同过移动物体所在的空间位置略有不同 活动图像中的两幅相邻的图像有较大的相关活动图像中的两幅相邻的图像有较大的相关性，这反映为性，这反映为时间冗余时间冗余。在前一幅图像的基础上，只需改变少量的数在前一幅图像的基础上，只需改变少量的数据，便可以表示出后一幅图像，达到数据压缩的据，便可以表示出后一幅图像，达到数据压缩的目的。目的。这种压缩对活动图像往往能得到很高的压缩比，这种压缩对活动图像往往能得到很高的压缩比，这也称为这也称为时间压缩时间压缩或或帧间压缩帧间压缩。3.3.统计冗余统计冗余 空间冗余和时间冗余是将图像信号看作空间冗余和时间冗余是将图像信号看作为随机信号时所反映出的统计特征，因此为随机信号时所反映出的统计特征，因此有时把这两种冗余称为有时把这两种冗余称为统计冗余统计冗余。4.4.信息熵冗余信息熵冗余信息熵是针对数据的信息量而言的，它代表信息熵是针对数据的信息量而言的，它代表从图像信息源中发出的一个符号的平均信息量从图像信息源中发出的一个符号的平均信息量设某种编码的平均码长单位（符号）的设某种编码的平均码长单位（符号）的数据量数据量为为式中，式中，为分配给第为分配给第 符号的比特数，即符号的比特数，即二进制位数二进制位数 由于实际中很难估算各符号出现的概率，我由于实际中很难估算各符号出现的概率，我们一般认为它们是等概率的，所以每个符号比特们一般认为它们是等概率的，所以每个符号比特数相同。数相同。这种编码的符号的数据量这种编码的符号的数据量L L为最大。为最大。但实际各符号出现的概率并不相同。但实际各符号出现的概率并不相同。这样所得的这样所得的L L必然大于实际的信源熵必然大于实际的信源熵H H，由此，由此带来的冗余我们称为带来的冗余我们称为信息熵冗余信息熵冗余或或编码冗余编码冗余。总结：总结：数据中通常包含很大的冗余，数据的大小与所数据中通常包含很大的冗余，数据的大小与所携带的信息量的关系由下式给出：携带的信息量的关系由下式给出：L=H+R L=H+R H H：信源熵（信息量：信源熵（信息量/符号，代表最小比特数）、符号，代表最小比特数）、L L：数据量（平均码长单位，即符号实际的比特：数据量（平均码长单位，即符号实际的比特数）数）R R：冗余量（即信息冗余量）：冗余量（即信息冗余量）R=L-HR=L-H5.5.结构冗余结构冗余 有些图像从整体上看存在着非常强的纹理结构。有些图像从整体上看存在着非常强的纹理结构。下图为草席图像。是一种下图为草席图像。是一种规则有序排列的图形，规则有序排列的图形，我们称它在结构上存在冗余我们称它在结构上存在冗余 。是一种结构冗余。是一种结构冗余。规则有序排列的图形6.6.知识冗余知识冗余 有些图像的理解与某些知识有相当大的相关有些图像的理解与某些知识有相当大的相关性。性。比如人脸的图像有固定的结构：比如人脸的图像有固定的结构：嘴的上方有鼻子、鼻子的上方有双眼睛，鼻嘴的上方有鼻子、鼻子的上方有双眼睛，鼻子位于正脸图像的中线上等等子位于正脸图像的中线上等等 这类规律的结构可由先验知识和背景知识得这类规律的结构可由先验知识和背景知识得到，因此这类信息对一般人来说就是冗余信息。到，因此这类信息对一般人来说就是冗余信息。这就是知识冗余。这就是知识冗余。7.7.视觉冗余视觉冗余 由于人眼的视觉特性有所限制，人类的视觉由于人眼的视觉特性有所限制，人类的视觉系统不能对图像画面的任何变化都能感觉到。系统不能对图像画面的任何变化都能感觉到。举例：举例：人眼视觉系统的一般分辨率为人眼视觉系统的一般分辨率为6464灰度等级灰度等级,而而一般图像的量化采用的是一般图像的量化采用的是256256的灰度等级。的灰度等级。这种差别就是视觉冗余。这种差别就是视觉冗余。视频压缩编码方法及其分类视频压缩编码方法及其分类 图像压缩的基本目标就是减小数据量。图像压缩的基本目标就是减小数据量。至于图像压缩到什么程度而又没有明显的至于图像压缩到什么程度而又没有明显的失真失真,则取决于图像数据的冗余度。则取决于图像数据的冗余度。所有的所有的这些冗余度都可以被除去而不会引起显著这些冗余度都可以被除去而不会引起显著的信息损失。的信息损失。空间冗余空间冗余和和时间冗余时间冗余是图像信号最常见的冗是图像信号最常见的冗余。余。压缩编码分类压缩编码分类1.1.按恢复的图像性质划分按恢复的图像性质划分 按恢复的图像性质按恢复的图像性质,数字图像压缩方法可以数字图像压缩方法可以分为两种：分为两种：无损压缩编码无损压缩编码 有损压缩编码有损压缩编码 压缩编码分类压缩编码分类 无损压缩编码：无损压缩编码：也称为熵编码、可逆编码或无失真编码。也称为熵编码、可逆编码或无失真编码。当系统采用此方法进行数据压缩时当系统采用此方法进行数据压缩时,在接收在接收端所获得的解码与原图像完全相同。端所获得的解码与原图像完全相同。无损压缩不能提供较高的压缩比。无损压缩不能提供较高的压缩比。一般在一般在2:12:15:15:1。压缩编码分类压缩编码分类 有损编码：有损编码：也称为不可逆编码、熵压缩编码或失真编也称为不可逆编码、熵压缩编码或失真编码。码。由于压缩了熵，会减少信息而不能再恢复。由于压缩了熵，会减少信息而不能再恢复。这种压缩编码具有较高的压缩比。这种压缩编码具有较高的压缩比。最大可达几百比一。最大可达几百比一。压缩编码分类压缩编码分类2.2.按压缩方法的原理划分按压缩方法的原理划分 按压缩原理划分按压缩原理划分,数字图像压缩方法可以分为以数字图像压缩方法可以分为以下几种编码下几种编码:预测编码预测编码 变换编码变换编码 标量量化和矢量量化编码标量量化和矢量量化编码 信息熵编码信息熵编码 子带编码子带编码 结构编码结构编码 模型编码模型编码图像压缩编码无损压缩有损压缩霍夫曼编码行程编码算术编码L-Z编码预测编码:量化编码:模型编码:混合编码:变换编码:DPCM；运动补偿DCT；子带编码分形编码；知识基编码JPEG；MPEG；H.26X编码采样编码；矢量量化编码图像压缩算法分类图像压缩算法分类压缩编码分类压缩编码分类（1 1）预测编码：）预测编码：其典型的压缩方法有其典型的压缩方法有DPCMDPCM和和ADPCM.ADPCM.它它们比较适合于图像数据的压缩。们比较适合于图像数据的压缩。它主要是减少图像数据在它主要是减少图像数据在空间上空间上和和时间上时间上的相关性，从而达到数据压缩的目的，但的相关性，从而达到数据压缩的目的，但这是一种有失真的压缩方法。这是一种有失真的压缩方法。压缩编码分类压缩编码分类（2 2）变换编码：）变换编码：它是将图像它是将图像时域信号时域信号转换到转换到变换域变换域（系数空（系数空间、频域）上进行处理。间、频域）上进行处理。在实际编码中，常常利用图像的统计特性和在实际编码中，常常利用图像的统计特性和人眼的视觉特性，只是选择部分变换系数来进行人眼的视觉特性，只是选择部分变换系数来进行信息传输，因此恢复的图像中将存在一定的失真。信息传输，因此恢复的图像中将存在一定的失真。常用的正交变换有：离散傅氏变换常用的正交变换有：离散傅氏变换DFTDFT、离、离散余弦变换散余弦变换DCTDCT、离散正弦变换、离散正弦变换DSTDST和和K-LK-L变换。变换。压缩编码分类压缩编码分类（3 3）标量量化和矢量量化编码：）标量量化和矢量量化编码：标量量化指传统的量化，是将具有无标量量化指传统的量化，是将具有无限电平的点样值，用有限电平数表示的方限电平的点样值，用有限电平数表示的方法，是一个样点、一个样点地进行量化编法，是一个样点、一个样点地进行量化编码。码。这里量化器的设计是一个很关键的步骤。这里量化器的设计是一个很关键的步骤。压缩编码分类压缩编码分类（3 3）标量量化和矢量量化编码：）标量量化和矢量量化编码：矢量编码是相对标量量化而提出的。矢量编码是相对标量量化而提出的。矢量编码中一次可以量化多个样点。矢量编码中一次可以量化多个样点。矢量量化也是一种有损压缩编码。矢量量化也是一种有损压缩编码。压缩编码分类压缩编码分类（4 4）信息熵编码：）信息熵编码：信息熵编码是一种基于图像统计特性的编码信息熵编码是一种基于图像统计特性的编码方法。方法。是一种无损压缩编码方法。是一种无损压缩编码方法。压缩编码分类压缩编码分类（4 4）信息熵编码：）信息熵编码：它是根据信息熵的原理：它是根据信息熵的原理：用最短的位数表示出现概率大的信息，而出现用最短的位数表示出现概率大的信息，而出现概率较小的信息则用较长的位数来表示，以此达概率较小的信息则用较长的位数来表示，以此达到压缩数据的目的。到压缩数据的目的。常见的熵编码有常见的熵编码有哈夫曼编码哈夫曼编码、游程编码游程编码和和算术算术编码编码。压缩编码分类压缩编码分类（5 5）子带编码：）子带编码：在子带编码中，首先将图像数据转换到频在子带编码中，首先将图像数据转换到频域，然后按频率分成若干子带，对每个子带用不域，然后按频率分成若干子带，对每个子带用不同的编码器进行抽样、量化和编码，并将各子带同的编码器进行抽样、量化和编码，并将各子带输出数据合成为数据码流，从而获得压缩数据。输出数据合成为数据码流，从而获得压缩数据。压缩编码分类压缩编码分类（6 6）结构编码：）结构编码：结构编码也称为第二代编码。结构编码也称为第二代编码。编码时首先求出图像中的边界、轮廓、编码时首先求出图像中的边界、轮廓、纹理等结构特征参数，然后保存这些参数纹理等结构特征参数，然后保存这些参数信息，进行编码。信息，进行编码。在解码时则根据这些结构和参数信息进在解码时则根据这些结构和参数信息进行图像合成，从而恢复出原图像。行图像合成，从而恢复出原图像。压缩编码分类压缩编码分类（7 7）模型编码：）模型编码：这是一种基于知识的编码。这是一种基于知识的编码。利用人们对自然知识的了解而形成一个利用人们对自然知识的了解而形成一个规则库，将人脸变化等特征用一系列参数规则库，将人脸变化等特征用一系列参数来进行描述。来进行描述。利用参数再加上模型就可以实现人脸的利用参数再加上模型就可以实现人脸的图像编码和解码，达到压缩图像数据的目图像编码和解码，达到压缩图像数据的目的。的。数据压缩技术的性能指标数据压缩技术的性能指标 1 1、压缩比、压缩比用来定义压缩性能。指压缩过程中输入数据用来定义压缩性能。指压缩过程中输入数据量与输出数据量之比。量与输出数据量之比。设原图像的平均码长为设原图像的平均码长为Lc,Lc,压缩后图像的平均码压缩后图像的平均码长为长为L L，则压缩比，则压缩比C C为为压缩比越大，说明数据压缩的程度越高。冗余度冗余度和和编码效率编码效率也是衡量信源特性以及编解码也是衡量信源特性以及编解码设备性能的重要指标，定义如下：设备性能的重要指标，定义如下：冗余度冗余度:指冗余量在信息量中占的比例指冗余量在信息量中占的比例 L L为平均码字长度为平均码字长度 H(X)H(X)为信源熵。为信源熵。编码效率编码效率：指信息量在数据量中占的比例：指信息量在数据量中占的比例 数据压缩技术的性能指标数据压缩技术的性能指标2 2、重现质量：、重现质量：恢复效果要好，要尽可能地恢复原始数据。恢复效果要好，要尽可能地恢复原始数据。3 3、压缩和解压缩速度、压缩和解压缩速度无损图像压缩编码方法无损图像压缩编码方法 无失真（无损）图像压缩编码就是指图无失真（无损）图像压缩编码就是指图像经过压缩、编码后恢复出的图像与原图像经过压缩、编码后恢复出的图像与原图像完全一样像完全一样,没有任何失真。没有任何失真。无失真压缩编码无失真压缩编码-熵熵编码编码。广泛应用于文本数据和特殊应用场合广泛应用于文本数据和特殊应用场合的图像数据（指纹图像、医学图像、卫星的图像数据（指纹图像、医学图像、卫星图像等）的压缩。图像等）的压缩。无损图像压缩编码方法无损图像压缩编码方法 香农信息论认为香农信息论认为,信源中或多或少地含信源中或多或少地含有自然冗余度。有自然冗余度。这些冗余度既来自于信源本身的相关性这些冗余度既来自于信源本身的相关性,又来自于信源概率分布的不均匀性中。又来自于信源概率分布的不均匀性中。只要找到去除相关性或改变概率分布不只要找到去除相关性或改变概率分布不均匀性的方法和手段均匀性的方法和手段,也就找到了信息熵编也就找到了信息熵编码的方法。码的方法。无损图像压缩编码方法无损图像压缩编码方法 例如：例如：在图像中存在着空间上的相关性在图像中存在着空间上的相关性 对运动图像而言存在着帧与帧之间在时间对运动图像而言存在着帧与帧之间在时间上的相关性。上的相关性。这些都说明存在着颜色的概率分布的不均匀这些都说明存在着颜色的概率分布的不均匀性。性。无损图像压缩编码方法无损图像压缩编码方法 信息熵编码所要解决的问题：信息熵编码所要解决的问题：如何利用信息熵理论（香农信息论）减如何利用信息熵理论（香农信息论）减少数据在传输和存储时的冗余度。少数据在传输和存储时的冗余度。香农信息论香农信息论 香农信息论认为：香农信息论认为：信源所含有的信息熵就是进行无失真编码的信源所含有的信息熵就是进行无失真编码的理论极限。理论极限。香农信息论香农信息论 低于此极限的无失真编码方法是找不到的低于此极限的无失真编码方法是找不到的,而只要不低于此极限而只要不低于此极限,那就总能找到某种适宜的那就总能找到某种适宜的编码方法任意的逼近信息熵。编码方法任意的逼近信息熵。熵编码的目的就是要使编码后的图像熵编码的目的就是要使编码后的图像平均码字平均码字长度（比特数）长度（比特数）L L近可能接近这个近可能接近这个信息熵信息熵H(x)H(x)无损图像压缩编码方法无损图像压缩编码方法根据：根据：L=H+R L=H+R H H：信源熵（信息量：信源熵（信息量/符号，代表符号的最小符号，代表符号的最小比特数）、比特数）、L L：数据量（每个符号实际平均的比特数，：数据量（每个符号实际平均的比特数，也称也称码字长度码字长度）R R：冗余量（即信息冗余量）：冗余量（即信息冗余量）R=L-HR=L-H 无损数据压缩的本质：通过减少冗余量无损数据压缩的本质：通过减少冗余量R R，减少数据量减少数据量L L，使之接近，使之接近H H。无损图像压缩编码方法无损图像压缩编码方法 无损图像压缩编码方法由于其中并没有考无损图像压缩编码方法由于其中并没有考虑人眼的视觉特性虑人眼的视觉特性,因此其所能达到的压缩因此其所能达到的压缩比非常有限。比非常有限。常用的无失真图像压缩编码有：常用的无失真图像压缩编码有：哈夫曼编码哈夫曼编码 游程编码（行程编码）游程编码（行程编码）算术编码算术编码 无损图像压缩编码方法无损图像压缩编码方法 在实际应用中在实际应用中,常将游程编码与哈夫曼编常将游程编码与哈夫曼编码结合起来使用码结合起来使用,例如在例如在H.261H.261、JPEGJPEG、MPEGMPEG等国际标准中正是采用此种编码技术。等国际标准中正是采用此种编码技术。而在而在H.263H.263等国际标准中则采用算术编码技等国际标准中则采用算术编码技术。术。哈夫曼编码哈夫曼编码 哈夫曼哈夫曼(Huffman)(Huffman)编码方法于编码方法于19521952年问世年问世,迄迄今为止仍经久不衰今为止仍经久不衰,广泛应用于各种数据压广泛应用于各种数据压缩技术中缩技术中,且仍不失为熵编码中的最佳编码且仍不失为熵编码中的最佳编码方法。方法。主要编码思路：主要编码思路：对对出现频率较大出现频率较大的符号用的符号用较短的码较短的码来表示，来表示，而对于而对于出现频率较小出现频率较小的符号则用的符号则用较长的码较长的码来表示。来表示。这样的编码结果所获得的平均码字长度最这样的编码结果所获得的平均码字长度最短。短。哈夫曼编码哈夫曼编码 哈夫曼编码的码长是变化的，即可变长哈夫曼编码的码长是变化的，即可变长编码编码(VLC),(VLC),而且哈夫曼编码通常被称为最优而且哈夫曼编码通常被称为最优码。码。最优的含义是：最优的含义是：对于给定的符号集和概率模型，找不到任对于给定的符号集和概率模型，找不到任何其它整数码比哈夫曼编码有更短的码长。何其它整数码比哈夫曼编码有更短的码长。整数码：指每个符号所对应的码字的位数整数码：指每个符号所对应的码字的位数都是整数。都是整数。哈夫曼编码哈夫曼编码具体编码过程：具体编码过程：1 1、排序：按符号出现的概率从大到小进、排序：按符号出现的概率从大到小进行排列。行排列。2 2、赋值：对排在最后的两个符号进行、赋值：对排在最后的两个符号进行赋值，概率大的赋赋值，概率大的赋“1”1”，概率小的赋，概率小的赋“0”0”。或相反。或相反。3 3、合并：将上述最后的两个符号出现、合并：将上述最后的两个符号出现的概率相加合成一个概率。的概率相加合成一个概率。哈夫曼编码哈夫曼编码4 4、重新排序：将合成后的概率与其它符号、重新排序：将合成后的概率与其它符号概率一起进行重新排序（从大到小）。然概率一起进行重新排序（从大到小）。然后重复步骤后重复步骤2 2、3 3的内容，直至概率相加为的内容，直至概率相加为1 1为止。为止。5 5、码字分配：从最后一步开始反向进行码、码字分配：从最后一步开始反向进行码字分配。从而形成一个码字。字分配。从而形成一个码字。哈夫曼编码的基本原理哈夫曼编码的基本原理例：例：aaaaaaaa bbbbbb cccc d d eeeeeeeeee ffffffffffffff 4 3 2 1 5 7 4 3 2 1 5 7 如果不进行特殊的编码，用字符方式如果不进行特殊的编码，用字符方式（ASCIIASCII码）传送，每个字符码）传送，每个字符8 8位，需要的数位，需要的数据量为：据量为：22*8=22*8=176176 bit bit 哈夫曼编码的基本原理哈夫曼编码的基本原理cbafe7/225/224/222/2210f=11 e=01 a=00 b=101 c=1001 d=1000d1/223/226/2222/2213/229/223/2210101010哈夫曼编码哈夫曼编码原始符号原始符号各符号出现概率各符号出现概率组成的二进制码组成的二进制码码长码长La a4/224/2200002 2b b3/223/221011013 3c c2/222/22100110014 4d d1/221/22100010004 4e e5/225/2201012 2f f7/227/2211112 2哈夫曼编码的基本原理哈夫曼编码的基本原理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比比22*8=176bit 22*8=176bit 少了少了123123bitbit平均编码长度平均编码长度平均编码长度平均编码长度L L L L为为为为哈夫曼编码的基本原理哈夫曼编码的基本原理例例 设信号源为设信号源为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,试给出该信源的霍夫曼编码方案。试给出该信源的霍夫曼编码方案。并计算压缩比并计算压缩比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 teacher”“I am a teacher”，共，共1414个字个字符，其中包括符，其中包括9 9个不同的字符。个不同的字符。（1 1）若使用自然编码（等长二进制编码），该字）若使用自然编码（等长二进制编码），该字符串中有符串中有9 9个不同的符号，至少需要个不同的符号，至少需要4 4位二进制才位二进制才能表示，这样传送该字符串也要能表示，这样传送该字符串也要5656位。位。（2 2）HuffmanHuffman编码只需要编码只需要4242位位，平均编码长度为，平均编码长度为2.982.98。平均码字长度公式为：平均码字长度公式为：求压缩比、冗余度和编码效率求压缩比、冗余度和编码效率求压缩比、冗余度和编码效率求压缩比、冗余度和编码效率:压缩比压缩比压缩比压缩比C C C C：14 14 14 14个字符，需个字符，需个字符，需个字符，需4 4 4 4位二进制数位二进制数位二进制数位二进制数 Lc=4 Lc=4 Lc=4 Lc=4 C=Lc/L=4/2.98=C=Lc/L=4/2.98=C=Lc/L=4/2.98=C=Lc/L=4/2.98=1.34:11.34:11.34:11.34:1 冗余度冗余度冗余度冗余度R R R R=(L-H)/H=(2.98-2.97)/2.97=0.34%=(L-H)/H=(2.98-2.97)/2.97=0.34%=(L-H)/H=(2.98-2.97)/2.97=0.34%=(L-H)/H=(2.98-2.97)/2.97=0.34%编码效率编码效率编码效率编码效率哈夫曼编码哈夫曼编码例：某信源符号及其对应的概率如下：例：某信源符号及其对应的概率如下：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.04 0.1 0.1 0.07 0.06 0.18 0.40 0.04 0.1 0.1 0.07 0.06 0.18 0.040.04请完成哈夫曼编码，并计算压缩比、冗余度请完成哈夫曼编码，并计算压缩比、冗余度和编码效率。和编码效率。a1:a1:0 0 a2:a2:11100 11100 a3:a3:100 100 a4:a4:1111 1111 a5:a5:1011 1011 a6:a6:1010 1010 a7:a7:11101 11101 a8:a8:110110哈夫曼编码哈夫曼编码 特点：特点：特点：特点：（1 1）虽然哈夫曼码长可变）虽然哈夫曼码长可变,但却不需要另附但却不需要另附同步码。同步码。（2 2）通信双方只要均拥有预先编写的解释通信双方只要均拥有预先编写的解释各种代码意义的各种代码意义的词典词典(即即码本码本),),即可根据即可根据码本码本逐码译出。逐码译出。哈夫曼编码哈夫曼编码哈夫曼编码有几个问题值得注意哈夫曼编码有几个问题值得注意:一、哈夫曼码没有错误保护功能。一、哈夫曼码没有错误保护功能。如果码串中有错如果码串中有错,哪怕仅仅是哪怕仅仅是1 1位出错位出错,不不但该码本身将会译错但该码本身将会译错,更糟糕的是对后面的更糟糕的是对后面的影响影响,一错就是一串一错就是一串,一般称这种现象为错误一般称这种现象为错误传播。传播。哈夫曼编码哈夫曼编码二、不可调用中间的内容二、不可调用中间的内容 哈夫曼码是可变长度码，因此很难随意哈夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再查找或调用压缩文件中间的内容，然后再译码译码;三、接收端需保存一个与发送端相同的霍夫三、接收端需保存一个与发送端相同的霍夫曼码表曼码表 哈夫曼码还是得到广泛应用哈夫曼码还是得到广泛应用,哈夫曼哈夫曼编码毕竟属于最佳编码方法。编码毕竟属于最佳编码方法。游程编码游程编码RLCRLC 游程编码（行程编码）游程编码（行程编码）RLCRLC（RLE)RLE)是一种是一种非常简单的数据压缩编码形式。它在某些非常简单的数据压缩编码形式。它在某些场合是非常有效的一种无损压缩编码方法。场合是非常有效的一种无损压缩编码方法。游程编码游程编码RLCRLC 游程编码编码原则游程编码编码原则:连续重复的数据值序列（或称为连续重复的数据值序列（或称为“流流”）用一个重复次数和单个数据值来代替。用一个重复次数和单个数据值来代替。比如：得到的字符串为比如：得到的字符串为AAAAAABCDDDDDDDDDBBBBBBBBAAAAAABCDDDDDDDDDBBBBBBBB 可压缩为可压缩为*6ABC*9D*8B*6ABC*9D*8B 颜色相同的区域游程编码游程编码RLCRLC 不需要存储每一个像素的颜色值，而仅存不需要存储每一个像素的颜色值，而仅存储一个像素的颜色值以及具有相同颜色的像素数储一个像素的颜色值以及具有相同颜色的像素数目。目。或者存储一个像素的颜色值，以及具有相同颜或者存储一个像素的颜色值，以及具有相同颜色值的行数。色值的行数。这种压缩编码称为这种压缩编码称为游程编码游程编码或或行程编码行程编码。游程编码游程编码RLCRLC 游程编码多用于黑白图像或图形的压缩。游程编码多用于黑白图像或图形的压缩。具有相同灰度等级的连续的像素数目称为具有相同灰度等级的连续的像素数目称为游程游程长度长度RLRL。图像中具有相同灰度的图像块越大越多，压缩图像中具有相同灰度的图像块越大越多，压缩的效果就越好。的效果就越好。宽度：宽度：宽度：宽度：263 263 263 263 宽度：宽度：宽度：宽度：263263263263 高度：高度：高度：高度：300 300 300 300 高度：高度：高度：高度：300 300 300 300 灰度：灰度：灰度：灰度：4 4 4 4 灰度：灰度：灰度：灰度：8 8 8 8 游程编码游程编码RLCRLC RLCRLC特点：特点：编码简单直观，编码编码简单直观，编码/解码速度快解码速度快，只需要简只需要简单地复制字符若干遍即可以了。单地复制字符若干遍即可以了。BMPBMP、TIFFTIFF、AVIAVI等格式文件的压缩均采用此方等格式文件的压缩均采用此方法。在法。在PDFPDF文件格式中也得到应用。文件格式中也得到应用。存在着不同的实现技术和文件格式。存在着不同的实现技术和文件格式。游程编码游程编码RLCRLC的构成的构成在在RLCRLC中用中用3 3个字节表示一个字符串：个字节表示一个字符串：由一个指示符、一个重复次数字节和一个被重复的由一个指示符、一个重复次数字节和一个被重复的字符构成的字符构成的3 3字节码字节码 指示符指示符 重复次数重复次数RLRL 被重复字符被重复字符 思考：RL?时，数据压缩才用意义3游程编码游程编码RLCRLC方法方法例如例如:字符串字符串 RTAAAASDEEEEERTAAAASDEEEEE经经RLERLE压缩后为：压缩后为：RT*4ASD*5E RT*4ASD*5E “*4A”“*4A”代替了代替了“AAAA”“AAAA”“*5E”“*5E”代替代替“EEEEE”“EEEEE”指示符采用特殊字符指示符采用特殊字符*：指出一个指出一个RLCRLC编码的开始，后面的数字表编码的开始，后面的数字表示重复的次数，数字后的单个字符是被重示重复的次数，数字后的单个字符是被重复的字符。复的字符。游程编码游程编码RLCRLC方法方法例例:设有数据设有数据“AAAABBBBCCCCCCCDAAAAAAAAAABBBBCCCCCCCDAAAAAA”试计算该数据的行程编码。试计算该数据的行程编码。解：解：A A重复重复4 4次，次，B B重复重复4 4次，次，C C重复重复7 7次，次，D D不重复，不重复，A A重复重复6 6次，次，RLC RLC数据流为：数据流为：“#4A#4B#7CD#6A#4A#4B#7CD#6A”，其中，其中#为指示符。总共占用为指示符。总共占用1313个字节，而源数据占用个字节，而源数据占用2222个字节。个字节。游程编码也可以不用指示符游程编码也可以不用指示符:重复与否相同对待，相应的重复与否相同对待，相应的RLCRLC为为“3A4B5C1D6A3A4B5C1D6A”占用占用1010个字节。个字节。游程编码游程编码RLCRLC方法方法 例：例：aaaaaaaa bbbbbb cccc d d eeeeeeeeee ffffffffffffff (共共22*8=176 bit)22*8=176 bit)4a3b2c1d5e7f 4a3b2c1d5e7f (共共12*8=96 bit)12*8=96 bit)压缩率为：压缩率为：176/96=1.83:1176/96=1.83:1游程编码游程编码 游程编码的压缩率不高，但编码、解码游程编码的压缩率不高，但编码、解码的速度快，仍被得到广泛的应用。的速度快，仍被得到广泛的应用。特别是在特别是在变换编码变换编码后再进行后再进行游程编码游程编码，有很，有很好的效果。在图像数据压缩标准好的效果。在图像数据压缩标准(JPEG)(JPEG)中扮中扮演重要角色。演重要角色。算术编码算术编码 算术编码产生于算术编码产生于2020世纪世纪6060年代初年代初,在图在图像数据压缩标准中算术编码扮演了重要的像数据压缩标准中算术编码扮演了重要的角色。能有效地压缩信源冗余度，属于熵角色。能有效地压缩信源冗余度，属于熵编码的一种。编码的一种。该方法实现较为复杂，常与其它有损压该方法实现较为复杂，常与其它有损压缩编码结合使用，在视频数据压缩标准缩编码结合使用，在视频数据压缩标准(如如H.263)H.263)中扮演重要角色。中扮演重要角色。算术编码算术编码 算术编码与哈夫曼编码一样，也是对概率算术编码与哈夫曼编码一样，也是对概率较大的符号采用短码，对概率较小的符号较大的符号采用短码，对概率较小的符号采用长码。采用长码。它突破了哈夫曼编码每个符号只能按整数它突破了哈夫曼编码每个符号只能按整数比特来逼近信源熵的限制比特来逼近信源熵的限制:每个符号的平均编码长度可以按每个符号的平均编码长度可以按小数比小数比特特来逼近信源熵。来逼近信源熵。算术编码基本思想算术编码基本思想 算术编码不是将单个信源符号映射成一个码算术编码不是将单个信源符号映射成一个码字。字。而是把而是把整个信源整个信源表示为实数线上的表示为实数线上的0 0到到1 1之间的之间的一个区间，其长度等于该一个区间，其长度等于该信源信源的概率。的概率。再在该区间内选择一个代表性的小数，转化再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。为二进制作为实际的编码输出。算术编码基本步骤算术编码基本步骤 将编码的消息表示成实数将编码的消息表示成实数0 0和和1 1之间之间的一个区间。的一个区间。消息序列中的每个元素都要用来缩短消息序列中的每个元素都要用来缩短这个区间。这个区间。消息序列中元素越多，所得到的区间就消息序列中元素越多，所得到的区间就越小，当区间变小时，表示这一区间所需越小，当区间变小时，表示这一区间所需的二进制位就越多。的二进制位就越多。消息结束时就最后所得到区间的下边界消息结束时就最后所得到区间的下边界值表示该消息。值表示该消息。给定符号序列的算术编码步骤如下：给定符号序列的算术编码步骤如下：（1 1）初始化：）初始化：编码器开始时将编码器开始时将“当前区间当前区间”设置为一。设置为一。为为0 0，1)1)（2 2）按消息（符号序列）中符号的顺序：）按消息（符号序列）中符号的顺序：对每一符号，编码器按步骤对每一符号，编码器按步骤（a a）和和（b b）重复进重复进行处理行处理 给定符号序列的算术编码步骤如下：给定符号序列的算术编码步骤如下：（a a）编码器将编码器将“当前区间当前区间”分为分为子区间子区间，每一，每一个符号分配一个子区间。一个子区间的大小与符个符号分配一个子区间。一个子区间的大小与符号的概率成比例。号的概率成比例。（b b）对应于一个确切发生的符号，编码器选择对应于一个确切发生的符号，编码器选择其子区间，并使它成为其子区间，并使它成为新的新的“当前区间当前区间”。这也称为重新归一化。这也称为重新归一化。给定符号序列的算术编码步骤如下：给定符号序列的算术编码步骤如下：（3 3）最后一个符号对应有最后输出的）最后一个符号对应有最后输出的“当前区间当前区间”。最后输出的最后输出的“当前区间当前区间”的下边界就是该给定的的下边界就是该给定的整个符号序列的算术编码。整个符号序列的算术编码。算术编码方法算术编码方法算算术术编编码码用用到到两两个个基基本本的的参参数数：符符号号的的概概率率和和它它的累积概率。的累积概率。累积概率（下边界值）：累积概率（下边界值）：设信源符号集为设信源符号集为 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 0 0 ，a a2 2的的累累积积概率为概率为 P P0 0 0 0+P+P1 1 1 1算术编码示例：算术编码示例：符号符号符号符号 S1 S1 S1 S1、S2 S2 S2 S2、S3 S3 S3 S3、S4 S4 S4 S4 十进制概率十进制概率十进制概率十进制概率 1/8 1/4 1/2 1/8 1/8 1/4 1/2 1/8 1/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 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.1110 0.001 0.011 0.1110 0.001 0.011 0.111 0 1/8 3/8 7/8 1 0 1/8 3/8 7/8 1 0 1/8 3/8 7/8 1 0 1/8 3/8 7/8 1 0 0.001 0.011 0.111 10 0.001 0.011 0.111 10 0.001 0.011 0.111 10 0.001 0.011 0.111 1 S1S2S3S4现在以符号序列：现在以符号序列：s3 s3 s2 s4 s3 s3 s2 s4 为例来解释编码过程为例来解释编码过程算术编码的基本法则归纳如下算术编码的基本法则归纳如下:(1)(1)初始状态初始状态 区间起始点区间起始点C=0C=0,区间宽度区间宽度A=1.0A=1.0。(2)(2)新区间起点新区间起点C C=原起点原起点C+C+原区间宽度原区间宽度AAP Pr r,新区间宽度新区间宽度A A=原区间宽度原区间宽度AAPi Pi 其中其中P Pr r为所编符号为所编符号si si对应的对应的累积概率累积概率 Pi Pi为所编符号为所编符号si si对应的对应的概率概率。对序列对序列s3 s3 s2 s4s3 s3 s2 s4 进行编码的过程如下进行编码的过程如下:初始起点初始起点C=0 C=0 初始区间宽度初始区间宽度A=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.1110.011-0.111第第2 2个符号个符号s3s3:新区间起点：新区间起点：C C=0.011+0.10.011=0.1001=0.011+0.10.011=0.1001新区间宽度新区间宽度：A A=0.1=0.10.10.1=0.01=0.01 区间终点区间终点0.11010.1101新的新的当前区间当前区间为：为：0.1001-0.11010.1001-0.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.101010.10011-0.10101 第第4 4个符号个符号s4:s4:新区间起点：新区间起点：C C=0.10011+0.0001=0.10011+0.00010.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的最小整数。的最小整数。代码取其值小数点后的代码取其值小数点后的L L位。若有尾数，就进位位。若有尾数，就进位到第到第L L位。位。如：如：则取则取 L=3 L=3 如果最后符号的下边界为如果最后符号的下边界为0.101100010.10110001 取：取：c=0.110c=0.110 传输的二进制代码序列是传输的二进制代码序列是110110刚才例题最终编完的码字刚才例题最终编完的码字0.10100110.1010011传输传输s3 s3 s2 s4s3 s3 s2 s4共共4 4个符号，得个符号，得取取7 7位位所以传输的码流为所以传输的码流为10100111010011压缩率为：压缩率为：42/7=8/7=1.14:142/7=8/7=1.14:1算术编码解码过程算术编码解码过程 在解码器中在解码器中,当收到码字串当收到码字串0.10100110.1010011时时,这个码字串指向子区间这个码字串指向子区间0.011,0.111)0.011,0.111),解出的第一个符号应为解出的第一个符号应为s3s3 0 0.001 0.011 0.111 1.0 0 0.001 0.011 0.111 1.0 0 0.001 0.011 0.111 1.0 0 0.001 0.011 0.111 1.0 S1S2S3S4算术编码解码过程算术编码解码过程 之后采取与编码过程相反的步骤：之后采取与编码过程相反的步骤：即：从码字串中减去即：从码字串中减去已解符号已解符号的的累积概率累积概率,并将并将差差值值除以除以概率值概率值,则得到新码字串。则得到新码字串。(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。后面的过程以此类推后面的过程以此类推 0 0.001 0.011 0.111 1.0 0 0.001 0.011 0.111 1.0 0 0.001 0.011 0.111 1.0 0 0.001 0.011 0.111 1.0 S1S2S3S4（0.100011-0.0110.100011-0.011）/0.1=0.01011/0.1=0.01011 0.01011 0.01011在在0.0010.001，0.0110.011）所以是所以是s2s2区间区间 解出的第解出的第3 3个符号为个符号为s2s2第四步：（第四步：（0.01011-0.0010.01011-0.001）/0.01=0.111/0.01=0.111因为因为0.1110.111在在0.1110.111，1.01.0）是）是s4s4区间区间解出的第解出的第4 4个符号为个符号为s4s4所以（所以（0.111-0.1110.111-0.111）/0.001=0/0.001=0 即：即：s3 s3 s2 s4s3 s3 s2 s4 解码完毕！解码完毕！0 0.001 0.011 0.111 1.00 0.001 0.011 0.111 1.00 0.001 0.011 0.111 1.00 0.001 0.011 0.111 1.0S1S2S3S4例：假设信源符号为例：假设信源符号为AA，B B，C C，DD，这些符号，这些符号的概率分别为的概率分别为 0.1 0.1，0.40.4，0.20.2，0.3 0.3，根据这些概率可把间隔根据这些概率可把间隔0 0，1 1）分成）分成4 4个子间个子间0 0，0.10.1）、）、0.10.1，0.50.5）、）、0.50.5，0.70.7）、）、0.70.7，1 1），），其中其中x x，y y）表示半开放间隔，即包含）表示半开放间隔，即包含x x不包含不包含y y。符号符号 A A B B C C D D 概率概率 0.1 0.1 0.4 0.4 0.2 0.2 0.3 0.3 初始编码子间隔初始编码子间隔 00，0.1)0.1)0.10.1，0.5)0.5)0.50.5，0.7)0.7)0.70.7，1 1）累积概率累积概率 0 0 0.1 0.1 0.5 0.5 0.7 0.7二进制消息序列的输入为：二进制消息序列的输入为：C A D A C D B C A D A C D B。编码：编码：首先输入的符号是首先输入的符号是C C：新区间起点：新区间起点：C C=0+1=0+10.50.5=0.5=0.5新区间宽度：新区间宽度：A A=1=10.20.2=0.2=0.2 区间终点区间终点:0.5+0.2=0.7:0.5+0.2=0.7新的当前区间范围为：新的当前区间范围为：0.5-0.70.5-0.7二进制消息序列的输入为：二进制消息序列的输入为：C A D A C D B C A D A C D B。新的当前区间范围为：新的当前区间范围为：0.5-0.70.5-0.7 新区间宽度：新区间宽度：A A=1=10.20.2=0.2=0.2 第第2 2个符号个符号A:A:新区间起点：新区间起点：C C=0.5+0.2=0.5+0.20 0=0.5=0.5新区间宽度：新区间宽度：A A=0.2=0.20.10.1=0.02 =0.02 终点：终点：0.5+0.02=0.520.5+0.02=0.52新的当前区间为：新的当前区间为：0.5-0.520.5-0.52二进制消息序列的输入为：二进制消息序列的输入为：C A D A C D B C A D A C D B。当前区间为：当前区间为：0.5-0.520.5-0.52新区间宽度：新区间宽度：A A=0.2=0.20.10.1=0.02 =0.02 第第3 3个符号个符号D:D:新区间起点：新区间起点：C C=0.5+0.02=0.5+0.020.70.7=0.514=0.514新区间宽度：新区间宽度：A A=0.02=0.020.30.3=0.006 =0.006 终点：终点：0.514+0.006=0.520.514+0.006=0.52新的当前区间为：新的当前区间为：0.514-0.520.514-0.52二进制消息序列的输入为：二进制消息序列的输入为：C A D A C D B C A D A C D B。当前区间为：当前区间为：0.514-0.520.51