一種高效二維小波分解算法的FPGA實現

張傳雨，楊夢達

（1.哈爾濱工業大學 電氣工程系，黑龍江 哈爾濱150001；2.清華大學 交叉信息研究院，北京100084）

在對數字圖像進行多分辨率觀察和處理時，離散小波變換（DWT）是首選的數學工具。小波提升算法[1]作為小波變換的快速實現方法，使濾波過程被分解為幾個提升步驟，運算量大為減少，便于實現即位計算，同時節省了存儲空間，非常適合進行硬件實現。

目前普遍應用的實現二維提升小波變換的硬件架構包括基于幀的硬件架構和基于行的硬件架構[2]。隨著大量相關研究工作[3-5]的不斷進行，新的VLSI架構不斷產生，電路整體性能逐漸提高，但在降低電路控制復雜度和對存儲空間的耗費的兼顧上仍存在不足。本文提出一種直接二維提升小波變換VLSI架構，可有效降低控制電路的復雜度，明顯地節省片上存儲空間，使得設計的電路具有較好的綜合性能。

1 小波提升算法

1.1 提升小波變換

通過提升框架實現小波變換分為三個步驟：分裂、預測和更新[3]。離散情況下，給定輸入的離散信號數據集pk(pk代表序列p中的第k個數)，并將其分為奇數集合和偶數集合，經過完整提升步驟后，分解成數據集sk和dk。其中sk表示尺度系數，dk表示小波系數。以Le Gall 5/3小波為例，1-D整數小波變換分解步驟如圖1所示。

常用的5/3整數小波變換計算公式如下：

式中，pk為原圖像素數據，dk為變換結果高頻成分，sk為變換結果低頻成分。

完成二維變換過程如下：圖像在經過一次行變換后就分成2個子帶(sub-band)；再經過一次列變換后，2個子帶就變成了4個子帶，每個子帶的大小變為原圖1/4；要進行下一級小波變換，只要對LL子帶以同樣先行后列變換的方法處理即可。二級小波變換的原理的示意圖如圖2所示。

由于列變換是沿著列的方向進行，需要把行變換的結果逐列輸入，因此通常需要先對圖像進行行變換，存儲行變換結果，再進行列變換。因此，需要存儲大量的中間結果，增加了硬件的開銷，限制了芯片的數據處理速度。

1.2 二維變換公式的進一步推導

為設計出性能更好的二維變換VLSI架構，將式(2)代入式(1)進行合并：

為實現對一幅圖片二維變換處理，對公式進行進一步推導，設圖片中第i行、第j列數據為pi，j，在進行行變換后得出結果，再將公式應用于豎直方向進行列變換，以兩次低通濾波結果為例，得到如下結果：

將其乘法系數寫成行列式，如圖3(a)所示。

圖3 二維變換乘法系數陣列

同理，為獲得先高通后低通濾波結果HL、先低通后高通濾波結果LH及兩次高通濾波結果HH數據，可將式(1)和式(3)通過同樣的方式應用于二維變換。以行列式方式表達，如圖 3(b)、(c)、(d)所示。

2 架構設計

2.1 整體架構

對于2-D DWT，本文以圖3推導出的公式為基礎，設計直接進行二維變換的提升小波變換實現方式。系統結構框圖如圖4所示。圖像數據從外部存儲器中讀出，經地址拓展單元進行邊界延拓后，寫入緩沖單元；之后將數據送入二維DWT處理模塊，產生4個子帶數據，進行降2采樣后，結果數據送至VGA顯示器進行顯示輸出。系統控制模塊產生各種控制信號約束系統各部分在特定的時序下工作。

2.2 內部結構

在進行數字圖像的二維小波分解過程中，二維變換處理器是核心，它將影響整個系統的時序設計和綜合性能。

通過圖3中給出的參數行列式可以得出結論，二維變換過程實際上是一個5×5的采樣窗口中數據的加權求和，其包含的運算主要為乘法運算和加法運算。

根據圖3中行列式參數二維變換設計處理器具體結構，如圖5所示。

該結構包含15個加法器、18個移位器和34個延遲單元(D)，不再需要額外的乘法器。可以估計，該一維5/3小波變換架構在FPGA中的實現需要占用邏輯單元數量約為40A(A為原始數據位寬)。完成一幅大小為N×N的圖像的L級分解所需時鐘周期數為：

其中，W為除去延時，處理器進行實際運算產生有效數據所需時鐘周期個數；Ld為行變換和列變換之間的延遲。Ld=0，即在此過程中行列變換同時完成，不會產生中間數據，節省了大量片上存儲空間，消除了行列變換的延時。另外，外部存儲器讀取次數有所增加，但處理器工作時間明顯縮短，大大降低了系統總功耗。

3 實驗結果和分析

為對本設計中的二維小波變換架構進行功能驗證并直觀地觀察進行小波分解后的圖像效果，通過ModelSim軟件對處理器模塊進行了仿真，如圖6所示。

表1分別就所需的硬件復雜度、存儲空間占用量、延遲時間以及控制電路的復雜度等方面的性能給出本文設計架構與現存其他二維DWT架構的對比情況。

本文以Le Gall 5/3小波為例，提出了一種直接二維提升小波變換VLSI架構。作為基于行的變換架構的一種改進，該架構具有結構簡單、節省片上存儲空間、靈活性高等優點，為硬件電路實現二維提升小波變換提出了新的思路。純計算邏輯下，其處理速度可達到157.78 MHz。

為對文中提出的架構進行功能驗證，采用Cyclone II系列 FPGA-EP2C35F672C6搭建其硬件電路。通過實驗證實能較好地完成預定的設計功能。

表1 5/3小波二維離散小波變換架構性能比較

[1]SWELDENS W.The lifting scheme：a custom-design construction of biothogonal wavelets[J].Data Compression Conference，1996，3(2)：186-200.

[2]CHRYSAFIS C，ORTEGA A.Line based，reduced memory，wavelet image comperssion[C].IEEE Trans.on Image Processing，Washington，DC，USA，1998：398-407.

[3]ANDRA K，CHAKRABARTI C，ACHARYA T.A VLSI architecture for lifting-based forward and inverse wavelet transform[J].IEEE Trans.Signal Process.，2002，50(4)：966-977.

[4]LIAO H，MANDAL M K，COCKBURN B F.Efficient architectures for 1-D and 2-D lifting-based wavelet transforms[J].IEEE Trans.Signal Process.，2004，52(5)：1315-1326.

[5]BARUA S，CARLETTA J E，KOTTERI K A.An efficient architecture for lifting-based two-dimensional discrete wavelet transform，Integr[J].VLSI J.，2005，38(3)：341-352.

[6]MAAMOUN M，BRADAI R，MERAGHNI A，et al.Low cost VLSI discrete wavelet transform and FIR filters architectures for very high-speed signal and image processing[C].IEEE 9th International Conference on Cybernetic Intelligent Systems，2010：1-6.