第三章 数据压缩的基本技术

1、第3章 数据压缩的基本技术 3.1 概述概述 3.2数据压缩的理论依据数据压缩的理论依据3.5预测编码预测编码3.6正交变换编码正交变换编码3.9量化量化3.10熵编码熵编码 3.1 概述概述 数据压缩处理一般由两个过程组成数据压缩处理一般由两个过程组成: 一是编码过程一是编码过程, 即对原始数据进行编码压缩即对原始数据进行编码压缩, 以便存储和传输以便存储和传输; 二是解二是解码过程码过程, 即对压缩的数据进行解压即对压缩的数据进行解压, 恢复成可用的数据。恢复成可用的数据。根据解压后数据的保真度根据解压后数据的保真度, 数据压缩技术可分为数据压缩技术可分为无损压无损压缩编码缩编码和和有损压

2、缩编码有损压缩编码两大类两大类。无损压缩编码无损压缩编码是指是指解码后的数据与原始数据完全相同解码后的数据与原始数据完全相同, 无任何偏差。这种无任何偏差。这种编码通常基于信息熵原理编码通常基于信息熵原理, 常用的编码有哈夫曼编码、常用的编码有哈夫曼编码、 算术编码、算术编码、 行程编码等。行程编码等。它的压缩比通常比较低它的压缩比通常比较低, 一般一般在在2 15 1。主要用于要求数据无损压缩存储。主要用于要求数据无损压缩存储和传和传输的场合输的场合, 如传真机、文本文件传输等。如传真机、文本文件传输等。 有损压缩编码有损压缩编码是指解码后的数据与原始数据相比是指解码后的数据与原始数据相比有

3、一定的偏差有一定的偏差, 但仍可保持一定的视听质量和效果。但仍可保持一定的视听质量和效果。 它主要是在保持一定保真度下对数据进行压缩它主要是在保持一定保真度下对数据进行压缩, 其压其压缩比可达缩比可达100 1。 压缩比愈高压缩比愈高, 其解压缩后的视、其解压缩后的视、 音音频质量就愈低。编码方法有：频质量就愈低。编码方法有：基于线性预测原理的基于线性预测原理的预预测编码测编码、基于分量量化的、基于分量量化的量化编码量化编码、基于正交变换原、基于正交变换原理的理的正交变换编码正交变换编码、基于分层处理的、基于分层处理的分层编码分层编码以及基以及基于频带分割原理的于频带分割原理的子带编码子带编码

4、等等。主要用于。主要用于对音频和视对音频和视频数据的压缩。频数据的压缩。 多媒体信息编码技术主要侧重于有损压缩编码的研多媒体信息编码技术主要侧重于有损压缩编码的研究。究。 经过多年的研究与开发经过多年的研究与开发, 已经出台了一系列有关的已经出台了一系列有关的国际标准。其中国际标准。其中, 最著名的是国际标准组织（最著名的是国际标准组织（ISO）制）制定的定的JPEG和和MPEG。JPEG是静止图像的压缩标准是静止图像的压缩标准, 其其压缩比可达压缩比可达40 1。 MPEG（MPEG-1、 MPEG-2及及MPEG-4）是动态图像的压缩标准）是动态图像的压缩标准, 采用采用MPEG-2标准标

5、准对对NTSC质量视频进行压缩后质量视频进行压缩后, 网络带宽需求可降低到网络带宽需求可降低到3.36 Mb/s。 其它的标准还有国际电信联合会（其它的标准还有国际电信联合会（ITU）制定的用于可视电话、制定的用于可视电话、 会议电视的会议电视的H.261和和H.263; 用用于音频的于音频的G.711、 G.721、 G.728等。等。 3.2数据压缩的理论依据数据压缩的理论依据离散信源X：信息源所产生的符号取自某一离散集合。每个符号的信息量I：指符号si出现的概率，I是随机变量；最大离散熵定理最大离散熵定理熵（H）：各个符号信息量 I 的统计平均，是从统计平均的角度反映信源的一个总体特征符

6、号出现之前，熵表示符号出现的平均不肯定性；符号出现之后，熵表示接收一个符号所得到的平均信息量；各符号出现的概率分布不同，信源的熵也不同；当信源符号出现的概率相等时，信源具有最大熵，每个符号携带的平均信息量最大。最大离散熵定理，在熵编码时，可以确保每个符号携带最大的信息量。3.2.2信源的相关性与序列熵的关系信源的相关性与序列熵的关系平稳序列平稳序列：序列中的各符号有相同的概率分布；：序列中的各符号有相同的概率分布；无记忆序列无记忆序列：序列中的各符号间为统计独立；：序列中的各符号间为统计独立；联合熵联合熵：又称：又称序列熵序列熵，随机序列中包含两个符号，随机序列中包含两个符号X、Y， X、Y取

