多媒体技术课件 ch4

1、多媒体技术基础第四章：无损数据压缩多媒体技术基础,2006年中山大学信息科学与技术学院主要内容数据压缩概述经典数据压缩理论香农范诺与霍夫曼编码算术编码行程编码词典编码多媒体技术,2006年中山大学信息科学与技术学院什么是数据压缩 数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号信源编码信道编码信道信道译码信源译码信源信宿多媒体技术,2006年中山大学信息科学与技术学院多媒体信源引起了“数据爆炸”如果不进行数据压缩 传输和存储都难以实用化。多媒体数据数据压缩的必要性多媒体技术,2006年中山大学信息科学与技术学院分钟数字音频信号需要的存储空间1多媒体技术,2006年中山大学信

2、息科学与技术学院分钟数字视频信号需要的存储空间1多媒体技术,2006年中山大学信息科学与技术学院时间域压缩迅速传输媒体信源频率域压缩并行开通更多业务空间域压缩降低存储费用能量域压缩降低发射功率数据压缩的好处多媒体技术,2006年中山大学信息科学与技术学院压缩比要大恢复后的失真小压缩算法要简单、速度快压缩能否用硬件实现数据压缩技术实现的衡量标准多媒体技术,2006年中山大学信息科学与技术学院 无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。 有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来

3、的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。数据压缩技术的分类多媒体技术,2006年中山大学信息科学与技术学院经典数据压缩理论信息论中的信源编码理论解决的主要问题：（1）数据压缩的理论极限（2）数据压缩的基本途径多媒体技术,2006年中山大学信息科学与技术学院熵（Entropy）事件集合（样本空间）X中每个事件的自信息量I(x)是定义在这个样本空间上的一个随机变量，所以我们要研究它的统计特性。其数学期望为：H(X)表明了集合X中随机事件的平均不确定性，或者说平均信息量。称H(X)为一阶信息熵或者简称为熵(Entropy)多媒

4、体技术,2006年中山大学信息科学与技术学院熵（Entropy）在符号出现之前，熵表示符号集中的符号出现的平均不确定性；在符号出现之后，熵代表接收一个符号所获得的平均信息量。根据直觉，信源编码的数据输出速率（平均码长）与信源熵之间应该有某种对应关系。多媒体技术,2006年中山大学信息科学与技术学院平均码长与熵如果采用单字符二进制编码方式，设字符aj的编码长度为Lj，则信源字母表的平均码长为：根据前面对二进制信源的分析，有： 在Lj log2pj时，平均码长取得极小值H(X)多媒体技术,2006年中山大学信息科学与技术学院例4.1 有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A、B、

5、C、D和E表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有7个等等，如表4-01所示。如果用3个位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位。符 号 出现的次数157765按照仙农理论，这幅图像的熵为H(S) = (15/40) (40/15) + (7/40) (40/7) + + (5/40) (40/5) =2.196这就是说每个符号用2.196位表示，40个象素需用87.84位。多媒体技术,2006年中山大学信息科学与技术学院熵编码熵编码包括香农范诺编码、霍夫曼编码和算术编码，其宗旨在于找到一种编码使得平均码

6、长到达熵极限，基本思想就是对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长。多媒体技术,2006年中山大学信息科学与技术学院霍夫曼编码初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表4-03和图4-02所示。 把概率最小的两个符号组成一个节点，如图4-02中的D和E组成节点P1。 重复步骤2，得到节点P2、P3和P4，形成一棵“树”，其中的P4称为根节点。 从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。 从根节点P4开始顺

7、着树枝到每个叶子分别写出每个符号的代码，如表4-03所示。 按照仙农理论，这幅图像的熵为多媒体技术,2006年中山大学信息科学与技术学院符号出现的次数log2(1/pi)分配的代码需要的位数A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115多媒体技术,2006年中山大学信息科学与技术学院A (0.12), E (0.42), I (0.09), O (0.30), U (0.07), A - 100 E - 0 I - 1011 O - 11 U - 101

8、0 多媒体技术,2006年中山大学信息科学与技术学院霍夫曼编码的局限性利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限。输入符号数受限于可实现的码表尺寸译码复杂需要实现知道输入符号集的概率分布没有错误保护功能多媒体技术,2006年中山大学信息科学与技术学院香农范诺编码香农范诺编码与Huffman编码相反，采用从上到下的方法。具体步骤为： （1）首先将编码字符集中的字符按照出现频度和概率进行排序。 （2）用递归的方法分成两部分，使两个部分的概率和接近于相等。直至不可再分，即每一个叶子对应一个字符。 （3）编码。多媒体技术,2006年中

9、山大学信息科学与技术学院香农范诺编码举例A BC D EABCD EDE符号ABCDE次数15776501010011多媒体技术,2006年中山大学信息科学与技术学院算术编码Huffman 编码的局限性： Huffman 编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 0.322 位编码，但 Huffman 编码一定会为其分配一位 0 或一位 1 的编码。可以想象，整个信息的 80% 在压缩后都几乎相当于理想长度的 3 倍左右。，多媒体技术,2006年中山大学信息科学与技术学院算术

