一種高效的三維DWT VLSI結構設計方法

高濤，白璘

（長安大學 信息工程學院，陜西 西安 710064）

小波變換以其優異的時頻局部特性以及良好的去相關能力，在信號檢測，噪聲消除，圖像處理等領域中得到了廣泛的應用。由于三維小波變換（3D DWT）可以同時去除空間域和時間軸上的冗余度，因此廣泛應用于視頻壓縮，多/高光譜圖像壓縮，圖像融合等領域。傳統的離散小波變換多采用卷積算法，需要復雜的計算和大量的存儲空間，不利于高速和低功耗的硬件實現。Daubechies等人提出的提升算法（Lifting Scheme），大幅減少了小波變換的計算復雜度，其計算復雜度約是傳統卷積算法的一半。小波變換的VLSI設計與實現，尤其是三維小波變換的硬件設計，近幾年剛剛起步，是當今研究小波變換的一個熱門課題[1-4]。

現有的有關三維DWT的VLSI設計文獻中，采用Mallat算法的一般需要大量乘法器，成本較高；而基于提升方案的三維小波變換占用的芯片資源少。作者采用并行化技術，設計并實現了一種快速高效的3D DWT硬件架構。序列圖像首先經過時間維Harr小波變換，然后再經過基于行的 （Linebased）提升結構二維DWT變換，從而完成序列圖像的三維小波變換[5-7]。本文使用Verilog HDL對系統結構進行了描述，利用Modelsim6.1f軟件平臺進行仿真試驗。該模塊可作為視頻編碼器的核心模塊嵌入到視頻編碼器中。

1 三維DWT核心算法

三維小波變換實現方法通常有兩種。一種是利用可分離濾波器，先對空間的行和列進行變換，從而獲得代表原序列圖像不同時間和空間頻率特性的子帶圖像，即將二維小波變換的Mallat算法推廣到三維。對時間低頻、空間低頻的子帶信號重復進行分解即可完成多級三維小波變換。以視頻編碼為例，采用此種小波變換方式時，時間維的圖像幀數不能隨意選取，必須根據三維小波變換的級數確定。如進行4級三維小波分解則至少必須存儲16幀圖像才可滿足變換要求。隨著變換級數的增加，需要大量的存儲空間來存儲多幅圖像并且導致編碼延遲增加。另一種三維小波變換的實現方式是將序列圖像時間一維變換和空間二維變換分開進行，即先對序列圖像在時間維按一維小波變換的方法進行分解，獲得代表不同時間頻率特性的時間子帶圖像。然后，再對各時間子帶圖像利用于基于行的提升結構二維DWT變換進行分解，從而得到代表原圖像不同時間和空間頻率特性的子帶圖像。采用這種三維小波變換方式由于時間維小波變換和空間二維小波變換各自獨立進行，因此可以根據需要選取時間方向的圖像幀數，在編碼性能和編碼延時之間找到一個適當的折中。本文設計的三維小波變換模塊讓序列圖像首先經過時間維Harr小波變換，然后再經過基于行的（Line-based）提升結構二維DWT變換，從而完成序列圖像的三維小波變換。

對于空間二維圖像的小波變換，一般處理方法是直接法和卷積算法，即先對圖像的行（列）進行濾波變換，再存儲行（列）處理的中間結果，然后進行列（行）濾波變換，這需要N2/2存儲空間，增加了計算量和硬件消耗。而基于行的濾波結構減少了行列變換之間的中間緩存，實現行變換和列變換的并行處理。本文采用一種基于行的提升9/7小波濾波器對harr小波變換后的子帶圖像進行空間2維小波變換。

提升算法的基本原理是歐幾里德算法把濾波器多相矩陣分為多個三角陣相乘，這樣通過矩陣的乘法來實現濾波。對于9/7小波，一維離散小波變換的實現包括6個步驟。其中，step1到step4為提升步驟，包括2個預測和2個更新操作，每個提升步驟根據 3 個輸入（x2n-1，x2n，x2n+1）產生一個輸出（y2n）；step5 和 step6 為規整化（Scaling）步驟。 信號長度的有限性導致了小波濾波器處理信號的邊界效應，為了消除小波重構圖像的邊界效應，本文采用信號的對稱擴展法，如圖1虛線所示部分。由于對稱擴展的點和原圖像數據計算相同，可以采用多路器為加法器的2個輸入端選擇與已更新點相同的值。假設為輸入數據，為小波系數，則9/7小波的變換方程如下：

