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

1.阜陽師范學院 計算機與信息學院，安徽 阜陽 236037

2.東南大學 毫米波國家重點實驗室，南京 210096

1 引言

二維9/7離散小波變換（Discrete Wavelet Transform，DWT）與逆變換（Inverse Discrete Wavelet Transform，IDWT）以優(yōu)越的顯示效果、良好的壓縮比、多分辨率等特性而廣泛應用于各類圖像處理中。傳統(tǒng)上，離散小波變換通過卷積實現(xiàn)，Daubechies和Sweldens提出了離散小波變換的提升結構[1-2]，極大地降低了計算量與復雜度。以9/7離散小波逆變換為例，其實現(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）先沿著行方向進行一維IDWT，再沿著列方向完成二維IDWT。盡管提升結構9/7離散小波逆變換通過一組加法與乘法實現(xiàn)，極大地降低了算法復雜度，但隨著高清圖像實時處理、編解碼的廣泛應用，對計算過程中的內存消耗、計算速率提出了更高要求。國外文獻[3-6]也是以此研究方向，先后從算法優(yōu)化、電路結構等方面展開了優(yōu)化，但效果有限，沒有實現(xiàn)性能的綜合提升。國內的眾多研究結構也就該領域展開了一系列的研究[7-16]。

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

2 翻轉結構IDWT

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

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

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

（2）一級翻轉

（3）二級翻轉：

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

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

3 VLSI設計

3.1 系統(tǒng)架構

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

3.2 行方向逆變換核

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

圖1 整體處理架構

圖2 一級翻轉結電路原理

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

圖3 完整的兩級翻轉結構變換過程

3.3 列方向逆變換核

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

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

4 實驗分析

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

表1 性能分析

5 總結

本文研究了一種新的翻轉結構二維9/7離散小波逆變換，并綜合了流水線技術與并行技術，設計了一種高性能的VLSI結構，以滿足高清實時圖像處理的需要。

[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設計[J].電子學報，1997，25（2）：29-32.

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

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

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

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

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

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

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

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

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