多媒体数据压缩技术课件.ppt

1、 多媒体数据压缩技术概述概述常用的数据压缩技术常用的数据压缩技术数据压缩新技术数据压缩新技术 多媒体数据压缩标准多媒体数据压缩标准 多媒体数据压缩技术概述数据压缩的必要性和可能性数据压缩的必要性和可能性 数据压缩的必要性数据压缩的必要性尺寸尺寸：640480类型：类型：24位位真彩色图像真彩色图像大小大小：900KB/帧帧制式：制式：NTSC类型：类型：视频视频大小大小：26.4MB/秒秒音质：音质：CD音质音质类型：类型：音频音频大小大小：10.09MB/分分多媒体数据压缩技术概述数据压缩的必要性和可能性数据压缩的必要性和可能性 数据压缩的必要性数据压缩的必要性 数据压缩的可能性数据压缩的可

2、能性标标 准：准：JPEG格格 式：式：.JPG压缩比压缩比：几倍到几十倍几倍到几十倍 数据压缩可以有效地解决多媒体信息的存储与实时数据压缩可以有效地解决多媒体信息的存储与实时传输问题传输问题 多媒体数据压缩技术概述 数据冗余的类型数据冗余的类型.空间冗余空间冗余 这是静态图像数据存在的最主要的一种冗余。在这是静态图像数据存在的最主要的一种冗余。在同一幅图像中，规则物体和规则背景的表面物理同一幅图像中，规则物体和规则背景的表面物理特性具有相关性，这些相关性的光成像结果在数特性具有相关性，这些相关性的光成像结果在数字化图像中就表现为数据冗余。字化图像中就表现为数据冗余。例如，某图片画面中有一个规

3、则物体，其表面颜例如，某图片画面中有一个规则物体，其表面颜色均匀，各部分的亮度、饱和度相近，将该图片色均匀，各部分的亮度、饱和度相近，将该图片进行数字化处理，生成位图图像。其中的规则物进行数字化处理，生成位图图像。其中的规则物体区域内，各像素点的数据是完全一样的或十分体区域内，各像素点的数据是完全一样的或十分接近的。这将使得数据有很大的空间冗余。接近的。这将使得数据有很大的空间冗余。数据冗余的类型2、时间冗余、时间冗余 由于序列图像（电视图像与运动图像）和语音数由于序列图像（电视图像与运动图像）和语音数据的前后存在着很强的相关性，因而包含着大量据的前后存在着很强的相关性，因而包含着大量的冗余。

4、在播放序列图像时，随着时间的推移，的冗余。在播放序列图像时，随着时间的推移，若干帧画面的同一部位没有变化，而只是其中的若干帧画面的同一部位没有变化，而只是其中的某些地方发生了变化，这就形成了时间冗余。同某些地方发生了变化，这就形成了时间冗余。同理，由于语音信号是连续的、渐变的，相邻样值理，由于语音信号是连续的、渐变的，相邻样值是相近甚至相同的，因而也存在时间冗余。是相近甚至相同的，因而也存在时间冗余。数据冗余的类型3、信息熵冗余、信息熵冗余 信息熵冗余是指数据所携带的信息量少于数据本信息熵冗余是指数据所携带的信息量少于数据本身，而反映出来的数据冗余。身，而反映出来的数据冗余。在实际信源编码中，

5、由于信源的先验概率很难预在实际信源编码中，由于信源的先验概率很难预知，一般实际的单位数据量总是大于信源熵，这知，一般实际的单位数据量总是大于信源熵，这就造成了信息熵冗余。就造成了信息熵冗余。数据冗余的类型4、视觉冗余、视觉冗余 实验表明，人类的视觉系统对于图像场的注意是实验表明，人类的视觉系统对于图像场的注意是非均匀和非线性的，并不能对图像的任何变化都非均匀和非线性的，并不能对图像的任何变化都感知。然而，在记录原始图像数据时，通常对视感知。然而，在记录原始图像数据时，通常对视觉敏感与不敏感的部分都同样对待，从而产生了觉敏感与不敏感的部分都同样对待，从而产生了数据冗余，这就是视觉冗余。数据冗余，

6、这就是视觉冗余。例如，视觉系统对亮度的敏感度远远高于对色彩例如，视觉系统对亮度的敏感度远远高于对色彩度的敏感度；分辨黑白图像细节的能力远远高于度的敏感度；分辨黑白图像细节的能力远远高于分辨彩色图像的能力；分辨红、黄之间颜色变化分辨彩色图像的能力；分辨红、黄之间颜色变化的能力最强，分辨蓝、紫之间颜色变化的能力最的能力最强，分辨蓝、紫之间颜色变化的能力最弱。弱。数据冗余的类型5、听觉冗余、听觉冗余 实验表明，人耳对不同频率的声音的敏感程度是不同的，实验表明，人耳对不同频率的声音的敏感程度是不同的，通常对低频端较之对高频端更敏感。即使是对同样声压通常对低频端较之对高频端更敏感。即使是对同样声压级的声

