MTIMTI数据压缩基础数据压缩基础多媒体技术第五章第五章1主要内容数据压缩概述经典数据压缩理论香农范诺与霍夫曼编码算术编码行程编码词典编码预测编码变换编码2什么是数据压缩 数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号信源编码信道编码信道信道译码信源译码信源信宿3多媒体信源引起了“数据爆炸”如果不进行数据压缩 传输和存储都难以实用化。多媒体数据数据压缩的必要性4分钟数字音频信号需要的存储空间1 15分钟数字视频信号需要的存储空间1 16时间域压缩时间域压缩迅速传输媒体信源迅速传输媒体信源频率域压缩频率域压缩并行开通更多业务并行开通更多业务空间域压缩空间域压缩降低存储费用降低存储费用能量域压缩能量域压缩降低发射功率降低发射功率数据压缩的好处7l压缩比要大压缩比要大l恢复后的失真小恢复后的失真小l压缩算法要简单、速度快压缩算法要简单、速度快l压缩能否用硬件实现压缩能否用硬件实现数据压缩技术实现的衡量标准8 无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。 有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。数据压缩技术的分类9经典数据压缩理论信息论中的信源编码理论解决的主要问题：（1）数据压缩的理论极限（2）数据压缩的基本途径10离散事件的非平均自信息量为了完全确定事件x(使后验概率为1)所必须提供的信息量称为x事件的非平均自信息量I(x)11熵（Entropy）事件集合（样本空间）X中每个事件的自信息量I(x)是定义在这个样本空间上的一个随机变量，所以我们要研究它的统计特性。其数学期望为：H(X)表明了集合X中随机事件的平均不确定性，或者说平均信息量。称H(X)为一阶信息熵或者简称为熵(Entropy)12熵（Entropy）在符号出现之前，熵表示符号集中的符号出现的平均不确定性；在符号出现之后，熵代表接收一个符号所获得的平均信息量。根据直觉，信源编码的数据输出速率（平均码长）与信源熵之间应该有某种对应关系。13信源的概率分布与熵的关系熵的大小与信源的概率分布模型有着密切的关系。最大离散熵定理：当与信源对应的字符集中的各个字符为等概率分布时，熵具有极大值log2m。m为字符集中字符个数。14二进制信源的熵二进制信源输出一个二进制数码所携带的平均信息量最大为1bit。pH10.50115最大离散熵定理的应用对于同一个信源其总的信息量是不变的，如果能够通过某种变换（编码），使信源尽量等概率分布，则每个输出符号所独立携带的信息量增大，那么传送相同信息量所需要的序列长度就越短。离散无记忆信源的冗余度隐含在信源符号的非等概率 分布之中。只要H（X）小于log2m，就存在数据压缩的可能。16编码信源 X1, X2, ,XL a1, a2, a3, aK编码器 Y1, Y2, , YN b1, b2, b3, bD0,1信源字母表码元表消息分组码字17平均码长与熵如果采用单字符二进制编码方式，设字符aj的编码长度为Lj，则信源字母表的平均码长为：根据前面对二进制信源的分析，有： 在Lj log2pj时，平均码长取得极小值H(X)18关于离散无记忆平稳信源的结论一阶熵即为离散无记忆平稳信源的压缩极限。（基本极限）只要信源不是等概率分布，就存在着数据压缩的可能性。数据压缩的基本途径之一：使各字符的编码长度尽量等于字符的信息量。19熵编码熵编码包括香农范诺编码、霍夫曼编码和算术编码，其宗旨在于找到一种编码使得平均码长到达熵极限，基本思想就是对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长。20霍夫曼编码具体步骤：（1）初始化（2）合并概率最小的两个事件（3）排序（4）如果事件个数大于2则重复（2）和（3）（5）赋值（6）编码21霍夫曼编码举例符号S1S2S3S4出现概率1/21/41/81/8等长编码00011011霍夫曼010110111H(X) = 1.75 L1=2 L2=1.75源S1S2S1S3S2S1S1S4等0001001001000011霍0100110100011122霍夫曼编码的局限性利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限。输入符号数受限于可实现的码表尺寸译码复杂需要实现知道输入符号集的概率分布没有错误保护功能23香农范诺编码香农范诺编码与Huffman编码相反，采用从上到下的方法。具体步骤为： （1）首先将编码字符集中的字符按照出现频度和概率进行排序。 （2）用递归的方法分成两部分，使两个部分的概率和接近于相等。直至不可再分，即每一个叶子对应一个字符。 （3）编码。24香农范诺编码举例A BC D EABCD EDE符号符号ABCDE次数次数1577650101001125算术编码Huffman 编码的局限性： Huffman 编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 0.322 位编码，但 Huffman 编码一定会为其分配一位 0 或一位 1 的编码。可以想象，整个信息的 80% 在压缩后都几乎相当于理想长度的 3 倍左右。26算术编码基本思想：算术编码不是将单个信源符号映射成一个码字，而是把真个信源表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。27算术编码举例（一）符号00011011概率0.10.40.20.3初始区间0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1)28算术编码举例（二）最后的子区间起始位置 85/256 = 0.01010101 子区间长度 27/256 = 0.00011011 子区间尾 7/16 = 0.0111取编码区间中的一个值，最后编码为：011符号01频度1/43/4消息序列1011区间起始1/41/419/6485/256区间长度3/43/169/6427/256信源分布：信源分布：29算术编码的具体实现因为实际只能用有限长的寄存器，这就要求将已编码的高位码字及时输出，但又不能输出过早，以免后续运算还要调整已输出的码位。（请看参考书上给出的算法）算术编码每次递推都要做乘法，所以效率比较低。二进制算术编码是一种实用的编码算法，用移位代替了乘法，使效率大大提高。自适应算术编码可以在编码过程中根据符号出现的频繁程度动态的修改分布概率，这样可以避免在编码之前必须精确求出信源概率的难题。30行程编码（RLE）行程编码（Run-Length Encoding）：它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。例如：RTTTTTTTTABBCDG被转换为：R#8TABBCDG，其中“”作为转义字符，表明其后所跟的字符表示长度。行程编码多用于黑白二值图像的压缩中。例如00000000111111111111000001111111被转化为一系列黑串和白串长度的编码：81257。因为串长度并非等概率分布，所以一般要配合以统计编码（Huffman编码）。31词典编码词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。32第一类词典编码第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。33第二类词典编码第二类算法的想法是企图从输入的数据中创建一个“短语词典 (dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。34预测编码预测编码是数据压缩理论的一个重要分支。它根据离散信号之间存在一定相关性的特点，利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差（预测误差）进行编码。如果预测比较准确，那么误差信号就会很小，就可以用较少的码位进行编码，以达到数据压缩的目的。第n个符号Xn的熵满足：所以参与预测的符号越多，预测就越准确，该信源的不确定性就越小，数码率就可以降低。35DPCM编码预测器xkekxkxk-ekDPCM是有损型还是无损型关键看对预测误差是有损型还是无损型关键看对预测误差ek如何编码。36预测方程式 线性预测： 如果ai是常数，则为时不变线性预测，否则为自适应线性预测（ADPCM） 最简单的预测方程：37最佳线性预测使误差函数达到最小值的预测方程式叫做最佳线性预测。求最佳线性预测的各个参数ai，列方程组：代入得到联立方程组：如果为一阶线性预测，则可求得：38图像信号的预测编码一副数字图像可以看成一个空间点阵，图像信号不仅在水平方向是相关的，在垂直方向也是相关的。根据已知样值与待预测样值间的位置关系，可以分为： （1）一维预测（行内预测）：利用同一行上相邻的样值进行预测。 （2）二维预测（帧内预测）：利用同一行和前面几行的数据进行预测。 （3）三维预测（帧间预测）：利用相邻几帧（或不同波段）上的取样值进行预测39静止图像的二维预测编码这种压缩算法被应用到JPEG标准的无损压缩模式之中，中等复杂程度的图像压缩比可达到2:1。cabx选择值预测值0非预测1a2b3c4a+b-c5a+(b-c)/26b+(a-c)/27(a+b)/2d三邻域预测法三邻域预测法40活动图像的帧间预测编码视频信号的冗余度主要体现在空间相关性（帧内）、时间相关性（帧间）和色度空间表示上的相关性。对于每秒25帧（30）的电视信号，其相继帧之间存在极强的相关性。据统计256级灰度的黑白图像序列，帧间差值超过3的象素数不超过4。所以在活动图像序列中可以利用前面的帧来预测后面的帧，以实现数据压缩。帧间预测编码技术被广泛应用到H.261、H.263、MPEG-1和MPEG-2等视频压缩标准之中。41变换编码预测编码希望通过对信源建模来尽可能的预测源数据；而变换编码则考虑将原始数据变换到另一个表示空间，使数据在新的空间上尽可能相互独立，而能量更集中。XYXY42MTIMTIXIDIANXIDIAN结束43