二維翻轉(zhuǎn)結(jié)構(gòu)9/7離散小波逆變換研究與VLSI實(shí)現(xiàn)

宋有才 ，譚拂曉 ，王詩兵 ，韓 波 ，2，趙正平

1.阜陽師范學(xué)院 計算機(jī)與信息學(xué)院，安徽 阜陽 236037

2.東南大學(xué) 毫米波國家重點(diǎn)實(shí)驗(yàn)室，南京 210096

1 引言

二維9/7離散小波變換（Discrete Wavelet Transform，DWT）與逆變換（Inverse Discrete Wavelet Transform，IDWT）以優(yōu)越的顯示效果、良好的壓縮比、多分辨率等特性而廣泛應(yīng)用于各類圖像處理中。傳統(tǒng)上，離散小波變換通過卷積實(shí)現(xiàn)，Daubechies和Sweldens提出了離散小波變換的提升結(jié)構(gòu)[1-2]，極大地降低了計算量與復(fù)雜度。以9/7離散小波逆變換為例，其實(shí)現(xiàn)步驟如下：

（1）系數(shù)伸縮：

（2）一級提升：

（3）二級提升：

（4）數(shù)據(jù)輸出：

式中，α=-1.586 1，β=-0.052 98，γ=0.882 9，δ=0.443 5，K=1.149 6。與分別為偶數(shù)行與奇數(shù)行小波系數(shù)。與分別為逆變換后的偶數(shù)行與奇數(shù)行原始信號。所謂的二維IDWT，即是基于公式（1）到（4）先沿著行方向進(jìn)行一維IDWT，再沿著列方向完成二維IDWT。盡管提升結(jié)構(gòu)9/7離散小波逆變換通過一組加法與乘法實(shí)現(xiàn)，極大地降低了算法復(fù)雜度，但隨著高清圖像實(shí)時處理、編解碼的廣泛應(yīng)用，對計算過程中的內(nèi)存消耗、計算速率提出了更高要求。國外文獻(xiàn)[3-6]也是以此研究方向，先后從算法優(yōu)化、電路結(jié)構(gòu)等方面展開了優(yōu)化，但效果有限，沒有實(shí)現(xiàn)性能的綜合提升。國內(nèi)的眾多研究結(jié)構(gòu)也就該領(lǐng)域展開了一系列的研究[7-16]。

本文的創(chuàng)新點(diǎn)在于：通過研究算法結(jié)構(gòu)與分析數(shù)據(jù)輸入輸出格式，提出了一種適合電路建模的翻轉(zhuǎn)結(jié)構(gòu)。在此基礎(chǔ)上，采用流水線技術(shù)，將關(guān)鍵路徑降為1級乘法器延時；設(shè)計了多核結(jié)構(gòu)，并行地完成行列方向逆變換，在提高處理速率的同時，處理N×N圖像僅需4N的內(nèi)存消耗。

2 翻轉(zhuǎn)結(jié)構(gòu)IDWT

電路實(shí)現(xiàn)過程中，如何將IDWT的計算過程分解融入到各級流水線中，直接影響了電路的關(guān)鍵路徑延遲，從而決定了電路的運(yùn)行時鐘。IDWT運(yùn)算類型雖僅有乘法和加法，但一般情況下，乘法運(yùn)算通過專用乘法器實(shí)現(xiàn)，比起電路模型中的其他基本邏輯運(yùn)算，最影響關(guān)鍵路徑延遲。因此，計算過程的優(yōu)化思路就進(jìn)一步集中在如何分割乘法運(yùn)算到各級流水線實(shí)現(xiàn)。

分析公式（2）與（3），在進(jìn)行乘法運(yùn)算前，首先需要進(jìn)行一次加法運(yùn)算。盡管可以通過流水線來優(yōu)化，但是數(shù)據(jù)須先后流經(jīng)乘法計算路徑與加法計算路徑，增加電路設(shè)計時的復(fù)雜度。為此，本文提出下式所示的計算過程：

（1）系數(shù)伸縮：

（2）一級翻轉(zhuǎn)

（3）二級翻轉(zhuǎn)：

（4）數(shù)據(jù)輸出：

