第四章 预测编码和变换编码

第四章预测编码和变换编码

4.1预测编码

4.2变换编码4.1预测编码预测编码是数据压缩理论的一个重要分支。根据离散信号之间存在一定相关性的特点，利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差（预测误差）进行编码。如果预测比较准确，那么误差信号就会很小，就可以用较少的码位进行编码，以达到数据压缩的目的。第n个符号Xn的熵满足：n越大考虑更多元素之间的依赖关系时，熵值进一步降低，得到的熵越接近于实际信源所含的实际熵（极限熵）。所以参与预测的符号越多，预测就越准确，该信源的不确定性就越小，数码率就可以降低。原理利用以往的样本值对新样本值进行预测，将新样本值的实际值与其预测值相减，得到误差值，对该误差值进行编码，传送此编码即可。理论上数据源可以准确地用一个数学模型表示，使其输出数据总是与模型的输出一致，因此可以准确地预测数据，但是实际上预测器不可能找到如此完美的数学模型；预测本身不会造成失真。误差值的編码可以采用无失真压縮法或失真压縮法。分类无损预测编码有损预测编码DPCM：差分脉冲调制预测，DifferentialPulseCodeModulation：差值脉冲编码调制是利用信号的相关性找出可以反映信号变化特征的一个差值量进行编码。ADPCM：自适应差分脉冲调制预测，AdaptiveDifferentialPulseCodeModulation4.1.1无损预测编码原理整数舍入预测器译码器预测器-＋编码器发送端接收端Xk^Xkekek^XkXk图4-1整数舍入当输入信号序列X(k＝1，2、…)逐个进入编码器时，预测器根据若干个过去的输入产生当前输入的预测(估计)值。将预测器的输出舍入成最接近的整数，并用来计算预测误差ek

ek

=

xk-这个误差可用符号编码器借助变长码进行编码以产生压缩信号数据流的下—个元素。在解码器方根据接收到的变长码字重建预测误差，并执行以下操作以得到解码信号

xk

=ek+借助预测器将原来对原始信号的编码转换成对预测误差的编码。在预测比较准确时，预测误差的动态范围会远小于原始信号序列的动态范围，所以对顶测误差的编码所需的比持数会大大减少，这是预测编码获得数据压缩结果的原因。

在多数情况下，可通过将M个先前的值进行线性组合以得到预测值^Xk^Xk^Xk预测方程式:K>N表示x1,x2,…,xN

的时序在xk

之前。线性预测是指预测方程式的右方是各个xi的线性函数：

如果ai

(k)是常数，则为时不变线性预测。最简单的预测方程：最佳线性预测使误差函数达到最小值的预测方程式叫做最佳线性预测。求最佳线性预测的各个参数ai，列方程组：代入得到联立方程组，解方程定出ai。量化器预测器译码器预测器－＋＋编码器发送端接收端Xkek^XkXk’ek’ek’^XkXk’4.1.2有损预测编码原理（DPCM）^Xkxk’=ek’+图4-2在无损预测编码系统的基础上加一个量化器构成压缩过程发送端预测器带有存储器，把tn时刻以前的采样值x1,x2,x3,…,xk-1存储起来并据此对xk进行预测，得到预测值ek为xn与的差值，ek’为ek经量化器量化的值xk’是接收端的输出信号误差ek为ek=xk-xk’=xk-(+ek’)=(xk-)-ek’=ek

-ek’实际上就是发送端的量化器对误差ek’量化的误差对

ek’的量化越粗糙，压缩比越高，失真越大.^Xk^Xk^Xk^Xk有损预测编码（DPCM）为接纳量化步骤，需要改变图4-1中的无损编码器以使编码器和解码器所产生的预测能相等。为此在图4-2中将有损编码器的预测器放在1个反馈环中。这个环的输入是过去预测和与其对应的量化误差的函数

这样一个闭环结构能防止在解码器的输出端产生误差。这里解码器的输出也由上式给出。^Xkxk’=ek’+示例一：德尔塔调制(DM或ΔM)

最简单的有损预测编码方法是德尔塔（或称增量）调制(DM或ΔM)方法，早期在数字电话中采用，是一种最简单的差值脉冲编码。其预测器和量化器分别定义为其中a是预测系数(一般小于等于1)，c是1个正的常数。因为量化器的输出可用单个位符表示(输出只有2个值)，所以编码器中的符号编码器可以只用长度固定为1比特的码。由DM方法得到的码率是1比特／像素。示例：取a＝1和c＝5。设输入序列为12，16，12，14，20、32，46，52，50，51，50。编码开始时先将第1个输入像素直接传给编码器。DM编码失真示例上例的输入和输出中显示出2种有损预测编码典型的失真现象。其一，当c远大于输入中的最小变化时，如在n＝0到n＝3的相对平滑区间，DM编码会产生颗粒噪声，即误差正负波动。其二，当c远小于输入中的最大变化时，如在n=5到n=9的相对陡峭区间，DM编码会产生斜率过载，有较大的误差。对大多数图像来说，上述2种情况分别会导致图像中目标边缘发生模糊和整个图像产生纹状表面。输入数据不是平稳的随机过程自适应差分脉冲调制（ADPCM）预测定期重新调整预测器的预测参数，使预测器随输入数据的变化而变化自适应改变量化器的量化阶数，用小量化阶量化小差值，大量化阶量化大差值分为线性自适应预测与非线性自适应预测两种4.1.3自适应差分脉冲调制（ADPCM）预测

