ch4-多媒体数据压缩编码技术

1、1多媒体技术基础多媒体技术基础蔡宇辉蔡宇辉湖南大学软件学院湖南大学软件学院rj_2第四章第四章 多媒体数据压缩编码技术多媒体数据压缩编码技术3第四章的内容第四章的内容1.多媒体数据压缩编码概述多媒体数据压缩编码概述重要性、可能性、分类重要性、可能性、分类2.脉冲编码调制脉冲编码调制PCM3.统计编码：统计编码：Huffman编码、算术编码编码、算术编码4.预测编码：预测编码：DPCM、ADPCM、帧间预测、帧间预测5.变换编码变换编码6.多媒体数据压缩编码的国际标准多媒体数据压缩编码的国际标准JPEG、MPEG4第一节第一节 数据压缩编码概述数据压缩编码概述1.1 多媒体数据压缩编码的重要性多

2、媒体数据压缩编码的重要性1.2 多媒体数据压缩编码的可能性多媒体数据压缩编码的可能性1.3 多媒体数据压缩编码的分类多媒体数据压缩编码的分类51.1 数据压缩编码的重要性数据压缩编码的重要性 在多媒体技术中，处理的多媒体数据都在多媒体技术中，处理的多媒体数据都应是数字信号，传统的媒体信息需要进应是数字信号，传统的媒体信息需要进行采样和量化后方能在计算机中处理。行采样和量化后方能在计算机中处理。ADC放大器放大器6 原始媒体信息数字化后的数据量巨大。原始媒体信息数字化后的数据量巨大。 例例1：一页：一页B5（180255mm）大小的文）大小的文件，以中等分辨率件，以中等分辨率300dpi、8位色

3、方式扫位色方式扫描，其数据量为描，其数据量为6.61MB。 保存一部保存一部鹿鼎记鹿鼎记 （1813页）需要页）需要11983.93M（650M的的CD得刻得刻19张）。张）。7 例例2：立体声的激光唱盘，采样频率为：立体声的激光唱盘，采样频率为44.1kHz，量化位数为，量化位数为16，则一秒钟的音，则一秒钟的音频数据量就可达频数据量就可达172KB。 650M的的CD只可存储只可存储1小时音乐。小时音乐。ADC8 对于视频，数据量的问题则更加突出。对于视频，数据量的问题则更加突出。 例例3：采用：采用PAL制式，采样格式为制式，采样格式为4:4:4，24位色，则一秒钟的视频数据量就可达位色

4、，则一秒钟的视频数据量就可达31.3MB。 电影电影龙骑士龙骑士（时长（时长100分钟）需要约分钟）需要约289张张650M的的CD存放。存放。采集卡采集卡9 由于多媒体信息的数据量十分庞大，给由于多媒体信息的数据量十分庞大，给存储器的存储容量、通信线路的带宽资存储器的存储容量、通信线路的带宽资源、传输速率以及计算机的处理速度都源、传输速率以及计算机的处理速度都增加了极大压力。增加了极大压力。 解决方法：解决方法： 从硬件设备入手：增加存储器、带宽资源；从硬件设备入手：增加存储器、带宽资源；研究新型线缆提高传输效率；使用快速的高研究新型线缆提高传输效率；使用快速的高档计算机档计算机 从信息内容

5、入手：进行数据压缩编码。从信息内容入手：进行数据压缩编码。根本的解决之道根本的解决之道10数据压缩对多媒体应用的意义数据压缩对多媒体应用的意义 通过数据压缩技术可减少多媒体信息的通过数据压缩技术可减少多媒体信息的数据量，其意义在于：数据量，其意义在于：111.2 数据压缩编码的可能性数据压缩编码的可能性 多媒体数据能否进行压缩？多媒体数据能否进行压缩？ 研究表明，多媒体信息中存在大量的冗研究表明，多媒体信息中存在大量的冗余，去掉这些余，去掉这些冗余数据冗余数据便可实现数据的便可实现数据的压缩。压缩。12音频中的冗余音频中的冗余音频中的冗余信息主要有：音频中的冗余信息主要有：1. 时域冗余时域冗

6、余幅度的非均匀分布；样本间的相关性；周期幅度的非均匀分布；样本间的相关性；周期之间的相关性；基音之间的相关性；静止系之间的相关性；基音之间的相关性；静止系数（间隔）；长时自相关函数。数（间隔）；长时自相关函数。2. 频域冗余频域冗余非均匀的长时功率谱密度；语音特有的短时非均匀的长时功率谱密度；语音特有的短时功率谱密度。功率谱密度。3. 人耳的听感觉分辨能力有限。人耳的听感觉分辨能力有限。13图像图像/视频中的冗余视频中的冗余 图像图像/视频信息中包含有大量的冗余，主视频信息中包含有大量的冗余，主要有下列不同类型的冗余信息：要有下列不同类型的冗余信息： 空间冗余空间冗余 时间冗余时间冗余 结构冗

7、余结构冗余 知识冗余知识冗余 视觉冗余视觉冗余 图像区域的相同性冗余图像区域的相同性冗余 纹理的统计冗余纹理的统计冗余14a. 空间冗余空间冗余 空间冗余是静态图像中最主要的一种冗余。空间冗余是静态图像中最主要的一种冗余。 通常的图像都描述了某个场景，其相邻像素点通常的图像都描述了某个场景，其相邻像素点之间存在一定的空间连贯性。如果编码时不考之间存在一定的空间连贯性。如果编码时不考虑这一相关性，就会造成空间冗余。虑这一相关性，就会造成空间冗余。左边的图像显示了一个规则左边的图像显示了一个规则物体，其大量像素点的亮度、物体，其大量像素点的亮度、饱和度、色调等参数都一样。饱和度、色调等参数都一样。

