離散余弦變換原理

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

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

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

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

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

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

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

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