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

第3章数据压缩的基本技术第3章数据压缩的基本技术学习目标了解常见的多媒体数据压缩编码技术的核心思想掌握多媒体数据压缩码的必要性、可能性及分类掌握信息熵的概念掌握信息率失真理论理解预测编码和变换编码目的及原理了解子带编码、小波变换编码基本原理掌握熵编码的原理和算法掌握量化对压缩编码产生的重要影响数据压缩的基本技术主要内容3.1概述3.2数据压缩理论依据

3.2.1离散信源的信息熵

3.2.2信源的概率分布与熵的关系

3.2.3信源的相关性与序列熵的关系3.3信息率失真理论

3.3.1通信系统的一般模型

3.3.2信息率—失真函数

3.3.3限失真信源编码定理

3.5预测编码3.6正交变换编码3.7子带编码（了解原理）3.8小波变换编码（了解原理）3.9量化3.9.1——3.9.63.10熵编码3.11压缩编码算法性能的评价3.1概述第一代编码技术：基于香农的信息论，主要利用数据的统计特性来达到压缩目的，此类方法称为“基于像素”的压缩方法。常用方法：信息熵编码，预测编码，变换编码第二代编码技术：考虑人眼的视觉特性，根据人眼识别图像的特征构造图像模型。常用方法：结构编码第三代编码技术3.2数据压缩的理论依据数据压缩原理数据压缩的对象是数据。数据是信息的载体，用来记录和传送信息。真正有用的不是数据本身，而是数据所携带的信息。大的数据量并不代表含有大的信息量。而对于去掉冗余的数据对信息没有本质的影响称为压缩。3.2.1离散信源的熵1、信息量在信息论中，可以说：信息是用不确定的度量来定义的；一个消息的可能性越小，其信息含量越大；消息的可能性越大，则信息含量越小。●信息量的大小和消息有一定的关系。在数学上，消息是其出现概率的单调下降函数。信息量越大，消息的可能性越小，反之亦然。1、信息量

定义：一个随机事件发生某一结果所带来的信息量称为自信息量，简称自信息。表示为概率对数的负值。

单位：比特（bit）2、离散信源的信息熵

离散信源：信源发出的符号取自离散集合，离散信源X可用下式描述：离散信源集合X发出符号集si（i=1,2,…,n）中各符号信息量统计平均（即求其数学期望），从而得到符号集中每个符号的平均信息量：H(X)称为信源X的“熵”，单位bit/符号2、离散信源的信息熵总括起来，信源熵有三种物理含义：信源熵H(X)表示符号出现后，接收到一个符号获得的的平均信息量。信源熵H(X)表示符号出现前，符号集中的符号出现的平均不确定度。信源熵H(X)反映了符号出现的随机性。1233.2.2信源的概率分布与熵的关系最大离散熵定理定理

对于离散无记忆信源，信源中各符号出现的概率相等，，信源具有最大熵。时熵与概率的关系3.2.2信源的概率分布与熵的关系由此可见，数据压缩的方法之一，就是使每个符号所代表的信息量最大，通常通过压缩各信源符号间的冗余度使信源符号呈现等概分布来达到各符号所携带的信息量最大。

这些冗余度既来自于信源本身的相关性，又来自于信源概率分布的不均匀性，只要找到去除相关性或改变概率分布不均匀性的手段和方法，也就找到了信息熵编码的方法。2.2.3信源的相关性与序列熵的关系对于一个离散无记忆信源，如果已知输出随机序列包含两个符号X和Y，其中X取自Y取自因此可用联合熵表示接收到该序列后获得的平均信息量：其中rij为符号si和tj同时发生的联合概率2.2.3信源的相关性与序列熵的关系由于X和Y彼此相互独立，故则前式可改写成

可见离散无记忆信源所产生的符号序列的熵等于各符号熵之和。但是许多离散信源都是有记忆的，其前一个符号直接对后面所出现的符号构成影响，或者说后面出现的符号由前面几个出现的符号决定。进而有：2.2.3信源的相关性与序列熵的关系当图像的信息源的输出序列包含多种相关符号时，也能得到相同的结果。序列熵与其可能达到的最大值之间的差值就是该信息源中所含的冗余度。如果能使信源输出的各符号之间的冗余度越小，那么每个符号所携带的信息量也越大，这样传送相同的信息量所需要的序列长度也越短，即所含的比特数也越少。去除信源各符号间的相关性，其相关性去除越多，则信源特性越趋于无记忆信源的特性。3.3信息率失真理论3.3.1通信系统的一般模型图3-3通信系统模型3.3.1通信系统的一般模型假设离散信源产生离散随机过程{Ur},输出后的输出序列为随机过程{Vr}。u是信源符号U的样，v是V的样，失真的大小可以用一个量来表示，即失真函数d(u,v)，用来衡量信源每发出符号u，而在接收端再现成符号v所引起的失真程度。