8、 15b. 时间冗余时间冗余 时间冗余是视频中常见的一种冗余。时间冗余是视频中常见的一种冗余。 序列图像中，相邻帧往往包含有相同的背景和序列图像中，相邻帧往往包含有相同的背景和运动物体，只是运动物体的位置有所变化，因运动物体，只是运动物体的位置有所变化，因此相邻两帧的数据差别很小，具有时间上的连此相邻两帧的数据差别很小，具有时间上的连贯性。如果编码时不考虑这一相关性，就会造贯性。如果编码时不考虑这一相关性，就会造成时间冗余。成时间冗余。16c. 结构冗余结构冗余 有些图像中有规则纹理，其像素值存在有些图像中有规则纹理，其像素值存在明显的分布模式，明显的分布模式， 只要知道分布模式，便可通过某种

9、方法只要知道分布模式，便可通过某种方法生成图像，这种数据冗余即结构冗余。生成图像，这种数据冗余即结构冗余。规则的纹理图像规则的纹理图像17d. 知识冗余知识冗余 对图像的理解有时与某些知识有相当大的相关对图像的理解有时与某些知识有相当大的相关性，例如人脸的图像就具有同样的五官位置。性，例如人脸的图像就具有同样的五官位置。 可以根据已有的知识构造基本模型，并创建特可以根据已有的知识构造基本模型，并创建特征图像库，则只需提供少量的特征参数信息便征图像库，则只需提供少量的特征参数信息便可生成图像，这种数据冗余即知识冗余。可生成图像，这种数据冗余即知识冗余。18e. 视觉冗余视觉冗余 视觉冗余是针对人

10、眼的视觉特性而言的。视觉冗余是针对人眼的视觉特性而言的。 人对图像的敏感性是非均匀、非线性的，而一人对图像的敏感性是非均匀、非线性的，而一般的编码却是线性方式，因此存在视觉冗余。般的编码却是线性方式，因此存在视觉冗余。 视觉系统对亮度比对色度敏感。视觉系统对亮度比对色度敏感。 视觉系统对低频信号比对高频信号敏感。视觉系统对低频信号比对高频信号敏感。 视觉系统对静止图像比对运动图像敏感。视觉系统对静止图像比对运动图像敏感。 视觉系统对水平、垂直线条比对斜线条敏感。视觉系统对水平、垂直线条比对斜线条敏感。 随着亮度的增加，视觉系统对量化误差的敏感度降随着亮度的增加，视觉系统对量化误差的敏感度降低。

11、（高光区可用较少的量化位数）低。（高光区可用较少的量化位数） 视觉系统把图像的边缘和非边缘区域分开处理。视觉系统把图像的边缘和非边缘区域分开处理。 视觉系统总是把视网膜上的图像分解成若干个空间视觉系统总是把视网膜上的图像分解成若干个空间有向的频率通道后，再做进一步处理。有向的频率通道后，再做进一步处理。19f. 图像区域的相同性冗余图像区域的相同性冗余 有的图像存在一些相同或相近的区域，有的图像存在一些相同或相近的区域，从而产生数据的重复性存储，这就是图从而产生数据的重复性存储，这就是图像区域的相同性冗余。像区域的相同性冗余。 可以只记录一个区域中各个像素的值，可以只记录一个区域中各个像素的值

12、，与其相同或相近的区域则不必记录。与其相同或相近的区域则不必记录。 向量量化方法就是针对这种冗余进行数向量量化方法就是针对这种冗余进行数据压缩的。据压缩的。20g. 纹理的统计冗余纹理的统计冗余 有些纹理并不严格服从某一分布规律，有些纹理并不严格服从某一分布规律，但它在统计意义上又符合该规律，这种但它在统计意义上又符合该规律，这种数据冗余即纹理的统计冗余。数据冗余即纹理的统计冗余。孔雀羽毛的孔雀羽毛的纹理分布纹理分布211.3 数据压缩编码的分类数据压缩编码的分类22多媒体数据压缩编码方法有很多种，根多媒体数据压缩编码方法有很多种，根据不同的依据可产生不同的分类：据不同的依据可产生不同的分类：

13、按照编码算法的原理：分成脉冲编码调制、按照编码算法的原理：分成脉冲编码调制、预测编码、变换编码、量化与向量量化编预测编码、变换编码、量化与向量量化编码、统计编码、子带编码、结构编码、模码、统计编码、子带编码、结构编码、模型编码、混合编码等等；型编码、混合编码等等；根据质量有无失真：分成有损失编码和无根据质量有无失真：分成有损失编码和无损失编码；损失编码；按照其作用域在空间或频率上：分成空间按照其作用域在空间或频率上：分成空间方法、变换方法和混合方法；方法、变换方法和混合方法；根据是否自适应：分成自适应性编码和非根据是否自适应：分成自适应性编码和非适应性编码。适应性编码。23无损编码和有损编码无

14、损编码和有损编码 实际上，信息进行数字化时，量化误差是不可实际上，信息进行数字化时，量化误差是不可避免的。此处的避免的。此处的“无损无损” 和和“有损有损”是针对编是针对编码过程而言的。码过程而言的。 无损编码：也称冗余压缩法。将编码后的数据进行无损编码：也称冗余压缩法。将编码后的数据进行解码，所得数据和编码前的原始数据严格一致，压解码，所得数据和编码前的原始数据严格一致，压缩比约为缩比约为2:15:1，常用的算法有：，常用的算法有：Huffman编码、编码、算术编码、行程编码算术编码、行程编码RLE、词典编码等。、词典编码等。 有损编码：也称熵压缩法。解码得到的还原数据与有损编码：也称熵压缩