式中各參數(shù)定義和取值與基本提升結(jié)構(gòu)相同。Kγ、α-1、K-1、δγ、α/γ與αβ六個乘法系數(shù)可以提前計算得到。所謂的翻轉(zhuǎn)結(jié)構(gòu)就是將公式（2）與（3）中第二個算式的提升系數(shù)翻轉(zhuǎn)，從而將計算路徑分割為乘法路徑和加法路徑兩個部分，流水線設(shè)計時可在第一個周期完成乘法，之后只需進(jìn)行幾次加法即可，便于電路實(shí)現(xiàn)。同時，上述翻轉(zhuǎn)結(jié)構(gòu)按正常順序讀入和輸出數(shù)據(jù)，兩級翻轉(zhuǎn)僅翻轉(zhuǎn)系數(shù)不同，便于電路結(jié)構(gòu)的復(fù)用。

3 VLSI設(shè)計

3.1 系統(tǒng)架構(gòu)

基于本文提出的翻轉(zhuǎn)結(jié)構(gòu)IDWT，設(shè)計電路系統(tǒng)架構(gòu)如圖1所示。包括行方向一維逆變換核、數(shù)據(jù)流組織模塊、列方向一維逆變換核三部分。處理時，小波子帶系數(shù)按行方向順序輸入，進(jìn)行一維行方向逆變換。數(shù)據(jù)緩存模塊僅需緩存2N的中間數(shù)據(jù)，即可流水線地進(jìn)行一維列方向逆變換。每級小波逆變換結(jié)束后，輸出的LL子帶系數(shù)可返回至輸入內(nèi)存，用于上一級小波逆變換。如此反復(fù)，直到獲取原始圖像。下面將詳細(xì)介紹各模塊的電路實(shí)現(xiàn)。

3.2 行方向逆變換核

一級翻轉(zhuǎn)結(jié)構(gòu)行方向逆變換的電路原理如圖2所示。圖中，⊕表示加法器，?表示乘法器，□表示寄存器。假設(shè)伸縮變換后的與已經(jīng)讀入，則在第t個周期內(nèi)與δγ完成乘法進(jìn)入d2，則緩存在reg中；第t+1周期，完成與的減法存入s_temp，同時讀入并完成與δγ的乘法存入d2中；第t+2個周期，s_temp緩存數(shù)據(jù)與d2緩存數(shù)據(jù)相減，獲得。為了對齊時鐘，在輸出前加了一級寄存器，即在t+4個周期同時輸出與。參考公式（6）與圖2同樣可知的計算過程。顯然，由于流水線技術(shù)的使用，在每個時鐘周期內(nèi)僅需完成一個計算步驟，關(guān)鍵路徑為一級乘法器延遲。通過以上分析，該電路單元共采用了4級流水線，共需1個乘法器、4個加法器和9個寄存器。

圖1 整體處理架構(gòu)

圖2 一級翻轉(zhuǎn)結(jié)電路原理

比較公式（6）與公式（7），兩者計算過程相近，僅僅是乘法系數(shù)不同。因此，可通過選擇器選擇乘法系數(shù)，從而復(fù)用一級翻轉(zhuǎn)結(jié)構(gòu)的電路實(shí)現(xiàn)。完整的兩級翻轉(zhuǎn)結(jié)構(gòu)逆變換過程如圖3所示。

圖3 完整的兩級翻轉(zhuǎn)結(jié)構(gòu)變換過程

3.3 列方向逆變換核

不失一般性的，以6×6圖像處理過程為例說明變換列方向逆變換核的電路結(jié)構(gòu)。理論上，一維列方向逆變換電路結(jié)構(gòu)與一維行方向逆變換電路結(jié)構(gòu)基本相同。但一維列方向小波逆變換是逐列進(jìn)行，而一維行方向小波逆變換是逐行輸出，如圖4（a）所示。為了在有效提高電路并行度的同時有效降低數(shù)據(jù)緩存模塊大小，在緩存相鄰兩行共2N的一維列方向小波逆變換結(jié)果后，立即如圖4（b）所示按列兩兩讀入進(jìn)行一維列方向小波逆變換，其中，黑框部分是采用周期對稱延拓的邊界數(shù)據(jù)。根據(jù)上一節(jié)分析，s_temp和d_temp分別需要緩存N/2數(shù)據(jù)。但在此之后，每輸入2個一維行方向逆變換的結(jié)果，便可繼續(xù)流水線的完成操作。其關(guān)鍵路徑仍為1個乘法器延時，流水線仍為4級，數(shù)據(jù)緩存模塊共消耗2N的轉(zhuǎn)換內(nèi)存。

