二維翻轉結構9/7離散小波逆變換研究與VLSI實現

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

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

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

1 引言

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

（1）系數伸縮：

（2）一級提升：

（3）二級提升：

（4）數據輸出：

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

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

2 翻轉結構IDWT

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

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

（1）系數伸縮：

（2）一級翻轉

（3）二級翻轉：

（4）數據輸出：

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

3 VLSI設計

3.1 系統架構

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

3.2 行方向逆變換核

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

圖1 整體處理架構

圖2 一級翻轉結電路原理

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

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

3.3 列方向逆變換核

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

圖4 數據緩存模塊處理流程

4 實驗分析

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

表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]孟軍，魏同立，吳金，等.數字圖像離散小波變換的原理與硬件實現分析[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實現[J].微電子學，2009，39（6）：852-856.

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

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