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具有更好的性能。