圖1 9/7小波變換示意圖Fig.1 Figure of 9/7 wavelet translation

預測 P1：Y2n+1=X2n+1+α（X2n+X2n+2）

更新 U1：Y2n=X2n+β（Y2n-1+Y2n+1）

預測 P2：Y2n+1=X2n+1+γ（Y2n+Y2n+2）

更新 U2：Y2n=Y2n+δ（Y2n-1+Y2n+1）

規整 G1：Y2n+1=KY2n+1

規整 G2：Y2n=（1/K）Y2n

其 中 α=-1.586 134 342，β=-0.052 980 118 5，γ=0.882 911 075，δ=0.443 506 852 2，K=1.496 043 98。

若分別對水平和垂直2個方向進行一維小波變換即可實現二維DWT。考慮到對稱邊界處擴展，處于起始邊界的快行方向像素為12個點，以后輸入數據為8個點。在完成5行行濾波輸出數據之后，便可進行列濾波變換。此后，行濾波每處理完2行，將輸出結果更新列濾波所需的5行數據，達到行列方向濾波運算的并行處理。保證小波變換的連續性，需對前一個塊的邊界輸出結果保存起來作為下一個塊的輸入。

在行方向濾波過程中，依次從片外存儲器按水平方向讀取12個數據，對這些數據進行基于一維提升小波變換，可得到 4 個低頻輸出（L0，L1，L2，L4）和 4 個高頻輸出（H0，H1，H2，H4）。重復該過程直到處理完5行數據。為實現一行圖像數據完整的連續小波變換，需用具有讀寫功能的SRAM對每行12個數據處理后的邊界結果進行緩存。

為滿足每個時鐘周期同時讀取兩個輸入數據進行處理，需要用2個SRAM分別存儲R1和R2，總共需要存儲25個數據。

在列方向濾波過程中，所需數據來自行濾波后的結果，只有行濾波變換一定的數據時才能啟動列濾波運算。對于9/7小波變換，一般行濾波需要變換9行數據，由于采用邊界對稱擴展處理故只需5個數據即可進行列濾波。因此，當行濾波在處理完第5行數據后啟動列濾波。在每個時鐘周期，行濾波產生兩個輸出，而列濾波一次處理5個數據，當列濾波處理完 4 列數據（L0，H0，L1，H1）時，行濾波恰好處理完第 6 行數據；列濾波繼續處理后4列數據，此時行濾波恰完成第7行的數據處理。用地6、7行的結果更新原5行中的前兩行數據。再將新的5行數據作為列濾波的輸入，這樣行濾波和列濾波便可保持完全的同步處理。按照上述方法依次處理剩余的圖像數據便可完成一級二維DWT。在一級DWT分解后產生的輸出中，LL數據被寫回片外存儲器以作下一級分解操作，而LH，HL和HH高頻子代則輸出給后續編碼模塊進行處理。

2 算法硬件實現模型

2.1 乘法器設計

由于乘法器占用很大的硬件資源，且鑒于小波濾波器的系數是固定的，本文采用CSD（Canonic signed digit，正則有符號數）乘法器把乘法操作優化為移位寄存器和加法操作。為保證精度，本文采用32位定點數，其中最高位（MSB）為符號位，整數部分為15位，小數部分為16位。將濾波器系數量化為二進制數，如 γ=0.882 911 07510=0.111 000 12，則 X×γ 就可轉化為 X×0.111 000 12=2-1（X+2-1X+2-2X+2-6X）=2-1[（X+2-1X）+2-2（X+2-4X）]。

2.2 核心算法整體硬件架構