由于U，V都是随机变量，所以失真函数d(u,v)也是随机变量，将失真函数的数学期望或统计平均值称为平均失真。长度为N的符号组的平均失真度;3.3.2信息率失真函数无论是无噪信道还是有噪信道：如果R(信息传输率)＜C(信道容量)，总能找到一种编码使在信道上能以任意小的错误概率、任意接近C的传输率来传送信息。如果R＞C，就必须对信源压缩，使其压缩后的信息传输率R小于信道容量C，但同时要保证压缩所引入的失真不超过预先规定的限度。因此，信息压缩问题就是对于给定的信源，在满足平均失真的前提下，使信息率尽可能小。3.3.2信息率失真函数信息率失真函数R(D)限定失真为D的条件下，信源输出的最小信息率。在信源给定后，希望在满足一定失真的情况下，使信源传输给信宿的信息传输率R尽可能地小。从信宿来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最小平均信息量。即在满足保真度准则条件下寻找平均互信息的最小值。3.3.3限失真信源编码定理对于给定的离散平稳无记忆信源，若该信源的信息率失真函数为R（D），选定有限的失真测度，对于任意允许的平均失真度D≥0，和任意小的ε>0,当信息率R>R(D)，只要信源L足够长，一定存在一种编码方式C，使译码后的平均失真度

