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