预测误差原始数据预测值编码器码流预测器预测误差恢复数据解码器码流预测器图3.2 基本预测编码/解码系统
例如有一组数200，201，203，202，204，204，假设我们用前一个数据来预测后一个数据，预测编码的工作过程示于图3.3。预测误差，即原始数据真值与预测值之差分别为1，2，-1，2，0，...。
原始数据200201203202204204 ...预测值初值200201203202204 ...预测误差恢复误差 1 . . 1 2 . . 2-1 . .-1 2 . . 2 0 ... . . 0 ...恢复数据200201203202204204 ...图3.3 预测编码原理示意图
如果采用二进制对原始数据编码，每个数据都需8比特。预测编码不是对原始数据编码，而是对预测误差编码。由于预测误差动态范围大大缩小，因此只用3比特就可以了，这就减少了码长，达到了压缩的目的。
预测编码系统性能的好坏，预测器的设计是关键，预测器设计得越好，预测误差就越小，甚至会有很多0值出现，从而有利于数据的有效压缩，目前常用的预测器是具有图3.4所示结构的线性预测器。这种预测器通过计算n时刻以前若干时刻
?(n)，其公式为 的线性加权和来预测n时刻的值x?(n)? x
?ak?1mkx(n?k) （3-10）
306
预测器x(n)预测值am......a2a1 X(n-k)X(n-2)X(n-1)图3.4 线性预测器的结构
其中，ak为样本x(n?k)的预测系数，m为预测阶数，即用x(n)前m个样本进行预测。
n时刻的样本真值与预测值的差，称为n时刻的预测误差d(n)，为
?(n) d(n)?x(n)?x ?x(n)??ax(n?k) （3-11）
kk?1m为了获得好的预测效果，要求预测器是最佳预测器，那么，最佳线性预测就是选取ak使预测误差d(n)的均方差最小。假设x(n)是广义平稳的，且均值为零，则预测误差的方差为
令
m??d ??2E{x(n?i)[x(n)??akx(n?k)]2}?0 （3-13）
?aik?12?d?E{d(n)}?E{[x(n)??akx(n?k)]2} （3-12）
22k?1m. , i?1,2,..m可得
R(i)?. , （3-14） ?aR(k?i)?0 i?1,2,..mkk?1m其中，R(i)为样本数据x(n)的自相关函数。
假设x(n)是各态历经的，且数据样本数N充分大，则x(n)的自相关函数可用下式计算
307
1 R(i)?R(?i)?N将方程写成矩阵形式为
?x(n)x(n?i) （3-15）
n?1N?R(0)?R(1) ?????R(m?1)R(1)R(0)?R(m?2)?R(m?1)??a1??R(m?2)??a2???????????????R(0)??am??R(1)??R(2)??? （3-16） ?????R(m)??解上面方程，便可求出最佳线性预测器的系数ak。
对于二维图象数据f(m,n)，其线性预测值为
?(m,n)? f预测差值为
??a(k,l)?zk,lf(m?k,n?l) （3-17）
?(m,n) d(m,n)?f(m,n)?f ?f(m,n)???a(k,l)?zk,lf(m?k,n?l) （3-18）
其中z为对象素f(m,n)进行预测的邻近区域。例如图3.5中对f0点预测时，可供考虑的邻域次序为f1f2f3...f11。
f11f7f5f8f3f1f6f2f0f9f4f12f10图3.5 预测区域示意图
假设f(m,n)是二维平稳随机过程，均值为零，d(m,n)的方差为 令
?d2?E{d2(m,n)} （3-19）
2??d?0， 可得
?ai,j R(i,j)???a(k,l)?zk,l R(k?i,l?j)?0， (i,j)?z （3-20）
由方程组3-20便可求出二维线性最佳预测器的各个系数ak,l。
上述最佳线性预测是假定原始图象为平稳随机过程，实际图象虽然在总体上一
般可看作是平稳的，但在局部上一般是不平稳的。另外，非线性预测器可能比线性
308
预测器更接近实际情况，因此，采用非线性自适应预测可获得最佳预测效果。
3.4 变换编码
上述编码方法都是在空间域直接对图象和声音数据进行编码。本节介绍的变换编码不是直接对原始数据编码，而是首先将原始数据进行某种变换，得到一组变换系数，然后对这些系数进行量化、编码、传输，理论上和实践上都证明变换编码是一种非常有效的编码方法。
为了达到数据压缩的目的，希望变换后的变换系数之间冗余度减小，例如变换系数中只有少数系数具有较大数值，而大部分系数具有较小数值，那么我们可舍弃数值小的系数，只对较大数值的系数进行编码，显然这就可以达到压缩的目的。 理论分析证明，正交变换可以满足上述要求。正交变换方法很多，目前，人们熟知的有傅里叶变换、哈德玛变换、余弦变换和K-L变换等。其中K-L变换后的各系数相关性小，能量集中，舍弃低值系数所造成的误差最小，但是它的变换矩阵是由原始图象矩阵的协方差矩阵的特征向量组成，随着待编码的原始图象的种类变化，其变换矩阵要随之改变，所以 K-L变换存在计算复杂、速度慢等缺点。由于离散余弦变换与 K-L变换性能最为接近，而该算法的计算复杂程度适中，又具有快速算法的特点，所以近年来在图象和声音数据压缩中得到广泛应用。因此，本节重点介绍离散余弦变换DCT方法。
3.4.1 一维离散余弦变换
在傅里叶变换中，若被变换的函数是任意连续的偶函数，那么傅里叶变换后只存在余弦项，这一性质启示我们，即使被变换函数不是偶函数，只要我们把该函数变换成偶对称函数，然后再对变换后的偶函数进行傅里叶变换，那么傅里叶变换后的函数也只含余弦项，根据上述思想，我们首先分析一维离散情况。
设f(x),x?0,1,2,?,M?1, 为一离散序列，我们可以根据下式，把它变换成偶对称序列fe(x)，在正半轴坐标时，
fe(x)?f(x),x?0,1,2,?,M?1 (3-21) 在负半轴坐标时，
fe(x)?f(?x?1),x??1,?2,?,?M (3-22) 这样构成的偶对称序列fe(x)，其对称中心位于x??1/2处．因此, fe(x)的傅里叶变换为
Fe(u)?2?1u(x?)2M212M{?fe(x)ex??M?1?j2?1u(x?)2M2??fe(x)ex?0M?1?j}
309
?12M{?fe(x)ex??1?M?j2?1u(x?)2M2??fe(x)ex?0M?1?j2?1u(x?)2M2 } （3-23）
令x???x?1, 对上式第一项进行代换，可得， Fe?12M1{?fe(?x??1)ex/?0M?1j2?1u(x??)2M2??fe(x)ex?0?jM?1?j2?1u(x?)2M2}
?{?f(x)eM?1j2?1u(x?)2M2??f(x)eM?12?1u(x?)2M2 } （3-24）
2Mx?0x?0利用公式 ej??e?j??2co?s 上式可改写为 M??1 Fe(u)?2Mf(x)cos?u(2x?1) x?02M这就是一维离散余弦变换的公式。
因此，归一化的一维离散余弦变换公式如下
M?1 F(u)?2MK(u)?f(x)cos2[x(?1)u?2M] x?0M 2??1f(x)?MK(u)F(u)cos2[x(?1)u?2M] u?0其中，
x?0，1，?,M?1 u?0，1，?,M?1 K(u)???1/2,u?0, ?1u?1,2,?,M?1
3.4.2 二维离散余弦变换
二维离散余弦变换是一维情况的推广，公式如下，
M?1N? F(u,v)?21MNK(u)K(v)??f(x,y)co sx?0y?0 [(2x?1)u?/2M]?cos2[y(?1)v?/2N] u?0,1,2,..M.,?1 310
(3-25)
（3-26） (3-27a)
(3-27b)
(3-28a)