7、音，人耳实际感受到的音量也随频率而变化级的声音，人耳实际感受到的音量也随频率而变化 人耳对语音信号的相位变化不敏感人耳对语音信号的相位变化不敏感 人的听觉具有掩蔽效应。当几个强弱不同的声音同时存人的听觉具有掩蔽效应。当几个强弱不同的声音同时存在时，强声使弱声难以听见的现象称为同时掩蔽，它受在时，强声使弱声难以听见的现象称为同时掩蔽，它受掩蔽声音和被掩蔽声音之间的相对频率关系影响很大；掩蔽声音和被掩蔽声音之间的相对频率关系影响很大；声音在不同时间先后发生时，强声使其周围的弱声难以声音在不同时间先后发生时，强声使其周围的弱声难以听见的现象称为异时掩蔽。听见的现象称为异时掩蔽。这些人耳听不到或感知极

8、不灵敏的声音分量都可以视为这些人耳听不到或感知极不灵敏的声音分量都可以视为冗余，因而存在听觉冗余。冗余，因而存在听觉冗余。数据冗余的类型6、结构冗余、结构冗余 有些图像中的物体表面区域存在着很强的纹理结有些图像中的物体表面区域存在着很强的纹理结构，如木质纹理、布纹纹理等，这些结构往往存构，如木质纹理、布纹纹理等，这些结构往往存在着冗余，称为结构冗余。在着冗余，称为结构冗余。数据冗余的类型7、知识冗余、知识冗余 人对有些图像的理解与某些基础知识有很大的相人对有些图像的理解与某些基础知识有很大的相关性。关性。例如，人脸的图像有固定的结构。比如嘴的上方例如，人脸的图像有固定的结构。比如嘴的上方是鼻子

9、，鼻子的上面有眼睛，鼻子位于脸的中线是鼻子，鼻子的上面有眼睛，鼻子位于脸的中线上等等。上等等。这些规律性的结构可由先验知识和背景知识得到。这些规律性的结构可由先验知识和背景知识得到。人具有这样的知识，但计算机没有。计算机存储人具有这样的知识，但计算机没有。计算机存储图像时仍需要一个像素一个像素地保存，这就形图像时仍需要一个像素一个像素地保存，这就形成了冗余。成了冗余。数据压缩的基本原理 所谓数据压缩就是以尽可能少的数码来表所谓数据压缩就是以尽可能少的数码来表示信源所发出的信号，减少容纳给定的消示信源所发出的信号，减少容纳给定的消息集合或数据采样集合的信号空间。息集合或数据采样集合的信号空间。这

10、里的信号空间就是被压缩的对象，是指这里的信号空间就是被压缩的对象，是指某信号集合所占的时域、空域和频域。信某信号集合所占的时域、空域和频域。信号空间的这几种形式是相互关联的：存储号空间的这几种形式是相互关联的：存储空间的减少就意味着信号传输效率的提高，空间的减少就意味着信号传输效率的提高，节省所占用的带宽。因此，只要采取某种节省所占用的带宽。因此，只要采取某种方法减少了某个信号空间，就实现了数据方法减少了某个信号空间，就实现了数据压缩。压缩。数据压缩的基本原理 数据压缩技术的理论基础是信息论。数据压缩技术的理论基础是信息论。信息论认为，信源中或多或少含有自然冗信息论认为，信源中或多或少含有自然

11、冗余度，这些冗余度来自于信源本身的相关余度，这些冗余度来自于信源本身的相关性和信源概率分布的不均匀性中。只要找性和信源概率分布的不均匀性中。只要找到去除相关性或改变概率分布不均匀性的到去除相关性或改变概率分布不均匀性的方法和手段，就找到了数据压缩的方法。方法和手段，就找到了数据压缩的方法。数据压缩的基本原理 根据信息论的原理，可以找到最佳数据压根据信息论的原理，可以找到最佳数据压缩编码方法，数据压缩的理论极限是信息缩编码方法，数据压缩的理论极限是信息熵。即低于此极限的无失真编码方法是找熵。即低于此极限的无失真编码方法是找不到的，而只要不低于此极限，就一定能不到的，而只要不低于此极限，就一定能找