自适应量化在一定量化级数下减少量化误差或在同样的误差条件下压缩数据，根据信号分布不均匀的特点，希望系统具有随输入信号的变化区间足以保持输入量化器的信号基本均匀的能力，这种能力叫自适应量化。示例二：

ADPCM采用与DPCM相同的预测器，但对误差量化时采用自适应改变量化器的量化阶数的压缩结果自适应预测预测参数的最佳化依赖信源的特征，要得到最佳预测参数显然是一件繁琐的工作。而采用固定的预测参数往往又得不到较好的性能。为了能使性能较佳，又不致于有太大的工作量，可以采用自适应预测。为了减少计算工作量，预测参数仍采用固定的，但此时有多组预测参数可供选择，这些预测参数根据常见的信源特征求得。编码时具体采用哪组预测参数需根据特征来自适应地确定。为了自适应地选择最佳参数，通常将信源数据分区间编码，编码时自动地选择一组预测参数，使该实际值与预测值的均方误差最小。随着编码区间的不同，预测参数自适应地变化，以达到准最佳预测。示例三：4个不同的预测器如下所示其中第4个预测器是自适应预测器，它通过计算图像的局部方向性来选择合适的预测值以达到保持图像边缘的目的。4.1.4图像信号的预测编码一幅数字图像可以看成一个空间点阵，图像信号不仅在水平方向是相关的，在垂直方向也是相关的。根据已知样值与待预测样值间的位置关系，可以分为：（1）一维预测（行内预测）：利用同一行上相邻的样值进行预测。（2）二维预测（帧内预测）：利用同一行和前面几行的数据进行预测。一、静止图像的二维预测编码这种压缩算法被应用到JPEG标准的无损压缩模式之中，中等复杂程度的图像压缩比可达到2:1。LosslessJPEGDPCM/HuffmanCodignDPCM/ArithmeticCodingcabx选择值预测值0非预测1a2b3c4a+b-c5a+(b-c)/26b+(a-c)/27(a+b)/2d三邻域预测法ResultsDPCMat1.0bppResultsDPCMat2.0bppResultsDPCMat3.0bpp二、活动图像的帧间预测编码视频信号的冗余度主要体现在空间相关性（帧内）、时间相关性（帧间）和色度空间表示上的相关性。对于每秒25帧（30）的电视信号，其相继帧之间存在极强的相关性。所以在活动图像序列中可以利用前面的帧来预测后面的帧，以实现数据压缩。帧间预测编码技术被广泛应用到H.261、H.263、MPEG-1和MPEG-2等视频压缩标准之中。采用预测编码的方法消除序列图像在时间上的相关性，即不直接传送当前帧的像素值，而是传送x和其前一帧或后一帧的对应像素x‘

之间的差值,这称为帧间预测。当图像中存在着运动物体时，简单的预测不能收到好的效果，例如当前帧与前一帧的背景完全一样，只是小球平移了一个位置，如果简单地以第k-1帧像素值作为k帧的预测值，则在实线和虚线所示的圆内的预测误差都不为零。如果已经知道了小球运动的方向和速度，可以从小球在k-1帧的位置推算出它在k帧中的位置来，而背景图像（不考虑被遮挡的部分）仍以前一帧的背景代替，将这种考虑了小球位移的k-1帧图像作为k帧的预测值，就比简单的预测准确得多，从而可以达到更高的数据压缩比。这种预测方法称为具有运动补偿的帧间预测。

三、具有运动补偿的帧间预测活动图像序列中的一个画面可以大致划分为3个区域：背景区：相邻两个画面的背景区基本相同。运动物体区：可以视为由前一个画面的某一区域的像素平移而成。（位移矢量）暴露区：指物体运动后而显露出来的曾被遮盖的背景区域。运动补偿预测就是将前一个画面的背景区＋平移后的运动物体区作为后一个画面的预测值。运动补偿帧间预测编码运动补偿帧间预测从原理上包括如下几个基本步骤：（1）图像分割：把图像划分为静止的背景和若干运动的物体，各个物体可能有不同的位移，但构成同一物体的所有像素的位移相同。（2）运动矢量估值：考察前后两个画面，利用运动估值算法得到每个物体的位移矢量。（3）运动补偿：用运动矢量补偿物体的运动效果再进行预测。（4）编码：除了对实测值与预测值之间的差值进行编码传送外，还要传送位移矢量以及区域分割信息。运动补偿帧间预测编码编码器运动补偿图像输入运动矢量输出-译码器帧缓存运动估值预测误差输出4.2变换编码利用预测编码可以去除图象数据的时间和空间的冗余。它的优点是直观、简捷、易于实现，特别是用于硬件实现。但压缩能力有限，DPCM一般只能压缩到2~4bit/像素。变换编码是进行一种函数变换，映射变换从信号域变换到另一个信号域。预测编码希望通过对信源建模来尽可能的预测源数据；而变换编码则考虑将原始数据变换到另一个表示空间，使数据在新的空间上尽可能相互独立，而能量更集中。原理为达到目的，可以通过不同的路径——殊途同归例1：数学计算机中，经常利用某些数学函数略加转换可以找出一条计算的捷径。 乘法：1000000X100000＝100000000000

