多媒体数据压缩技术,什么是数据压缩,数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号,分钟数字音频信号需要的存储空间,1,分钟数字视频信号需要的存储空间,1,压缩编码技术基础,多媒体数据压缩的必要性 多媒体信息是海量信息：彩色电视信号信息量100Mb/S、图象、声音 多媒体海量信息的数据存储、处理、传输是软、硬件技术难题 数据压缩的可行性 信息论观点：信源数据是信息量（信源熵）和信息冗余量之和 信息冗余：空间冗余、时间冗余、结构冗余、知识冗余、视觉冗余等 数据压缩通过减少冗余量而尽可能保留信源信息量 压缩编码方法分类 冗余度压缩：无损压缩，信息保持编码或熵编码，可逆运算 信息量压缩：有损压缩，失真度编码或熵压缩编码，不可逆，允许失真,空间冗余,一幅图像表面上各采样点的颜色之 间往往存在着空间连贯性，基于离散像 素采样来表示物体表面颜色的像素存储 方式可利用空间连贯性，达到减少数据 量的目的。 例如，在静态图像中有一块表面颜 色均匀的区域，在此区域中所有点的光 强和色彩以及饱和度都是相同的，因此 数据有很大的空间冗余。,时间冗余,运动图像一般为位于一时间轴区间 的一组连续画面，其中的相邻帧往往包 含相同的背景和移动物体，只不过移动 物体所在的空间位置略有不同，所以后 一帧的数据与前一帧的数据有许多共同 的地方，这种共同性是由于相邻帧记录 了相邻时刻的同一场景画面，所以称为 时间冗余。 同理，语音数据中也存在着时间冗 余。,视觉冗余,人类的视觉系统对图像场的敏感度 是非均匀的。但是，在记录原始的图像 数据时，通常假定视觉系统近似线性的 和均匀的，对视觉敏感和不敏感的部分 同等对待，从而产生比理想编码（即把 视觉敏感和不敏感的部分区分开来的编 码）更多的数据，这就是视觉冗余。,时间域压缩迅速传输媒体信源 频率域压缩并行开通更多业务 空间域压缩降低存储费用 能量域压缩降低发射功率,数据压缩的好处,压缩编码的衡量指标,压缩比要大 恢复后的失真小 压缩算法要简单、速度快 压缩能否用硬件实现,经典数据压缩理论,信息论中的信源编码理论解决的主要问题： （1）数据压缩的理论极限 （2）数据压缩的基本途径,信源,信源被抽象为一个随机变量序列（随机过程）。 如果信源输出的随机变量取值于某一连续区间，就叫做连续信源。比如语音信号X(t)。 如果信源输出的随机变量取值于某一离散符号集合，就叫做离散信源。比如平面图像X(x，y)和电报。,信源,X1, X2, X3, X4,离散信源,如果随机序列中各个变量具有相同的概率分布，则称为离散平稳信源。 如果离散平稳信源的输出序列中各个变量是相互独立的，即前一个符号的出现不影响以后任何一个符号出现的概率，则称为离散无记忆平稳信源，否则称为离散有记忆平稳信源。,信源,X1, X2, X3, X4,a1, a2, a3, am,信息量和熵,信息量的度量,信源S熵的定义,信源熵举例 一幅用256级灰度表示的图象，每个像素点灰度的概率均等，编码每个像素需8位 40个像素组成的灰度图象，灰度为5级，ABCDE，出现每个灰度的像素个数不同，为：15、7、7、6、5，该图象的熵为H（s）=2.196，40个像素需40*2.196=87.84位,信息量和熵,仙农信息论把一个事件（字符a1）所携带的信息量定义为： I(a1) = log2 (1/p) = -log2 p (bit) 其中p为事件发生（字符出现）的概率 I(a1)即随机变量X取值为a1时所携带的信息量 因为X的信息量也是一个随机变量，所以我们要研究它的统计特性。其数学期望为： 称H(X)为一阶信息熵或者简称为熵(Entropy),熵（Entropy）,在符号出现之前，熵表示符号集中的符号出现的平均不确定性；在符号出现之后，熵代表接收一个符号所获得的平均信息量。 根据直觉，信源编码的数据输出速率（平均码长）与信源熵之间应该有某种对应关系。,信源的概率分布与熵的关系,熵的大小与信源的概率模型有着密切的关系。 最大离散熵定理：当与信源对应的字符集中的各个字符为等概率分布时，熵具有极大值log2m。m为字符集中字符个数。,二进制信源的熵,二进制信源输出一个二进制数码所携带的平均信息量最大为1bit。,最大离散熵定理的应用,对于同一个信源其总的信息量是不变的，如果能够通过某种变换（编码），使信源尽量等概率分布，则每个输出符号所独立携带的信息量增大，那么传送相同信息量所需要的序列长度就越短。 离散无记忆信源的冗余度隐含在信源符号的非等概率 分布之中。只要H（X）小于log2m，就存在数据压缩的可能。,编码,信源,X1, X2, X3, X4,a1, a2, a3, am,信源,X1, X2, X3, X4,b1, b2, b3, bn,0,1,平均码长与熵,如果对字符aj的编码长度为Lj，则X的平均码长为： 根据前面对二进制信源的分析，有：,在Lj log2pj时，平均码长取得极小值H(X),关于离散无记忆平稳信源的结论,一阶熵即为离散无记忆平稳信源的压缩极限。（基本极限） 只要信源不是等概率分布，就存在着数据压缩的可能性。 数据压缩的基本途径之一：使各字符的编码长度尽量等于字符的信息量。,联合熵与条件熵,设随机变量X和Y分别取值于符号表a1, a2, am和b1, b2, b3, bn 定义X与Y的联合熵为： 定义X关于Y的条件熵为：,离散有记忆信源的冗余,联合熵与其可能达到的最大值之间的差值反映了该有记忆信源所含的冗余度，这种冗余是由于随机变量序列之间的相关性造成的。,关于离散有记忆平稳信源的结论,离散有记忆平稳信源的压缩极限为： 压缩的基本途径之二：尽量去除各分量之间的相关性，再对各分量进行独立编码。 压缩的基本途径之三：可利用条件概率进行编码，阶越高越有利。 压缩的基本途径之四：可将多个分量合并成向量，利用其联合概率进行编码，联合的分量越多越有利。,多媒体数据压缩编码分类,无损压缩 香农-范诺编码 哈夫曼编码 算术编码 （前三个为统计编码） RLE编码（行程编码） 增量调制编码 词典编码,有损压缩 预测编码：DPCM，运动补偿等 面向频率域方法：正交变换（DCT）、子带编码等 面向空间域方法：统计分块编码等 基于重要性方法：滤波、子采样、比特分配、矢量量化等 模型方法：分形编码、模型基编码等,混合压缩编码 JBIG、JPEG、MPEG、H.261等技术标准,熵编码,熵编码包括香农范诺编码、霍夫曼编码和算术编码，其宗旨在于找到一种编码使得平均码长到达熵极限，基本思想就是对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长。,无损压缩编码算法,香农-范诺编码与哈夫曼编码 哈夫曼编码：根据统计频率生成Huffman树，然后编码 前缀码：编解码简单 实际使用时，对文件进行两遍扫描，第一遍统计频率，第二遍编码 压缩比不高 对错误敏感，没有错误保护功能，形成错误传播,霍夫曼编码,具体步骤： （1）初始化 （2）合并概率最小的两个事件 （3）排序 （4）如果事件个数大于2则重复（2）和（3） （5）赋值 （6）编码,霍夫曼编码举例,H(X) = 1.75 L1=2 L2=1.75,霍夫曼编码的局限性,利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限。 输入符号数受限于可实现的码表尺寸 译码复杂 需要实现知道输入符号集的概率分布 没有错误保护功能,香农范诺编码,香农范诺编码与Huffman编码相反，采用从上到下的方法。 具体步骤为： （1）首先将编码字符集中的字符按照出现频度和概率进行排序。 （2）用递归的方法分成两部分，使两个部分的概率和接近于相等。直至不可再分，即每一个叶子对应一个字符。 （3）编码。,香农范诺编码举例,0,1,0,1,0,0,1,1,无损压缩编码算法,算术编码 消息用0到1之间的实数进行编码 两个参数：符号的概率和它的编码间隔 信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔 对错误敏感，容易形成错误传播,算术编码,Huffman 编码的局限性： Huffman 编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 0.322 位编码，但 Huffman 编码一定会为其分配一位 0 或一位 1 的编码。可以想象，整个信息的 80% 在压缩后都几乎相当于理想长度的 3 倍左右。,算术编码,基本思想：算术编码不是将单个信源符号映射成一个码字，而是把真个信源表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。 采用算术编码每个符号的平均编码长度可以为小数。,算术编码举例（一）,算术编码举例（二）,最后的子区间起始位置 85/256 = 0.01010101 子区间长度 27/256 = 0.00011011 子区间尾 7/16 = 0.0111 取编码区间中的一个值，最后编码为：011,信源分布：,算术编码的具体实现,因为实际只能用有限长的寄存器，这就要求将已编码的高位码字及时输出，但又不能输出过早，以免后续运算还要调整已输出的码位。（请看参考书上给出的算法） 算术编码每次递推都要做乘法，所以效率比较低。二进制算术编码是一种实用的编码算法，用移位代替了乘法，使效率大大提高。 自适应算术编码可以在编码过程中根据符号出现的频繁程度动态的修改分布概率，这样可以避免在编码之前必须精确求出信源概率的难题。,自适应算术编码举例,输入序列为：bcc.,行程编码（RLE）,行程编码（Run-Length Encoding）：它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。 例如：RTTTTTTTTABBCDG被转换为：R#8TABBCDG，其中“”作为转义字符，表明其后所跟的字符表示长度。 行程编码多用于黑白二值图像的压缩中。例如00000000111111111111000001111111被转化为一系列黑串和白串长度的编码：81257。因为串长度并非等概率分布，所以一般要配合以统计编码（Huffman编码）。,无损压缩编码算法,RLE行程编码 一系列重复值有一个单独值和计数值代替 当一行中有连续n（n=63）个相同像素时，第一个字节最高两位为11，低位为n，第二个字节为重复像素值 当一个像素与后续不同时，如果像素高位为11，则仍用两个字节表示，但重复个数为1，即第一个为11000001，第二为像素值 当一个像素与后续不同且高位不为11时，直接存储该像素 压缩比取决于图象的连续性,无损压缩编码算法,词典编码 通用数据流压缩方法 编码前不需要构造码表，它从一个简单的表开始 随着工作进展构建一个更有效的码表 用简单代码替换比较复杂的字串，并用一个转换表记录这些替换关系 转换表通过动态生成，且压缩完毕后，无须记录该转换表,词典编码,词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。 实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。,第一类词典编码,第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。,LZ77算法,LZ77 算法在某种意义上又可以称为“滑动窗口压缩”