圖4 數(shù)據(jù)緩存模塊處理流程

4 實(shí)驗(yàn)分析

采用Verilog語言實(shí)現(xiàn)本文描述電路，基于Sparten6-xc6slx150t FPGA平臺，在Xilinx ISE下仿真驗(yàn)證，模塊運(yùn)行時鐘達(dá)166.34 MHz。選取相關(guān)文獻(xiàn)中列出的研究成果進(jìn)行比較，如表1所示。其中，Tm是指乘法器延時，Ta是指加法器延時。本文所提出的翻轉(zhuǎn)結(jié)構(gòu)9/7離散小波逆變換及其實(shí)現(xiàn)電路在得到最小內(nèi)存消耗的同時具有最小的關(guān)鍵路徑，綜合性能最佳。

表1 性能分析

5 總結(jié)

本文研究了一種新的翻轉(zhuǎn)結(jié)構(gòu)二維9/7離散小波逆變換，并綜合了流水線技術(shù)與并行技術(shù)，設(shè)計了一種高性能的VLSI結(jié)構(gòu)，以滿足高清實(shí)時圖像處理的需要。

[1]Daubechies I，Sweldens W.Factoring wavelet transform into lifting steps[J].J Fourier Anal Appl，1998，4（3）：247-269.

[2]Sweldens W.The lifting scheme：a custom-design construction of biorthogonal wavelets[J].Applied and Computation Harmonic Analysis，1997，15（3）：186-200.

[3]Liao H，Mandal M K，Cockburn B F.Efficient architectures for 1-D and 2-D lifting-based wavelet transforms[J].IEEE Transactions on Signal Processing，2004，52（5）：1315-1326.

[4]Tseng P C，Huang C T，Chen L G.Generic RAM-based architectures for two-dimensional discrete wavelet transform with line-based method[J].IEEE Transactionson Circuits and Systems for Video Technology，2005，15（7）：910-920.

[5]Huang C T，Tseng P C，Chen L G.Flipping structure：an efficient VLSI architecture for lifting-based discrete wavelet transform[J].IEEE Transactionson Signal Processing，2004，52（4）：1080-1089.

[6]Li W M，Hsia C H，Chiang J S.Memory-efficient architecture of 2-D dual-mode discrete wavelet transform using lifting scheme for motion-JPEG2000[C]//ISCAS 2009.Taipei，China：IEEE，2009：750-753.

[7]陳旭昀，周汀，閔昊.二維DWT/IDWT處理器的VLSI設(shè)計[J].電子學(xué)報，1997，25（2）：29-32.

[8]孟軍，魏同立，吳金，等.數(shù)字圖像離散小波變換的原理與硬件實(shí)現(xiàn)分析[J].東南大學(xué)學(xué)報：自然科學(xué)版，2002，32（6）：842-847.

[9]熊承義，田金文，柳健.一種基于提升算法的小波濾波器硬件結(jié)構(gòu)設(shè)計[J].華中科技大學(xué)學(xué)報：自然科學(xué)版，2003，31（9）：82-83.

[10]陳大科，韓九強(qiáng).5/3提升小波變換及逆變換的FPGA設(shè)計方法[J].東南大學(xué)學(xué)報：自然科學(xué)版，2005，35（SupII）：211-214.

[11]趙楠楠，孫紅星，徐心和.改進(jìn)的基于提升格式的DWT硬件實(shí)施方案[J].東北大學(xué)學(xué)報：自然科學(xué)版，2006，27（6）：606-609.

[12]曹鵬，王超，李杰.一種高效的多級遞歸提升離散小波變換VLSI架構(gòu)[J].應(yīng)用科學(xué)學(xué)報，2007，25（5）：475-480.

[13]郝燕玲，劉營.改進(jìn)的離散小波變換流水線VLSI結(jié)構(gòu)[J].華中科技大學(xué)學(xué)報：自然科學(xué)版，2008，36（12）：8-11.

[14]王巍，杜治蕓，曾勇.9/7提升小波變換圖像處理算法的高速FPGA實(shí)現(xiàn)[J].微電子學(xué)，2009，39（6）：852-856.

[15]曹鵬，王超.高性能低存儲的2維離散小波變換架構(gòu)[J].中國圖象圖形學(xué)報，2009，14（11）：2198-2204.

[16]高志榮，熊承義.提升小波變換的并行處理與高速實(shí)現(xiàn)[J].光電工程，2009，36（8）：112-122.