12、到某种适宜的编码方法任意地逼近熵。找到某种适宜的编码方法任意地逼近熵。数据压缩的基本原理熵的概念熵的概念 熵是信息量的度量方法，而信息量则表示消息所包熵是信息量的度量方法，而信息量则表示消息所包含的不确定性有多少。含的不确定性有多少。根据信息论原理，信息函数（即某个事件的信息量）根据信息论原理，信息函数（即某个事件的信息量）定义为：定义为：其中，其中，表示信源表示信源 发出发出 的先验概率的先验概率 表示信源表示信源X发出发出 这个消息（随机事件）后，这个消息（随机事件）后，接收端收到的信息量的量度。接收端收到的信息量的量度。niPxIii,2,1log)(2 ,:21nxxxXiPix)(i

13、xIix很显然，一个消息的可能性愈小，其信息量愈多；很显然，一个消息的可能性愈小，其信息量愈多；反之，消息的可能性愈大，则其信息量愈少。反之，消息的可能性愈大，则其信息量愈少。数据压缩的基本原理信息熵信息熵 根据信息论原理，信源根据信息论原理，信源X的熵定义为：的熵定义为：信息熵用来度量信源中每一种消息所包含的平均信信息熵用来度量信源中每一种消息所包含的平均信息量，是信息函数的统计平均值，其单位为比特。息量，是信息函数的统计平均值，其单位为比特。niiiniiiiPPxIPxIExH121log)()()(数据压缩的基本原理对于信息量，应该这样理解：对于信息量，应该这样理解：一个消息所表示的内

14、容对于接收者来说，应一个消息所表示的内容对于接收者来说，应该是事先不知道的，这样的消息才是信息，该是事先不知道的，这样的消息才是信息，否则毫无意义；否则毫无意义；这个信息要有正确的表达方式，否则接收者这个信息要有正确的表达方式，否则接收者无法理解，当然也就无法接收；无法理解，当然也就无法接收；该信息对于使用者来说是有意义的，即要有该信息对于使用者来说是有意义的，即要有使用价值。使用价值。数据压缩的基本原理信源的冗余度信源的冗余度 根据信息论原理，信源根据信息论原理，信源X的冗余度定义为：的冗余度定义为：其中，其中，为信源为信源X的熵，的熵，d为信源编码的熵，表示信为信源编码的熵，表示信源编码后

15、输出码字的平均码长，即单位数据量。源编码后输出码字的平均码长，即单位数据量。)(xHdr )(xH在信源编码中，熵值是数据压缩的理论极限，是平均在信源编码中，熵值是数据压缩的理论极限，是平均码长的下限。即，如果平均码长大于信源熵，则一定码长的下限。即，如果平均码长大于信源熵，则一定存在冗余，是可以进行压缩的。存在冗余，是可以进行压缩的。只有当平均码长等于或接近信源熵时，冗余度才等于只有当平均码长等于或接近信源熵时，冗余度才等于0，才达到压缩极限，此时的编码方法才是最佳编码，才达到压缩极限，此时的编码方法才是最佳编码举例举例例，有一幅例，有一幅64个像素组成的灰度图像，灰度共有个像素组成的灰度图

16、像，灰度共有5级，分别用符号级，分别用符号A、B、C、D、E表示。表示。64个像素个像素中出现灰度中出现灰度A的像素数有的像素数有27个，出现灰度个，出现灰度B的像素的像素数有数有15个，出现灰度个，出现灰度C的像素数有的像素数有12个，出现灰个，出现灰度度D的像素数有的像素数有6个，出现灰度个，出现灰度D的像素数有的像素数有4个。个。如果采用等长编码，则如果采用等长编码，则5个等级的灰度值至少需要个等级的灰度值至少需要3个二进制位表示，即每个像素用个二进制位表示，即每个像素用3位二进制表示，位二进制表示，则编码这幅图像总共需要则编码这幅图像总共需要643192位。位。按照信息论，这幅图像的熵

17、为：按照信息论，这幅图像的熵为：03883.2)64/4(log)64/4()64/15(log)64/15()64/27(log)64/27()(222 xH举例这就是说，每个符号平均用这就是说，每个符号平均用2.03883位表示，位表示，64个个像素用像素用130.485位即可。位即可。根据信息论原理，只要找到某种编码方法能使得根据信息论原理，只要找到某种编码方法能使得其平均码长等于或接近信源熵其平均码长等于或接近信源熵2.03883，则这种编，则这种编码方法就是最佳编码。码方法就是最佳编码。很显然，等长编码不是最佳编码。因为采用等长很显然，等长编码不是最佳编码。因为采用等长编码的平均码长

18、为编码的平均码长为3，大于信源熵，大于信源熵2.03883，存在，存在冗余，其冗余度为冗余，其冗余度为0.96117，冗余量为，冗余量为61.515位。位。数据压缩方法的分类1.按压缩方法是否产生失真分类按压缩方法是否产生失真分类 无损压缩：又称为无失真压缩，是指压缩后的数据经无损压缩：又称为无失真压缩，是指压缩后的数据经解压缩还原后，得到的数据与原始数据完全相同。解压缩还原后，得到的数据与原始数据完全相同。这类压缩方法只是去掉或减少了数据中的冗余，并没这类压缩方法只是去掉或减少了数据中的冗余，并没有损失熵，而这些冗余数据是可以重新插入到数据中有损失熵，而这些冗余数据是可以重新插入到数据中的，

19、因此无损压缩是可逆的，数据是可以原样恢复的。的，因此无损压缩是可逆的，数据是可以原样恢复的。无损压缩方法适用于要求还原的信号与原始信号完全无损压缩方法适用于要求还原的信号与原始信号完全一致的场合。例如，文本、数据、计算机程序的压缩一致的场合。例如，文本、数据、计算机程序的压缩就需要采用无损压缩。典型的无损压缩算法有算术编就需要采用无损压缩。典型的无损压缩算法有算术编码、码、Huffman编码和编码和LZW编码等统计编码方法。编码等统计编码方法。数据压缩方法的分类1.按压缩方法是否产生失真分类按压缩方法是否产生失真分类 有损压缩有损压缩：又称为熵压缩或有失真压缩，是指压缩后：又称为熵压缩或有失真

20、压缩，是指压缩后的数据经解压缩还原后，得到的数据与原始数据有所的数据经解压缩还原后，得到的数据与原始数据有所不同。不同。这类压缩方法压缩了熵，减少了信息量，数据不能完这类压缩方法压缩了熵，减少了信息量，数据不能完全恢复，不过在允许的范围内损失一定的熵，数据是全恢复，不过在允许的范围内损失一定的熵，数据是可以近似恢复的。可以近似恢复的。有损压缩方法适用于还原信号不一定非要和原始信号有损压缩方法适用于还原信号不一定非要和原始信号完全相同的场合。完全相同的场合。例，图像和声音的压缩就可以采用有损压缩。由于人例，图像和声音的压缩就可以采用有损压缩。由于人的视觉和听觉对某些信号（如颜色）不很敏感，丢掉的

21、视觉和听觉对某些信号（如颜色）不很敏感，丢掉一些数据而不至于对声音或者图像所表达的意思产生一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。常用的有损压缩算法有误解，但可大大提高压缩比。常用的有损压缩算法有预测编码、变换编码、混合编码等。预测编码、变换编码、混合编码等。数据压缩方法的分类2.按压缩方法的原理分类按压缩方法的原理分类 预测编码预测编码 变换编码变换编码 统计编码统计编码 分析分析-合成编码合成编码 混合编码混合编码数据压缩技术的性能指标1、压缩比压缩比 压缩比：一般定义为压缩前后所需的信息存储压缩比：一般定义为压缩前后所需的信息存储量或数据传输率之比。这个比

22、值越大，压缩比量或数据传输率之比。这个比值越大，压缩比越高。越高。此外，还有一种较实用的方法，就是看压缩后此外，还有一种较实用的方法，就是看压缩后的比特流中每个像素所需的比特数。的比特流中每个像素所需的比特数。例如，一幅例如，一幅640480的图像，压缩后的存储量的图像，压缩后的存储量为为614400字节，则压缩比为：字节，则压缩比为：（6144008）（）（640480）2位像素位像素数据压缩技术的性能指标2、压缩质量压缩质量压缩质量是衡量还原后的数据与原始数据之间是否有差别压缩质量是衡量还原后的数据与原始数据之间是否有差别的指标，这与压缩类型有关。的指标，这与压缩类型有关。无损压缩只去掉了

23、冗余，没有减少信息量，可以保证完全无损压缩只去掉了冗余，没有减少信息量，可以保证完全恢复原始数据，所以不必担心质量问题，但压缩比较低。恢复原始数据，所以不必担心质量问题，但压缩比较低。一般为一般为2：14：1。有损压缩除了去掉原始信源数据本身所包含的冗余信息外，有损压缩除了去掉原始信源数据本身所包含的冗余信息外，还利用了人的生理特性，进一步压缩数据。因此有损压缩还利用了人的生理特性，进一步压缩数据。因此有损压缩减少了熵，压缩前后的数据不完全相同，但人难以察觉。减少了熵，压缩前后的数据不完全相同，但人难以察觉。由于允许一定程度的失真，所以有损压缩可获得较大的压由于允许一定程度的失真，所以有损压缩

24、可获得较大的压缩比。缩比。例，例，JPEG标准的压缩比可以从几倍到几十倍，甚至上百标准的压缩比可以从几倍到几十倍，甚至上百倍。倍。MPEG标准的压缩比标准的压缩比50：1100：1数据压缩技术的性能指标3、压缩和解压缩的速度压缩和解压缩的速度 人们希望实现压缩的算法要简单，压缩和解压人们希望实现压缩的算法要简单，压缩和解压缩的速度要快，尽可能适应实时压缩和解压缩缩的速度要快，尽可能适应实时压缩和解压缩 在实际应用中，由于压缩和解压缩使用的地点、在实际应用中，由于压缩和解压缩使用的地点、场合、时间和系统不同，所以要求也不同场合、时间和系统不同，所以要求也不同例，视频会议系统，则要求视频的压缩与解

25、压缩例，视频会议系统，则要求视频的压缩与解压缩都必须是实时的，速度必须满足人眼的需求都必须是实时的，速度必须满足人眼的需求.而多媒体而多媒体CD-ROM节目，制作时可以采用非实节目，制作时可以采用非实时压缩，但播放时解压缩必须是实时的。时压缩，但播放时解压缩必须是实时的。此外，还应考虑压缩算法所需的软件和硬件。此外，还应考虑压缩算法所需的软件和硬件。压缩和解压缩过程中的硬件和软件开销与算法压缩和解压缩过程中的硬件和软件开销与算法的复杂性有关。的复杂性有关。统计编码1.问题的提出问题的提出n数据压缩的必要性和可能性数据压缩的必要性和可能性 数据压缩的必要性：数据量巨大数据压缩的必要性：数据量巨大

26、 数据压缩的可能性：存在大量的冗余数据压缩的可能性：存在大量的冗余 信源的冗余度：信源的冗余度：其中：其中：H(X)H(X)为信源为信源X X的熵，的熵，d d为信源为信源X X编码的熵，表编码的熵，表示信源编码后输出码字的平均码长，即单位数据量。示信源编码后输出码字的平均码长，即单位数据量。)(xHdr 信息论认为：信源的冗余度来自于信源本身的相关性和信源概率分布的不均匀性中。统计编码1.问题的提出问题的提出n无记忆信源能否压缩？无记忆信源能否压缩？信源分类信源分类s 记忆信源：有记忆的、存在相关性的消息序列记忆信源：有记忆的、存在相关性的消息序列s 无记忆信源：无记忆的、相对独立的的消息序

27、列无记忆信源：无记忆的、相对独立的的消息序列 无记忆信源的冗余度来自于信源中各个元素出现的概率不相等中。统计编码正是针对无记忆信源提出的2.统计编码的基本思想统计编码的原理统计编码的原理 根据消息出现概率的分布特性进行压缩编码根据消息出现概率的分布特性进行压缩编码消息消息码字码字准确恢复准确恢复 平均码长最小平均码长最小一一对应一一对应属于无失真压缩：属于无失真压缩：只去掉或减少了数据中只去掉或减少了数据中的冗余，可以完全恢复。的冗余，可以完全恢复。2.统计编码的基本思想变长码变长码统计编码中最常用的方法统计编码中最常用的方法在在Morse码中，码中，e最最常出现，编码为常出现，编码为“”q最

28、少出现，编码为最少出现，编码为“”Morse电报的报文最短电报的报文最短 字母与码字一一对应，翻译时可以准确无误。字母与码字一一对应，翻译时可以准确无误。3.Huffman编码（1）最佳编码定理）最佳编码定理在变长编码中，对于出现在变长编码中，对于出现概率大概率大的信源符号赋予的信源符号赋予短码短码字字，而对于出现，而对于出现概率小概率小的信源符号赋予的信源符号赋予长码字长码字。如果码。如果码字长度严格按照所对应符号出现概率大小的字长度严格按照所对应符号出现概率大小的逆序排列逆序排列，则编码结果则编码结果平均码字长度一定小于平均码字长度一定小于任何其他排列方式。任何其他排列方式。大概率用短码，

29、小概率用长码；大概率用短码，小概率用长码；按概率递减排列，则平均码长最小。按概率递减排列，则平均码长最小。（2）Huffman编码的具体步骤 将信源符号按概率将信源符号按概率递减顺序排列递减顺序排列；把把两个最小概率相加两个最小概率相加作为新符号的概率，并按重排；作为新符号的概率，并按重排；重复步骤、，直到重复步骤、，直到概率为概率为1；在每次合并信源时，将被合并的信源分别在每次合并信源时，将被合并的信源分别赋赋1和和0；寻找从每一信源符号到概率为寻找从每一信源符号到概率为1处的路径，记录路径上处的路径，记录路径上的的1和和0；写出每一符号的写出每一符号的“1”、“0”序列（序列（从树根到信源

30、符号从树根到信源符号节点节点）。）。合并合并赋值赋值例，例，对信源对信源进行进行Huffman编码编码的过程如下：的过程如下：04.005.006.007.010.010.018.040.0:87654321xxxxxxxxX 1 1 1 0 00011 5 1 1 0 0011 3 1 1 0（3）Huffman编码的特点 对信源对信源X进行进行Huffman编码的平均码字长度为：编码的平均码字长度为：61.2504.0505.0406.0407.0410.0310.0318.0140.01niiiLPd信源信源X的熵为：的熵为：55.2)04.0log04.005.0log05.006.0