15、法。解码得到的还原数据与原始数据之间存在一定的误差，但并不影响人对原原始数据之间存在一定的误差，但并不影响人对原始资料表达信息的理解，压缩比从几倍到上百倍。始资料表达信息的理解，压缩比从几倍到上百倍。2425压缩软件实际上就是使用上述这些算法进行压缩的。压缩软件实际上就是使用上述这些算法进行压缩的。26衡量编码方法优劣的指标衡量编码方法优劣的指标 衡量压缩编码方法优衡量压缩编码方法优劣的重要指标有：劣的重要指标有： 压缩比要高；压缩比要高； 压缩与解压的速度快；压缩与解压的速度快； 算法简单，适合于硬件算法简单，适合于硬件实现；实现； 解压缩后还原信息的质解压缩后还原信息的质量高。量高。27第

16、二节第二节 脉冲编码调制脉冲编码调制 脉冲编码调制：脉冲编码调制：PCM，即将连续模拟信，即将连续模拟信号数字化，包括采样、量化号数字化，包括采样、量化/编码。编码。 模拟量经过模拟量经过A/D转换，得到二进制码的过转换，得到二进制码的过程，也称程，也称PCM编码。编码。 其它的编码方法都是其它的编码方法都是在模拟信号经过在模拟信号经过PCM编码后再进行的压缩编码后再进行的压缩编码方法。编码方法。28PCM编码过程编码过程29第三节第三节 统计编码统计编码 数据压缩技术的理论基础是信息论，根据数据压缩技术的理论基础是信息论，根据信息论的原理，可以找到最佳的数据压缩信息论的原理，可以找到最佳的数

17、据压缩编码方法。编码方法。 数据压缩的理论极限是数据压缩的理论极限是信息熵信息熵，统计编码，统计编码就是利用了信息熵原理，因此也称作信息就是利用了信息熵原理，因此也称作信息熵编码、熵保存编码或熵编码。熵编码、熵保存编码或熵编码。 统计编码是一种无损的压缩方法，如香农统计编码是一种无损的压缩方法，如香农编码、编码、 Huffman编码、算术编码等。编码、算术编码等。303.1 统计编码的原理统计编码的原理信息量和信息熵信息量和信息熵 熵是信息论中的概念，是信息量的度量方法。熵是信息论中的概念，是信息量的度量方法。 要理解什么是要理解什么是“信息熵信息熵”，先得了解，先得了解信息信息、信信息量息量

18、的含义。的含义。31 下面以信源编码模型来说明。下面以信源编码模型来说明。编码器编码器信源（消息集）信源（消息集）编码输出集编码输出集X=x1,xnZ=z1,zn符号集符号集Am=a1,am X为消息集，由为消息集，由n个信号单元个信号单元xj构成构成 Z为输出集，由为输出集，由n个码字个码字zj构成，构成，zj与与xj一一一一对应。对应。 Am 是符号集，由是符号集，由m个码元个码元 ai构成，符号集构成，符号集中间的码元组成输出码字。中间的码元组成输出码字。32 当信源发出某个随机事件（消息）当信源发出某个随机事件（消息）xj后，后，接收端收到一个相应的码字接收端收到一个相应的码字zj。

19、那么，接收到的这个码字中包含了多少那么，接收到的这个码字中包含了多少有用的信息呢？有用的信息呢？ 信息是用不确定性的量度定义的。信息是用不确定性的量度定义的。 消息消息xj出现的可能性愈小，则其带给人们出现的可能性愈小，则其带给人们的信息就愈多；反之，消息出现的可能的信息就愈多；反之，消息出现的可能性愈大，则它能给人们提供的新信息性愈大，则它能给人们提供的新信息（有用信息）就愈少。（有用信息）就愈少。 在数学上，一条消息所传输的信息是其在数学上，一条消息所传输的信息是其出现概率的单调下降函数。出现概率的单调下降函数。33信息量信息量 信息量：从信息量：从N个可能事件中选出一个事件个可能事件中选

20、出一个事件所需要的信息度量或含量。所需要的信息度量或含量。 对于计算机的二进制编码，可以这么理对于计算机的二进制编码，可以这么理解：从解：从N个事件中辨别出一个特定事件，个事件中辨别出一个特定事件，最少需要回答多少次最少需要回答多少次“yes or no”疑问。疑问。 事实上，每次提问都会得到一个事实上，每次提问都会得到一个“yes or no”的答复，可以用的答复，可以用0或或1表示，即表示，即1bit，如果提问如果提问n次，则信息量为次，则信息量为nbit。34示例示例 例一：从例一：从164的整数中选出一个数。的整数中选出一个数。 可先提问可先提问“是否大于是否大于32?”，以消除半数的

21、可能，然，以消除半数的可能，然后再进行半数的询问，这样只需后再进行半数的询问，这样只需6次便可确定一个数，次便可确定一个数，其信息量为其信息量为6bit。 例二：如果只要辨别某个数是否大于例二：如果只要辨别某个数是否大于32，则只，则只需询问一次便可得出结论，其信息量只有需询问一次便可得出结论，其信息量只有1bit。 从上两例中可看出，大于或者小于从上两例中可看出，大于或者小于32，这种情，这种情况的概率比具体等于某一个数的概率要大，但况的概率比具体等于某一个数的概率要大，但其信息量反而小（单调下降）。其信息量反而小（单调下降）。35信息量的数学表述信息量的数学表述 信息论定义了一种度量信息量

