一種基于減少內(nèi)存訪問的Pruning Fast DCT算法改進(jìn)

　1．引言

　　散余弦變換（dct）的定義是由ahmed和rao與1974年提出，對于圖像數(shù)據(jù)，通過散余弦變換，可以將低頻數(shù)據(jù)集中，利用人對高頻數(shù)據(jù)不敏感這一特點(diǎn)，去掉高頻部分?jǐn)?shù)據(jù)，可以實(shí)現(xiàn)對數(shù)據(jù)的壓縮。近年來，基于這一思想的算法大都是在通用計(jì)算機(jī)上實(shí)現(xiàn)的，然而對數(shù)字信號處理的最佳平臺是DSP平臺，直接在DSP平臺上運(yùn)行此類算法存在一定問題。眾所周知，DSP處理器大都應(yīng)用與移動(dòng)平臺，對速度和耗電量要求較高。在DCT算法中存在大量的內(nèi)存訪問操作，這些操作會(huì)帶來很多長延時(shí)，而這會(huì)影響運(yùn)行速度和電量消耗。比如，在TITMS320C64XDSP平臺上，執(zhí)行一次內(nèi)存裝載指令要執(zhí)行5條操作，需要4次延時(shí)，因此，頻繁的內(nèi)存訪問會(huì)增加時(shí)間開銷。雖然PruningDCT算法中已經(jīng)省去了對高頻數(shù)據(jù)的運(yùn)算操作，但PruningDCT算法中的大量權(quán)重系數(shù)和輸入序列還是會(huì)導(dǎo)致較多的內(nèi)存訪問操作。如果能進(jìn)一步減少對這些權(quán)重系數(shù)和輸入序列的運(yùn)算，就能進(jìn)一步優(yōu)化算法執(zhí)行時(shí)間。

　　本文針對這一情況提出了一種改進(jìn)方法，通過分解DCTpruning算法中的權(quán)重系數(shù)，減少了系數(shù)的個(gè)數(shù)，并由此減少了算法中的步驟。在C64X實(shí)驗(yàn)平臺上出實(shí)驗(yàn)證明，這種改進(jìn)可以有效減少運(yùn)算過程中對內(nèi)存的訪問次數(shù)。文中第2章節(jié)主要介紹第2類DCT算法思想，第3章節(jié)介紹對DCT-II的一種改進(jìn)算法PruningFCT，第4章節(jié)詳細(xì)描述了一種降低PruningFCT算法在DSP上運(yùn)行時(shí)間的改進(jìn)思想，第5和第6章節(jié)對改進(jìn)算法進(jìn)行了分析及總結(jié)。

　　2關(guān)于FASTDCTPruning

　　這一章節(jié)主要介紹基本的DCT計(jì)算過程。當(dāng)前被介紹最多的DCT運(yùn)算是第二類DCT（DCT-II），其定義是：

　�。�1）

　　其中當(dāng)m＝0時(shí)，

　�。�

　�。划�(dāng)m

　　0時(shí)，

　�。�1。x[n]為輸入序列，X[n]為輸出序列。直接的算法若不加以變換，在軟件和硬件上實(shí)現(xiàn)都比較困難，為此，在第二類DCT算法的基礎(chǔ)上又出現(xiàn)了很多改進(jìn)算法，如FASTDCT。

　　2.2FASTPRUNINGDCT

　　針對以上問題，一些改進(jìn)方法又被提出，如FCT(FASTDISCRETECOSINETRANSFORM)，次算法針對DCT-II難以硬件實(shí)現(xiàn)，對輸入序列的計(jì)算過程進(jìn)行了一些變換，其實(shí)現(xiàn)過程如下：

　　首先對輸入序列調(diào)整

　　[n]=x[2n],

　　[N-n-1]=x[2n+1],n=0,1,……N-1

　　于是DCT公式調(diào)整如下：

　　m=0,1,……N-1（2）

　　利用三角變換公式：cos[(2k+1)φ]=2cosφcos(2kφ)-cos[(2k-1)φ]

　　可以把變換后的公式分解成2部分，N/2-pt的奇數(shù)部分x[2k+1],N/2-pt偶數(shù)部分x[2k],偶數(shù)部分和奇數(shù)部分可以繼續(xù)分解，直到分解成2-pt的輸入序列。

　　對于16-pt的FCT運(yùn)算，其設(shè)計(jì)圖如下：

　　圖1

　　圖1分為兩個(gè)部分，蝶形運(yùn)算和位運(yùn)算。其中蝶形運(yùn)算又分為若干階段（stage），根據(jù)輸入序列數(shù)量每個(gè)階段所包含的蝶形運(yùn)算數(shù)量是固定的，對于N個(gè)輸入點(diǎn)（即N-pt）的FCT運(yùn)算，其蝶形運(yùn)算部分分為

　　N個(gè)階段（stage），每個(gè)stage有N/2個(gè)蝶形運(yùn)算以及N/

　　個(gè)權(quán)重系數(shù)。在運(yùn)算過程中，蝶形運(yùn)算部分占據(jù)了主要運(yùn)算，在此期間存在大量內(nèi)存訪問操作，為了降低算法執(zhí)行時(shí)間，應(yīng)對這一部分進(jìn)行改進(jìn)。