运算时，数据很大，可以变成对数进行加法1000000X100000＝100000000000取对数lg106取对数lg105取指数10116＋5＝11算法变换例2：X(t)为模拟输入信号，取样后成为样本序列{Xk}

现在以n=8为例，即对（x0,…,x7)进行正交变换，可得到YL

的8个输出值（y0,…,y8).在该坐标系中，信息集中在y0,y1,y2三个值上。例3:对缓变信号，相邻采样值x1,x2各用3bit编码，有64种合成可能；x1,x2同时出现相同等级的可能性比较高，如绿圈所示（相关圈）；对数据进行正交变换（旋转45o）后，去掉了相关性，X1’,X2’合成种类减少，达到了压缩的效果0X1X2变换去掉相关性示意图X1’X2’定义：变换域编码就是将时间域信号(如语声信号)或空间域信号(如图像信号)，变换到另外一些正交矢量空间(即变换域)，产生一批变换系数，对系数进行编码处理原理：信号在时域或空域时信息冗余度大，变换后参数之间相关性很小或互不相关，数据量减少。利用人的视觉特性，对高频细节不敏感，可以滤除高频系数，保留低频系数，达到数据压缩的效果。4.2.1变换编码原理4.2.2变换编码的系统构成原始信号正变换量化编码存储和传输解码反变换重建信号编码信号4.2.3正交变换的讨论定义相邻的n个信号样本看作在n维线性空间中的一个列向量例4：Walsh-Hadamard变换能量守恒：42+62+52+22=

8.52+1.52+（-2.5）2+0.52=81由Y可逆变换重建X能量集中：可将Y量化为[9，1，-3，0]后重建为[3.56.55.52.5]0.50.5

0.5

0.50.50.5-0.5-0.50.5-0.5-0.50.50.5-0.50.5-0.5X=[4652]A=Y=AX=[8.51.5-2.50.5]例5:二维离散余弦变换DCT变换DCT逆变换正交变换与编码相关的性质熵保持：极限熵的保持通过正交变换本身并不丢失信息，因此，可以用传送变换系数来达到传输信息的目的。能量保持：变换域中的信号能量与原来空间域中的信号能量相等。其对于数据压缩的指导意义在于：只有当空间域信号能量全部转换到某个变换域后，有限个空间取样值才能完全由有限个变换系数对于基矢量的加权来恢复。去(解)相关：正交变换可使强相关的空间样值变为不相关或弱相关的变换系数，使得存在于相关性之中的数据冗余度得以去除。在一定条件下甚至可以使这些系数相互独立，从而得到无记忆信源。如果能得到无记忆信源，正交变换具有保熵性，就得到了通常无法得到的原始数据块(如图像)的极限熵。这预示着可望达到更高的压缩倍数。能量重新分配与集中：这是正交变换法最重要的优点，也是利用它能实现数据压缩的物理本质。此性质DPCM并不具备。变换域系数(除直流系数外)与DPCM法相同，零和小幅值系数占绝大多数．但DPCM的幅度分布在全空间均可能相同，对每个残差均需编码；而变换法则按统计规律集中分布在一定的区域上，这就使我们可利用先验知识在质量允许的情况下，舍弃一些能量较小者(或者只给其分配较少的位数)，从而使数据率有较大的压缩。关键：如何找A矩阵。4.2.4图像的正交变换编码1.变换矩阵的选择从实用意义上考虑，必须从去相关与能量集中性能以及实现的难易程度（运算量）来综合选择。只要在性能满足要求的条件下，尽量选择简单的变换。按正交变换运算量从大到小排序为：K-L变换→Fourier变换→

DCT→

斜变换→

Walsh-Hadamard

变换按正交变换的能量集中性能从差到好排序为：Walsh-Hadamard

变换→斜变换→

DCT→Fourier变换→

K-L变换能量集中与去相关性能当然以K-L变换为最佳。但由于对任意实际的数据集合，很难得到K-L变换的结果，因此常以K-L变换性能作比较标准。2变换域系数的选择1）区域编码只对规定区域内的变换系数进行量化编码，略去区域外的系数。编码区域的形状和大小取决于所需压缩比的大小、所选用的变换方法、变换块的大小等。关键在于选出能量相对集中的区域，以便保留大部分图像能量，使得恢复图像的质量劣化不显著。变换域信号的能量大部分集中在矩阵的左上部，且左上角元素集中的能量最大。这个现象反映出变换域信号能量集中于低频部分。这就是只对变换域左上部区域变换系数进行编码传输，对右下角不进行编码传输的一种编码