22、的方法：信息论定义了一种度量信息量的方法： 其中：其中： I(xj)是信源是信源X发出发出xj后，接收端接收到的信后，接收端接收到的信息量的量度。息量的量度。 P(xj)是信源是信源X发出发出xj的先验概率，有：的先验概率，有：njxPxIjj,.,3 , 2 , 1)(log)(2), 2 , 1(1011njppjnjj请用上述公式求例一的信息量。请用上述公式求例一的信息量。36信息熵信息熵 如果将信源所有可能事件的信息量进行如果将信源所有可能事件的信息量进行统计平均（即求其数学期望），就得到统计平均（即求其数学期望），就得到了信息熵。了信息熵。 信源信源X发出的发出的xj（j=1,2,n

23、），），xj出现的出现的概率为概率为P(xj)，则信源，则信源X的熵为：的熵为： )(log)()()(211jnjjjnjjxPxPxIxPXH37示例示例 假设一幅由假设一幅由40个像素组成的灰度图像，个像素组成的灰度图像，共有共有5级灰度，每一级灰度都是一种信源级灰度，每一级灰度都是一种信源发出的符号，分别用发出的符号，分别用AE表示。表示。 40个像素中有个像素中有15个灰度为个灰度为A，7个灰度为个灰度为B，7个灰度为个灰度为C，6个灰度为个灰度为D，5个灰度个灰度为为E。 试求该灰度图像的熵。试求该灰度图像的熵。38 该灰度图像的熵为该灰度图像的熵为2.196bit。 196. 2

24、405log405406log406407log407407log4074015log4015)(log)()()(22222211jnjjjnjjxPxPxIxPXH39统计编码的目的统计编码的目的统计编码就根据信源信号出现概率的分统计编码就根据信源信号出现概率的分布特性进行压缩的。布特性进行压缩的。统计编码的目的：统计编码的目的：1. 在信源符号和码字之间建立明确的一一对在信源符号和码字之间建立明确的一一对应关系；应关系；2. 编码过程中不丢失信息量（即信息熵的大编码过程中不丢失信息量（即信息熵的大小不变），以便在恢复时能准确地再现原小不变），以便在恢复时能准确地再现原信号，实现无损压缩；

25、信号，实现无损压缩；3. 平均码长或码率应尽量小。平均码长或码率应尽量小。40熵和平均码长熵和平均码长 可用熵来衡量该编码是否为最佳编码：可用熵来衡量该编码是否为最佳编码： 当当 ，有冗余，不是最佳；，有冗余，不是最佳； 当当 ，不可能出现；，不可能出现； 当当 ，是最佳编码（，是最佳编码（ 稍大于稍大于 ）其中其中 表示编码器输出码字的平均码长。表示编码器输出码字的平均码长。 可见，熵值是平均码长的下限。可见，熵值是平均码长的下限。)(xHN )(xHN )(xHN N)(xHNnjjjLPN1413.2 Huffman编码编码 最佳编码定理：最佳编码定理： 在在变字长变字长码中，对于出现概

26、率大的信息符号码中，对于出现概率大的信息符号编以短字长的码，对于出现概率小的信息符编以短字长的码，对于出现概率小的信息符号编以长字长的码。号编以长字长的码。 如果码字长度严格按照符号概率的大小的相如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长度一定小于按任反顺序排列，则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度。何其他符号顺序排列方式得到的码字长度。 Huffman编码：利用了最佳编码定理，编码：利用了最佳编码定理，是最常用的一种统计编码。是最常用的一种统计编码。42 Huffman编码方法先把信源符号按概率编码方法先把信源符号按概率大小顺序排列，并设法按逆次

27、序分配码大小顺序排列，并设法按逆次序分配码字长度。字长度。 对于出现频率大的符号用较少的位数来对于出现频率大的符号用较少的位数来表示；对于出现频率小的符号用较多的表示；对于出现频率小的符号用较多的位数来表示。位数来表示。 Huffman编码方法采用的码字长度是可编码方法采用的码字长度是可变的，因此较难在压缩编码后的文件中变的，因此较难在压缩编码后的文件中进行内容的查找。进行内容的查找。43Huffman编码的思路编码的思路1. 把信源符号按概率大小顺序排列，并设法按把信源符号按概率大小顺序排列，并设法按逆次序分配码字的长度。逆次序分配码字的长度。2. 在分配码字长度时，首先将出现概率最小的在分

28、配码字长度时，首先将出现概率最小的两个符号的概率相加合成一个概率。两个符号的概率相加合成一个概率。3. 把这个合成概率看成是一个新组合符号地概把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两个符号率，重复上述做法直到最后只剩下两个符号概率为止。概率为止。4. 完成以上概率顺序排列后，再反过来逐步向完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有二个分支各赋予一个前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为二进制码，可以对概率大的赋为0，概率小的，概率小的赋为赋为1。44Huffman编码的步骤编码的步骤1. 对每个信息符号进行概率统计；对每

29、个信息符号进行概率统计；2. 将信源符号按概率的递减顺序排列；将信源符号按概率的递减顺序排列；3. 将最后的两个小概率相加作为新符号的概率，将最后的两个小概率相加作为新符号的概率， 此时概率个数将减少一个；此时概率个数将减少一个；4. 重复第重复第2、3步，直到只剩两个概率；步，直到只剩两个概率；5. 将概率大的赋将概率大的赋“0”，概率小的赋，概率小的赋“1”；6. 逆顺序往信源符号推，不是合并的编码不变，逆顺序往信源符号推，不是合并的编码不变，如果是合并的，则在编码后面按照第如果是合并的，则在编码后面按照第5步的方步的方法添加法添加0或或1。45编码实例编码实例 信源信源X有有7个信息符号

30、，其概率为：个信息符号，其概率为： 请对其进行请对其进行Huffman编码，写出其码树、编码，写出其码树、码长，并计算平均码长和熵。码长，并计算平均码长和熵。12345670.350.200.150.100.100.060.0446信息信息符号符号概率概率第第1步步第第2步步第第3步步第第4步步第第5步步10.350.350.350.350.400.6020.200.200.200.250.350.4030.150.150.200.200.2540.100.100.150.2050.100.100.1060.060.1070.0401100010001101100101101001100100

31、1001111011100100100111101110111147 码字的平均码长为：码字的平均码长为：bitLPLPNjjjnjjj55. 24)04. 006. 0(3)10. 010. 015. 0(2)20. 035. 0(711 熵为：熵为：bitxPxPxPxPHjjjnjjj4986. 2)04. 0log04. 006. 0log06. 010. 0log10. 010. 0log10. 015. 0log15. 020. 0log20. 035. 0log35. 0()(log)()(log)(22222227121248Huffman编码小结编码小结 平均码长大于熵，小于

32、等长码的码长。平均码长大于熵，小于等长码的码长。 Huffman编码能保证解码的唯一性，短码字不编码能保证解码的唯一性，短码字不会是长码字的前缀。会是长码字的前缀。 Huffman编码没有错误保护功能。编码没有错误保护功能。 使用使用Huffman编码时，接收端需保存一个与发编码时，接收端需保存一个与发送端完全相同的送端完全相同的Huffman码表。码表。 Huffman编码在信源符号出现概率分布不均匀编码在信源符号出现概率分布不均匀时编码效率较高，若概率分别均匀时一般不采时编码效率较高，若概率分别均匀时一般不采用用Huffman编码。编码。 Huffman编码的压缩比取决于信源符号出现的编码

33、的压缩比取决于信源符号出现的概率，越集中则压缩比越高。概率，越集中则压缩比越高。493.3 算术编码算术编码 20世纪世纪60年代初，年代初，Elias首次提出了算术首次提出了算术编码的概念。编码的概念。 1976年，发展了算术编码的实用技术。年，发展了算术编码的实用技术。 算术编码方法比算术编码方法比Huffman编码复杂，但编码复杂，但它不需要接收端保存一份它不需要接收端保存一份Huffman码表，码表，且具有自适应能力。且具有自适应能力。 算术编码是目前实现高效压缩数据中很算术编码是目前实现高效压缩数据中很有前途的编码方法。有前途的编码方法。50基本原理和编码步骤基本原理和编码步骤算术编

34、码实际上是用一个浮点数代替一算术编码实际上是用一个浮点数代替一个输入流中的符号。个输入流中的符号。1. 将实数半开区间将实数半开区间0, 1) 进行分割，每一符号进行分割，每一符号对应对应0, 1)上的一个子区间，区间长度为该上的一个子区间，区间长度为该符号出现的概率；符号出现的概率；2. 把要编码的整段消息映射到把要编码的整段消息映射到0, 1)，根据这，根据这段消息符号的顺序确定新的实数子区间；段消息符号的顺序确定新的实数子区间；3. 最终得到一个最终得到一个0, 1)上的子区间，从中任选上的子区间，从中任选一个实数，该实数就是对整段数据进行编一个实数，该实数就是对整段数据进行编码后的输出

