離散余弦變換原理

1、1離散余弦變換的原理視頻編碼和圖像編碼的對象主要是自然視頻信號、圖像信號或其預(yù)測殘差（包括幀內(nèi)和幀間”言號。號在空間域上的相關(guān)性己部分減弱，但是統(tǒng)計數(shù)據(jù)表明，在某些情況下殘差數(shù)據(jù)之間仍有其較強(qiáng)的相關(guān)性。所以類似于圖像信號和視頻信號，殘差信號也需要進(jìn)行一定的處理。這種去除相關(guān)性的處理過程就是變換編碼過程。變換編碼的基本思路是將在空間域中描述的視頻信號、圖像信號或殘差信號變換到另一個正交向量空間（變換域）中。如果該正交向量空間的基向量與圖像本身的特征向量很接近，那么經(jīng)過正交變換后，系數(shù)間的相關(guān)性基本消除，能量主要集中在直流和少數(shù)低頻的變換系數(shù)上。因此，對頻率域變換系數(shù)編碼的效率遠(yuǎn)遠(yuǎn)高于直接對空間域

2、像素編碼，從而達(dá)到圖像壓縮的目的。K一L變換的基本原理自然圖像信號或視頻信號在空間上存在的相關(guān)性可以用協(xié)方差矩陣來表示。協(xié)方差矩陣是圖像統(tǒng)計特性的重要反映。令NxN的編碼圖像塊的協(xié)方差矩陣為C:,根據(jù)正交變換的性質(zhì)，在對NxN像素塊作變換的同時，對其協(xié)方差矩陣C、作同樣的變換就可以得到變換系數(shù)塊的協(xié)方差矩陣Cy。理想的變換能使變換后的變換系數(shù)塊中各個系數(shù)互不相關(guān)，讓Cy成為對角陣，即變換系數(shù)塊中的各個系數(shù)只是自相關(guān)系數(shù)非零，而互相關(guān)系數(shù)全為oK-L變換就是在這種基本思路下產(chǎn)生的。它根據(jù)C、的特征值求出的特征矢量作為變換矩陣的基向量，得到變換矩陣A,然C,AC,Ar后用A對C、實(shí)施下式變換，即：

3、由矩陣?yán)碚摽芍鲜阶儞Q的結(jié)果是典型的對角陣?？梢姡?jīng)過K-L變換可以將空間域的相關(guān)性完全消除。如果取特征值前面k個絕對值較大者，則還原后的空間域信號的均方誤差最小，換言之還原圖像的逼真度最佳。但是，K-L變換的難點(diǎn)在于要根據(jù)圖像的統(tǒng)計特性來決定變換矩陣，即變換矩陣與輸入數(shù)據(jù)有關(guān)，需要求出C:的特征向量矩陣作為變換矩陣。嚴(yán)格地說，C、并不是一個固定的矩陣，因而它反映的特征向量矩陣和參數(shù)設(shè)計的不確定性是制約它實(shí)際應(yīng)用的關(guān)鍵。而且至今為止KL變換沒有快速算法，用實(shí)際電路來完成是十分困難的。離散余弦變換的基本原理鑒于K-L變換的缺點(diǎn)，視頻編碼和圖像編碼中需要有一個算法相對簡單，而變換矩陣與KL變換矩

4、陣相似的正交變換來實(shí)現(xiàn)去相關(guān)處理。而在斜變換(slantTransform)、沃爾什哈達(dá)馬變換(HadamardTransform)、哈爾變換(HaarTransform)、傅里葉變換(Fourier介ansform)等眾多離散正交變換中，離散余弦變換與K一L變換最接近。離散余弦變換是N.AhmedT.Natarajan以及K.R.Rao在1974年提出的12o對于一個MxN的像素塊，其二維離散余弦變換（DCT）定義為：而二維離散余弦逆變換（IDCT:InverseDisereteCosineTransform）定義為:=雷喝（喝7同喈4cMp鏟Q2）上述兩式中的變量氣，C、定義如下:1/V2

