Implementation and Optimization of Two-dimensional DCT Based on DSP
摘 要：介紹了圖像的二維DCT變換原理，分析了Loeffler的DCT變換算法。根據(jù)DSP處理器BF533的結(jié)構(gòu)和指令特點，使用匯編語言對DCT算法程序進行優(yōu)化，并且在 BF533實驗平臺上進行驗證。實驗結(jié)果表明，優(yōu)化后的代碼無論在空間還是在時間上運算效率都得到很大提高。
關(guān)鍵詞：DCT; DSP ; 代碼優(yōu)化
Abstract: The principle of two dimensional Discrete Cosine Transform(DCT) is introduced in this paper. The algorithm of Loeffler’s DCT is analyzed. The algorithm of DCT is performed in assembly according to the structure and characteristics of BF533. The codes mentioned above are run on ADSP-BF533 platform successfully. Experiment results show that optimized codes are more efficiency than before in whatever code store space and code execution time.
Keywords: DCT； DSP；Code optimization
1 引言
現(xiàn)今的圖像編碼標準，一般采用紋理編碼方式對圖像進行壓縮。這種方式極大的利用了圖像數(shù)據(jù)的空間相關(guān)性，使圖像數(shù)據(jù)的壓縮能夠達到很高的比率。它主要是利用數(shù)學變換的方法，使用極少量的離散信號來表示大量的時域連續(xù)信號[1]。常用的數(shù)學變換有很多種，比如離散傅立葉變換DFT、沃爾什變換、哈爾變換、斜變換、離散余弦變換DCT、離散正弦變換DST 、K-L變換等。其中，K-L變換為理想狀態(tài)下的最佳變換方法，但是，由于K-L變換沒有快速的變換算法，而DCT、DFT和DST都具有與K-L變換近似的良好性質(zhì),尤其是當一階馬爾可夫過程相鄰元素相關(guān)系數(shù)ρ逼近1時，DCT的近似性能遠遠優(yōu)于其它兩者,并且DCT變換有具體的快速算法。因此，圖像壓縮標準中，使用DCT變換來實現(xiàn)紋理編碼。
由于DCT變換在各種編碼標準中要被反復調(diào)用，因此，其代碼執(zhí)行效率對實時視頻壓縮起著至關(guān)重要的作用[2]。實際應(yīng)用中，如何實現(xiàn)DCT變換的編碼及如何用硬件電路實現(xiàn)這種編碼變換是使用者關(guān)心的問題[3]。本文將利用DSP實現(xiàn)圖像的二維DCT變換并對其實行優(yōu)化。
2 DCT 變換
1974年Ahmed和Rao首先給出二維DCT 變換的數(shù)學表達式。該表達式適用于N點的DCT定義，但是，由于MPEG編碼一般是把視頻圖像幀或圖片分為場、片、宏塊的結(jié)構(gòu)，一幀圖像一般包括1－2場，每場包括若干片，每片包括若干宏塊，為了方便處理，把每個宏快分成8×8的子塊，即DCT處理的基本單元是8×8的子塊。因此，直接定義實用8點二維DCT變換：
因此，可以使用2次一維DCT變換來實現(xiàn)二維DCT變換。
在該定義被提出以后，很多優(yōu)秀的算法也被提了出來。如Chen,Lee的快速DCT算法等，Loeffler 在1989年提出的實用快速DCT算法共使用11次乘法和29次加法，該算法比起Chen的算法快而且不會發(fā)生Lee算法中的上溢問題，并且該算法被證明已經(jīng)達到了算法極限，是最優(yōu)秀的算法[4]。該算法如圖1，它把整個DCT過程分成了四級，第一級只有8次加法，第二級分為上下兩塊，上面是偶塊，下面是奇塊，偶塊有4次加法，奇塊有6次乘法和6次加法，第三級上面有5次加法3次乘法，下面有4次加法，第四級僅奇塊有2次乘法和2次加法。由圖1可見，奇數(shù)部分的第四級與第二級的計算構(gòu)成了連續(xù)的乘法，這種運算實現(xiàn)的時間將增加實際的計算時間。故Loeffler 提出了無乘法串行的并行計算方法，該方法使用了12次乘法和32次加法，這在具有并行的MAC處理器的運算中，并不增加實際的計算時間[1]。本文即采用這種DCT算法實現(xiàn)圖像的壓縮與處理。