31、log06.007.0log07.010.0log10.0218.0log18.040.0log40.0()(log)()(2222222812 iiixPxPxH最佳编码信源的冗余度信源的冗余度 根据信息论原理，信源根据信息论原理，信源X的冗余度定义为：的冗余度定义为：其中，其中，为信源为信源X的熵，的熵，d为信源编码的熵，表示信为信源编码的熵，表示信源编码后输出码字的平均码长，即单位数据量。源编码后输出码字的平均码长，即单位数据量。)(xHdr )(xH 在无失真压缩编码中，熵值是数据压缩的理论极限，是在无失真压缩编码中，熵值是数据压缩的理论极限，是平均码长的下限。平均码长的下限。只有当平

32、均码长等于或接近信源本身的熵时，冗余度才只有当平均码长等于或接近信源本身的熵时，冗余度才等于等于0，才达到压缩极限，此时的编码方法才是最佳编码。，才达到压缩极限，此时的编码方法才是最佳编码。（3）Huffman编码的特点 保证解码的唯一性，短码字不构成长码字的前缀保证解码的唯一性，短码字不构成长码字的前缀平均码长平均码长)(xHd，是最佳编码是最佳编码平均码长平均码长bitsd3（等长编码需要的比特数）（等长编码需要的比特数）等等 长长 编编 码码符号编码符号编码 X1:000 X2:001 X3:010 X4:011 X5:100 X6:101 X7:110 X8:111比特数比特数 3 （

33、23=8）4.算术编码（1）算术编码的基本定理）算术编码的基本定理 算术编码将一个信源集合表示为算术编码将一个信源集合表示为实数实数0和和1之间的一个区间之间的一个区间。这个集合中的每个元素。这个集合中的每个元素都要用来缩短这个区间。信源集合的元素越都要用来缩短这个区间。信源集合的元素越多，所得到的区间就越小，表示这一区间所多，所得到的区间就越小，表示这一区间所需的二进制位就越多。需的二进制位就越多。（1）算术编码的基本原理 基本原理基本原理采用区间作为代码采用区间作为代码 每一符号对应每一符号对应00，1 1）上的一子区间，区间长度为）上的一子区间，区间长度为 该符号出现的概率；该符号出现的

34、概率；设编码的初始区间为设编码的初始区间为00，1 1）；）；每个元素都用来每个元素都用来缩短缩短这个区间；这个区间；信源的元素越多，所得区间就越小；信源的元素越多，所得区间就越小；在最终子区间中，在最终子区间中，选取一个码字较短选取一个码字较短的作为信源的作为信源 编码。编码。（2）算术编码的具体步骤 根据每个信源符号的概率，分配根据每个信源符号的概率，分配字符范围字符范围 Clow，Chigh）；设编码区间为设编码区间为 low，high)，编码区间的长度为编码区间的长度为range；令编码的初始区间为令编码的初始区间为 0,1)；随着被编码字符的输入，子区间逐渐缩小。随着被编码字符的输入