7、自各自的离散信源，则新序列的平均信息量为取自各自的离散信源，则新序列的平均信息量为独立熵独立熵：离散信源：离散信源X、Y如果统计独立，则如果统计独立，则H（X）、）、H（Y）称为独立熵。）称为独立熵。此时有：此时有：给定给定X的条件下，的条件下，Y所具有的熵，称为所具有的熵，称为条件熵条件熵联合熵与条件熵的关系：联合熵与条件熵的关系：互信息互信息：无条件熵和条件熵之差，反映两个事件之间的：无条件熵和条件熵之差，反映两个事件之间的相关性。相关性。互信息越小，两个事件的相关性越小，当统计独立时，互信息越小，两个事件的相关性越小，当统计独立时，联合熵为独立熵之和，联合熵达到最大值。联合熵为独立熵之和

8、，联合熵达到最大值。应用意义应用意义：数据压缩的一个基本途径就是去除信源符号之间的数据压缩的一个基本途径就是去除信源符号之间的相关性，尽可能使得信源符号统计独立，使序列成为相关性，尽可能使得信源符号统计独立，使序列成为无记忆序列。无记忆序列。无记忆序列有最大的联合熵，保证每个符号所独立携带无记忆序列有最大的联合熵，保证每个符号所独立携带的信息量最大，传送相同的信息量所需要的序列长度越短，的信息量最大，传送相同的信息量所需要的序列长度越短，从而达到数据压缩的目的。从而达到数据压缩的目的。最大离散熵定理，告诉我们，在等概率情况下，离散平稳最大离散熵定理，告诉我们，在等概率情况下，离散平稳无记忆信源