　　3對FCTPruning算法的改進(jìn)

　　為了進(jìn)一步減少FCTPruning算法中因?yàn)闄?quán)重系數(shù)和輸入x[n]帶來的內(nèi)存訪問次數(shù)，文中設(shè)計(jì)了一種改進(jìn)方法，首先，通過對權(quán)重系數(shù)的分解，降低所要調(diào)用的系數(shù)的個(gè)數(shù)；然后，合并運(yùn)算階段，減少stage個(gè)數(shù)。

　　3.1系數(shù)分解

　　通過三角恒等變換公式：

　　m

　　（3）

　　其中

　　=

　　m=1,2,……N/2-1

　　可以對FCTPruning算法中的權(quán)重系數(shù)進(jìn)行分解，分解后權(quán)重系數(shù)從N-1個(gè)減少為（2N-1）/3個(gè)。

　　例如，對圖1中stage3和stage4出現(xiàn)的權(quán)重系數(shù)

　　，

　　，

　　，其中

　　可以分解為[

　　-

　　]/2。

　　[

　　-

　　]/2=2[

　　-

　　]

　　=2{

　　-[-

　　}

　　=2[

　　-

　　]

　　=2{

　　-[

　　}

　　=2[

　　-

　　]

　　=

　　=

　　=

　　經(jīng)過分解后，在stage3和stage4中的權(quán)重系數(shù)從3個(gè)減少為2個(gè)。同樣，stage2中的

　　，

　　，

　　，

　　分別替換如下：

　　=[

　　-

　　]/2

　　=[

　　-

　　]/2

　　=[

　　-

　　]/2

　　=[

　　-

　　]/2

　　自此，對于16-pt的FCTPruning的權(quán)重系數(shù)個(gè)數(shù)由15個(gè)減少為10個(gè)。

　　在此基礎(chǔ)上，可以把原有的4個(gè)運(yùn)算階段（stage1，stage2，stage3，stage4）合并為2個(gè)。

　　3.2合并簡化計(jì)算

　　在進(jìn)行了權(quán)重系數(shù)分解后，可以把2個(gè)階段的蝶形運(yùn)算合并成一個(gè)，由此減少了程序運(yùn)行過程中循環(huán)執(zhí)行次數(shù)，也就減少了執(zhí)行期間從內(nèi)存讀寫權(quán)重系數(shù)和x[]的次數(shù)，從而使得算法執(zhí)行速度獲得較大提高。在s(s=1,2……

　　)階段，共有N/

　　個(gè)不同的權(quán)重系數(shù)，每個(gè)系數(shù)按如下法則遞歸生成：

　　第一個(gè)和第二個(gè)分別是：

　　，

　　(k=

　　)

　　第三個(gè)和第四個(gè)分別是：

　　，

　　第五個(gè)和第六個(gè)分別是：

　　，

　　……

　　該法則類似Fibonacci數(shù)列

　　X[n+N/

　　]

　　圖2（a）

　　X[n+N/

　　]

　　X[n]

　　圖2（b）

　　圖2（a）顯示了在s和s+1階段的蝶形運(yùn)算規(guī)則，其中在圖2（b）中被挖掉的節(jié)點(diǎn)表示此處由于x[n]帶來的內(nèi)存訪問操作被消除。消除的原因是由于原本的2個(gè)階段合并成一個(gè)階段，此處的讀x[n]操作只會(huì)在一次stage循環(huán)中被執(zhí)行，而不會(huì)被執(zhí)行2次。由4.1章節(jié)中三角恒等變換公式可得2

　　=

　　，因此，只需從內(nèi)存中訪問

　　和

　　這2個(gè)系數(shù)，就可以對圖2（a）中的4個(gè)蝶形運(yùn)算進(jìn)行計(jì)算，據(jù)此，圖2（a）中的2個(gè)階段可以合并成1個(gè)階段，即圖2（b）所示。在3.1章節(jié)中提到，F(xiàn)CTPruning的蝶形運(yùn)算部分可分為

　　個(gè)階段（stage）,改進(jìn)后對運(yùn)算階段進(jìn)行了合并，使得stage數(shù)量減少為：

　　為奇數(shù)

　　為偶數(shù)

　　改進(jìn)后PruningFCT蝶形運(yùn)算部分設(shè)計(jì)如圖（3）所示：

　　e

　　c

　　e

　　e

　　e

　　d

　　b

　　a

　　注：a=[

　　-

　　]/2,b=[

　　-

　　]/2,c=[

　　-

　　]/2

　　e=[

　　-

　　]/2

　　圖（3）

　　4對算法的分析和驗(yàn)證

　　通過上述的改進(jìn)設(shè)計(jì)，由權(quán)重系數(shù)和x[n]輸入引發(fā)的內(nèi)存訪問操作進(jìn)一步減少。以圖1和圖3中16-pt的FCT為例，圖1中顯示，16-pt的FCT中共有15個(gè)權(quán)重系數(shù)，經(jīng)過分解后圖3中權(quán)重系數(shù)降低為10個(gè)。圖1中由x[n]輸入引發(fā)的內(nèi)存訪問有128次，即圖1中實(shí)心圓和空心圓的數(shù)量，圖3中經(jīng)過合并，stage數(shù)量由4個(gè)合并成2個(gè)，程序段2算法中最外層對stage的循環(huán)次數(shù)減少為2次，大量的x[n]重復(fù)訪問被省掉，由x[n]輸入引發(fā)的內(nèi)存訪問由是減少為64次，即圖3中實(shí)心圓和空心圓的數(shù)量。對于PruningFCT算法，輸入序列數(shù)量N=16,當(dāng)

　　=3時(shí)，圖1中由x[n]輸入引發(fā)的內(nèi)存訪問有87次，圖3中由x[n]輸入引發(fā)的內(nèi)存訪問有43次。

　　通過簡單對比顯然易見，改進(jìn)后的PruningFCT算法內(nèi)存訪問次數(shù)進(jìn)一步降低，這必然提高運(yùn)行速度。為了更好的顯示改進(jìn)的效果，將文中程序段1和程序段2針對同樣的輸入序列在C64XDSP平臺上運(yùn)行，輸入序列分別為8-pt，16-pt，32-pt，64-pt的一維數(shù)組。輸出

　　為了方便起見，只取2的整數(shù)次冪，實(shí)驗(yàn)結(jié)果如下表：

　　N248163264

　　8程序段1415470

　　程序段2233652

　　16程序段189118150194

　　程序段2426581125

　　32程序段1185246310386498

　　程序段295140172248360

　　64程序段13775026307709451218

　　程序段2188273321429541813

　　表1

　　PruningFCT算法改進(jìn)前改進(jìn)后對內(nèi)存的占用情況如下表：

　　N8163264

　　程序段1143062126

　　程序段210204184

　　表2

　　由表1和表2中試驗(yàn)數(shù)據(jù)可見，改進(jìn)后的算法無論在內(nèi)存訪問時(shí)間上還是內(nèi)存占用方面都有了明顯提升，對表1的數(shù)據(jù)進(jìn)行計(jì)算分析得出，平均訪問次數(shù)降低了41.5%；對表2的數(shù)據(jù)分析表明，內(nèi)存占用減少了32.2%。

　　5總結(jié)及后續(xù)發(fā)展

　　本文介紹了一種對PruningFCT算法改進(jìn)設(shè)計(jì)，該設(shè)計(jì)的基本思想是利用三角恒等變換，把s+1階段的權(quán)重系數(shù)用s階段的權(quán)重系數(shù)來替代，從而減少了算法中的權(quán)重系數(shù)，進(jìn)而把蝶形運(yùn)算中的階段合并，減少了階段數(shù)量，從而減少了對輸入序列的訪問次數(shù)。試驗(yàn)結(jié)果顯示，改進(jìn)后的算法不僅降低了內(nèi)存訪問次數(shù)，還減少了內(nèi)存的占用。文中只對一維的PruningFCT算法進(jìn)行了改進(jìn)，二維的PruningFCT算法在圖像壓縮中的應(yīng)用更有實(shí)際意義，下一步可沿用文中所提思想對二維的PruningFCT算法進(jìn)行改進(jìn)。

　　參考文獻(xiàn)

　　1 N. AHMED, T. NATARAJAN, and K. R. RAO “DiscreteCosine Transform,” IEEE Transactions on Computers, vol. C-23, pp.90-93, January 1974.

　　2 K. R. Rao and P. Yip, Discrete Cosine Transform: Algorithms,Advantages, Applications. New York: Academic, 1990.

　　3 M. Wezelenburg, “General radix-2n DCT and DST algorithms,”Proceedings of the International Conference on ECCTD’97,pp.789-794, Budapest, Hungary, September 1997.

　　4 Y.-H. Chan and W.-C. Siu, “Mixed-radix discrete cosinetransform,” IEEE transactions on Signal Processing, vol. 41,no.11, pp. 3157-3161, November 1993.

　　5 Z. Wang, “Pruning the fast discrete cosine transform,” IEEETrans. Commun. vol. 39, no. 5, pp. 640-643, May 1991.

　　6 Athanassios N. Skodras, “Fast Discrete Cosine TransformPruning,” IEEE Trans. On Signal Processing, Vol. 42, no. 7,pp.1833-1837, July 1994.

　　7 S.C.Chan and K.L.Ho “A new two-dimensional fast cosinetransform algorithm,” IEEE Trans. Signal Processing,vol. 39,no. 2, pp. 481-485, February 1991.

【一種基于減少內(nèi)存訪問的Pruning Fast DC】相關(guān)文章：

減少污染作文09-09

減少污染作文06-03

訪問記作文06-03

申請減少租金的申請書12-07

婚內(nèi)存款協(xié)議03-25

申請減少租金的申請書9篇12-07

申請減少租金的申請書13篇12-07

對什么的一次訪問作文（通用17篇）06-19

減少聚餐倡議書范文（通用14篇）12-20