《多媒体技术基础04.ppt》由会员分享，可在线阅读，更多相关《多媒体技术基础04.ppt（46页珍藏版）》请在三一办公上搜索。
1、第四讲,无损数据压缩,主要内容,数据压缩概述香农范诺与霍夫曼编码算术编码行程编码词典编码,图形图像处理实验室,数据压缩的定义数据压缩的必要性数据压缩的好处数据压缩的衡量标准数据压缩的分类,数据压缩概述,数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号,数据压缩的定义,多媒体信源引起了“数据爆炸”,如果不进行数据压缩传输和存储都难以实用化。如下两表所示:,数据压缩的必要性,1分钟数字音频信号需要的存储空间,数据压缩的必要性(续),1分钟数字视频信号需要的存储空间,数据压缩的必要性(续),时间域压缩迅速传输媒体信源频率域压缩并行开通更多业务空间域压缩降低存储费用能量域压缩降低发
2、射功率,数据压缩的好处,压缩比要大恢复后的失真小压缩算法要简单、速度快压缩能否用硬件实现,数据压缩技术实现的衡量标准,根据还原后数据的有无失真分为：无损压缩:是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合，如文档、软件安装包等。有损压缩:是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合，如声音、图像、视频数据等。,数据压缩的分类,根据编码特点分为以下五种类型:脉冲编码调制：如PCM编码。预测编
3、码：如DM编码、ADPCM编码等。统计编码(无损)：如Huffman编码、算术编码、RLE编码、词典编码。变换编码：如DCT变换、K-L变换、Wavelet变换。混合编码：如Jpeg编码、Mpeg编码。,数据压缩的分类(续),熵的概念信源的熵香农-范诺编码霍夫曼编码,香农范诺与霍夫曼编码,熵的概念,在符号出现(事件发生)之前，熵(Entropy)表示符号集(离散信源)中的符号出现的不确定性；在符号出现之后，熵代表接收这个符号所获得的信息量或者表示这个符号所需的位数。熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。,熵的概念(续),为了完全确定事件
4、x(使后验概率为1)所必须提供的信息量称为x事件的非平均自信息量I(x)，非平均自信息量是随机事件的一个固有特性，它表明了事件的先验不确定性大小。某事件x的发生概率为p(x)，则其非平均自信息量I(x)为：,例一,信源被抽象为一个随机变量序列（随机过程）。如果信源输出的随机变量取值于某一连续区间，就叫做连续信源。比如语音信号X(t)。如果信源输出的随机变量取值于某一离散符号集合，就叫做离散信源。比如数字平面图像X(x，y)和电报等。,信源的熵,离散信源(随机事件集合)中每个事件的非平均自信息量I(x)是定义在这个样本空间上的一个随机变量，所以我们要研究它们的统计特性。其数学期望为：,信源的熵(
5、续),称H(X)为一阶信息熵或者简称为信源的熵，H(X)表明了集合中所有随机事件的平均不确定性，或者说平均信息量。根据直觉，信源编码的数据输出速率(平均码长)与信源熵之间应该有某种对应关系。,熵的大小与信源的概率分布模型有着密切的关系。最大离散熵定理：当与信源对应的符号集中的各个符号为等概率分布时，信源的熵具有极大值log2m。m为符号集中符号的个数。,信源的熵(续),对于同一个信源其总的信息量是不变的，如果能够通过某种变换(编码)，使信源尽量等概率分布，则每个输出符号所独立携带的信息量增大，那么传送相同信息量所需要的序列长度就越短。离散信源的冗余度隐含在信源符号的非等概率分布之中。只要H(x
6、)小于log2m，就存在数据压缩的可能。,信源的熵(续),如果采用二进制编码方式，设符号j的编码长度为Lj，则信源符号表的平均码长为：,在Lj log2pj时，平均码长取得极小值H(X),根据前面对二进制信源的分析，有：,信源的熵(续),例二,信源的熵即为离散信源的压缩极限。(理论极限)只要信源不是等概率分布，就存在着数据压缩的可能性。数据压缩的基本途径：使符号的编码长度尽量等于符号的信息量。典型的熵编码算法有香农-范诺编码与霍夫曼编码。,信源的熵(续),香农范诺编码,香农范诺编码采用从上到下的方法进行编码，具体步骤为：首先将编码字符集中的字符按照出现频度和概率进行排序。用递归的方法将其分成两
7、部分，使两个部分的概率和接近于相等。直至不可再分，即每一个叶子对应一个字符。对每一个叶子结点进行编码。,香农范诺编码(续),香农范诺编码(续),总位数=(15+7+7+)X2+(6+5)X3=91压缩比：120:91,霍夫曼编码,霍夫曼编码与香农-范诺编码正好相反，它采用自下向上的方式，其核心思想就是构建一棵霍夫曼树，然后对叶子结点编码，具体步骤：初始化，根据概率对符号进行排序。合并概率最小的两个符号形成新的中间结点。重复步骤2，直至形成一个Huffman树。对Huffman树叶子结点从根结点起进行编码。,霍夫曼编码(续),B C D E,A,B,C,D E,D,E,0,1,0,1,0,0,1
8、,1,B C,霍夫曼编码(续),总位数=15X1+(7+7+6+5)X3=90压缩比：120:90=4:3,霍夫曼编码(续),霍夫曼编码的特点：霍夫曼码没有错误保护功能，且错误发生后会出现错误传播，计算机无法更正这种错误，也不知错误发生在何处。霍夫曼码是可变长度码，无法从压缩后的数据中提取部分数据。霍夫曼编码又称为前辍码，即每个符号的编码不能够是其它符号编码的前辍。,熵编码算法的核心思想,香农范诺编码、霍夫曼编码和后面讲到的算术编码，它们共同的宗旨在于找到一种编码使得平均码长到达信源熵极限，基本思想就是对信源符号中出现概率较大的符号用较少的码长去表示，而对出现概率较小的符号用较长的码长去表示，
9、以使总的位数达到最少。,算术编码,基本思想：算术编码不是将单个信源符号映射成一个编码，而是把真个信源表示为0到1之间的一个实数区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。信源中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的位来表示这个区间。算术编码用到两个基本的参数：符号的概率和它的编码间隔。,算术编码(续),例 假设信源符号为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.
10、7),0.7,1)，如下表所示。,如果二进制消息序列的输入为：10 00 11 00 10 11 01。则编码过程如下所示。,算术编码(续),编码过程表,输入为10 00 11 00 10 11 01,输出为0.5143876。,算术编码(续),编码过程图示,算术编码(续),译码过程表,输入为0.5143876,输出为10 00 11 00 10 11 01。,算术编码(续),在算术编码中需要注意的几个问题：由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。算术编码器对整个消息只产生一个码字，这
11、个码字是在间隔0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。算术编码可以是静态的或者自适应的。,行程编码(RLE),行程编码（Run-Length Encoding）：它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。例如:RTTTTTTTTABBBBC被转换为：R#8TA#4BC，其中“”作为转义字符，表明其后所跟的字符表示长度。行程编码多用于黑白二值图像的压缩中。例如:00000000111111111111000001111111被转化为一系列黑串和白
12、串长度的编码：81257。,词典编码,词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。,实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。,第一类词典编码,第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。,第一类词典编码算法主要有LZ77算法和LZSS算法，这里只介绍LZ77算法。
13、,LZ77算法,LZ77算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。,LZ77算法编码过程:1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3
14、。2、输出三元符号组(off,len,c)。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len+1 个字符，继续步骤 1。3、输出三元符号组(0,0,c)。其中 c 为下一个字符。然后将窗口向后滑动 1 个字符，继续步骤 1。,LZ77算法(续),LZ77算法(续),LZ77算法编码示意图,LZ77算法(续),LZ77算法编码举例,第二类词典编码,第二类算法的想法是企图从输入的已编码的数据中创建一个“短语词典”，这种短语可以是任意字符的组合。在接下来的数据编码过程中当遇到已经在词典中出现的“短语”时，编
15、码器就输出“短语”在这个词典中“索引号”，而不是短语本身，从而达到压缩数据的目的。第二类词典编码的典型算法有LZ78算法和LZW算法，这里只介绍LZ78算法。,LZ78算法,LZ78的编码思想是不断地从字符流中提取新的字符串，通俗地理解为新“词条”，然后用“代号”也就是码字表示这个“词条”。这样一来，对字符流的编码就变成了用码字去替换字符流，生成码字流，从而达到压缩数据的目的。LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串用字符C进行扩展生成新的字符串，然后添加到词典中。,LZ78算法(续),LZ78算法编码过程：步骤1：在开始时，词典和当前前缀P都是空的。步骤2：当前字符C=字符流中的下一个字符。步骤3：判断P+C是否在词典中：(1)如果“是”：用C扩展P，让P=P+C；(2)如果“否”：输出与当前前缀P相对应的码字和当前字符C；把字符串P+C 添加到词典中。令P=空。(3)判断字符流中是否还有字符需要编码 如果“是”：返回到步骤2。如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。,LZ78编码举例,输入数据流：,编码过程：,LZ78算法(续),结束,