5、u=Q,_p/V2y=01u=111v=1對于自然圖像信號和視頻信號，其空間域各個像素之間的遞變特性一般可以近似等效為1階Markov過程，協(xié)方差矩陣C、具有近似ToePlitz矩陣的形式：研究表明，構(gòu)成K-L變換矩陣的向量也就是ToePhtz矩陣的特征向量。與此同時，離散余弦變換矩陣逼近于ToePutz矩陣的特征向量矩陣，所以離散余弦變換矩陣與自然圖像的K-L變換矩陣十分相似。經(jīng)過離散余弦變換后的變換系數(shù)塊的協(xié)方差矩陣Cy非常接近對角陣，即除了對角線元素以外，其它很多元素都近似為0,并且在左上角集中了主要能量。這反映了自然圖像大部分區(qū)域變化不大，亮度突變只占少數(shù)，即圖像能量以低頻成分為主的特

6、性。通過變換后的量化，舍棄對視覺效果影響較小的次要信息，可達(dá)到進(jìn)一步的壓縮效果。雖然從去相關(guān)性能的意義上講，DCT一種次于KL變換的準(zhǔn)最佳變換，但是從算法實(shí)現(xiàn)的角度來看，DC頂U(kuò)遠(yuǎn)遠(yuǎn)優(yōu)于K一L變換。首先，當(dāng)圖像的分塊大小確定后，DCTW變換矩陣也就隨之確定了，不隨輸入信號的統(tǒng)計特性變化而變化；其次，二維DCT夠分解成兩次一維DCT有利于硬件實(shí)現(xiàn)。同時，DCTW很多公開的快速算法，這些快速算法的相繼提出進(jìn)一步推動了其快速發(fā)展和應(yīng)用，使得DCTB經(jīng)成為了H.261、MPEG-1、MPEG一2、H.263、MPEG4JPEG等國際圖像視頻壓縮標(biāo)準(zhǔn)的基本算法。離散余弦變換的實(shí)現(xiàn)實(shí)現(xiàn)DC硒方法很多，最直

7、接的是根據(jù)DC硒定義來計算。以二維8xSDC偽例，需要作4096次乘法和3584次加法。這種算法的實(shí)現(xiàn)需要巨大的計算量，不具有實(shí)用價值。在應(yīng)用中，需要尋找快速而又精確的算法。較為常用的方法是利用DCT的可拆分特性，同樣以二維8xSDC偽例，先進(jìn)行8行一維DCT需要64xs次乘法和56xs次力口法，再進(jìn)行8列一維DCT要64xs次乘法和56xs次加法，共需要64x8xZ二1024次乘法和56x8xZ二896次加法，計算量減少為直接離散余弦變換的設(shè)計與實(shí)現(xiàn)計算的1/4。除此之外，DC而有很多公開的快速算法?？焖偎惴ㄖ饕峭ㄟ^減少運(yùn)算次數(shù)而減少運(yùn)算時間，這對于設(shè)計快速的硬件系統(tǒng)非常有效。二維DCT勺

8、快速算法則一般采用行列分離DCTB法，即轉(zhuǎn)換為兩次一維變換，其間通過轉(zhuǎn)置矩陣連接。最為經(jīng)典和常用的快速算法是由Arai等人于1988年提出的AANtff法l3以及由Loeffier等人于1989年提出的LLM算法14。這里值得一提的是，需要運(yùn)算次數(shù)最少的算法是l習(xí)中提出的二維直接計算算法。但是，由于行列分離DCT法能夠重復(fù)使用一維變換結(jié)構(gòu)，因此在實(shí)際實(shí)現(xiàn)上，尤其在硬件上比二維直接計算算法更有優(yōu)勢。對于一維8點(diǎn)IX二T來說，AA噂法通過將最后的縮放和（反）量化合二為一，因此共只需要5次乘法和29次加法。此算法主要缺點(diǎn)是在固定精度的定點(diǎn)運(yùn)算中，由于縮放和量化相結(jié)合導(dǎo)致計算結(jié)果不精確。原始的量化值越小，精度越差，所以對高質(zhì)量圖像的影響比低質(zhì)量圖像要大。二維8xs點(diǎn)DC琛用AA睜法需要16xs80次乘法和16x29=464次加法（不考慮縮放），是從一維DCT#算二維DCT!算量最小的方法。相比之下，使用LLM算法實(shí)現(xiàn)一維8點(diǎn)D