離散余弦變換原理

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

2、域像素編碼，從而達(dá)到圖像壓縮的目的。1.1 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ù)全為零。K一L變換就是在這種基本思路下產(chǎn)生的。它根據(jù)C、的特征值求出的特征矢量作為變換矩陣的基向量，得到變換矩陣A，然后用A對C、實施下式變換，即:

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

4、一L變換矩陣相似的正交變換來實現(xiàn)去相關(guān)處理。而在斜變換(slantTransform)、沃爾什一哈達(dá)馬變換(HadamardTransform)、哈爾變換(HaarTransform)、傅里葉變換(Fourier介ansform)等眾多離散正交變換中，離散余弦變換與K一L變換最接近。離散余弦變換是N.Ahmed、T.Natarajan以及K.R.Rao在1974年提出的l2。對于一個MxN的像素塊，其二維離散余弦變換(DCT)定義為:  而二維離散余弦逆變換(IDCT:InverseDisereteCosineTransform)定義為:  上述兩式中的

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

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

7、本算法。1.3離散余弦變換的實現(xiàn)實現(xiàn)DCT的方法很多，最直接的是根據(jù)DCT的定義來計算。以二維8xSDCT為例，需要作4096次乘法和3584次加法。這種算法的實現(xiàn)需要巨大的計算量，不具有實用價值。在應(yīng)用中，需要尋找快速而又精確的算法。較為常用的方法是利用DCT的可拆分特性，同樣以二維8xSDCT為例，先進行8行一維DCT需要64xs次乘法和56xs次加法，再進行8列一維DCT要64xs次乘法和56xs次加法，共需要64x8xZ二1024次乘法和56x8xZ二896次加法，計算量減少為直接浙江大學(xué)碩士學(xué)位論文離散余弦變換的設(shè)計與實現(xiàn)計算的1/4。除此之外，DCT還有很多公開的快速算法?？焖偎惴?/p>

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