第四章多媒体数据压缩技术

内容几种冗余信息；压缩系统的评价；数据压缩分类；编码定理；统计编码；预测编码；变换编码；混合编码；图象和视频压缩标准简介重点和难点编码定理；统计编码(熵编码：Huffman;算术编码)第四章多媒体数据压缩技术一、基本概念通信的模型信源信源解码信道解码信道编码信源编码信宿信道第一节概述二、为什么要对媒体信息进行数字化？提高稳定性、精确性适于计算机处理三、为什么要进行数据压缩？是计算机信息处理的基本要求(音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。)因为编码数据中存在大量冗余举两个例子。视频图象：假设电视图象的清晰度为500线（分辨率640*480）25fps，每个点256色，90分钟的长度，问数据量？音频信息：4分37秒，44.1K采样频率，16bit量化，双声道立体声，问数据量？640*480*8*25*90*608*1024*1024=39550MB=39GB1、数据冗余度(重复数据、可忽略数据)3、信息传输与存储的限制(压缩→传输或存储→解压缩)重复数据可忽略数据2、人类不敏感因素(颜色、亮度、细节等)224颜色(16,777,216色)28颜色(256色)●音频不敏感因素(试听)●颜色不敏感因素四、进行压缩的可能性P93一般来说，多媒体数据中存在以下种类的冗余：空间冗余时间冗余统计冗余结构冗余信息熵冗余视觉冗余知识冗余其他冗余1、数据冗余度(重复数据、可忽略数据)P93[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[5]视觉冗余——视觉、听觉敏感度和非线性感觉[6]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[7]其他冗余——上述7种以外的冗余[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[5]视觉冗余——视觉、听觉敏感度和非线性感觉[6]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[7]其他冗余——上述7种以外的冗余[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[5]视觉冗余——视觉、听觉敏感度和非线性感觉[6]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[7]其他冗余——上述7种以外的冗余[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[5]视觉冗余——视觉、听觉敏感度和非线性感觉[6]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[7]其他冗余——上述7种以外的冗余[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[5]视觉冗余——视觉、听觉敏感度和非线性感觉[6]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[7]其他冗余——上述7种以外的冗余224色28色[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[5]视觉冗余——视觉、听觉敏感度和非线性感觉[6]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[7]其他冗余——上述7种以外的冗余[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[5]视觉冗余——视觉、听觉敏感度和非线性感觉[6]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[7]其他冗余——上述7种以外的冗余声音频率文字组句色彩渐变主观意识::第二节常用的压缩技术1948年Oliver提出脉冲编码调制（pulsecodemodulation；PCM）编码理论以来，我们已经有了多种多样的方法来压缩多媒体数据。●压缩比●图像质量●压缩解压速度●硬件和软件一、压缩系统的评价？压缩比的概念：数字化信息压缩前后文件大小（信息量）的比率。常用的压缩编码方法可以分为两大类：一类是无损压缩法（可逆编码），压缩比在2：1～5：1之间；另一类是有损压缩法（不可逆编码），压缩比可在几倍到上百倍之间调节。（一）图像质量（二）压缩比输入数据和输出数据比例如：图像512×480，24位。输入＝(512×480×24)/8=737280B输出15000B压缩比＝737280/15000＝49（三）压缩解压速度在许多应用中，压缩和解压可能不同时用，在不同的位置不同的系统中，压缩、解压速度分别估计。静态图像中，压缩速度没有解压速度严格；动态图像中，压缩、解压速度都有要求，因为需实时地从摄像机或其他设备中抓取动态视频。（四）硬软件系统有些压缩解压工作可用软件实现。设计系统时必须充分考虑：算法复杂－压缩解压过程长算法简单－压缩效果差目前有些特殊硬件可用于加速压缩/解压。硬件系统速度快，但各种选择在初始设计时已确定，一般不能更改。因此在设计硬件压缩/解压系统时必须先将算法标准化。二、数据压缩技术分类P96指使压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。典型的算法有：Huffman编码，算术编码，行程编码等。特点：压缩比较低，为2:1---5:1一般用来压缩文本，数据●无损压缩有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。典型的算法有：混合编码的JPEG标准，预测编码，变换编码等。特点：压缩比高，为几十到几百倍一般用于图像，声音，视频压缩。●有损压缩三、编码定理采用不同的编码方式得到了不同的压缩效果，是否可以不断的提高压缩效果，压缩效果是否存在一种极限，如果存在极限，那么数据压缩的极限如何确定，这些问题对压缩编码是十分重要的。1984面香农基于信息熵提出了编码定理。1、信源所谓信源，可以认为是由若干个（有限个）信源字母{a1,a2,a3……,am}产生字符序列的数学模型。在产生字符序列的过程中，信源字母按一定的概率法则进行选择。信源字母ai产生的概率记为p(ai)=pi三、编码定理2、平均码长平均码长可定义为L=∑ci*p(ai)式中p(ai)为信源字母产生的概率，ci为分配给ai的码字的长度。平均码长L乘以字符序列的长度，可以求出字符序列编码的码字序列的长度。显然，平均码长越短，码字序列的长度越短，表示数据压缩的效果就越好。3、信息熵P91信息量：对信息的度量称之为信息量一个消息的可能性越小，其信息量越大；消息的可能性越大，则信息量越小。定义一个集合X={Xi,i=1,2,3……n}XiP(Xi)信息量I(Xi)=-log2P(Xi)(bit)平均信息量：H(X)=-∑P(Xi)log2P(Xi)平均信息量又叫信息熵编码效率：E=H∕L冗余度：r=(L-H)∕H4、编码定理：设某信源的信源字母集合{a1,a2,a3……,am}中,ai出现的概率为P(ai),那么平均码长L与P(ai)间具有L≥-∑P(Xi)log2P(Xi)右侧为该编码系统的信息熵。表明，在任何理想的编码方式中，其平均码长不可能小于信息熵。在对图象数据分配一定码字时，一种最简单的方法是对于各种不同的图象数据都分配等长的码字，这是一种等长编码的方法，这种编码方法对于图象数据出现的频度相同的情况下是十分有效的。实际情况是，各种图象数据出现的频度是不同的。根据出现概率不同，分配不同的位数。出现概率较高的数据，分配较短的码字，出现概率较低的数据，分配较长的码字四、统计编码P99●霍夫曼编码——无损编码。●编码原理——出现频率高的数据编码长度短，反之亦然。1、将信源符号(图象数据)(0,1,2……,k-1)按其出现的概率从大到小的顺序进行排列。2、对于出现概率最小的符号和次最小的符号，分配1和03、将出现概率最低的两个符号合并为一个符号，其出现的概率应为合并前两符号出现概率之和4、通过3的处理，信源的符号数少了一个，可以将它作为一种新的信源进行考虑。对于新的信源，按信源出现概率的大小排序。5、反复进行2—4的处理。直到符号数为11.Huffman编码P99a1a2a3a4a5a6a70.20.190.180.170.150.10.010.1110100.260.3510100.39100.61101.00码字：a1:11a2:10a3:011a4:010a5:001a6:0001a7:0000码长：2233344码字：a1:11a2:10a3:011a4:010a5:001a6:0001a7:0000码长：2233344求信息熵：平均编码长度：编码效率：冗余度：0.20.190.180.170.150.10.01H(X)=-∑P(Xi)log2P(Xi)L=∑ci*p(ai)E=H∕Lr=(L-H)∕H信息熵：2.61bit平均编码长度：2.72bit编码效率：96%冗余度：0.042a10.20a20.19a30.18a40.17a50.15a60.10a70.01010.11010.2600.3510.611101000.391.00码字码长0120021113110310131001410004平均码长：2.72Huffman编码过程练习题对信源:X:X1X2X3X4X5X60.250.250.20.150.10.05进行Huffman编码，写出码字，码长及平均码长，信息熵，编码效率，冗余度。2、行程编码P100最简单、最古老的压缩技术之一，主要技术是检测重复的比特或字符序列，并用它们的出现次数取而代之。是一种统计编码，属于无损压缩编码。该方法有两大模式：一是消零(消空白)，二是行(游)程(runlength)编码。消零(或消空白)法将数字中连续的“0”或文本中连续的空白用一个标识符(或特殊字符)后跟数字N(连续“0”的个数)来代替。如数字序列：742300000000000000000055编码为：7423Z1855行程编码法任何重复的字符序列可被一个短格式取代。该算法适合于任何重复的字符。一组n个连续的字符c将被c和一个特殊的字符取代。当然，若给定字符仅重复两次就不要用此方法。任何重复4次或4次以上的字符由“该字符＋记号(M)＋重复次数”代替。例如数字序列：Name:..........CR编码为：Name:.M10CR●算术编码——无损压缩编码，属于统计编码。20世纪60年代由Elias提出，某些方面优于霍夫曼编码。因此，在JPEG标准的扩展系统中，算术编码已经取代了霍夫曼编码。●基本原理算术编码把一个信源集合表示为实数线上的0到1之间的一个区间。这个集合中的每个元素都要用来缩短这个区间。信源集合的元素越多，所得到的区间就越小，当区间变小时，就需要一些更多的数位来表示这个区间，这就是区间作为代码的原理。算术编码首先假设一个信源的概率模型，然后用这些概率来缩小表示信源集的区间。3、算术编码P101算术编码例如：输出eaiou,对该字符序列进行算术编码aeiouP0.20.30.10.20.200.20.50.60.81定义LowHighrange(区间长度)LowHigh为左右端点子区间的左右端点：rangelowrangehigh初始化：Low=0High=1range=High-Low=1-0=1low=low+range*rangelowhigh=low+range*rangehighaeiouP0.20.30.10.20.200.20.50.60.81编码过程：1、elow=low+range*rangelow=0+1*0.2=0.2high=low+range*rangehigh=0+1*0.5=0.5range=high-low=0.5-0.2=0.32、