3.6 正交变换编码

3.6.1 最佳线性正交变换

正交变换编码与预测编码一样，都是利用去除信源序列的相关性来达到数据压缩的目的。它们之间的不同之处在于，预测编码是在空间域或时间域内进行，而变换编码则是在变换域（频率域）内进行的。

在数据压缩中，进行正交变换的目的是希望为给定的某类信号找到一种最有效的表示方式。假定一个离散时间（或空间）信号由N个采样值所组成，则可以认为它是一个在N维空间中的点，而每个采样值代表N维信号空间中数据向量X的一个分量。为了找到有效的表示方法，我们选取X的一个正交变换，使

Y＝TX　（3-53）

式中，Y与T分别为变换向量和正交变换矩阵。我们的目的是要寻找一个变换矩阵T，将经上式变换得到的Y用一个由M（M＜N）个分量构成的子集来近似，当删去Y中剩下的（N－M）个分量，仅用这个子集来恢复X时，不引起明显的误差。这样就可以用Y的这个只有M个分量的子集来代表有N个分量的信号X，从而达到数据压缩的目的。

为了找到“最佳”的正交变换，通常使用的判断准则是，能使得在恢复X时所产生的均方误差最小。

设变换矩阵具有如下形式：

TH≡T＊T＝[Φ1，Φ2，…，ΦΝ]　（3-54）

式中，上标＊和上标T分别代表矩阵的共轭与转置，上标H代表共轭、且转置，Φi是N维的列向量，且是标准正交（Orthonormal）的，即

由于Φi相互正交，所以它们是线性独立的，即它们之中的任何一个不能由其余向量的线性组合来产生。我们知道，N个线性独立的向量可以生成一个N维空间，这一组向量称为该空间的基，其中的每一个Φi称为基向量。例如，三维欧几里得空间的三个基向量分别是i，j和k。

由（3-54）式和（3-55）式，得到TTH＝THT＝I，即T的逆矩阵为

T－1＝TH　（3-56）

满足上述条件的矩阵称为酉（Unitary）矩阵，它所对应的变换称为酉变换。当T为实数矩阵，且T－1＝TT时，T称为正交矩阵，其对应的变换称为正交变换。数据压缩中所研究的主要是正交（或酉）变换。我们熟悉的傅氏变换，当其基向量时，就是一个酉变换。

由（3-53）式和（3-56）式，得到

上式表明将X转换到由基向量Φi（i＝1，…，N）生成的N维空间（通常称为变换域）中，yi代表X在Φi上投影的大小，称为变换系数。因此，由变换系数所构成的向量Y是信号X在变换域中的表示。

假设信号X是一个均值为零的随机向量，即〈X〉＝0。若只保留M（M＜N）个变换系数，将其余（N－M）个系数置为零，则所得到的X的近似值XM与原信号的差值ΔX为

其均方误差MSE则为

上式的最后一步由基向量的正交性得到。由（3-53）式可知，yi＝ΦHi·X，且标量的转置为其自身，则（3-59）式可改写为

当〈X〉＝0时，〈X·XH〉即为X的协方差矩阵ΣX。

利用拉格朗日乘数法可以证明，在ΦHi·Φi＝1的条件下，使MSE为最小的条件是

ΣXΦi＝λiΦi （1≤i≤N）　（3-61）

由上式看出Φi和λi分别是矩阵ΣX的本征向量和本征值。这也就是说，以信号的协方差矩阵ΣX的本征向量Φi（i＝1，2，…，N）组成的变换矩阵是均方误差最小准则下的最佳变换矩阵，用此矩阵构成的最佳变换Y＝TX称为卡南—洛伊夫变换（Karhunen-LoeveTransform），简称KLT。

经KL变换后，Y的协方差矩阵ΣY为

根据协方差矩阵的定义可知，ΣY矩阵对角线上的元素为Y的分量yi的方差，而非对角线上的元素代表Y的分量之间的协方差值。（3-62）式说明，KL变换解除了随机向量X的分量之间的相关性，在变换域中Y的各分量之间是互不相关的（因为协方差为零），从而有利于对各分量分别独立地进行处理。同时，将（3-61）式代入（3-60）式，得到

上式说明最小均方误差等于Y向量中被丢弃的分量的方差之和。由此可知，应该选择具有较大方差的M个Y分量所构成的子集来恢复X，以使得恢复后所产生的误差最小（能量损失最小）。

