多媒体技术-04数据压缩基础

1、MTIMTIMTIMTIMTIMTIXIDIAN数据压缩基础数据压缩基础多媒体技术第四讲第四讲2主要内容 数据压缩概述 经典数据压缩理论 香农范诺与霍夫曼编码 算术编码 行程编码 词典编码 预测编码 变换编码 分析综合编码3什么是数据压缩 数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号信源编码信道编码信道信道译码信源译码信源信宿4多媒体信源引起了“数据爆炸”如果不进行数据压缩 传输和存储都难以实用化。多媒体数据数据压缩的必要性5数字音数字音频格式频格式频带频带(Hz)带宽带宽(KHz)取样率取样率(KHz)量化量化位数位数存储容存储容量量(MB)电话电话20034003.

2、2880.48会议电会议电视伴音视伴音507000716141.68CD-DACD-DA20200002044.1165.2922DATDAT20200002048165.762数字音数字音频广播频广播20200002048165.766分钟数字音频信号需要的存储空间1 16分钟数字视频信号需要的存储空间1 17 时间域压缩时间域压缩迅速传输媒体信源迅速传输媒体信源 频率域压缩频率域压缩并行开通更多业务并行开通更多业务 空间域压缩空间域压缩降低存储费用降低存储费用 能量域压缩能量域压缩降低发射功率降低发射功率数据压缩的好处8l压缩比要大压缩比要大l恢复后的失真小恢复后的失真小l压缩算法要简单、

3、速度快压缩算法要简单、速度快l压缩能否用硬件实现压缩能否用硬件实现数据压缩技术实现的衡量标准9 无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。 有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。数据压缩技术的分类10经典数据压缩理论信息论中的信源编码理论解决的主要问题：（1）数据压缩的理论极限（2）数据压缩的基本途径11信源 信源被抽象为一个随机变量序列（随机过程）。 如果信

4、源输出的随机变量取值于某一连续区间，就叫做连续信源。比如语音信号X(t)。 如果信源输出的随机变量取值于某一离散符号集合，就叫做离散信源。比如平面图像X(x，y)和电报。信源 X1, X2, X3, X412离散信源 如果随机序列中各个变量独立具有相同的概率分布，则称为简单离散信源。 如果离散平稳信源的输出序列中各个变量是相互独立的，即前一个符号的出现不影响以后任何一个符号出现的概率，则称为离散无记忆平稳信源，否则称为离散有记忆平稳信源。信源 X1, X2, X3, X4 a1, a2, a3, am13离散事件的非平均互信息量 y事件的发生对判断x事件所带来的信息量取决于x的先验概率p(x)

