多媒体技术基础04课件

1、第四讲无损数据压缩第1页，共46页。主要内容数据压缩概述香农范诺与霍夫曼编码算术编码行程编码词典编码图形图像处理实验室第2页，共46页。数据压缩的定义数据压缩的必要性数据压缩的好处数据压缩的衡量标准数据压缩的分类数据压缩概述第3页，共46页。数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号信源编码信道编码信道信道译码信源译码信源信宿数据压缩的定义第4页，共46页。多媒体信源引起了“数据爆炸”,如果不进行数据压缩传输和存储都难以实用化。如下两表所示:多媒体数据数据压缩的必要性第5页，共46页。1分钟数字音频信号需要的存储空间数据压缩的必要性(续)第6页，共46页。1分钟数字视

2、频信号需要的存储空间数据压缩的必要性(续)第7页，共46页。时间域压缩迅速传输媒体信源频率域压缩并行开通更多业务空间域压缩降低存储费用能量域压缩降低发射功率数据压缩的好处第8页，共46页。压缩比要大恢复后的失真小压缩算法要简单、速度快压缩能否用硬件实现数据压缩技术实现的衡量标准第9页，共46页。根据还原后数据的有无失真分为： 无损压缩:是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合，如文档、软件安装包等。 有损压缩:是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达

3、的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合，如声音、图像、视频数据等。数据压缩的分类第10页，共46页。根据编码特点分为以下五种类型:脉冲编码调制：如PCM编码。预测编码：如DM编码、ADPCM编码等。统计编码(无损)：如Huffman编码、算术编码、RLE编码、词典编码。变换编码：如DCT变换、K-L变换、Wavelet变换。混合编码：如Jpeg编码、Mpeg编码。数据压缩的分类(续)第11页，共46页。熵的概念信源的熵香农-范诺编码霍夫曼编码香农范诺与霍夫曼编码第12页，共46页。熵的概念在符号出现 (事件发生)之前，熵(Entropy)表示符号集(离散信源)

4、中的符号出现的不确定性；在符号出现之后，熵代表接收这个符号所获得的信息量或者表示这个符号所需的位数。熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。 第13页，共46页。熵的概念(续)为了完全确定事件x(使后验概率为1)所必须提供的信息量称为x事件的非平均自信息量I(x)，非平均自信息量是随机事件的一个固有特性，它表明了事件的先验不确定性大小。某事件x的发生概率为p(x)，则其非平均自信息量I(x)为：例一第14页，共46页。信源被抽象为一个随机变量序列（随机过程）。如果信源输出的随机变量取值于某一连续区间，就叫做连续信源。比如语音信号X(t)。

5、如果信源输出的随机变量取值于某一离散符号集合，就叫做离散信源。比如数字平面图像X(x，y)和电报等。信源的熵第15页，共46页。离散信源(随机事件集合)中每个事件的非平均自信息量I(x)是定义在这个样本空间上的一个随机变量，所以我们要研究它们的统计特性。其数学期望为：信源的熵(续)称H(X)为一阶信息熵或者简称为信源的熵，H(X)表明了集合中所有随机事件的平均不确定性，或者说平均信息量。根据直觉，信源编码的数据输出速率(平均码长)与信源熵之间应该有某种对应关系。第16页，共46页。熵的大小与信源的概率分布模型有着密切的关系。最大离散熵定理：当与信源对应的符号集中的各个符号为等概率分布时，信源的

6、熵具有极大值log2m。m为符号集中符号的个数。信源的熵(续)第17页，共46页。对于同一个信源其总的信息量是不变的，如果能够通过某种变换(编码)，使信源尽量等概率分布，则每个输出符号所独立携带的信息量增大，那么传送相同信息量所需要的序列长度就越短。离散信源的冗余度隐含在信源符号的非等概率分布之中。只要H(x)小于log2m，就存在数据压缩的可能。信源的熵(续)第18页，共46页。如果采用二进制编码方式，设符号j的编码长度为Lj，则信源符号表的平均码长为： 在Lj log2pj时，平均码长取得极小值H(X)根据前面对二进制信源的分析，有：信源的熵(续)例二第19页，共46页。信源的熵即为离散信

7、源的压缩极限。(理论极限)只要信源不是等概率分布，就存在着数据压缩的可能性。数据压缩的基本途径：使符号的编码长度尽量等于符号的信息量。典型的熵编码算法有香农-范诺编码与霍夫曼编码。信源的熵(续)第20页，共46页。香农范诺编码香农范诺编码采用从上到下的方法进行编码，具体步骤为：首先将编码字符集中的字符按照出现频度和概率进行排序。用递归的方法将其分成两部分，使两个部分的概率和接近于相等。直至不可再分，即每一个叶子对应一个字符。对每一个叶子结点进行编码。第21页，共46页。符号ABCDE次数157765A BC D EABCD EDE01010011香农范诺编码(续)第22页，共46页。香农范诺编

8、码(续)符号出现次数编码A1500B701C710D6110E5111总位数=(15+7+7+)X2+(6+5)X3=91压缩比：120:91第23页，共46页。霍夫曼编码霍夫曼编码与香农-范诺编码正好相反，它采用自下向上的方式，其核心思想就是构建一棵霍夫曼树，然后对叶子结点编码，具体步骤：初始化，根据概率对符号进行排序。合并概率最小的两个符号形成新的中间结点。重复步骤2，直至形成一个Huffman树。对Huffman树叶子结点从根结点起进行编码。第24页，共46页。霍夫曼编码(续)符号ABCDE次数157765B C D EABCD EDE01010011B C第25页，共46页。霍夫曼编码

