整數(shù)提升小波的算法分析及FPGA實現(xiàn)

1 引　言

小波變換是近幾年發(fā)展起來的一門數(shù)學(xué)理論和工具.由于它具有良好的時頻局部特性和多分辨率分析特性,因而在現(xiàn)代信號處理,特別是在圖像數(shù)據(jù)壓縮和處理中得到了廣泛的應(yīng)用.新一代靜止圖像壓縮標(biāo)準(zhǔn)JPEG2000也將小波變換納入標(biāo)準(zhǔn)之中,并采用二維離散小波變換(2D,DWT)作為系統(tǒng)編碼算法的核心.

二維離散小波變換最有效的實現(xiàn)方法之一是采用Mallat算法,通過在圖像的水平和垂直方向交替采用低通和高通濾波實現(xiàn),如圖1所示.這種傳統(tǒng)的基于卷積的離散小波變換計算量大,計算復(fù)雜度高,對存儲空間的要求高,不利于硬件實現(xiàn).提升小波的出現(xiàn)有效地解決了這一問題.提升算法相對于Mallat算法而言,是一種更為快速有效的小波變換實現(xiàn)方法,被譽(yù)為第2代小波變換.它不依賴于傅立葉變換,繼承了第1代小波的多分辨率特征,小波變換后的系數(shù)是整數(shù),計算速度快,計算時無需額外的存儲開銷.Daubechies已經(jīng)證明,任何離散小波變換或具有有限長濾波器的兩階濾波變換都可以被分解成為一系列簡單的提升步驟,所有能夠用Mallat算法實現(xiàn)的小波,都可以用提升算法來實現(xiàn).

本文引用地址：http://www.ex-cimer.com/article/201706/349397.htm
2 提升算法

對信號進(jìn)行離散小波變換就是用多分辨率的形式分解信號，消除信號間的相關(guān)性。在每層分解信號都是用小波信號分解為高頻段信號和低頻段信號，即分別由相應(yīng)的高通濾波器和低通濾波器來獲得。提升方法是實現(xiàn)這些濾波運(yùn)算的一個有效方法，而且方法相當(dāng)簡單。它使用基本的多項式插補(bǔ)來獲取信號的高頻分量，然后通過構(gòu)建尺度函數(shù)來獲取信號的低頻分量。每一步提升包含個步驟分解，預(yù)測和更新.如圖2所示.

分解

分解就是把信號at-1，分為偶數(shù)抽樣點(diǎn)at，和奇數(shù)抽樣點(diǎn)dt，這也稱為懶小波變換(Lazy Wavelet Transform)。設(shè)信號at-1為有限長度的一維離散輸入序列，它們之間存在一定的相關(guān)性。為了消除相關(guān)性，首選把信號at-1分解為兩個子信號at和dt。一般來說，對于信號分解的形式、兩個子信號的大小等，沒有什么特別的限制，但要求存在某一與分解相對應(yīng)的算子，可以從子信號at和dt，還原到at-1，這是離散小波變換和子帶編碼中最基本的要求，是由完全重構(gòu)性質(zhì)所決定的。在離散小波變換和子帶編碼中常用的是二通道向下抽樣(Downsampling)，也就是把信號at-1分解為偶數(shù)采樣點(diǎn)at，和奇數(shù)抽樣點(diǎn)dt。這個變換實際上什么也沒做，對信號表示形式也沒什么改進(jìn)，但這是后面步驟的基礎(chǔ)，所有的二進(jìn)小波變換都是從這一步開始的。

預(yù)測

預(yù)測也被稱對偶提升(Dual Lifting)，就是由at預(yù)測dt，用預(yù)測誤差代替dt，
dt?dt-P(at)
at-1之間存在一定的相關(guān)性，故可以從at估計dt，令dt=P(at)這就是預(yù)測。也可以說，是將at作為at-1的近似值。若信號之間的相關(guān)性很大，那么預(yù)測效果會很好，將at作為at-1的近似表示不會“丟失”很多信息。這就意味著可以“扔掉”部分信息，即dt，以達(dá)到簡練表示的目的。為了完全重建信號at-1，就只能“扔掉”包含在dt中的關(guān)于at的那部分信息，即可用dt-P(at)代替dt，既達(dá)到消除相關(guān)性的目的，也能保證存在某種逆算子，可以重建信號at-1。

更新

更新又稱為主要提升(Primal Lifting)，即用dt更新at，
at?at+U(dt)
預(yù)測后得到的這樣一種新的表示形式中，很可能會丟失信號的某些特征，如信號的均值，而這正是我們所期望的如對信號進(jìn)行壓縮時。為了恢復(fù)這些特征，在提升算法中又引入了另外一種操作一一更新(U)，即用新得到的dt來更新at.

