基于FPGA的5/3提升小波優化算法

陳占良，金龍旭，陶宏江，韓雙麗，張 敏

(1. 中國科學院長 春光學精密機械與物理研究所，吉林 長春 130033； 2.中國科學院大學，北京 100049)

基于FPGA的5/3提升小波優化算法

陳占良1，2，金龍旭1，陶宏江1，韓雙麗1，張 敏1，2

(1. 中國科學院長 春光學精密機械與物理研究所，吉林 長春 130033； 2.中國科學院大學，北京 100049)

為了實現線陣CCD空間相機圖像的實時壓縮處理，在提升算法的基礎上，提出了一種適用于FPGA的二維提升小波變換結構與實現方案。該系統利用FPGA片內的存儲資源，采用乒乓操作實現了行列變換之間的數據緩存傳輸，降低了功耗，提高了硬件利用率和運算速度。并且為了適應硬件實現速度，在進行小波邊界處理時不需要額外的邊界延拓過程，很大程度上降低了算法的復雜度；整個模塊采用verilog HDL語言進行設計，并在QuestaSim下進行了仿真試驗。實驗結果表明，該系統工作穩定可靠，完全滿足實時處理的要求，并適用于JPEG2000的多級二維5/3小波變換。

實時壓縮；提升算法；流水線結構；5/3小波變換；FPGA

離散小波變換是由Mallat提出的作為圖像壓縮的有效手段[1]，它是一種可以把信號分解為包括時間和頻率信息的多種子帶的變換，因此可以看作是一種多分辨率的信號處理方法[2]。在圖像數據壓縮中，離散小波變換使能量集中，并且在低比特率時能夠實現更好的壓縮效果[3-5]。

傳統的小波變換都是通過卷積進行運算的，在此過程中需要復雜的加乘運算，硬件實現困難并且會耗費大量的寄存器資源。在提升算法的基礎上提出的離散小波變換[6-7]有效地解決了傳統小波變換的缺點，使小波變換的硬件實現成為可能，并且成為了圖像壓縮標準JPEG2000的基本算法[8-9]。本文在提升小波算法的基礎上，基于流水線結構提出了一種多級5/3二維離散小波變換的FPGA實現方案。在遙感圖像的實時處理過程中，線陣CCD空間相機采用推掃成像模式，所以CCD輸出的圖像格式是以行為單位實時輸出的。本系統為了適應這種數據結構，并且達到實時處理的效果，提出了一種基于提升算法的二維小波變換結構，并且在ISE和QuestaSim下進行綜合、仿真分析，達到了理想的運算速度和合理的資源利用。

1 提升小波變換算法原理

快速小波變換——Mallat算法是在多分辨率理論的基礎上提出的，使小波分析理論得到了廣泛的應用。Mallat算法如下

(1)

(2)

Mallat算法中存在大量的卷積運算，為了暫存中間結果，在硬件實現過程中就需要大量的存儲單元，實現過程復雜。小波提升變換算法不依賴于傅里葉變換，從而不存在卷積運算，而是采用了預測、更新的方法來簡化運算過程。在此過程中，復雜的卷積運算被簡單的加減、移位運算代替，降低了計算量和復雜程度，運算效率提高了一倍，這都有利于硬件的實現和資源的節省。提升小波算法的實現包括分解(split)、預測(predict)、更新(update)3個步驟[10]，分別產生高頻分量和低頻分量。其中，高頻分量表示圖像的細節信息，低頻分量表示圖像背景等大尺度信息，提升小波變換結構如圖1所示。

圖1 提升小波變換

2 二維5/3提升小波變換的FPGA實現原理及系統結構

在5/3提升小波算法中以加減運算為主，伴有少量的除法運算，但也只是簡單的除以2或者除以4的計算，在二進制的計算過程中右移一位或者兩位即可，在硬件中移位運算很容易實現，因此采用FPGA來實現小波變換具有可行性。現在使用的高密度FPGA一般具有幾萬到幾百萬不等的門電路，以及豐富的EDA工具，為FPGA的開發、布局布線和綜合仿真提供了充足的邏輯資源和良好的開發環境。