9、(续)符号出现次数编码A150B7100C7101D6110E5111总位数=15X1+(7+7+6+5)X3=90压缩比：120:90=4:3第26页，共46页。霍夫曼编码(续)霍夫曼编码的特点：霍夫曼码没有错误保护功能，且错误发生后会出现错误传播，计算机无法更正这种错误，也不知错误发生在何处。霍夫曼码是可变长度码，无法从压缩后的数据中提取部分数据。霍夫曼编码又称为前辍码，即每个符号的编码不能够是其它符号编码的前辍。 第27页，共46页。熵编码算法的核心思想香农范诺编码、霍夫曼编码和后面讲到的算术编码，它们共同的宗旨在于找到一种编码使得平均码长到达信源熵极限，基本思想就是对信源符号中出现概率

10、较大的符号用较少的码长去表示，而对出现概率较小的符号用较长的码长去表示，以使总的位数达到最少。第28页，共46页。算术编码基本思想：算术编码不是将单个信源符号映射成一个编码，而是把真个信源表示为0到1之间的一个实数区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。信源中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的位来表示这个区间。算术编码用到两个基本的参数：符号的概率和它的编码间隔。 第29页，共46页。算术编码(续)例 假设信源符号为00, 01, 10, 11，这些符号的概率分别为 0.1,

11、 0.4, 0.2, 0.3 ，根据这些概率可把间隔0, 1)分成4个子间隔：0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)，如下表所示。 符号00011011概率0.10.40.20.3初始区间0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1)如果二进制消息序列的输入为：10 00 11 00 10 11 01。则编码过程如下所示 。第30页，共46页。步骤 输入符号编码间隔 编码判决1100.5, 0.7)符号的间隔范围0.5, 0.7) 2000.5, 0.52)0.5, 0.7)间隔的第一个1/103110.514, 0.52)0.5, 0.

12、52)间隔的最后一个1/104000.514, 0.5146)0.514, 0.52)间隔的第一个1/105100.5143, 0.51442)0.514, 0.5146)间隔的第五个1/10开始，二个1/106110.514384, 0.51442)0.5143, 0.51442)间隔的最后3个1/107010.5143836, 0.514402)0.514384, 0.51442)间隔的4个1/10，从第1个1/10开始8从0.5143876, 0.514402中选择一个数作为输出：0.5143876算术编码(续)编码过程表输入为10 00 11 00 10 11 01,输出为0.5143

13、876 。第31页，共46页。算术编码(续)编码过程图示第32页，共46页。算术编码(续)步骤间隔符号译码判决10.5, 0.7)100.51439在间隔 0.5, 0.7)20.5, 0.52)000.51439在间隔 0.5, 0.7)的第1个1/1030.514, 0.52)110.51439在间隔0.5, 0.52)的第7个1/1040.514, 0.5146)000.51439在间隔0.514, 0.52)的第1个1/1050.5143, 0.51442)100.51439在间隔0.514, 0.5146)的第5个1/1060.514384, 0.51442)110.51439在间隔

14、0.5143, 0.51442)的第7个1/1070.5143876, 0.514402)010.51439在间隔0.51439, 0.5143948)的第1个1/108译码的消息：10 00 11 00 10 11 01译码过程表输入为0.5143876,输出为10 00 11 00 10 11 01。第33页，共46页。算术编码(续)在算术编码中需要注意的几个问题：由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。 算术编码器对整个消息只产生一个码字，这个码字是在间隔0, 1)中的一个实数，

15、因此译码器在接受到表示这个实数的所有位之前不能进行译码。 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。算术编码可以是静态的或者自适应的。第34页，共46页。行程编码(RLE) 行程编码（Run-Length Encoding）：它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。 例如:RTTTTTTTTABBBBC被转换为：R#8TA#4BC，其中“”作为转义字符，表明其后所跟的字符表示长度。 行程编码多用于黑白二值图像的压缩中。 例如:00000000111111111111000001111111被转化为一系列黑串和白串长度的编

16、码：81257。第35页，共46页。词典编码词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。 实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。第36页，共46页。第一类词典编码第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。第一类词典编码算法主要有LZ77算法和LZSS算法，这

17、里只介绍LZ77算法。第37页，共46页。LZ77算法LZ77算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。第38页，共46页。LZ77算法编码过程:1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长

18、的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 1 个字符，继续步骤 1。LZ77算法(续)第39页，共46页。LZ77算法(续)LZ77算法编码示意图第40页，共46页。AABCBBABCA步骤位置匹配串输出110, 0, A22A1, 1, B340, 0, C45B2, 1, B57ABC5, 3, ALZ77算法(续)LZ77算法编码举例第41页，共46页。第二类词典编码第二类算法的想法是企图从输入的已编码的数据中创建一个“短语词典”，这种短语可以是任意字符的组合。在接下来的数据编码过程中当遇到已经在词典中出现的“短语”时，编码器就输出“短语”在这个词典中 “索引号”，而不是短语本身，从而达到