5、与y发生后x的后验概率p(x|y)之比。 非平均互信息量 I(x ; y) 互信息量的性质：)()()(log)()|(log);(ypxpxypxpyxpyxI);();()1(xyIyxI)|;();();()2(yzxIyxIyzxI14离散事件的非平均自信息量 为了完全确定事件x(使后验概率为1)所必须提供的信息量称为x事件的非平均自信息量I(x) 非平均自信息量是随机事件的一个固有特性，它表明了事件的先验不确定性大小)(log)(1log)(xpxpxI);()(yxIxI15联合自信息量与条件自信息量 条件自信息量I(x|y)：y确定时x所保留的不确定性大小： 联合自信息量I(xy

6、)：)|(log)|(yxpyxI)(log)(xypxyI16一些结论)|()()|()();()4(xyIyIyxIxIyxII(x)I(y)I(x;y)I(xy)()()();()5(xyIyIxIyxI);()()()()6(yxIyIxIxyI)()()()3(yIxIxyI)()|()1(xIyxI)|()|()()()2(xyzIxyIxIxyzI17熵（Entropy） 事件集合（样本空间）X中每个事件的自信息量I(x)是定义在这个样本空间上的一个随机变量，所以我们要研究它的统计特性。其数学期望为： H(X)表明了集合X中随机事件的平均不确定性，或者说平均信息量。 称H(X)为

7、一阶信息熵或者简称为熵(Entropy)XxXxxpxpxIxpXH)(log)()()()(18熵（Entropy） 在符号出现之前，熵表示符号集中的符号出现的平均不确定性；在符号出现之后，熵代表接收一个符号所获得的平均信息量。 根据直觉，信源编码的数据输出速率（平均码长）与信源熵之间应该有某种对应关系。19信源的概率分布与熵的关系 熵的大小与信源的概率分布模型有着密切的关系。 最大离散熵定理：当与信源对应的字符集中的各个字符为等概率分布时，熵具有极大值log2m。m为字符集中字符个数。mjjjppxH1log)(mjjp1120二进制信源的熵 二进制信源输出一个二进制数码所携带的平均信息量

8、最大为1bit。pH10.50121最大离散熵定理的应用 对于同一个信源其总的信息量是不变的，如果能够通过某种变换（编码），使信源尽量等概率分布，则每个输出符号所独立携带的信息量增大，那么传送相同信息量所需要的序列长度就越短。 离散无记忆信源的冗余度隐含在信源符号的非等概率 分布之中。只要H（X）小于log2m，就存在数据压缩的可能。22编码信源 X1, X2, ,XL a1, a2, a3, aK编码器 Y1, Y2, , YN b1, b2, b3, bD0,1信源字母表码元表消息分组码字23平均码长与熵 如果采用单字符二进制编码方式，设字符aj的编码长度为Lj，则信源字母表的平均码长为：

9、 根据前面对二进制信源的分析，有：KjjjLpL1)(1)(XHLLXHKjjjjKjjppLp121log 在Lj log2pj时，平均码长取得极小值H(X)24关于离散无记忆平稳信源的结论 一阶熵即为离散无记忆平稳信源的压缩极限。（基本极限） 只要信源不是等概率分布，就存在着数据压缩的可能性。 数据压缩的基本途径之一：使各字符的编码长度尽量等于字符的信息量。25联合熵与条件熵 设随机变量X和Y分别取值于符号表a1, a2, am和b1, b2, b3, bn 定义X与Y的联合熵为： 定义X关于Y的条件熵为： mjnkkjkjbaPbaPYXH11),(log),(),( mjnkkjkjb

10、aPbaPYXH11)|(log),()|(26离散有记忆信源的冗余)()|(XHYXH)()()|()(),(YHXHXYHXHYXH联合熵与其可能达到的最大值之间的差值反映了该有记忆信源所含的冗余度，这种冗余是由于随机变量序列之间的相关性造成的。27关于离散有记忆平稳信源的结论 离散有记忆平稳信源的压缩极限为： 压缩的基本途径之二：尽量去除各分量之间的相关性，再对各分量进行独立编码。 压缩的基本途径之三：可利用条件概率进行编码，阶越高越有利。 压缩的基本途径之四：可将多个分量合并成向量，利用其联合概率进行编码，联合的分量越多越有利。),.,|(121limnnnXXXXH28熵编码 熵编码

11、包括香农范诺编码、霍夫曼编码和算术编码，其宗旨在于找到一种编码使得平均码长到达熵极限，基本思想就是对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长。29霍夫曼编码 具体步骤：（1）初始化（2）合并概率最小的两个事件（3）排序（4）如果事件个数大于2则重复（2）和（3）（5）赋值（6）编码30霍夫曼编码举例符号S1S2S3S4出现概率1/21/41/81/8等长编码00011011霍夫曼010110111H(X) = 1.75 L1=2 L2=1.75源S1S2S1S3S2S1S1S4等0001001001000011霍0100110100011131霍夫曼编码的局限性 利用

12、霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限。 输入符号数受限于可实现的码表尺寸 译码复杂 需要实现知道输入符号集的概率分布 没有错误保护功能32香农范诺编码 香农范诺编码与Huffman编码相反，采用从上到下的方法。 具体步骤为： （1）首先将编码字符集中的字符按照出现频度和概率进行排序。 （2）用递归的方法分成两部分，使两个部分的概率和接近于相等。直至不可再分，即每一个叶子对应一个字符。 （3）编码。33香农范诺编码举例A BC D EABCD EDE符号符号ABCDE次数次数1577650101001134算术编码 Huffm

13、an 编码的局限性： Huffman 编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 0.322 位编码，但 Huffman 编码一定会为其分配一位 0 或一位 1 的编码。可以想象，整个信息的 80% 在压缩后都几乎相当于理想长度的 3 倍左右。35算术编码 基本思想：算术编码不是将单个信源符号映射成一个码字，而是把真个信源表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要用来缩

14、短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。 采用算术编码每个符号的平均编码长度可以为小数。36算术编码举例（一）符号00011011概率0.10.40.20.3初始区间0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1)37算术编码举例（二） 最后的子区间起始位置 85/256 = 0.01010101 子区间长度 27/256 = 0.00011011 子区间尾 7/16 = 0.0111 取编码区间中的一个值，最后编码为：011符号01频度1/43/4消息序列1011区间起始1/41/419/6485/256区间长度3/4

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

16、340.60010.58340.66670.65010.63900.6334c1/31/42/53/6b1/32/42/52/6a1/31/41/51/6输入序列为：输入序列为：bcc.40行程编码（RLE） 行程编码（Run-Length Encoding）：它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。 例如：RTTTTTTTTABBCDG被转换为：R#8TABBCDG，其中“”作为转义字符，表明其后所跟的字符表示长度。 行程编码多用于黑白二值图像的压缩中。例如00000000111111111111000001111111被转化为一系列黑串和白串长度的编码：

17、81257。因为串长度并非等概率分布，所以一般要配合以统计编码（Huffman编码）。41词典编码 词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。 实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。42第一类词典编码 第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。43LZ77

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

19、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 1 个字符，继续步骤 1。45LZ77算法46LZ77编码举例AABCBBABCA步骤步骤位置位置匹配串匹配串输出输出110, 0, A22A1, 1, B340, 0, C45B2, 1, B57ABC5, 3, A47LZSS算法 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的

20、问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。 LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针（匹配串长度大于等于MIN_LENGTH），否则就输出真实字符。另外要输出额外的标志位区分是指针还是字符。48LZSS编码的基本流程1、从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len = MIN_LENGTH），则进行步骤 2，否则进行步骤 3。2、输出指针二元组 ( off, len)。其中 off 为

21、窗口中匹配字符串相对窗口边界的偏移，len 为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。3、输出当前字符c，然后将窗口向后滑动 1 个字符，继续步骤 1。49LZSS编码举例位置位置1234567891011字符字符AABBCBBAABC步骤步骤位置位置匹配串匹配串输出输出11A22AA33B44BB55C66BB（3，2）78AAB（7，3）811CC输入数据流：输入数据流：编码过程编码过程MIN_LEN =250LZSS算法 在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档

22、压缩程序都使用了LZSS的思想。例如，PKZip, GZip, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。 LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。51第二类词典编码 第二类算法的想法是企图从输入的数据中创建一个“短语词典 (dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。52LZ78算法 LZ78的编码思想是不断

23、地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Char stream)，生成码字流(Code stream)，从而达到压缩数据的目的。 LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。53LZ78编码算法步骤1：将词典和当前前缀P都初始化为空。步骤2：当前字符C:=字符流中的下一个字符。步骤3：判断PC是否在词典

24、中 （1）如果“是”，则用C扩展P，即让P:=PC，返回到步骤2。 （2）如果“否”，则 输出与当前前缀P相对应的码字W和当前字符C， 即（W，C）； 将PC添加到词典中； 令P:=空值，并返回到步骤254LZ78编码举例位置位置123456789字符字符ABBCBCABA步骤步骤位置位置词典词典输出输出11A(0, A)22B(0, B)33BC(2, C)45BCA(3, A)58BA(2, A)输入数据流：输入数据流：编码过程：编码过程：55LZW算法 J.Ziv和A.Lempel在1978年首次发表了介绍第二类词典编码算法的文章。在他们的研究基础上，Terry A.Welch在1984

25、年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码。 在编码原理上，LZW与LZ78相比有如下差别： LZW只输出代表词典中的字符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符。即在编码匹配时，至少可以在词典中找到长度为1的匹配串。 LZW编码是围绕称为词典的转换表来完成的。56LZW算法的词典 LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Char stream)，字符流可以是用8位ASCII字符组