圖3 串行流水線結構的提升小波變換電路結構

圖4 一維5/3提升小波算法步驟

2.1 針對線陣CCD的二維離散小波變換實現方案

針對CCD是以行為單位輸出圖像的，為了達到圖像的實時處理效果而不存在數據等待時間，提出了如圖2所示的二維離散小波變換。該變換采用串行的流水線結構，一次可實現一級的二維小波變換。該結構包括小波變換模塊和片內存儲器模塊，小波變換模塊是對數據進行小波提升變換，片內存儲器模塊用來存儲小波變換的中間結果。該小波變換分解得到4個子帶頻率，其中HH1、HL1、LH1用于后續的編碼運算，而LL1直接輸入下一級的小波變換中；輸入到下一級的LL1頻帶數據當作行數據繼續進行小波變換，得到的HH2、HL2和LH2同樣用于后續的編碼運算，而LL2輸出作為下一級小波變換的數據。

圖2 二維提升小波變換結構

依此循環進行，直到滿足相應的小波級數要求[11]。這種結構數據流清晰，把主要精力放在數據的控制方面便可實現多級的二維小波變換結構。

2.2 5/3小波變換的邊界處理

一維5/3提升小波變換的算法如下

(3)

(4)

小波變換公式的邊界條件要求圖像是無限長的輸入序列，但是圖像數據均由有限的行和列構成。在JPEG2000的標準協議的邊界處理的方法是將數據周期對稱延拓[12]，但是在對CCD產生的行數據進行實時處理時，周期對稱延拓就意味著要產生多余的等待時間，在一定程度上會影響圖像壓縮的效率。因此，本文采用流水線的結構，嚴格控制數據路徑，避免了對每行數據進行周期對稱延拓，從而在一定程度上提高了運算速度。基于串行流水線結構的一維提升小波電路結構示意圖如圖3所示。根據行使能信號是否有效以及時序要求嚴格控制每個寄存器的數據傳輸，并且在適當的時序點使相應的寄存器數據為零，這樣就有效地控制了邊界數據的小波運算，而不必進行周期對稱延拓邊界數據，得到一維5/3小波提升步驟，如圖4所示。

2.3 5/3提升小波變換的FPGA實現結構

要想進行小波變換，首先進作數據分解。數據分解的方式有很多種，最簡單的就是采取奇、偶分解。對行數據進行數據分解的過程中，為了節省時鐘資源和保證信號的同步性，本文放棄使用時鐘分頻單元對時鐘信號進行分頻、倍頻操作，取而代之的是附加一個有效信號(valid)來決定寄存器數據的傳輸。這樣既保證了多級小波變換信號間的同步性，同時以豐富的寄存器資源代替了片內有限的時鐘資源，有利于片內資源的合理利用。

圖3所示的電路結構可進行行提升小波變換。在行提升小波變換中，輸入的CCD圖像數據經過數據分解模塊之后，得到的偶數序列和奇數序列同時輸入到行小波變換模塊中，在邊界處理部分中，沒有進行數據的周期對稱延拓，而是選擇了嚴格控制數據流，使用圖4所示的小波提升算法步驟，避免了數據的等待時間，提高了運算速度。

由圖2可知，列提升小波變換的輸入是行提升小波變換結果的輸出，本文采用的列提升小波變換的結構是以兩行數據同時輸入為基準，而行變換的輸出為同步的高頻和低頻數據，且實際只是列變換中的一行數據。因此，在行變換與列變換之間用寄存器來緩沖數據，以此達到兩行數據同時輸出的效果。為了提高數據的處理速度，緩沖寄存器采用片內的塊RAM結構來實現。本文采用3個線性RAM結構，以乒乓操作來實現數據的緩存傳輸，其結構示意如圖5所示。

