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

(1. 中國(guó)科學(xué)院長(zhǎng) 春光學(xué)精密機(jī)械與物理研究所，吉林 長(zhǎng)春 130033； 2.中國(guó)科學(xué)院大學(xué)，北京 100049)

基于FPGA的5/3提升小波優(yōu)化算法

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

(1. 中國(guó)科學(xué)院長(zhǎng) 春光學(xué)精密機(jī)械與物理研究所，吉林 長(zhǎng)春 130033； 2.中國(guó)科學(xué)院大學(xué)，北京 100049)

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

實(shí)時(shí)壓縮；提升算法；流水線結(jié)構(gòu)；5/3小波變換；FPGA

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

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

1 提升小波變換算法原理

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

(1)

(2)

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

圖1 提升小波變換

2 二維5/3提升小波變換的FPGA實(shí)現(xiàn)原理及系統(tǒng)結(jié)構(gòu)

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

圖3 串行流水線結(jié)構(gòu)的提升小波變換電路結(jié)構(gòu)

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

2.1 針對(duì)線陣CCD的二維離散小波變換實(shí)現(xiàn)方案

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

圖2 二維提升小波變換結(jié)構(gòu)

依此循環(huán)進(jìn)行，直到滿足相應(yīng)的小波級(jí)數(shù)要求[11]。這種結(jié)構(gòu)數(shù)據(jù)流清晰，把主要精力放在數(shù)據(jù)的控制方面便可實(shí)現(xiàn)多級(jí)的二維小波變換結(jié)構(gòu)。

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

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

(3)

(4)

小波變換公式的邊界條件要求圖像是無限長(zhǎng)的輸入序列，但是圖像數(shù)據(jù)均由有限的行和列構(gòu)成。在JPEG2000的標(biāo)準(zhǔn)協(xié)議的邊界處理的方法是將數(shù)據(jù)周期對(duì)稱延拓[12]，但是在對(duì)CCD產(chǎn)生的行數(shù)據(jù)進(jìn)行實(shí)時(shí)處理時(shí)，周期對(duì)稱延拓就意味著要產(chǎn)生多余的等待時(shí)間，在一定程度上會(huì)影響圖像壓縮的效率。因此，本文采用流水線的結(jié)構(gòu)，嚴(yán)格控制數(shù)據(jù)路徑，避免了對(duì)每行數(shù)據(jù)進(jìn)行周期對(duì)稱延拓，從而在一定程度上提高了運(yùn)算速度?；诖辛魉€結(jié)構(gòu)的一維提升小波電路結(jié)構(gòu)示意圖如圖3所示。根據(jù)行使能信號(hào)是否有效以及時(shí)序要求嚴(yán)格控制每個(gè)寄存器的數(shù)據(jù)傳輸，并且在適當(dāng)?shù)臅r(shí)序點(diǎn)使相應(yīng)的寄存器數(shù)據(jù)為零，這樣就有效地控制了邊界數(shù)據(jù)的小波運(yùn)算，而不必進(jìn)行周期對(duì)稱延拓邊界數(shù)據(jù)，得到一維5/3小波提升步驟，如圖4所示。

2.3 5/3提升小波變換的FPGA實(shí)現(xiàn)結(jié)構(gòu)

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

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

由圖2可知，列提升小波變換的輸入是行提升小波變換結(jié)果的輸出，本文采用的列提升小波變換的結(jié)構(gòu)是以兩行數(shù)據(jù)同時(shí)輸入為基準(zhǔn)，而行變換的輸出為同步的高頻和低頻數(shù)據(jù)，且實(shí)際只是列變換中的一行數(shù)據(jù)。因此，在行變換與列變換之間用寄存器來緩沖數(shù)據(jù)，以此達(dá)到兩行數(shù)據(jù)同時(shí)輸出的效果。為了提高數(shù)據(jù)的處理速度，緩沖寄存器采用片內(nèi)的塊RAM結(jié)構(gòu)來實(shí)現(xiàn)。本文采用3個(gè)線性RAM結(jié)構(gòu)，以乒乓操作來實(shí)現(xiàn)數(shù)據(jù)的緩存?zhèn)鬏?，其結(jié)構(gòu)示意如圖5所示。

圖5 數(shù)據(jù)緩存輸出結(jié)構(gòu)示意圖

如圖5所示，數(shù)據(jù)的緩沖輸出分為3個(gè)階段：

階段①，由行變換產(chǎn)生的高頻HP1、低頻LP1信號(hào)分別緩存在BRAM1和BRAM2中。