35、代码。码后的输出代码。51例：输入例：输入“eai”，最后得到的子区间为，最后得到的子区间为0.23, 0.236)，取该区间的任一个数（一般，取该区间的任一个数（一般取最小的值），如取最小的值），如0.230即为即为”eai”的编码。的编码。52 在算术编码中，一段消息是用在算术编码中，一段消息是用0到到1之间之间的一个实数来编码表示的。的一个实数来编码表示的。 算术编码方法用到了两个基本的参数：算术编码方法用到了两个基本的参数：信源符号的概率和编码间隔。信源符号的概率和编码间隔。 信源符号的概率决定了压缩编码的效率，也信源符号的概率决定了压缩编码的效率，也决定了编码过程中的间隔。决定了编码

36、过程中的间隔。 编码间隔最终决定了符号编码后的输出。编码间隔最终决定了符号编码后的输出。 需要编码的信息越长，则表示它的编码需要编码的信息越长，则表示它的编码间隔就越小，实数的小数位就越多。间隔就越小，实数的小数位就越多。53编码实例编码实例 假设信源符号有假设信源符号有4个个(00, 01, 10, 11)，其概率分，其概率分别为别为(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)。 消息序列的输入为：消息序列的输入为：10 00 11 00 10 11

37、 015455二进制的算术编码二进制的算术编码 计算机中任何消息都是由计算机中任何消息都是由0、1组合而成组合而成的，可以理解为信源符号只有的，可以理解为信源符号只有0和和1。 即：每次分割区间时，只要分成两个子即：每次分割区间时，只要分成两个子区间，一个对应区间，一个对应0，一个对应，一个对应1。 例：已知二进制符号中例：已知二进制符号中0出现的概率为出现的概率为0.25，1出现的概率为出现的概率为0.75，试对输入流，试对输入流1011进行算术编码。进行算术编码。56 设设C为子区间的左端起始位置，为子区间的左端起始位置，L为子区间的为子区间的长度，则对于符号长度，则对于符号“0”，C=0

38、，L=0.25；对于；对于符号符号“1”，C=0.25，L=0.75。 算术编码步骤如下：算术编码步骤如下：步骤步骤 输入符号输入符号C L 1 1 0.25 0.75 2 0 0.25 0.75*0.25=0.1875 3 1 0.25+0.1875*0.25 0.1875*0.75=0.296875=0.140625 4 1 0. 296875+0.140625*0.750.140625*0.25=0.10546875=0.3320312557 当当4个字符输入完后，最终得到的子区间个字符输入完后，最终得到的子区间左端起始位置为左端起始位置为0.33203125，终止位置为，终止位置为C+