圖5 數據緩存輸出結構示意圖

如圖5所示，數據的緩沖輸出分為3個階段：

階段①，由行變換產生的高頻HP1、低頻LP1信號分別緩存在BRAM1和BRAM2中。

階段②，BRAM1輸出階段①中存儲的低頻信號LP1，同時BRAM3緩存行變換產生的高頻信號HP2，行變換產生的低頻信號LP2與LP1信號同時輸出，構成兩行數據中的前部分。

階段③，BRAM2和BRAM3分別輸出在階段①和階段②中緩存的高頻信號HP1和HP2，與階段②中的低頻信號LP1和LP2共同組成完整的兩行信號，此時下一行變換的高頻HP3、低頻LP3信號分別緩存在BRAM1和BRAM2中，此過程重復下去，直到完成數據緩存傳輸。

該緩存傳輸結構中用到的存儲器是片內的塊RAM，每個緩存器的長度為行數據的一半，利用乒乓操作，在速度與面積之間得到了很好的折中，合理利用了FPGA內部的寄存器資源。

列提升小波變換的算法步驟類似于圖4所示，由于采用的是每次輸入兩行行數據，因此要完成列小波變換就需要等待其他行數據的輸入，為此引入了緩存器用作緩存處理中間數據，本文提出的列提升小波變換電路結構如圖6所示。

圖6 列提升小波變換電路結構

3 仿真實驗分析與結果

為了測試和仿真本算法的可行性，采用單行輸入雙行并行輸出的格式信號在QuestaSim下仿真，圖像數據大小為 16×16×16 bit，為了防止在運算過程中數據溢出，以及提高運算精度，在運算過程中采用20 bit的補碼運算。采用本文提出的一級二維5/3小波變換結構進行時序仿真，得到的仿真波形如圖7所示。

圖7 二維小波變換仿真波形圖(截圖)

選用Xilinx公司的FPGA Spartan6系列的xc6slx45t-3，用ISE進行綜合得到一級二維小波變換的最大時間頻率為230 MHz，資源占用情況如表1所示。

表1 資源占用情況

為了實現五級小波變換，只需要將一級小波變換模塊簡單處理就能實現，并且在占用相同的邏輯資源的情況下使用的片內RAM為上一級的一半，減少了資源的使用量。

將本文提出的二維提升小波變換結構與文獻 [13]提出的二維小波提升結構在使用資源和運算速度之間進行對比，如表2所示。從表中可以看出，當圖像數據大小為256×256時，本文提出的結構所用的寄存器資源偏大，但當圖像數據大小為512×512時，本文提出的結構所用的寄存器資源明顯減少。主要是因為本文的圖像像素大小是20 bit的定點數計算，而文獻[13]的圖像像素大小是13 bit，并且本文結構使用了更少的存儲器資源。而且可以看出，本文提出結構的運算速度明顯高于文獻[13]的運算速度。

表2 使用資源和運算速度的對比

4 總結

本文討論了用FPGA實現5/3提升小波變換的實現方法，根據線陣CCD成像的輸出特點，提出了基于流水線的串行二維小波變換結構，適用于圖像的實時處理過程。試驗結果表明，提出的二維提升小波變換合理地解決了資源占用和運算速度的問題。本文只針對一級小波變換進行分析實驗，但是多級變換僅僅是結構的復制與級聯，因此本文提出的結構能夠很好地實現多級小波變換，并適用于JPEG2000的多級二維5/3小波變換。

[1] MALLAT S. Theory for multiresolution signal decomposition： the wavelet representation[J]. IEEE Trans. Pattern Anal. and Machine Intel， 1989，11(7)：674-693.

[2] 劉平，王磊，郭中華，等. 基于小波變換的邊緣保留圖像去噪改進算法[J]. 電視技術，2014，38(5)：13-15.