圖3 提升算法的數(shù)據(jù)相關(guān)性

如圖3所示,提升方法可以實現(xiàn)原位運(yùn)算,即該算法不需要除了前級提升步驟的輸出之外的數(shù)據(jù),這樣在每個點(diǎn)都可以用新的數(shù)據(jù)流替換舊的數(shù)據(jù)流.當(dāng)重復(fù)使用原位提升濾波器組時,就獲得了交織的小波變換系數(shù).由于小波變換需要較大的計算量,且計算復(fù)雜度高,靠軟件實現(xiàn)無法滿足實用需要,其硬件實現(xiàn)日益受到重視.其中,基于FPGA的小波變換及編碼方法一直是研究的熱點(diǎn).

3．算法分析

內(nèi)存需求分析

對任何設(shè)計來說，我們都希望所耗的內(nèi)存越小越好。針對這點(diǎn)，在整數(shù)小波變換的設(shè)計中，首先要考慮到的就是整數(shù)小波系數(shù)的動態(tài)范圍，因為它直接決定內(nèi)部存儲器的字寬，在存儲器數(shù)量一定的情況下也就決定了所有存儲器的容量。

以整數(shù)5/3小波變換為例，設(shè)輸入信號為8位無符號數(shù)。那么沿行進(jìn)行計算時，最大的可能值為255，最小可能值為-255，故細(xì)節(jié)值d的最壞狀態(tài)必須用S9(表示9位有符號數(shù).對一個J級分解的小波變換來說，為了能一致的表示所有小波系數(shù)，內(nèi)部存儲器字的位寬必須滿足最壞的情況(就是在第J級的字長)，這個字長就是S(8+2J)。例如，個J=4級的分解需要S16來表示得到的小波系數(shù)。

邊界延拓處理

小波變換中，必須對原始圖像分塊邊界數(shù)據(jù)進(jìn)行對稱周期性延拓。設(shè)有信號ABCDEFGH，則延拓過程 如圖4所示

圖4 對稱周期數(shù)據(jù)延拓過程

如果將對原始圖像邊界數(shù)據(jù)的對稱周期延拓作為單獨(dú)的模塊獨(dú)立于小波變換模塊之外，將增加存儲器的數(shù)量和讀寫操作，增大硬件的面積。因此文獻(xiàn)[1]提出了一種將對稱周期延拓與小波變換模塊完全結(jié)合在一起的針對5／3小波變換的算法，文獻(xiàn)[2]又對該算法進(jìn)行了一定的改進(jìn)，使該算法在硬件實現(xiàn)時有更低的計算復(fù)雜度。該算法采用分段函數(shù)表示，用以將邊界延拓過程內(nèi)嵌于小波變換模塊中，分為3個階段：1)起始階段， 2)長時間的正常運(yùn)行階段，中間數(shù)據(jù)的處理；3)結(jié)束階段，處理右端數(shù)據(jù)，奇、偶數(shù)序號信號結(jié)束分別。

算法改進(jìn)

針對上面的改進(jìn)算法[2]，我們設(shè)計了一個5／3小波變換FPGA硬件結(jié)構(gòu)，如圖5。將預(yù)測系數(shù)改為正，預(yù)測部分加改為減，采取直接運(yùn)算，降低運(yùn)算復(fù)雜度；采取增加控制狀態(tài)，復(fù)用正常計算時的硬件結(jié)構(gòu)。很明顯，這種改進(jìn)的“內(nèi)嵌延拓提升小波變換”FPGA硬件結(jié)構(gòu)與文獻(xiàn)[1]比較，每行(每列)減少二個額外的硬件運(yùn)算模塊，降低了計算復(fù)雜度。對圖像的小波壓縮處理來說，提高了運(yùn)算速度和硬件芯片的利用率，同時降低功耗。

4．FPGA實現(xiàn)

根據(jù)以上的論述，我們設(shè)計以如下的實現(xiàn)方案，如圖5所示。

圖5 整數(shù)小波硬件系統(tǒng)結(jié)構(gòu)
5 性能分析

我們采用FPGA為Xilinx公司生產(chǎn)的 Virtex2-Pro 系列XC2VP30，所需要的資源如表1所示。
表1 整數(shù)小波變換占用FPGA資源

6 展望

如果采用更高系列的FPGA芯片， 無疑會達(dá)到更高的處理速度，但性價比是工程中考慮的一個重要因素。隨著FPGA內(nèi)部集成了越多越多的功能，用FPGA實現(xiàn)復(fù)雜運(yùn)算會受到人們越來越多的青睞。