35、，子区间逐渐缩小。按如下公式按如下公式递推计算递推计算新子区间的新子区间的low和和high值：值：low=low+rangeClow high=low+rangeChigh 将最终子区间转换为二进制数，取子区间内将最终子区间转换为二进制数，取子区间内码字较短的数作码字较短的数作为编码为编码。（3）算术编码的实例解：根据信源符号的概率，分配给每个符号的解：根据信源符号的概率，分配给每个符号的编码范围为：编码范围为：例，已知信源例，已知信源 ，对，对1011进行算术进行算术编编码码的具体过程如下：的具体过程如下：4/34/110X信源符号信源符号概率概率编码范围编码范围01/4=0.250,0.

36、25)13/4=0.750.25,1)设：编码区间为设：编码区间为low，high)，区间长度为，区间长度为range令：初始编码区间为令：初始编码区间为0，1)，则，则 当输入第一个字符当输入第一个字符“1”时，时，“1”的范围为的范围为0.25，1)即即 Clow0.25，Chigh1，所以，所以 low010.250.25 high0111 range10.250.75 此时的编码子区间为此时的编码子区间为0.25，1)算术编码过程 当输入第二个字符当输入第二个字符“0”时，时，“0”的范围为的范围为0，0.25)即即 Clow0，Chigh0.25，所以，所以 low0.250.750

