二維DCT編碼的DSP實(shí)現與優(yōu)化

1 引言

　　現今的圖像編碼標準，一般采用紋理編碼方式對圖像進(jìn)行壓縮。這種方式極大的利用了圖像數據的空間相關(guān)性，使圖像數據的壓縮能夠達到很高的比率。它主要是利用數學(xué)變換的方法，使用極少量的離散信號來(lái)表示大量的時(shí)域連續信號[1]。常用的數學(xué)變換有很多種，比如離散傅立葉變換DFT、沃爾什變換、哈爾變換、斜變換、離散余弦變換DCT、離散正弦變換DST 、K-L變換等。其中，K-L變換為理想狀態(tài)下的最佳變換方法，但是，由于K-L變換沒(méi)有快速的變換算法，而DCT、DFT和DST都具有與K-L變換近似的良好性質(zhì)，尤其是當一階馬爾可夫過(guò)程相鄰元素相關(guān)系數ρ逼近1時(shí)，DCT的近似性能遠遠優(yōu)于其它兩者，并且DCT變換有具體的快速算法。因此，圖像壓縮標準中，使用DCT變換來(lái)實(shí)現紋理編碼。

　　由于DCT變換在各種編碼標準中要被反復調用，因此，其代碼執行效率對實(shí)時(shí)視頻壓縮起著(zhù)至關(guān)重要的作用。實(shí)際應用中，如何實(shí)現DCT變換的編碼及如何用硬件電路實(shí)現這種編碼變換是使用者關(guān)心的問(wèn)題[。本文將利用DSP實(shí)現圖像的二維DCT變換并對其實(shí)行優(yōu)化。

　　2　DCT 變換

　　1974年Ahmed和Rao首先給出二維DCT 變換的數學(xué)表達式。該表達式適用于N點(diǎn)的DCT定義，但是，由于MPEG編碼一般是把視頻圖像幀或圖片分為場(chǎng)、片、宏塊的結構，一幀圖像一般包括1－2場(chǎng)，每場(chǎng)包括若干片，每片包括若干宏塊，為了方便處理，把每個(gè)宏快分成8×8的子塊，即DCT處理的基本單元是8×8的子塊。因此，直接定義實(shí)用8點(diǎn)二維DCT變換：

　　其反變換為：

　　其中 ，i,j,u,v=0,1…7.

　　在（1）式中，把變換核分離可得兩次一維DCT變換：


　　因此，可以使用2次一維DCT變換來(lái)實(shí)現二維DCT變換。

　　在該定義被提出以后，很多優(yōu)秀的算法也被提了出來(lái)。如Chen,Lee的快速DCT算法等，Loeffler 在1989年提出的實(shí)用快速DCT算法共使用11次乘法和29次加法，該算法比起Chen的算法快而且不會(huì )發(fā)生Lee算法中的上溢問(wèn)題，并且該算法被證明已經(jīng)達到了算法極限，是最優(yōu)秀的算法[4]。該算法如圖1，它把整個(gè)DCT過(guò)程分成了四級，第一級只有8次加法，第二級分為上下兩塊，上面是偶塊，下面是奇塊，偶塊有4次加法，奇塊有6次乘法和6次加法，第三級上面有5次加法3次乘法，下面有4次加法，第四級僅奇塊有2次乘法和2次加法。由圖1可見(jiàn)，奇數部分的第四級與第二級的計算構成了連續的乘法，這種運算實(shí)現的時(shí)間將增加實(shí)際的計算時(shí)間。故Loeffler 提出了無(wú)乘法串行的并行計算方法，該方法使用了12次乘法和32次加法，這在具有并行的MAC處理器的運算中，并不增加實(shí)際的計算時(shí)間[1]。本文即采用這種DCT算法實(shí)現圖像的壓縮與處理。

　　3　DSP及其視頻指令

　　我們使用ADI的ADSP－BF533EZLITE評估板作為實(shí)驗平臺，該評估板使用最大內部時(shí)鐘600M的BF533處理器。處理器內核包括二個(gè)40位的ALU,2個(gè)MAC,4個(gè)視頻ALU 及一個(gè)桶形移位寄存器。這種結構使并行的視頻處理成為可能[5]。實(shí)驗的軟件環(huán)境是VisualDSP4.5，該環(huán)境集成了高性能C/C++編譯器，并且具有比普通C/C++編譯器更高效的代碼優(yōu)化功能。

　　為了進(jìn)一步提高代碼效率，減少程序運行時(shí)間和代碼空間，根據DSP硬件結構及其指令的特點(diǎn)，對代碼進(jìn)行匯編優(yōu)化。本文主要注重以下三方面的優(yōu)化。

　?。?）利用高度并行的算術(shù)運算單元和功能強大的地址運算單元的相結合的特點(diǎn)，使用高密度指令代碼進(jìn)行代碼優(yōu)化。

　　Blackfin的高度并行結構能在計算的同時(shí)進(jìn)行數據的存儲，如R5=R1+R5,R4=R1-R5 ||R1=W[P0+0x4]（X）;該指令使用兩個(gè)加法器同時(shí)計算出兩個(gè)32位的值R1＋R5和R1－R5并把該結果分別存入到R5和R4中，此時(shí)占用的是算術(shù)運算單元的兩條內部總線(xiàn)一個(gè)指令周期時(shí)間，由于外部總線(xiàn)空閑，可以把外部Cache中的數據送入到R1中。索引尋址和變址尋址相結合的模式使一個(gè)指令周期內對不同塊的SDRAM訪(fǎng)問(wèn)成為了可能，比如上面的指令可以加一條R4=[I2++]仍能正確執行，而且不增加指令執行時(shí)間，地址運算單元DAG還包括兩個(gè)用于嵌套零開(kāi)銷(xiāo)循環(huán)的循環(huán)計數器以及支持傳輸過(guò)程中飽和的限幅的硬件。這些特性使得Blackfin指令操作的效率很高。

　?。?）利用有利于DCT變換的操作數位尋址指令來(lái)優(yōu)化

　　Blackfin DSP指令集不僅支持一個(gè)周期最多3條指令的并發(fā)執行，而且具有大量的像素操作和向量操作指令可以減少算法時(shí)間復雜度。位反轉指令對FFT、DCT、DFT等數學(xué)變換的操作數尋址提供了方便，在變換之前它把輸入數組數據通過(guò)位變換的方式變換到易于處理的排列方式，減少了操作數尋址的時(shí)間。

　?。?）利用IEEE 1180 舍入指令來(lái)支持DCT變換

　　Blackfin的加法指令支持預比例加減法，這種指令執行的時(shí)間首先通過(guò)算術(shù)移位將兩個(gè)操作數變大或者變小后再相加減，這在DCT變換中為了保證運算精度，一般會(huì )移位后相加減，這條指令大大加快了DCT變換的速度。