[3] AZAWI S， BOUSSAKTA S， YAKOVLEV A. Performance improvement algorithms for colour image compression using DWT and multilevel block truncation coding[C]//Proc. 7th International Symposium on Communication Systems Networks and Digital Signal Processing (CSNDSP).[S.l.]：IEEE Press，2010：811-815.

[4] AL-AZAWI S， BOUSSAKTA S， YAKOVLEV A. Image compression algorithms using intensity based adaptive equantization coding[J]. American Journal of Engineeringand Applied Sciences， 2011(4)：504-512.

[5] AL-AZAWI S， BOUSSAKTA S， YAKOVLEV A. High precision and low power DCT architectures for image compression applications[C]//Proc. IET Conference on Image Processing (IPR). [S.l.]：IEEE Press，2012：1-6.

[6] DAUBECHIES I，SWELDENS W. Factoring wavelet transforminto lifting steps[J]. Fourier Analysis and Applications， 1998，4：247-269.

[7] 鐘艷華. JPEG2000中DWT的VLSI結構設計[D]. 長沙：國防科學技術大學，2010.

[8] SKODRAS A， CHRISTOPOULOS C， EBRAHIMI T. The JPEG 2000 still image compression standard[J]. IEEE Signal Processing Magazine， 2001(18)：36-58.

[9] SKODRAS A N， CHRISTOPOULOS C A， EBRAHIMI T. JPEG2000： the upcoming still image compression standard[J]. Pattern Recognition Letters， 2001，22：1337-1345.

[10] 張立保，丘兵昌. 基于快速方向預測的高分辨率遙感影像壓縮[J]. 光學精密工程，2013(8)：2095-2102.

[11] 王建軍，劉波. 適于硬件實現的無損圖像壓縮[J].光學精密工程，2011(4)：922-928.

[12] TAN K C B， ARSLAN T. Low power embedded extension algorithm for lifting-based discrete wavelet transform in JPEG2000[J]. Electronics Letters， 2001， 37(22)： 1328-1330.

[13] AL-AZAWI S， ABBAS Y A ， JIDIN R. Low complexity multidimensional CDF 5/3 DWT architecture[C]//Proc. 9th International Symposium on Communication Systems Networks & Digital Sign (CSNDSP). [S.l.]：IEEE Press，2014：804-808.

陳占良(1990— )，碩士生，主研圖像壓縮和存儲；

金龍旭(1965— )，博士，研究員，主研光電成像與圖像處理；

陶宏江(1981— )，碩士，助理研究員，主研嵌入式系統和圖像處理；

韓雙麗(1968— )，女，副研究員，主研空間光學遙感器熱控制技術；

張 敏(1990— )，女，博士生，主研光電成像與圖像處理。

責任編輯：閆雯雯

Optimization Algorithm of 5/3 Lifting Wavelet Based on FPGA

CHEN Zhanliang1，2， JIN Longxu1，TAO Hongjiang1，HAN Shuangli1，ZHANG Min1，2

(1.ChangchunInstituteofOptics，FineMechanicsandPhysics，ChineseAcademyofSciences，Changchun130033，China；2.UniversityofChineseAcademyofSciences，Beijing100049，China)

In order to implement the real-time image data compression processing for line CCD space camera， a new method for lifting wavelet transform is proposed， which is based on the lifting algorithm structure. By using the abundant on-chip memories and ping-pong scheme， it can implement the data transmission between row transform and column transform. The method can reduce the power and enhance the speed of computation. It abandons the symmetric extension on the boundary， which can reduce the complexity of computation. The module is designed by verilog HDL， simulated by Questasim. The results indicate that the system can work steadily， and it is reasonable to implement real-time processing and multilevel 2-D 5/3 wavelet transform.

real-time compression； lifting algorithm； pipeline； 5/3 wavelet transform； FPGA

【本文獻信息】陳占良，金龍旭，陶宏江,等.基于FPGA的5/3提升小波優化算法[J].電視技術,2015，39(11).

TP391

A

10.16280/j.videoe.2015.11.026

2015-01-06