37、0.25 high0.250.750.250.4375 range0.43750.250.1875 此时的编码子区间变为此时的编码子区间变为0.25，0.4375)，是区间，是区间0.25，1)的第的第1个个1/4。依此类推，编码子区间将逐渐缩小，最后的依此类推，编码子区间将逐渐缩小，最后的编码区间为编码区间为0.3320312，0.4375)，将其转换为二，将其转换为二进制数进制数0.01010101，0.0111)。分配分配范围范围递递推推计计算算 0,1/4)1/4,1)1 1/4 1 1/4,1)0 1/4 7/16 1/4,7/16)1 19/64 7/16 19/64,7/16)1

38、 85/256 7/16 85/256,7/16)码码字字 0.01010101,0.0111)011 头头0.011尾尾 算术编码过程编码过程的图示法算术编码的过程就是随着被编码字符流的输入，编算术编码的过程就是随着被编码字符流的输入，编码子区间逐渐缩小的过程。码子区间逐渐缩小的过程。算术编码的过程还可以用另一种方式表示算术编码的过程还可以用另一种方式表示图示图示算术解码过程算术解码的过程是编码的逆过程算术解码的过程是编码的逆过程 首先，根据符号概率，将区间首先，根据符号概率，将区间0，1)分成了分成了M个子区间。个子区间。然后，判断被解码的码字值落在哪个区间，赋然后，判断被解码的码字值落在