階段②，BRAM1輸出階段①中存儲(chǔ)的低頻信號(hào)LP1，同時(shí)BRAM3緩存行變換產(chǎn)生的高頻信號(hào)HP2，行變換產(chǎn)生的低頻信號(hào)LP2與LP1信號(hào)同時(shí)輸出，構(gòu)成兩行數(shù)據(jù)中的前部分。

階段③，BRAM2和BRAM3分別輸出在階段①和階段②中緩存的高頻信號(hào)HP1和HP2，與階段②中的低頻信號(hào)LP1和LP2共同組成完整的兩行信號(hào)，此時(shí)下一行變換的高頻HP3、低頻LP3信號(hào)分別緩存在BRAM1和BRAM2中，此過程重復(fù)下去，直到完成數(shù)據(jù)緩存?zhèn)鬏敗?/p>

該緩存?zhèn)鬏斀Y(jié)構(gòu)中用到的存儲(chǔ)器是片內(nèi)的塊RAM，每個(gè)緩存器的長(zhǎng)度為行數(shù)據(jù)的一半，利用乒乓操作，在速度與面積之間得到了很好的折中，合理利用了FPGA內(nèi)部的寄存器資源。

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

圖6 列提升小波變換電路結(jié)構(gòu)

3 仿真實(shí)驗(yàn)分析與結(jié)果

為了測(cè)試和仿真本算法的可行性，采用單行輸入雙行并行輸出的格式信號(hào)在QuestaSim下仿真，圖像數(shù)據(jù)大小為 16×16×16 bit，為了防止在運(yùn)算過程中數(shù)據(jù)溢出，以及提高運(yùn)算精度，在運(yùn)算過程中采用20 bit的補(bǔ)碼運(yùn)算。采用本文提出的一級(jí)二維5/3小波變換結(jié)構(gòu)進(jìn)行時(shí)序仿真，得到的仿真波形如圖7所示。

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

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

表1 資源占用情況

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

將本文提出的二維提升小波變換結(jié)構(gòu)與文獻(xiàn) [13]提出的二維小波提升結(jié)構(gòu)在使用資源和運(yùn)算速度之間進(jìn)行對(duì)比，如表2所示。從表中可以看出，當(dāng)圖像數(shù)據(jù)大小為256×256時(shí)，本文提出的結(jié)構(gòu)所用的寄存器資源偏大，但當(dāng)圖像數(shù)據(jù)大小為512×512時(shí)，本文提出的結(jié)構(gòu)所用的寄存器資源明顯減少。主要是因?yàn)楸疚牡膱D像像素大小是20 bit的定點(diǎn)數(shù)計(jì)算，而文獻(xiàn)[13]的圖像像素大小是13 bit，并且本文結(jié)構(gòu)使用了更少的存儲(chǔ)器資源。而且可以看出，本文提出結(jié)構(gòu)的運(yùn)算速度明顯高于文獻(xiàn)[13]的運(yùn)算速度。

表2 使用資源和運(yùn)算速度的對(duì)比

4 總結(jié)

本文討論了用FPGA實(shí)現(xiàn)5/3提升小波變換的實(shí)現(xiàn)方法，根據(jù)線陣CCD成像的輸出特點(diǎn)，提出了基于流水線的串行二維小波變換結(jié)構(gòu)，適用于圖像的實(shí)時(shí)處理過程。試驗(yàn)結(jié)果表明，提出的二維提升小波變換合理地解決了資源占用和運(yùn)算速度的問題。本文只針對(duì)一級(jí)小波變換進(jìn)行分析實(shí)驗(yàn)，但是多級(jí)變換僅僅是結(jié)構(gòu)的復(fù)制與級(jí)聯(lián)，因此本文提出的結(jié)構(gòu)能夠很好地實(shí)現(xiàn)多級(jí)小波變換，并適用于JPEG2000的多級(jí)二維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ìn)算法[J]. 電視技術(shù)，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結(jié)構(gòu)設(shè)計(jì)[D]. 長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，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] 張立保，丘兵昌. 基于快速方向預(yù)測(cè)的高分辨率遙感影像壓縮[J]. 光學(xué)精密工程，2013(8)：2095-2102.

[11] 王建軍，劉波. 適于硬件實(shí)現(xiàn)的無損圖像壓縮[J].光學(xué)精密工程，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— )，碩士生，主研圖像壓縮和存儲(chǔ)；

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

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

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

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

責(zé)任編輯：閆雯雯

Optimization Algorithm of 5/3 Lifting Wavelet Based on FPGA

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

(1.ChangchunInstituteofOptics，F(xiàn)ineMechanicsandPhysics，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

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

TP391

A

10.16280/j.videoe.2015.11.026

2015-01-06