39、L=0.4375。 换算成二进制为：换算成二进制为： (0.33203125)d=(0.01010101) b (0.4375)d=(0.0111) b 在在0.01010101和和0.0111之间取一个数，要之间取一个数，要求其二进制形式的长度最短，如本例中求其二进制形式的长度最短，如本例中取取0.011，则该串输入，则该串输入“1011”最终可编码最终可编码成成011，数据量有所减少。，数据量有所减少。58几个问题几个问题1. 由于计算机的精度有限，算术编码的计算过由于计算机的精度有限，算术编码的计算过程中容易发生溢出，可以采用限制小数位数程中容易发生溢出，可以采用限制小数位数的方法来解决

40、。的方法来解决。 2. 算术编码器对消息只产生一个码字（在区间算术编码器对消息只产生一个码字（在区间0, 1)中的一个实数），译码器在接收到表示中的一个实数），译码器在接收到表示这个实数的所有位之前不能进行译码。这个实数的所有位之前不能进行译码。 3. 算术编码对错误很敏感，如果有一位发生错算术编码对错误很敏感，如果有一位发生错误就会导致整个消息译错。误就会导致整个消息译错。59自适应能力自适应能力 事实上，由于人们事先无法知道精确的信源概事实上，由于人们事先无法知道精确的信源概率，因此编码算法最好具有自适应能力，解决率，因此编码算法最好具有自适应能力，解决这一问题最有效的方法是在编码过程中进

41、行估这一问题最有效的方法是在编码过程中进行估算（动态建模）。算（动态建模）。 算术编码可以是静态的，也可以是具有自适应算术编码可以是静态的，也可以是具有自适应能力的动态编码。能力的动态编码。 在静态算术编码中，信源符号的概率是固定的。在静态算术编码中，信源符号的概率是固定的。 在自适应算术编码中，将根据编码时符号出现的频在自适应算术编码中，将根据编码时符号出现的频繁程度动态地修改信源符号的概率。繁程度动态地修改信源符号的概率。 动态建模是确定编码器压缩效率的关键。动态建模是确定编码器压缩效率的关键。60算术编码小结算术编码小结 不必预先定义概率模型，具有自适应能力，可不必预先定义概率模型，具有

42、自适应能力，可根据当前接收的数据不断更改概率模型。根据当前接收的数据不断更改概率模型。 若信源符号的概率值都很接近时，不宜使用若信源符号的概率值都很接近时，不宜使用Huffman编码，建议使用算术编码。编码，建议使用算术编码。 算术编码的实现较算术编码的实现较Huffman编码更复杂，但对编码更复杂，但对多幅图像进行测试的结果表明，算术编码较多幅图像进行测试的结果表明，算术编码较Huffman编码提高了编码提高了5%左右的压缩率，左右的压缩率，JPEG扩展系统中采用的就是算术编码。扩展系统中采用的就是算术编码。613.4 游程编码游程编码 RLE：run length encoding，游程编

43、码，游程编码，也称行程编码。也称行程编码。用用RLE编码方法得到的代码为：编码方法得到的代码为：80315084180 623.5 词典编码词典编码 词典编码是根据数据本身包含有词典编码是根据数据本身包含有重复内重复内容容这一特性进行压缩的。这一特性进行压缩的。 词典编码是无损的。词典编码是无损的。 常见的词典编码算法有：常见的词典编码算法有：LZ77 算法、算法、LZ78算法、算法、LZW算法等。算法等。63指针式词典指针式词典如如LZ77 算法、算法、LZSS算法、算法、LZ78算法。算法。64索引式词典索引式词典如如LZW算法算法65第四节第四节 预测编码预测编码 预测编码：先利用以往的

44、样本值对新样预测编码：先利用以往的样本值对新样本进行本进行预测预测，再将新样本的实际值和预，再将新样本的实际值和预测值相减得到一个测值相减得到一个误差值误差值，最后对该误，最后对该误差值进行量化编码传送。差值进行量化编码传送。 如果样本的时间或空间相关性较强，则如果样本的时间或空间相关性较强，则误差值的变化范围将远远小于原始信号误差值的变化范围将远远小于原始信号的变化范围，量化等级可大量减少，从的变化范围，量化等级可大量减少，从而实现数据压缩。而实现数据压缩。66 预测编码主要是利用数据在时间或空间预测编码主要是利用数据在时间或空间上的相关性来进行预测的，广泛适用于上的相关性来进行预测的，广泛

45、适用于音频、图像、视频等媒体的编解码。音频、图像、视频等媒体的编解码。 对于音频，主要利用时间上的相关性，采用对于音频，主要利用时间上的相关性，采用时间上的前几个采样值来做预测。时间上的前几个采样值来做预测。 对于静止图像，主要利用空间上的相关性，对于静止图像，主要利用空间上的相关性，如同一行上的前几个采样值，甚至可以是前如同一行上的前几个采样值，甚至可以是前几行上的像素。几行上的像素。 对于视频，不仅可以利用时间上的相关性对于视频，不仅可以利用时间上的相关性（帧间预测），还可以利用空间上的相关性（帧间预测），还可以利用空间上的相关性（帧内预测）。（帧内预测）。67684.1 DPCM 模拟信