26、成的字符串，而输出是用n位(例如12位)表示的码字流 (Code stream)，码字代表单个字符或多个字符组成的字符串(String)。57LZW编码算法步骤1：将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。步骤2：当前字符C:=字符流中的下一个字符。步骤3：判断PC是否在词典中 （1）如果“是”，则用C扩展P，即让P:=PC，返回到步骤2。 （2）如果“否”，则 输出与当前前缀P相对应的码字W； 将PC添加到词典中； 令P:=C，并返回到步骤258LZW编码举例位置位置123456789字符字符ABBABABAC步骤步骤位置位置码字码字词典词典输出输出1A2B3C114AB12

27、25BB2336BA2447ABA4568ABAC7输入数据流：输入数据流：编码过程：编码过程：59LZW算法 LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。 LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法。60预测编码 预测编码是数据压缩理论的一个重要分支。它根据离散信号之间存在一定相关性的特

28、点，利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差（预测误差）进行编码。如果预测比较准确，那么误差信号就会很小，就可以用较少的码位进行编码，以达到数据压缩的目的。 第n个符号Xn的熵满足：).|(.)|()|()(121211xxxxHxxxHxxHxHnnnnnnnnn所以参与预测的符号越多，预测就越准确，该信源的不确定性就越小，数码率就可以降低。61DPCM编码预测器xkekxkxk-ekDPCM是有损型还是无损型关键看对预测误差是有损型还是无损型关键看对预测误差ek如何编码。预测方程式 线性预测： 如果ai是常数，则为时不变线性预测，否则为自适应线性预测（ADPC

29、M） 最简单的预测方程：11)(kiiikxkax),.,(1321kxxxxfxkk1kkxx最佳线性预测使误差函数达到最小值的预测方程式叫做最佳线性预测。求最佳线性预测的各个参数ai，列方程组：2)(nnxxEmse)1,.,2,1(,0)(2niaxxEinn11niiinxax代入得到联立方程组：)1,.,2,1(, 11nixxEaxxEnlillin如果为一阶线性预测，则可求得：2111nnnxExxEa11nnxax64图像信号的预测编码 一副数字图像可以看成一个空间点阵，图像信号不仅在水平方向是相关的，在垂直方向也是相关的。根据已知样值与待预测样值间的位置关系，可以分为： （1）一维预测（行内预测）：利