10、编码基本思想：算术编码不是将单个信源符号映射成一个码字，而是把真个信源表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。多媒体技术,2006年中山大学信息科学与技术学院算术编码举例（一）符号00011011概率0.10.40.20.3初始区间0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1)多媒体技术,2006年中山大学信息科学与技

11、术学院算术编码的具体实现因为实际只能用有限长的寄存器，这就要求将已编码的高位码字及时输出，但又不能输出过早，以免后续运算还要调整已输出的码位。（请看参考书上给出的算法）算术编码每次递推都要做乘法，所以效率比较低。二进制算术编码是一种实用的编码算法，用移位代替了乘法，使效率大大提高。自适应算术编码可以在编码过程中根据符号出现的频繁程度动态的修改分布概率，这样可以避免在编码之前必须精确求出信源概率的难题。多媒体技术,2006年中山大学信息科学与技术学院自适应算术编码举例cba1.00000.66670.33330.00000.66670.58340.41670.33330.66670.63340.

12、60010.58340.66670.65010.63900.6334c1/31/42/53/6b1/32/42/52/6a1/31/41/51/6输入序列为：bcc.多媒体技术,2006年中山大学信息科学与技术学院行程编码（RLE）行程编码（Run-Length Encoding）：它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。例如：RTTTTTTTTABBCDG被转换为：R#8TABBCDG，其中“”作为转义字符，表明其后所跟的字符表示长度。用RLE编码方法得到的代码为：80315084180。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。

13、例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。多媒体技术,2006年中山大学信息科学与技术学院词典编码词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。多媒体技术,2006年中山大学信息科学与技术学院第一类词典编码第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部

14、分，它的输出仅仅是指向早期出现过的字符串的“指针”。多媒体技术,2006年中山大学信息科学与技术学院LZ77算法LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。多媒体技术,2006年中山大学信息科学与技术学院L

15、Z77编码的基本流程1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 1 个字符，继续步骤 1。多媒体技术,2006年中山大学信息科学与技术学院LZ77算法多媒体技术,2006年中山大学信息科学与技术学院LZ7

16、7编码举例AABCBBABCA步骤位置匹配串输出110, 0, A22A1, 1, B340, 0, C45B2, 1, B57ABC5, 3, A多媒体技术,2006年中山大学信息科学与技术学院LZSS算法LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针（匹配串长度大于等于MIN_LENGTH），否则就输出真实字符。另外要输出额外的标志位区分是指针还是字符。多媒体技术,2006年

17、中山大学信息科学与技术学院LZSS编码的基本流程1、从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len = MIN_LENGTH），则进行步骤 2，否则进行步骤 3。2、输出指针二元组 ( off, len)。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。3、输出当前字符c，然后将窗口向后滑动 1 个字符，继续步骤 1。多媒体技术,2006年中山大学信息科学与技术学院LZSS编码举例位置1234567891011字符AABBCBBAABC

18、步骤位置匹配串输出11A22AA33B44BB55C66BB（3，2）78AAB（7，3）811CC输入数据流：编码过程MIN_LEN =2多媒体技术,2006年中山大学信息科学与技术学院LZSS算法在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip, GZip, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它

19、的后续版本也采用霍夫曼编码。多媒体技术,2006年中山大学信息科学与技术学院第二类词典编码第二类算法的想法是企图从输入的数据中创建一个“短语词典 (dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。多媒体技术,2006年中山大学信息科学与技术学院LZ78算法LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(C

20、ode word)去替换字符流(Char stream)，生成码字流(Code stream)，从而达到压缩数据的目的。LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。多媒体技术,2006年中山大学信息科学与技术学院LZ78编码算法步骤1：将词典和当前前缀P都初始化为空。步骤2：当前字符C:=字符流中的下一个字符。步骤3：判断PC是否在词典中 （1）如果“是”，则用C扩展P，即让P:=PC，返回到步骤2。 （2）如果“否”，则 输出与当前前缀P相对应的码字W和当前字符C

21、， 即（W，C）； 将PC添加到词典中； 令P:=空值，并返回到步骤2多媒体技术,2006年中山大学信息科学与技术学院LZ78编码举例位置123456789字符ABBCBCABA步骤位置词典输出11A(0, A)22B(0, B)33BC(2, C)45BCA(3, A)58BA(2, A)输入数据流：编码过程：多媒体技术,2006年中山大学信息科学与技术学院LZW算法 J.Ziv和A.Lempel在1978年首次发表了介绍第二类词典编码算法的文章。在他们的研究基础上，Terry A.Welch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码。 在编码原理上，LZW与LZ78相比有如下差别： LZW只输出代表词典中的字符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符。即在编码匹配时，至少可以在词典中找到长度为1的匹配串。 LZW编码是围绕称为词典的转换表来完成的。多媒体技术,2006年中山大学信息科