05数据压缩编码

第5章数据压缩编码数据压缩基础第2页数据压缩编码技术概述多媒体数据压缩的必要性和可行性衡量多媒体数据压缩技术的指标：压缩比算法简单，压缩解压缩速度快尽可能地恢复原始数据压缩方法分类无损压缩：Huffman编码、游程编码、算术编码、LZW编码有损压缩：预测编码、变换编码、模型编码、基于重要性的编码、混合编码新一代的数据压缩方法：矢量量化和子代编码、基于模型的压缩、分形压缩、小波变换压缩等等。数据压缩基础第3页问题的提出音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。例如，一幅具有中等分辨率（640×480）的真彩色图像（24b/像素），它的数据量约为7.37Mb/帧，一个100MB（Byte）的硬盘只能存放约100帧图像。若要达到每秒25帧的全动态显示要求，每秒所需的数据量为184Mb，而且要求系统的数据传输率必须达到184Mb/s。对于声音也是如此，若采用16b样值的PCM编码，采样速率选为44.1kHZ，则双声道立体声声音每秒将有176KB的数据量。数据压缩基础第4页1分钟数字音频信号的存储空间1分钟数字音频信号的存储空间8*1024*1024S=(MB/s)采样频率（Hz)*量化位数(位)*声道数音频格式频带(kHz)带宽(kHz)采样率(kHz)量化位数容量(MB)电话[phone]会议电视伴音0.05-7716141.68CD-DA0.02-202044.1165.292*2DAT0.02-202048165.76*2数字音频广播0.02-202048165.76*6数据压缩基础第5页1分钟数字视频信号的存储空间8*1024*1024S=(MB)/帧图象分辨率（像素)*颜色深度(位)*帧率数字电视格式分辨率*帧率量化位数容量(MB)公用中间格式(CIF)352*288*30亮度、色差共12270CCIR601号建议NTSC720*480*30亮度、色差共161620PAL720*576*25亮度、色差共161620HDTV1280*720*6083600数据压缩基础第6页视频、图像、声音有很大的压缩潜力信息论认为：若信源编码的熵大于信源的实际熵，该信源中一定存在冗余度。原始信源的数据存在着很多冗余度：空间冗余、时间冗余、视觉冗余、听觉冗余等。数据压缩基础第7页数据压缩的好处时间域压缩──迅速传输媒体信源频率域压缩──并行开通更多业务空间域压缩──降低存储费用能量域压缩──降低发射功率数据压缩基础第8页数据压缩技术实现的衡量标准压缩比要大恢复后的失真小压缩算法要简单、速度快压缩能否用硬件实现数据压缩基础第9页多媒体数据压缩方法根据不同的依据可产生不同的分类根据质量有无损失可分为有损失编码和无损失编码。按照其作用域在空间域或频率域上分为空间方法、变换方法和混合方法。根据是否自适应分为自适应性编码和非适应性编码。数据压缩基础第10页无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。多媒体数据压缩技术分类多媒体数据压缩技术分类数据压缩基础第11页多媒体数据压缩技术分类平均信息量编码──可逆压缩──去冗余──统计特性源编码──不可逆压缩──有失真编码特征提取等两种压缩技术不互斥，两种压缩技术的结合，可以达到最高可能的压缩率。数据压缩基础第12页依据压缩算法分类统计编码Huffman编码、行程编码、LZW编码、算术编码预测编码差分（DPCM）、自适应差分脉码调制（ADPCM）变换编码最佳变换（K-L）、DCT混合编码量化编码、小波变换、分形图像编码、子带编码数据压缩基础第13页主要介绍目前用得最多和技术最成熟的无损压缩编码技术，包括：•霍夫曼编码•算术编码•RLE编码•词典编码无损数据压缩数据压缩基础第14页熵(Entropy)的概念熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。某个事件的信息量用Ii=-log2pi表示，其中pi为第i个事件的概率，0＜pi≤1。香农-范诺(Shannon-Fano)算法数据压缩基础第15页香农-范诺(Shannon-Fano)算法信源S的熵的定义按照香农(Shannon)的理论，信源S的熵定义为H(S)=Σipilog2(1/pi)其中，pi是符号si在S中出现的概率；log2(1/pi)表示包含在si中的信息量，也就是编码si所需的位数。其含义：信源S发出任意一个随机变量的平均信息量。数据压缩基础第16页香农-范诺(Shannon-Fano)算法最早阐述和实现这种编码的是Shannon（1948）和Fano（1949）采用从上到下的编码方法首先按照符号出现的频率或概率排序，然后使用递归方法分成两个部分，每一部分具有相似的次数。数据压缩基础第17页香农-范诺算法举例40个像素5级（ABCDE)灰度图象，如果每个像素用3位来表示，编码这幅图象共需120位。采用熵编码则需91位，压缩比为1.3：1。符号出现的次数pilog2(1/pi)分配的代码需要的位数A150.3751.41500030B70.1752.51450114C70.1752.51451014D60.1502.736911018E50.1253.000011115数据压缩基础第18页霍夫曼(Huffman)编码霍夫曼(Huffman)在1952年提出了另一种编码方法，即从下到上的编码方法。步骤如下：为每个字符指定一个只包含一个节点的二叉树。把字符的频率指派给对应的树，称之为树的权寻找权最小的两棵树。如果多于两棵，就随机选择。然后把这两棵树合并成一棵带有新的根节点的树，其左右子树分别是我们所选择的那两棵树重复前面的步骤直到只剩下最后一棵树数据压缩基础第19页霍夫曼(Huffman)编码字母频率编码A25%01B15%110C10%111D20%10E30%00数据压缩基础第20页霍夫曼(Huffman)编码ABCDE.25.15.10.20.30ABCDE.25.25.20.30ABCE.25.45.30DBC.45DEA.55数据压缩基础第21页霍夫曼(Huffman)编码00001111DEABC字母HuffmanA01B110C111D10E00数据压缩基础第22页霍夫曼(Huffman)编码霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。几个个问题值得注意：霍夫曼码没有错误保护功能；霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码；接收端需保存一个与发送端相同的霍夫曼码表。数据压缩基础第23页霍夫曼(Huffman)编码信源符号概率是2的负幂次方时，编码效率达到100%。依赖于信源的统计特性，必须先统计得到信源的概率特性才能编码，这就限制了实际的应用缺乏构造性，即它不能用某种数学方法建立起消息和码字之间的一一对应关系，而只能通过某种查表的方法建立起它们的对应关系。如果消息数目很多，那么所需存储的码表也很大，这将影响系统的存储量及编、译码速度。数据压缩基础第24页算术编码算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。数据压缩基础第25页算法举例假设信源符号为{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)，二进制消息序列的输入为：10001100101101数据压缩基础第26页算法举例新子区间的起始位置＝前子区间的起始位置＋当前符号的区间左端×前子区间长度新子区间的长度＝前子区间的长度×当前符号的概率（等价于范围长度）最后得到的子区间的长度决定了表示该区域内的某一个数所需的位数。数据压缩基础第27页算法举例数据压缩基础第28页算术编码算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开发动态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。数据压缩基础第29页算术编码需要注意的问题由于实际计算机精度不可能无限长，运算中溢出是明显的问题，但多数机器都有16位、32位或者64位的精度，因此可使用比例缩放法解决。算术编码器对消息只产生一个码字，这个码字是在[0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。数据压缩基础第30页RLE(runlengthencoding)编码用RLE编码方法得到的代码为：80315084180。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。数据压缩基础第31页第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。词典编码的思想数据压缩基础第32页词典编码的思想第二类算法的想法是企图从输入的数据中创建一个“短语”词典，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。数据压缩基础第33页词典编码J.Ziv和A.Lempel在1978年首次发表了介绍上述第二类编码方法的文章。TerryA.Welch在他们的研究基础上，于1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-ZivWalch)压缩编码，数据压缩基础第34页LZW算法LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法。数据压缩基础第35页LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedyparsingalgorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Currentcharacter)作为该前缀的扩展字符，形成新的扩展字符串——缀-符串(String)：Prefix.C。这个新的缀-符串(String)是否要加到词典中，还要看词典中是否存有和它相同的缀-符串String。如果有，那么这个缀-符串(String)就变成前缀(Prefix)，继续输入新的字符，否则就把这个缀-符串(Str