46、号进行采样量化后，如果直接使模拟信号进行采样量化后，如果直接使用用PCM编码，则数据量将很大，此时可编码，则数据量将很大，此时可以使用预测编码的思想来进行二进制编以使用预测编码的思想来进行二进制编码，常用的方法有码，常用的方法有线性预测线性预测LPC和非线和非线性预测。性预测。 DPCM：差分：差分(值值)脉冲编码调制，是线性脉冲编码调制，是线性预测方法。预测方法。 DPCM编码器记录与传送的不是样本的编码器记录与传送的不是样本的真实值，而是它与预测值的真实值，而是它与预测值的差差。69DPCM的基本原理的基本原理转入转入f(i,j)f(i,j)e(i,j)e(i,j)量化器量化器预测器预测器

47、预测器预测器编码器编码器解码器解码器信信道道传传输输e e(i,j)(i,j)f f(i,j)(i,j)输出输出f(i,j)f(i,j)f(i,j)f(i,j)f(i,j)f(i,j)f(i,j)f(i,j)发送端发送端接收端接收端e e(i,j)(i,j)704.2 ADPCM ADPCM：自适应差分脉冲编码调制。：自适应差分脉冲编码调制。 在在ADPCM中，预测器的预测系数和量化器中，预测器的预测系数和量化器的量化参数，都能够根据原数据的区域分的量化参数，都能够根据原数据的区域分布特点自动调整，具有自适应能力。布特点自动调整，具有自适应能力。 自适应预测：增加一个预测参数，该参数可根自适应

48、预测：增加一个预测参数，该参数可根据预测值的大小自适应调整；据预测值的大小自适应调整； 自适应量化：量化阶距的大小可自适应调整。自适应量化：量化阶距的大小可自适应调整。 实践证明，实践证明，ADPCM与与DPCM相比，压缩比相比，压缩比更高，解码后的质量也更好。更高，解码后的质量也更好。714.3 帧间预测编码帧间预测编码 帧间预测编码技术是专门针对视频对象帧间预测编码技术是专门针对视频对象的，利用连续几帧之间存在的时间相关的，利用连续几帧之间存在的时间相关性来消除冗余。性来消除冗余。 常见的帧间预测编码方法有：常见的帧间预测编码方法有： 条件补充法条件补充法：若帧间各对应像素的差值超过：若帧

49、间各对应像素的差值超过阈值，则传送；若没超过阈值则不传送，接阈值，则传送；若没超过阈值则不传送，接收端使用上一帧相应像素值代替。收端使用上一帧相应像素值代替。 运动补偿技术运动补偿技术：跟踪画面内运动部分的位移：跟踪画面内运动部分的位移情况，对其加以补偿后再进行帧间预测。情况，对其加以补偿后再进行帧间预测。72第五节第五节 变换编码变换编码 变换编码技术较成熟，目前广泛应用于变换编码技术较成熟，目前广泛应用于图像、视频的数据压缩。图像、视频的数据压缩。 算法思想：将空间域中的图像信号映射算法思想：将空间域中的图像信号映射变换到另一个正交的矢量空间中，产生变换到另一个正交的矢量空间中，产生一批一

50、批变换系数变换系数，然后对这些变换系数进，然后对这些变换系数进行编码。行编码。 如果变换的新正交空间选择得好，则可如果变换的新正交空间选择得好，则可以减少数据间的相关性，从而减少了数以减少数据间的相关性，从而减少了数据的冗余度，达到数据压缩的目的。据的冗余度，达到数据压缩的目的。73例子例子 有相邻的两个采样有相邻的两个采样值值x1和和x2，各用，各用3位位来表示，即有来表示，即有8种可种可能取值。考虑到样能取值。考虑到样值的相关性，值的相关性，x1和和x2同时出现相近幅度同时出现相近幅度的可能性最大，即的可能性最大，即图中的直线阴影部图中的直线阴影部分。分。 信源的相关性越大，信源的相关性越

51、大，阴影部分就越扁平。阴影部分就越扁平。74 若将坐标系旋转若将坐标系旋转45度，样本值度，样本值x1变换成变换成y1，x2变换成变换成y2。不管。不管y1在在07的可能等级内如何变的可能等级内如何变化，化，y2始终只在相当小的范围内变化。始终只在相当小的范围内变化。 可见，旋转后可见，旋转后y1和和y2的相关性减小了。的相关性减小了。 75变换编码的原理图变换编码的原理图子块子块 1子块子块 2子块子块 n.正变换正变换滤波滤波量化量化编编码码信道信道解解码码逆变换逆变换综合综合拼接拼接源图像（源图像（发送发送）恢复图像（恢复图像（接收接收）76常用的变换方法常用的变换方法 常用变换有：常用

52、变换有： 沃尔什沃尔什(Walsh)变换变换 傅立叶傅立叶(Fouries)变换变换 离散正弦离散正弦(DST)变换变换 离散余弦离散余弦(DCT)变换变换 哈尔哈尔(Haar)变换变换 斜斜(Slant)变换变换 K-L(Karhunen-Loeve)变换变换 小波小波(Wavelet)变换变换 77第六节第六节 多媒体数据压缩编码标准多媒体数据压缩编码标准6.1 静态图像压缩编码的国际标准静态图像压缩编码的国际标准JPEG6.2 动态图像压缩编码的国际标准动态图像压缩编码的国际标准MPEG-1MPEG-2MPEG-4MPEG-7MPEG-21786.1 JPEG标准标准 JPEG：Join

53、t Photograph Experts Group，联合图像专家组，于联合图像专家组，于1986年由年由CCITT和和ISO联合成立。联合成立。 JPEG标准即标准即多灰度连续色调静态图像压缩多灰度连续色调静态图像压缩编码编码，是适用于多级灰度、连续色调、静，是适用于多级灰度、连续色调、静态的数字图像压缩编码标准。态的数字图像压缩编码标准。 实际上，实际上，JPEG不仅适用于静态图像，视频不仅适用于静态图像，视频的帧内压缩就可采用的帧内压缩就可采用JPEG编码。编码。79 JPEG是一个适用范围很广的通用标准，其是一个适用范围很广的通用标准，其研发时的目标如下：研发时的目标如下：1. 算法在