39、哪个区间，赋予对应的符号。予对应的符号。本例的译码过程如下表所示：本例的译码过程如下表所示：算术解码过程步步骤骤区区 间间译码译码符号符号译码判决译码判决10.25，1)10.375在区间在区间0.25，1)20.25，0.4375)00.375在区间在区间0.25，1)的第的第1个个1/430.296875，0.4375)10.375在区间在区间0.25，0.4375)的第的第2个个1/440.3320312，0.4375)10.375在区间在区间0.296875，0.4375)的第的第2个个1/4译码的消息为：译码的消息为：1011（3）算术编码的特点 算术编码可以是静态的或者自适应的。在

40、静态算算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改。现的频繁程度动态地进行修改。当信源符号概率比较接近时，算术编码效率高于当信源符号概率比较接近时，算术编码效率高于Huffman编码。编码。算术编码的实现方法比较复杂，尤其是硬件实现。算术编码的实现方法比较复杂，尤其是硬件实现。但但JPEG成员对多幅图像的测试结果表明，算术成员对多幅图像的测试结果表明，算术编码比编码比Huffman编码能提高了编码能提高了

41、5%左右的效率。左右的效率。因此，在因此，在JPEG的扩展系统中，用算术编码取代的扩展系统中，用算术编码取代了了Huffman编码。编码。在使用算术编码时有两个问题需要注意：在使用算术编码时有两个问题需要注意：输入信息流越长，输出数值的位数就越多。而输入信息流越长，输出数值的位数就越多。而实际计算机的精度不可能无限长，运算中出现实际计算机的精度不可能无限长，运算中出现溢出是一个明显问题。但多数计算机都有溢出是一个明显问题。但多数计算机都有16位、位、32位或位或64位的精度，因此这个问题可使用比例位的精度，因此这个问题可使用比例缩放方法来解决。缩放方法来解决。算术编码方法也是一种对错误非常敏感

42、的编码算术编码方法也是一种对错误非常敏感的编码方法，如果有一位发生错误，就会导致整个消方法，如果有一位发生错误，就会导致整个消息译错。息译错。4行程编码行程编码行程编码RLE的基本思想是：将一个相同值的连续串用的基本思想是：将一个相同值的连续串用一个代表值和串长来代替。一个代表值和串长来代替。以图像编码为例，在一幅图像中往往具有许多颜色相同以图像编码为例，在一幅图像中往往具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，的图块。在这些图块中，许多行上都具有相同的颜色，或在一行上有许多连续的像素点都具有相同的颜色值。或在一行上有许多连续的像素点都具有相同的颜色值。对此，不需要存储每

43、一个像素的颜色值，而只需存储一对此，不需要存储每一个像素的颜色值，而只需存储一个像素点的颜色值和具有相同颜色的像素数目即可。个像素点的颜色值和具有相同颜色的像素数目即可。具体来说，可以定义在特定方向上具有相同颜色值的相具体来说，可以定义在特定方向上具有相同颜色值的相邻像素为一轮，其延续长度称为行程。行程终点位置由邻像素为一轮，其延续长度称为行程。行程终点位置由到前一行终点的相对距离确定，这样就可以由到前一行终点的相对距离确定，这样就可以由“像素的像素的值和同值像素的个数值和同值像素的个数”来表示图像数据。来表示图像数据。例如，若沿水平方向有一串（例如，若沿水平方向有一串（M个）像素具有相个）像

44、素具有相同的颜色同的颜色N，则行程编码后，只传递两个值（，则行程编码后，只传递两个值（N，M）就可以代替）就可以代替M个像素的个像素的M个颜色值个颜色值N。假定有一幅灰度图像，其中第假定有一幅灰度图像，其中第n行的像素值如下：行的像素值如下：行程编码后得到的代码为：行程编码后得到的代码为：08163507451808。代码中的黑体粗体数字表示行程长度，黑体粗体字代码中的黑体粗体数字表示行程长度，黑体粗体字前面的数字表示像素的颜色值。前面的数字表示像素的颜色值。思考练习题进行进行Huffman编码。编码。04.006.010.010.015.020.035.0:7654321xxxxxxxX1.