三維DWT整體結構框圖如圖2所示。時間維所采用的Harr的計算很簡單，是輸入圖像的均值和差值。因此，時間維的小波變換只涉及到簡單的加法和移位操作，且不需要邊界處理。此外，空間二維小波變換無需等到時間維小波變換完成即可開始。系統從緩存中讀出原始圖像數據，進行時間維Harr小波變換并直接將時間維小波變換的結果作為空間二維小波變換的輸入即可完成三維小波變換。因此，時間維小波變換的結果不需要緩存，而且可以和空間維小波變換并行執行，使硬件實現更加簡便。在實際應用中，可以采用兩組RAM，每組存放連續4幀圖像。在對其中一組RAM圖像進行變換時，另一組則可實時采集現場圖像，對兩組RAM實行乒乓操作，交替存儲和變換就可完成序列圖像的三維小波變換。

圖2 三維DWT結構框圖Fig.2 Structure diagram of 3D DWT

對于空間二維DWT模塊，行濾波和列濾波用于完成所有小波分解操作；存儲模塊包括邊界緩存，行變換結果緩存和列變換結果緩存；地址生成單元產生片內緩存和片外存儲器的地址；控制模塊通過一個有限狀態機實現，開始進入初始狀態，對所有寄存器清零，然后進行行濾波和列濾波處理。二維DWT產生的結果中LL數據被寫回片外存儲器以進行下一級小波分解。

3 仿真實驗結果及分析

基于本文提出的三維小波變換，編寫了其Verilog模型，空間二維小波變換為4級。利用Modelsim6.1f軟件平臺進行仿真，部分仿真波形如圖3所示，其仿真輸出結果與C語言仿真輸出結果相同，表明電路結構設計正確。由于時間維小波變換的結果不需要緩存，按二維DWT結構，所需的存儲空間很小，只需大小為5Nc的片內SRAM，且可實現行列方向小波變換的并行化處理。表1比較了幾種不同結構二維和三維DWT的存儲需求，設輸入單幅圖像大小為Nc×M。部分仿真波形如圖3所示。

表1 DWT的存儲需求比較Tab.1 Comparison of DWT storage requirement

圖3 核心算法部分仿真波形Fig.3 Part simulation waveform of core algorithm

4 結 論

文中提出了一種基于提升方案的易于硬件實現的序列圖像三維小波變換結構。序列圖像首先經過時間維Harr小波變換，然后再經過空間二維小波變換，從而完成整個序列圖像的三維小波變換。設計采用并行化技術，有效減少了片內存儲器的空間容量，行濾波與列濾波變換采用流水線技術，提高了小波變換的速度。該模塊可作為視頻編碼器的核心模塊嵌入到視頻編碼器中。

[1]魏本杰，劉明業，周藝華，等.快速3DDWT核心算法的VLSI并行化設計[J].北京理工大學學報，2006，26（3）:211-215.WEI Ben-jie，LIU Ming-ye，ZHOU Yi-hua，et al.Paralell VLSI design for the fast 3D discrete wavelet transform core algorithm[J].Transactions of Beijing Institute of Technology，2006，26（3）:211-215.

[2]金文光，王國雄，楊崇朋.一種低存儲需求的二維DWT VLSI結構設計方法[J].電路與系統學報，2007，12（3）:131-135.JIN Wen-guang，WANG Guo-xiong，YANG Chong-peng.A method of VLSI architecture design with low memory requirement for 2-D DWT[J].Journal of circuits and systems，2007，12（3）:131-135.

[3]喬世杰，智貴連.一種三維小波序列圖像編碼算法及其FPGA實現[J].電子器件， 2006，29（2）:420-423.QIAO Shi-Jie，ZHI Gui-lian.FPGA implementation of a 3D wavelet video coder[J].Chinese Journal of Electron Devices，2006，29（2）:420-423.

[4]Peng W S，Lee C Y.An efficient VLSI architecture for separable 2D discrete wavelet transform[C]//proc.IEEE Int.Conf.Image Processing，1999:524-527.

[5]Jung G C，Jin D Y，Park S M.An efficient line based VLSI architecture for 2-D lifting DWT[J].Circuit and Systems，2004，2:249-252.

[6]Chang W H， Lee Y S， Peng W S，et al.A line-based，memory efficient and programmable architecture for 2D DWT using lifting scheme[C]//IEEE Int.Symp.on Circuits and Systems，2001:330-333.

[7]Dai Q，Chen X，Lin C.A novel VLSI architecture for multidimensional discrete wavelet transform[J].IEEE Trans.Circuits Systems Video Technol，2004，14 （8）:1105-1110.