反之，若R<R(D)，无论采用任何编码方式，必有译码平均失真度大于允许失真度附：3.4冗余及压缩编码分类冗余分类●[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余冗余分类●[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余冗余分类●冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余●冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余●10110001110010110001110001011010101010111100010111111010冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余224色28色●冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余●印度金庙泰姬陵冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余声音频率文字组句色彩渐变主观意识::●3.4.2数据压缩算法分类●

无损压缩编码

——压缩数据还原后，与原始数据一致，无损失。(可逆编码)霍夫曼编码行程编码算术编码……●

有损压缩编码

——压缩后再还原的数据有损失。(不可逆编码)预测编码变换编码统计编码……压缩比：2:1～5:1压缩比：≤1：1003.4.2数据压缩算法分类视频压缩无损压缩有损压缩霍夫曼编码行程编码算术编码预测编码变换编码模型编码基于重要性混合编码DPCMADPCM运动编码DCT变换小波变换子带编码分形变换滤波子采样矢量量化H.261MPEG3.5预测编码●预测编码——有损压缩编码，主要对统计冗余进行压缩。1．预测编码的基本原理预测编码是一种针对统计冗余进行压缩的方法，它主要是减少数据在空间和时间上的相关性，达到对数据的压缩。用原样本值对新样本进行预测，得到新样本的预测值。接着，取新样本的实际值和预测值进行比较，二者相减得到差值，然后对差值进行编码。预测编码可细分为帧内预测和帧外预测。2．预测编码的应用预测编码用于图像的传输和存储。对于连续的多帧图像，新一帧通常保留前一帧的部分内容。首先存储当前内容，如像点、帧或线。然后与下一帧图像进行比较（预测），把不同点存储或传输，而相同点则是数据冗余，予以剔除。3.5.1差分脉冲编码调制DPCM●DPCM（DifferentialPulseCodeModulation）差分脉冲编码调制算法，主要用于对图像的像素进行预测、压缩处理。●工作原理首先比较相邻的像素，如果存在差异，则传送差异之处的差值；若无差异，则不传送差值。由于图像相邻像素通常是类似的，差异很小，因此，传送的差值总是少于图像的像素值，达到了减少数据量的目的。

DPCM方法简单，易于实现，因此得到了广泛的应用。

图3-13中线性预测器的输出为,式中N称为预测器的阶数，ai为固定的加权系数，由于等于各输入样值的线性叠加，该预测器称为线性预测器。综上所述，可以得出以下结论：

①DPCM为空间域预测：空间域相邻像素之间有很强的相关性，利用这些相关性对当前像素进行预测；

②接收端预测器必须与发送端的预测器一致，换句话说就是要保持收发两端具有相同的预测条件。

③预测值是以前面的N个样值为依据做出的，因此要求接收端的预测器也必须使用同样的N个样本，这样才能保证收、发之间的同步关系。

④最佳线性预测编码

如果根据预测误差平方值的统计平均最小准则来获得的线性预测则被称为在最小均方误差意义下的“最佳线性预测器”，即确定（i=1,……,m）使的最小均方误差最小，此时xn相关性最大，所能达到的压缩比也最大.3.5.1差分脉冲编码调制DPCM3.5.2序列图像中运动矢量的估值（帧间预测）●帧间预测是指由前一帧或前n帧图像来预测当前图像。在采用运动补偿技术后，帧间预测的准确度相当高。1、运动矢量估值的必要性活动图像序列中所存在的相关性大致分为以下几种：如果场景为静止画面，当前帧和前一帧的图像内容是完全相同的。对于运动物体而言，如果已知其运动规律，就可以根据其前一帧中的位置来推算出该运动物体它在新一帧中的位置。摄像时镜头做平移、放大和缩小等操作时，图像随时间的变化规律也是可以推算的。由于上述原因，因而发送端不需要发送把每幅图像中的全部像素，而只要将物体的运动信息告知收端，收端则按所接收到的运动信息和前一帧图像信息来恢复当前帧图像。可见要获得高质量的图像，则要求系统能准确地从图像序列中提取相关运动物体的信息。这一过程就称为运动估值。具体地说就是t时刻运动物体的像素值bt可以用在此之前τ时间的像素值bt-τ来表示。这两个像素点之差被称为位移矢量。bt(z)=bt-τ(z-D)3.5.2序列图像中运动矢量的估值（帧间预测）●实际中是比较相距时间τ的两帧图像估计出这段时间间隔内的位移D，通常采用的运动估值方法主要分为两大类，分别称为块匹配法和像素递归法。①像素递归法像素递归法是针对每个像素逐一地根据预测误差来进行位移矢量估算，可见在系统中无需单独传送位置信息。②块匹配法块匹配法的思路与像素递归法的分析思路不同。它是首先将图像划分成若干彼此互不重叠的子块(例如16×16)，并认为子块内所有像素的位移量相同，或者说它是把整个子块视为一个“运动物体”，但在实际图像序列中，一个运动物体的大小不可能恰好完全等于一个子块的大小，因此当一个真实物体运动时，如果仍以子块作为计量单位，那么严格意义上讲，在第k帧和第k+1帧图像中，不可能存在完全相同的子块，因此提出了相似性问题——匹配准则。2、块匹配法●假设在图像序列中，t时刻对应于第k帧图像，t-τ时刻对应于k-1帧图像，对于k帧图像中的一个块，在k-1帧中找与其最相似的块，称为匹配块，并认为该匹配块在k-1帧中的位置，就是k帧块位移前的位置，则经过计算可以得到位移矢量D。●为了节省计算量，k-1帧的匹配搜索只在一定范围内进行，假设τ时间内块的最大水平和垂直位移量为dm个像素，则搜索范围:SR=(M+2dm)x(N+2dm)目前常用的匹配准则：归一化的互相关函数（NCCF）；块亮度均方差值（MSE）；块亮度差的绝对值均值（MAD）；块亮度差的绝对值和（SAD）2、块匹配法SAD越小，相似性越高，当SAD最小时，两个子块达到匹配，计算出位移矢量D（i,j）,表示在k-1帧该子块在移动i行j列后与k帧中的子块相似。块亮度差的绝对值和定义如下：将当前帧划分为MxN的图像子块，其中各像素用bk(m,n)表示，当第k帧中的MxN图像子块与第k-1帧中的MxN图像子块进行比较时，绝对值和为：

dm≤i,j≥dm,(i,j)表示位移矢量，dm表示单方向上水平和垂直位移像素个数。

Step1：以待匹配块中心的同位像素（即前一帧中与之位置相同的像素）为中心，在中心点和与其相距4个像素点的8个邻域点上计算判决函数SAD值，取SAD最小的点作为下一步搜索的中心。Step2：以该点为中心，对与中心相距2个像素点的未搜索过的邻域点进行搜索。Step3：以上一步SAD值最小的点为中心，对距离中心1个像素的未搜索过的领域点进行搜索，最终找到最佳匹配位置。2、块匹配的快速搜索方法●

三步法搜索过程

3.5.3具有运动补偿的帧间预测1、前向预测

帧间预测是指信道中传输的不是当前帧中的像素值x,而传送的是x与其前一帧相应像素之间的差值，因此如果出现如图所示的情况，即有一个运动小球，从第k-1帧到第k帧过程中只做了位置平移。可见这两帧图像的背景相同，这样如果只简单地用k-1帧中对应位置的像素作为k帧相应位置上的像素预测值，那么在图（b）中所示的实线和虚线区域内的预测误差不为零。图像划分：将图像划分为静止部分和运动物体。每个物体可能有不同的位移，但构成同一物体的所有像素的位移相同。通过运动估值得到每个物体的位移矢量。1、前向预测除了对运动补偿后的预测误差进行编码、传送外，还需要传送位移矢量以及如何进行运动物体和静止背景分割等方面的附加信息。利用位移矢量计算经运动补偿后的预测值。●理想的运动补偿预测编码应由以下三个步骤组成。下图为预测器的原理方框图1、前向预测3.5.3具有运动补偿的帧间预测2、后向预测和双向预测

后向预测是指由第k帧来预测第k-1帧，这种预测方法称为后向预测。如果为了进一步提高信道的利用率，则可以采用双向预测，即用前、后两帧来预测中间帧。正交变换编码3.6●变换编码(Transformcoding)

有损压缩编码，用于消除图像序列中的相关性来进行压缩。●工作原理首先对时域（空间域）上的信号进行函数运算，并变换到频域（变换域）上，然后在频域上对变换后的信号进行编码。在频域上，信息是按照频谱的能量和频率分布进行排列的。卡南·洛伊夫变换（KLT）离散傅里叶变换（DFT）离散余弦变换（DTC）与空间域相比，变换域中对图像的描述相对简单。变换域中各变换系数之间的相关性明显下降，能量主要集中在低频部分，因而在进行编码时，可忽略某些能量很小的高频分量，或者在量化时对方差较小的分分量分配较小的比特数，从而实现数据压缩。最佳线性正交变换3.6.1●工作原理

假设X是采样后的N维时间（或空间）信号，选取X的一个正交变换，使Y=TX（3-53）Y为变换向量，T为正交变换矩阵。向量Y是由变换系数yi构成的，Y是X在变换域中的表示。经过变换以后，能量会几种在少数变换系数上，因而把能量很小的系数忽略，达到数据压缩的目的。

K-L变换（最佳线性正交变换）：恢复X所产生的均方误差最小（能量损失最小）。K-L变换无快速算法，很难满足实时性要求。3.6.2离散余弦变换

离散余弦变换（DCT） DCT变换的结果与K-L变换十分接近，而且变换后具有较高的能量集中度。特别是当信源的统计特性偏离一阶平稳马尔可夫过程的规律时，其性能下降并不显著。同时DCT变换又具有多种快速算法，因此在图像压缩编码中得到了广泛的应用。

系数选择

图像信号在空间域中像素的相关性很大。当它们经过DCT变换后，变换系数之间的相关性大大下降，并且信号能量主要集中在低频部分，为了进一步压缩编码速率，因此忽略那些能量很小的高频分量，不予以传输，而只对少数能量集中的方差大的变换系数进行量化编码。由此可见在变换编码中选择哪些变换系数进行量化编码，直接对系统性能构成影响。1、DCT定义如果已知S(k)为信号样值（一维实数信号序列），则一维DCT的正变换和反变换分别定义为：式中，为信号样值；为变换系数，且1、DCT定义由于二维DCT变换可以分解成行方向上的和列方向上的一维DCT变换，因此可以借助一维DCT变换推出MxN子块的二维DCT的正变换和反变换：其中，2、DCT的快速算法基于DFT的DCT算法

令，则k个点的DFT可表示为：最终得到：结论：一个函数的DCT系数，可以由该函数对应的偶函数的DFT系数的实部得到。3.7子带编码●

基本原理

子带编码是一种在频率域中进行数据压缩的算法。其指导思想是首先在发送端将图像信号在频率域分成若干子带，然后分别对这些子带信号进行频带搬移，将其转换成基带信号，再根据奈奎斯特定理对各基带信号进行取样、量化和编码，最后合并成为一个数据流进行传送。●

子带编码的工作原理流程图3.7子带编码●

采用子带编码的优点可以利用人眼（或人耳）对不同频率信号的感知灵敏度不同的特性，在人的听觉或视觉不敏感的频段采用较粗糙的量化，从而达到数据压缩的目的。在子带编码中，各个子带的量化噪声都被束缚在本子带内，这样就可以避免能量较小的频带内的信号被其他频带中的量化噪声所掩盖。3.9量化●3.9.1均匀量化器量化是将具有连续幅度值的输入信号转换到只有有限个幅度值的输出信号的过程。在量化器中从输入信号x到输出信号y的转换过程可以表示为：Xi：判决电平，即量化区间的端点Yi：输出电平，即量化后的输出电平均匀量化器的特性都是对称的，且3.9量化●3.9.1均匀量化器均匀量化器的量化特性包括：中平型中升型具有死区的中平型量化误差：式中，p(x)为量化器输入信号x的概率分布函数，N为量化级数。3.9量化●3.9.1均匀量化器均匀量化器的量化特性包括：中平型中升型具有死区的中平型量化误差：式中，p(x)为量化器输入信号x的概率分布函数，N为量化级数。3.9.2最小均方误差量化器●最小均方量化器——劳依德-麦可思量化器。如果输入信号的统计特性已知，则可通过使均方量化误差达到最小来设计量化级数为N的量化器的输出电平和判决电平。●

必要条件

对xi和yi的偏导数均为0。●结论判决电平应取在两相邻输出电平的中间；输出电平应取在两判决电平间隔对应的概率密度函数的重心；3.9.3-3.9.5其它量化器●

最小熵量化器N足够大时，采用均匀量化和熵编码相结合实现联合优化。●自适应量化器根据信号特性的动态变化自动切换到相应的量化器。●

预测误差量化预测误差引入的失真：颗粒噪声边缘忙乱斜率过载DPCM编码中时常用非均匀（自适应）量化器●DCT系数量化DCT变换引入的失真：颗粒噪声分辨率下降方块效应DCT编码中时常用自适应量化器3.10熵编码熵编码——无损压缩编码。根据消息出现的概率分布特性，在消息和码字之间确定严格的对应关系，以便准确无误地恢复数据。一般而言，图像中某些数据出现概率比较高，而另一些出现概率较低。对出现概率高的数据分配短码，对出现概率低的数据分配长码。此种方式不舍弃数据冗余，只改变编码分配的长度，因此总数据流量降低。3.10熵编码熵编码——

编码方式分为定长和变长两种方式。其中变长编码可以得到更好的压缩结果。●3.10.1熵编码的基本概念若信源符号集A中的符号个数为M，编码以后能达到的最大熵值为，若原信源的熵为H(X),编码后的平均码长为，则编码效率：3.10.2霍夫曼编码●

赫夫曼编码——无损编码。●

编码原理——出现频率高的数据编码长度短，反之亦然。1、排序：按符号出现的概率从大到小进行排列。2、赋值：对最后的两个符号进行赋值，概率大的赋“1”，概率小的赋“0”（反之也成立）。3、合并：将上述最后的两个符号出现概率相加和成一个概率。4、重新排序：将合成后的概率与其它符号概率一起进行重新排序（从大到小）。然后重复步骤2的内容，直至最后只剩下两个概率为止。5、码字分配：从最后一步开始反向进行码字分配，对最后两个概率中较大的赋“1”。对较小的赋“0”（与第二过程中的规定相同）。从而形成一个码字。如下图中虚线所示的方向。●

编码特点①赫夫曼编码所构造的码并不是惟一的，但其编码效率是惟一的。②对不同信源其编码效率是不同的。③存在误码传播问题。3.10.2赫夫曼编码

例假设某符号集X中包含6个符号：S1,S2,┈S6，各自出现的概率为X=

试求其赫夫曼编码及其编码效率。

解：1、赫夫曼编码

在图中给出了赫夫曼编码过程，其中设两个符号中较大的为”1”，较小的为”0”。编码结果如表所示。3.10.2霍夫曼编码3.10.2霍夫曼编码2、编码效率根据式可求出信源熵：=

）

=2.56可求出平均码长