45、1.对于信源对于信源，对，对1101111111011111进行算术编码。进行算术编码。878110X2.2.已知信源已知信源3.编程序实现编程序实现Huffman编码编码4.编程序实现算术编码编程序实现算术编码预测编码基本原理基本原理 预测编码的基本原理是：根据原始的离散信号之间预测编码的基本原理是：根据原始的离散信号之间存在着一定的相关性，利用前面一个或多个信号对存在着一定的相关性，利用前面一个或多个信号对下一个信号进行预测，然后对实际值与预测值之间下一个信号进行预测，然后对实际值与预测值之间的差（即预测误差）进行编码。如果预测比较准确，的差（即预测误差）进行编码。如果预测比较准确，那么预

46、测误差就比较小，这样对预测误差进行编码那么预测误差就比较小，这样对预测误差进行编码的数码位数就比直接对预测值或实际值进行编码的的数码位数就比直接对预测值或实际值进行编码的数码位数小，从而达到压缩数据的目的。数码位数小，从而达到压缩数据的目的。典型的预测编码方法有典型的预测编码方法有DPCM、ADPCM等，它们等，它们比较适合于声音、图像数据的压缩。因为这些数据比较适合于声音、图像数据的压缩。因为这些数据是模拟信号经过采样后得到的多媒体数据，相邻样是模拟信号经过采样后得到的多媒体数据，相邻样值之间的差不会相差很大，可以用较少的位来表示值之间的差不会相差很大，可以用较少的位来表示差值，实现数据压缩

47、。差值，实现数据压缩。DPCM编码1.PCM编码编码 PCM（Pulse Code Modulation）脉冲编码调制：对原始的模）脉冲编码调制：对原始的模拟信号经过采样、量化，直接进行二进制编码码的过程，即拟信号经过采样、量化，直接进行二进制编码码的过程，即模拟信号数字化过程。模拟信号数字化过程。PCM编码简单、直观，但数据量最大。编码简单、直观，但数据量最大。2.DPCM编码编码 DPCM（Differention Pulse Code Modulation）差分脉冲编码）差分脉冲编码调制：是利用样本与样本之间存在的信息冗余来进行编码的调制：是利用样本与样本之间存在的信息冗余来进行编码的一

48、种数据压缩技术。一种数据压缩技术。DPCM与与PCM编码不同的是：编码不同的是：PCM是直接对采样信号进行量是直接对采样信号进行量化编码，而化编码，而DPCM是对实际值与预测值之差进行量化编码，是对实际值与预测值之差进行量化编码，存储或传送的是差值而不是幅度绝对值，这就降低了传送或存储或传送的是差值而不是幅度绝对值，这就降低了传送或存储的数据量，达到压缩数据的目的。存储的数据量，达到压缩数据的目的。DPCM编码 DPCM编码的工作原理编码的工作原理 DPCM系统如图所示，由压缩和解压缩两系统如图所示，由压缩和解压缩两部分组成，其工作原理是：在压缩时，先对原部分组成，其工作原理是：在压缩时，先对

49、原始的模拟信号进行采样得到实际的采样值，然始的模拟信号进行采样得到实际的采样值，然后将采样值与预测器产生的预测值进行比较得后将采样值与预测器产生的预测值进行比较得到预测误差，最后将误差进行量化编码。在解到预测误差，最后将误差进行量化编码。在解压缩时，使用同样的预测器，将这一预测值与压缩时，使用同样的预测器，将这一预测值与解码得到的已经量化的差值相加，产生出近似解码得到的已经量化的差值相加，产生出近似的原始信号，基本恢复原始数据。的原始信号，基本恢复原始数据。预测误差)()()(nxnxnd 接收端的输出)()()(ndnxnx DPCM系统系统 DPCM系统中的误差来源是发送端的量化器，而与系

50、统中的误差来源是发送端的量化器，而与接收端无关。接收端无关。也就是说，如果去掉量化器，直接对预测误差进行也就是说，如果去掉量化器，直接对预测误差进行编码、传送，则接收端可以无误差地恢复出原始信编码、传送，则接收端可以无误差地恢复出原始信号，这种不带量化器的号，这种不带量化器的DPCM编码属于无失真编码，编码属于无失真编码，是信息保持编码。是信息保持编码。但是，如果是对预测误差量化后再进行编码，则由但是，如果是对预测误差量化后再进行编码，则由于量化器会导致不可逆的信息损失，接收端恢复出于量化器会导致不可逆的信息损失，接收端恢复出的信号与原始信号有一定误差，这种带有量化器的的信号与原始信号有一定误