由于构成KL变换的基向量是X协方差矩阵的本征向量，因此，KLT的基向量与信号的统计特性有关，必须针对某一类信号具体地设计。这一点是与傅氏变换不同的。在傅氏变换中，不管对具有何种特性的信号，均使用同样的基向量。此外，KLT也缺乏相应的快速算法，因此在数据压缩中应用并不普遍，但它常被用来作为评价各种变换的性能的基准。

3.6.2 离散余弦变换

选择不同的正交基向量，可以得到不同的正交变换。从数学上可以证明，各种正交变换都能在不同程度上减小随机向量各分量之间的相关性，而且信号经过大多数正交变换后，能量会相对集中在少数变换系数上，删去对信号贡献小（方差小）的系数，只利用保留下来的系数恢复信号时，不会引起明显的失真。因此，不同的正交变换，例如，离散傅氏变换（DFT），离散余弦变换（DCT），哈尔变换（HT），沃尔什—哈达马变换（WHT）等均在数据压缩中得到应用，只是在均方误差准则下，性能不如KLT好。

当信号的统计特性符合一阶平稳马尔柯夫过程，而且相关系数接近于1时（许多图像信号都可以足够精确地用此模型描述），DCT十分接近于信号的最佳变换KLT，变换后的能量集中程度较高。即使信号的统计特性偏离这一模型，DCT的性能下降也不显著。由于DCT的这一特性，再加上其基向量是固定的，并具有快速算法等原因，它在图像和视频数据压缩中得到了广泛的应用。

顾名思义，DCT的基向量由余弦函数构成。一维DCT的正变换和反变换分别由下式定义：

式中，s（k）为信号样值；S（n）为变换系数，且

由一维的DCT可以直接扩展到二维，即

其中

图3-26（a）表示出了二维DCT的基函数，（b）表示了N＝8时的信号矩阵和变换系数矩阵。

DCT与DFT一样，如果没有快速算法，就很难在实际中得到应用。如果直接利用正变换公式进行一个一维N点DCT的计算，需要作N2次乘法运算和N（N－1）次加法运算，与直接计算的DFT运算量相同。与FFT相类似，根据基函数的周期性和对称性，人们已经提出许多种快速DCT算法，典型的快速算法请参见本章参考文献。我们在这里只介绍一种基于DFT的DCT算法，以便理解DCT与DFT之间的关系。

令WK≡exp（－j2π/K）

则K个点的DFT可表示为

若有一个N点实数序列s（k），k＝0，1，…，N－1，我们定义一个与此序列相对于（2N－1）/2点对称的序列（见图3-27），即

s（2N－k－1）＝s（k）　（k＝N，N＋1，…，2N－1）　（3-72）

则整个K＝2N点序列的DFT可表示为

设i＝2N－k－1，并注意到W2NK＝1，上式则变为

用k代替i，并在等式两边同乘以Wn/2K/2，则得到

上式说明一个N点序列的DCT系数，可以由它对应的对称序列的前N个2N点DFT系数乘以适当的数值得到。为了进一步简化上述关系，我们注意到，由于（3-75）式右端是实数，因此左端也应为实数。用An和Bn分别表示F（n）的实数和虚数部分，则有

将上式展开并令虚部为零，得到

将Bn代入（3-76）式得到

式中Re｛F（n）｝表示对函数F（n）取实部。将上式代入（3-75）式，得到

由上式可以得到如下结论：一个函数的DCT系数可以由该函数对应的偶函数的DFT系数的实部得到。图3-27表示了这个过程。

二维的DCT可以直接计算，也可以通过这样的办法来实现：先按照行（或列）进行一维DCT变换，然后将变换结果再按列（或行）进行一维变换。

最后，有两点值得指出：

（1）我们知道，二维信号的傅氏变换的系数代表它所对应的空间频率分量的复振幅。（3-79）式表明，虽然DCT系数并不与空间频率分量的复振幅严格相等，但有一定的对应关系。特别是，n＝0时的DCT系数与DFT的零频分量一样，代表空间域内信号的均值；

（2）如前所述，一个函数的DCT系数可以通过与该函数对应的偶函数的DFT系数得到。由于偶函数的对称性减小了DFT中由于周期延拓而产生的空间域中边缘的不连续性，从而使能量在频率域内更为集中。因此在数据压缩的应用中，DCT比DFT具有更好的性能。