54、图像压缩率方面应接近当前科学水平，算法在图像压缩率方面应接近当前科学水平，图像的保真度在较宽的压缩范围里的评价是图像的保真度在较宽的压缩范围里的评价是“很好很好”、“优秀优秀”到与原图像到与原图像“不能区别不能区别”。2. 算法可实际应用于任何一类静态数字图像，对算法可实际应用于任何一类静态数字图像，对图像的大小、颜色空间、像素的长宽比、图像图像的大小、颜色空间、像素的长宽比、图像的内容、复杂程度、颜色数及统计特性等都不的内容、复杂程度、颜色数及统计特性等都不加限制。加限制。3. 在计算的复杂程度方面可以调整，因而可根据在计算的复杂程度方面可以调整，因而可根据性能和成本要求来选择用软件执行还是

55、用硬件性能和成本要求来选择用软件执行还是用硬件执行。执行。4. 包括四种操作方式：顺序编码、累进编码、无包括四种操作方式：顺序编码、累进编码、无失真编码和分层编码。失真编码和分层编码。 80JPEG压缩算法压缩算法 为了保证通用性，为了保证通用性，JPEG专家组开发了两专家组开发了两种基本的压缩算法：种基本的压缩算法： 基于基于离散余弦变换离散余弦变换DCT的有损压缩。的有损压缩。 基于基于空间空间DPCM预测技术预测技术的无损压缩。的无损压缩。 实际上，实际上，JPEG专家组还研究了一种称做专家组还研究了一种称做JPEG 2000的标准，其采用的压缩算法为的标准，其采用的压缩算法为基于小波（

56、基于小波（wavelet）变换的变换编码。）变换的变换编码。81JPEG的组成部分的组成部分 JPEG系统可分成三个组成部分：系统可分成三个组成部分： 基本系统基本系统：是实现离散余弦变换：是实现离散余弦变换DCT编码编码/解码所需的最小功能集。解码所需的最小功能集。 扩展系统扩展系统：是为了满足更为广阔领域的应用：是为了满足更为广阔领域的应用要求而设置的。要求而设置的。 独立功能独立功能：相对于：相对于JPEG的基本系统和扩展的基本系统和扩展系统来说，使用空间系统来说，使用空间DPCM预测方法的部分预测方法的部分称为独立功能。称为独立功能。82基于基于DPCM的无损压缩的无损压缩 如图，预测

57、器对原始数据如图，预测器对原始数据X进行预测，求得差进行预测，求得差值后再对差值进行无失真的熵编码。值后再对差值进行无失真的熵编码。 熵编码器常采用熵编码器常采用Huffman编码或算术编码。编码或算术编码。83基于基于DCT的有损压缩的有损压缩 基于基于DPCM预测编码的压缩比仅能达到预测编码的压缩比仅能达到2:1，而，而DCT编码的压缩比可高达编码的压缩比可高达10:1100:1。 当压缩比小于当压缩比小于40:1时，还原的图像与原始图像时，还原的图像与原始图像相比主观效果几乎一样。相比主观效果几乎一样。压缩效果（比特压缩效果（比特/像素）像素）质量质量0.250.50中好中好0.500.

58、75好很好好很好0.751.5极好极好1.22.0与原始图像分不出来与原始图像分不出来8485DCT变换公式变换公式 88的子块作为的子块作为DCT变换的输入。变换的输入。DCT变换使用下式计算：变换使用下式计算：逆变换逆变换IDCT使用下式计算：使用下式计算：86基于基于DCT编码的步骤编码的步骤基于基于DCT编码的计算步骤为：编码的计算步骤为：1. 分割子块：通常顺序分割成分割子块：通常顺序分割成88的子块。的子块。2. 对子块进行正向的离散余弦变换对子块进行正向的离散余弦变换FDCT。3. 对获得的对获得的DCT系数进行量化处理。系数进行量化处理。4. 将量化后的将量化后的DCT系数进行

59、系数进行Z字形编排。字形编排。5. 对直流系数对直流系数DC进行进行DPCM编码。编码。6. 对交流系数对交流系数AC进行进行RLE游程编码。游程编码。7. 熵编码。熵编码。876.2 MPEG标准标准 MPEG：Moving Pictures Experts Group，运动，运动图像专家组，于图像专家组，于1988年由年由ISO与与IEC联合成立，联合成立，致力于运动图像及其伴音的编码标准化。致力于运动图像及其伴音的编码标准化。 MPEG标准包括三个部分：标准包括三个部分： MPEG视频：如视频：如VCD、SVCD、DVD就是采就是采用这部分标准制作的电子产品。用这部分标准制作的电子产品。

60、 MPEG音频：如音频：如mp3。 MPEG系统：负责视频和音频的同步。系统：负责视频和音频的同步。88 最初，最初，MPEG专家组的工作项目是专家组的工作项目是3个：个： MPEG-1：在：在1.5Mbps传输速率下对图像编码。传输速率下对图像编码。 MPEG-2：在：在l0Mbps传输速率下对图像编码。传输速率下对图像编码。 MPEG-3：在：在40Mbps传输速率下对图像编码。传输速率下对图像编码。 l992年，年，MPEG-2的适用范围扩大到的适用范围扩大到HDTV（高清电视），能支持（高清电视），能支持MPEG-3的所有功能，的所有功能，于是便取消了于是便取消了MPEG-3。 到目前