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

1多媒体技术基础蔡宇辉湖南大学软件学院[e-mail]2第四章多媒体数据压缩编码技术3第四章的内容1.多媒体数据压缩编码概述−重要性、可能性、分类2.脉冲编码调制PCM3.统计编码：Huffman编码、算术编码4.预测编码：DPCM、ADPCM、帧间预测5.变换编码6.多媒体数据压缩编码的国际标准−JPEG、MPEG4第一节数据压缩编码概述1.1多媒体数据压缩编码的重要性1.2多媒体数据压缩编码的可能性1.3多媒体数据压缩编码的分类51.1数据压缩编码的重要性•在多媒体技术中，处理的多媒体数据都应是数字信号，传统的媒体信息需要进行采样和量化后方能在计算机中处理。ADC放大器6•原始媒体信息数字化后的数据量巨大。•例1：一页B5（180×255mm）大小的文件，以中等分辨率300dpi、8位色方式扫描，其数据量为6.61MB。–保存一部《鹿鼎记》（1813页）需要11983.93M（650M的CD得刻19张）。7•例2：立体声的激光唱盘，采样频率为44.1kHz，量化位数为16，则一秒钟的音频数据量就可达172KB。–650M的CD只可存储1小时音乐。ADC8•对于视频，数据量的问题则更加突出。•例3：采用PAL制式，采样格式为4:4:4，24位色，则一秒钟的视频数据量就可达31.3MB。–电影《龙骑士》（时长100分钟）需要约289张650M的CD存放。采集卡9•由于多媒体信息的数据量十分庞大，给存储器的存储容量、通信线路的带宽资源、传输速率以及计算机的处理速度都增加了极大压力。•解决方法：–从硬件设备入手：增加存储器、带宽资源；研究新型线缆提高传输效率；使用快速的高档计算机……–从信息内容入手：进行数据压缩编码。——根本的解决之道10数据压缩对多媒体应用的意义•通过数据压缩技术可减少多媒体信息的数据量，其意义在于：提高了传输效率节约了存储空间使计算机能够实时处理多媒体信息加快了处理速度111.2数据压缩编码的可能性•多媒体数据能否进行压缩？•研究表明，多媒体信息中存在大量的冗余，去掉这些冗余数据便可实现数据的压缩。冗余数据可用信息原始的多媒体数据12音频中的冗余•音频中的冗余信息主要有：1.时域冗余–幅度的非均匀分布；样本间的相关性；周期之间的相关性；基音之间的相关性；静止系数（间隔）；长时自相关函数。2.频域冗余–非均匀的长时功率谱密度；语音特有的短时功率谱密度。3.人耳的听感觉分辨能力有限。13图像/视频中的冗余•图像/视频信息中包含有大量的冗余，主要有下列不同类型的冗余信息：–空间冗余–时间冗余–结构冗余–知识冗余–视觉冗余–图像区域的相同性冗余–纹理的统计冗余14a.空间冗余•空间冗余是静态图像中最主要的一种冗余。•通常的图像都描述了某个场景，其相邻像素点之间存在一定的空间连贯性。如果编码时不考虑这一相关性，就会造成空间冗余。左边的图像显示了一个规则物体，其大量像素点的亮度、饱和度、色调等参数都一样。15b.时间冗余•时间冗余是视频中常见的一种冗余。•序列图像中，相邻帧往往包含有相同的背景和运动物体，只是运动物体的位置有所变化，因此相邻两帧的数据差别很小，具有时间上的连贯性。如果编码时不考虑这一相关性，就会造成时间冗余。16c.结构冗余•有些图像中有规则纹理，其像素值存在明显的分布模式，•只要知道分布模式，便可通过某种方法生成图像，这种数据冗余即结构冗余。规则的纹理图像17d.知识冗余•对图像的理解有时与某些知识有相当大的相关性，例如人脸的图像就具有同样的五官位置。•可以根据已有的知识构造基本模型，并创建特征图像库，则只需提供少量的特征参数信息便可生成图像，这种数据冗余即知识冗余。18e.视觉冗余•视觉冗余是针对人眼的视觉特性而言的。•人对图像的敏感性是非均匀、非线性的，而一般的编码却是线性方式，因此存在视觉冗余。–视觉系统对亮度比对色度敏感。–视觉系统对低频信号比对高频信号敏感。–视觉系统对静止图像比对运动图像敏感。–视觉系统对水平、垂直线条比对斜线条敏感。–随着亮度的增加，视觉系统对量化误差的敏感度降低。（高光区可用较少的量化位数）–视觉系统把图像的边缘和非边缘区域分开处理。–视觉系统总是把视网膜上的图像分解成若干个空间有向的频率通道后，再做进一步处理。19f.图像区域的相同性冗余•有的图像存在一些相同或相近的区域，从而产生数据的重复性存储，这就是图像区域的相同性冗余。•可以只记录一个区域中各个像素的值，与其相同或相近的区域则不必记录。•向量量化方法就是针对这种冗余进行数据压缩的。20g.纹理的统计冗余•有些纹理并不严格服从某一分布规律，但它在统计意义上又符合该规律，这种数据冗余即纹理的统计冗余。孔雀羽毛的纹理分布211.3数据压缩编码的分类22•多媒体数据压缩编码方法有很多种，根据不同的依据可产生不同的分类：–按照编码算法的原理：分成脉冲编码调制、预测编码、变换编码、量化与向量量化编码、统计编码、子带编码、结构编码、模型编码、混合编码等等；–根据质量有无失真：分成有损失编码和无损失编码；–按照其作用域在空间或频率上：分成空间方法、变换方法和混合方法；–根据是否自适应：分成自适应性编码和非适应性编码。23无损编码和有损编码•实际上，信息进行数字化时，量化误差是不可避免的。此处的“无损”和“有损”是针对编码过程而言的。–无损编码：也称冗余压缩法。将编码后的数据进行解码，所得数据和编码前的原始数据严格一致，压缩比约为2:1~5:1，常用的算法有：Huffman编码、算术编码、行程编码RLE、词典编码等。–有损编码：也称熵压缩法。解码得到的还原数据与原始数据之间存在一定的误差，但并不影响人对原始资料表达信息的理解，压缩比从几倍到上百倍。2425压缩软件实际上就是使用上述这些算法进行压缩的。26衡量编码方法优劣的指标•衡量压缩编码方法优劣的重要指标有：–压缩比要高；–压缩与解压的速度快；–算法简单，适合于硬件实现；–解压缩后还原信息的质量高。27第二节脉冲编码调制•脉冲编码调制：PCM，即将连续模拟信号数字化，包括采样、量化/编码。•模拟量经过A/D转换，得到二进制码的过程，也称PCM编码。•其它的编码方法都是在模拟信号经过PCM编码后再进行的压缩编码方法。28PCM编码过程29第三节统计编码•数据压缩技术的理论基础是信息论，根据信息论的原理，可以找到最佳的数据压缩编码方法。•数据压缩的理论极限是信息熵，统计编码就是利用了信息熵原理，因此也称作信息熵编码、熵保存编码或熵编码。•统计编码是一种无损的压缩方法，如香农编码、Huffman编码、算术编码等。303.1统计编码的原理——信息量和信息熵•熵是信息论中的概念，是信息量的度量方法。•要理解什么是“信息熵”，先得了解信息、信息量的含义。31•下面以信源编码模型来说明。编码器信源（消息集）编码输出集X={x1,…,xn}Z={z1,…,zn}符号集Am={a1,…,am}−X为消息集，由n个信号单元xj构成−Z为输出集，由n个码字zj构成，zj与xj一一对应。−Am是符号集，由m个码元ai构成，符号集中间的码元组成输出码字。32•当信源发出某个随机事件（消息）xj后，接收端收到一个相应的码字zj。•那么，接收到的这个码字中包含了多少有用的信息呢？•信息是用不确定性的量度定义的。•消息xj出现的可能性愈小，则其带给人们的信息就愈多；反之，消息出现的可能性愈大，则它能给人们提供的新信息（有用信息）就愈少。•在数学上，一条消息所传输的信息是其出现概率的单调下降函数。33信息量•信息量：从N个可能事件中选出一个事件所需要的信息度量或含量。•对于计算机的二进制编码，可以这么理解：从N个事件中辨别出一个特定事件，最少需要回答多少次“yesorno”疑问。•事实上，每次提问都会得到一个“yesorno”的答复，可以用0或1表示，即1bit，如果提问n次，则信息量为nbit。34示例•例一：从1～64的整数中选出一个数。–可先提问“是否大于32?”，以消除半数的可能，然后再进行半数的询问，这样只需6次便可确定一个数，其信息量为6bit。•例二：如果只要辨别某个数是否大于32，则只需询问一次便可得出结论，其信息量只有1bit。•从上两例中可看出，大于或者小于32，这种情况的概率比具体等于某一个数的概率要大，但其信息量反而小（单调下降）。35信息量的数学表述•信息论定义了一种度量信息量的方法：•其中：–I(xj)是信源X发出xj后，接收端接收到的信息量的量度。–P(xj)是信源X发出xj的先验概率，有：njxPxIjj,...,3,2,1)(log)(2),,2,1(1011njppjnjj请用上述公式求例一的信息量。36信息熵•如果将信源所有可能事件的信息量进行统计平均（即求其数学期望），就得到了信息熵。•信源X发出的xj（j=1,2,…,n），xj出现的概率为P(xj)，则信源X的熵为：)(log)()()(211jnjjjnjjxPxPxIxPXH37示例•假设一幅由40个像素组成的灰度图像，共有5级灰度，每一级灰度都是一种信源发出的符号，分别用A~E表示。•40个像素中有15个灰度为A，7个灰度为B，7个灰度为C，6个灰度为D，5个灰度为E。•试求该灰度图像的熵。38∴该灰度图像的熵为2.196bit。196.2405log405406log406407log407407log4074015log4015)(log)()()(22222211jnjjjnjjxPxPxIxPXH39统计编码的目的•统计编码就根据信源信号出现概率的分布特性进行压缩的。•统计编码的目的：1.在信源符号和码字之间建立明确的一一对应关系；2.编码过程中不丢失信息量（即信息熵的大小不变），以便在恢复时能准确地再现原信号，实现无损压缩；3.平均码长或码率应尽量小。40熵和平均码长•可用熵来衡量该编码是否为最佳编码：–当，有冗余，不是最佳；–当，不可能出现；–当，是最佳编码（稍大于）其中表示编码器输出码字的平均码长。•可见，熵值是平均码长的下限。)(xHN)(xHN)(xHNN)(xHNnjjjLPN1413.2Huffman编码•最佳编码定理：–在变字长码中，对于出现概率大的信息符号编以短字长的码，对于出现概率小的信息符号编以长字长的码。–如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度。•Huffman编码：利用了最佳编码定理，是最常用的一种统计编码。42•Huffman编码方法先把信源符号按概率大小顺序排列，并设法按逆次序分配码字长度。•对于出现频率大的符号用较少的位数来表示；对于出现频率小的符号用较多的位数来表示。•Huffman编码方法采用的码字长度是可变的，因此较难在压缩编码后的文件中进行内容的查找。43Huffman编码的思路1.把信源符号按概率大小顺序排列，并设法按逆次序分配码字的长度。2.在分配码字长度时，首先将出现概率最小的两个符号的概率相加合成一个概率。3.把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两个符号概率为止。4.完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为0，概率小的赋为1。44Huffman编码的步骤1.对每个信息符号进行概率统计；2.将信源符号按概率的递减顺序排列；3.将最后的两个小概率相加作为新符号的概率，此时概率个数将减少一个；4.重复第2、3步，直到只剩两个概率；5.将概率大的赋“0”，概率小的赋“1”；6.逆顺序往信源符号推，不是合并的编码不变，如果是合并的，则在编码后面按照第5步的方法添加0或1。45编码实例•信源X有7个信息符号，其概率为：•请对其进行Huffman编码，写出其码树、码长，并计算平均码长和熵。Ｘ1Ｘ2Ｘ3Ｘ4Ｘ5Ｘ6Ｘ70.350.200.150.100.100.060.0446