9、的单个符号有最大熵，数据压缩的另一途径是无记忆信源的单个符号有最大熵，数据压缩的另一途径是改变离散信源的概率分布，比如：霍夫曼编码；改变离散信源的概率分布，比如：霍夫曼编码；几种常用的压缩编码方法几种常用的压缩编码方法（差分）预测编码（离散余弦）正交变换编码量化编码熵编码 3.5.1 差分脉冲编码调制差分脉冲编码调制 图图 2.2 DPCM编码、解码器原理框图编码、解码器原理框图差分信息差分信息（通过预测和差分，将（通过预测和差分，将x(n)转化成差分信转化成差分信息息e(n),降低了信息冗余，实现压缩）降低了信息冗余，实现压缩）)( nx)(nx)( )()(nxnxne线性预测器：线性预测

10、器：)( nx3.5预测编码预测编码信息发送端的预测与差分的示意图信息发送端的预测与差分的示意图差分值差分值原信息值原信息值预测值预测值其中，e(n)x(n)，实现数据幅值方面的压缩；信道只传送：差分值与有限的几个初始值；有限的几个有限的几个初始值初始值信息接收端的信息重建的示意图信息接收端的信息重建的示意图接收到的接收到的差分值差分值重建的信息值重建的信息值重建的预测值重建的预测值接收到的接收到的初始值初始值有限的几个初始值，用于重建预测值；3.5.2 序列图像中运动矢量的估值序列图像中运动矢量的估值 运动补偿预测编码，是一种主要用于动态图像的压缩的预测编码。动态图像是由一系列视频帧组成,

11、帧与帧之间可能存在着瞬时冗余, 这种瞬时冗余主要是由静态背景前的运动物体或摄像机的移动引起的。运动补偿预测编码主要通过帧间编码来压缩时间冗余信息。 其基本原理如下: 在视频帧序列中设置参考帧（I帧）, 且第1帧总是参考帧。 对于当前的编码帧, 首先在该帧的前帧和/或后帧（参照帧）中寻找与该帧的一个图像块相匹配的图像块（匹配块），按照式3-47、3-48、3-49，进行块匹配计算。 帧内编码帧间预测编码 如果找到这样的匹配块, 则进行下列计算: 当前块的块亮度值与参照帧中对应块（称参照块）的块亮度值之间的差值信号; （背景差）当前块相对于参照块在x和y两个方向上的运动向量值, 表示该块在x和y方

12、向上的平移。 通过定义一个搜索域来限制x和y方向上的搜索范围, 以降低运动信息的开销; （运动估值）用差值信号和运动向量值来表示参照块与所预测块之间的误差, 称为预测误差。 这时, 只需对当前块的预测误差（运动向量值、差值信号）进行编码, 不必对当前块的图像进行编码, 以压缩时间冗余信息。 如果找不到这样的匹配块, 则必须进行帧内编码, 即对当前块的图像进行编码。 运动补偿预测编码可分成下列三种方式: 单向运动补偿预测: 只使用前参照帧或后参照帧之一进行预测。 双向运动补偿预测: 使用前、 后两个帧作为参照帧来计算各块的运动向量, 最后只选择具有最小匹配误差的参照帧相关的运动向量值。 插值运动

13、补偿预测: 使用前参照帧和后参照帧两者预测值的平均值。这时, 必须分别存储和传输这两个运动向量。 3.6.2离散余弦变换编码离散余弦变换编码 1、正交变换、正交变换彼此之间线性无关为正交基向量,i如：傅氏变换的基向量，就是一个正交（酉）变换基；正交变换：正交变换：重构：重构： 属于正交变换编码，选择不同的正交基向量，可以得到不同的正交变换。变换编码主要有离散傅立叶变换(DFT)编码、 离散余弦变换(DCT)编码等。其中, DCT编码方法被普遍使用, 在JPEG、 MPEG和H.261等标准中都采用了DCT编码。由于声音信号只有一个时间维, 因此音频信号压缩采用一维DCT编码, 而图像压缩必须考

14、虑水平和垂直两个方向, 因此图像压缩则采用二维DCT编码。2、DCT编码编码 DCT编码方法是对一个88图像块灰度样本数据流进行压缩, 而彩色图像压缩可看成是压缩图像的多个分量。在编码器中, 首先将源图像88样本数据块（像素块）的取值范围由0, 2p-1（无符号）转换成-2p-1, 2p-1-1（有符号）, 其中p为样本定义的精度。 然后对88样本数据块进行正向离散余弦变换（FDCT）。在解码器中, 利用逆向离散余弦变换（IDCT）重建88样本数据块, 恢复图像。 FDCT和IDCT的数学表达式如(1)式和(2)式所示: NvkNujvuSvCuCNkjsNvkNujkjsvCuCNuSNuN

15、vNjNk2) 12(cos2) 12(cos),()()(2),(2) 12(cos2) 12(cos),()()(2),(10101010式中： 121)()(vCuCu,v=0其它 二维二维DCT变换变换系数代表直流分量；，这时对应的时，两个余弦项均为零注意：对于DCT0 vu基函数基函数DCT系数系数直流成份 源图像88样本数据块实质上是64点离散信号（空间范围x和y的函数）, FDCT将其变换成64个正交基信号, FDCT的输出是64个DCT系数（即：基信号振幅）。由于图像帧上点与点之间的样本值变化比较缓慢, 大多数信号集中在低频区。 可以删去DCT系数中的高频分量，仅用低频分量子集

16、，逆DCT变换来重构原图像，不会引起明显误差，从而实现数据压缩。二维DCT变换将基系数绝对值10的分量置零 （DCT截断量化）二维逆DCT变换 重构图像（数据压缩程度较小） 图像清晰（截断量化误差较小）原图像对对DCT数据的截断量化示意图数据的截断量化示意图1二维DCT变换将基系数绝对值(10101101) 2十进制数转换成二进制数十进制数转换成二进制数低位数码低位数码高位数码高位数码对于离散无记忆信源，只要各符号出现的概率不相等，对于离散无记忆信源，只要各符号出现的概率不相等，该信源就还有冗余存在，还可以进一步压缩。该信源就还有冗余存在，还可以进一步压缩。霍夫曼霍夫曼(Huffman)编码是

17、一种无损压缩编码方法。编码是一种无损压缩编码方法。它是它是一种概率平衡的思想。一种概率平衡的思想。按信源符号出现的概率大小进行按信源符号出现的概率大小进行排序。排序。出现概率大的符号分配短码出现概率大的符号分配短码, 反之，反之，出现概率小出现概率小的符号的符号分配长码。分配长码。这样可以确保编码序列中的每个符号这样可以确保编码序列中的每个符号等概率出现，从而满足等概率出现，从而满足最大离散熵定理最大离散熵定理。1.霍夫曼编码霍夫曼编码3.10熵编码熵编码霍夫曼(Huffman)熵编码的一个应用实例平均码长平均码长越短，数据量越小，数据率越低；例：例：对于一个对于一个4电平量化（电平量化（4个符号）的信源个符号）的信源则，信源熵H=1.75比特/符号经计算可知，编码方式I：平均码长为2.0比特/符号；编码方式II：平均码长为1.75比特/符号，等于信源熵，达到最大；在分配代码过程中, 需要建立一个n阶二叉树, 如下: 对信源符号按其出现的概率进行递减排序; 将两个最小的概率相加, 其和作为合成事件的概率; 重复和, 直到概率之和达到1为止; 每次合并消息时, 将被合并的消息赋予1和0或者0和1; 寻找从每