整數提升小波的算法分析及FPGA實(shí)現

1 引　言

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

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

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

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

分解

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

預測

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

更新

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

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

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

3．算法分析

內存需求分析

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

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

邊界延拓處理

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

圖4 對稱(chēng)周期數據延拓過(guò)程

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

算法改進(jìn)

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

4．FPGA實(shí)現

根據以上的論述，我們設計以如下的實(shí)現方案，如圖5所示。

圖5 整數小波硬件系統結構
5 性能分析

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

6 展望

如果采用更高系列的FPGA芯片， 無(wú)疑會(huì )達到更高的處理速度，但性?xún)r(jià)比是工程中考慮的一個(gè)重要因素。隨著(zhù)FPGA內部集成了越多越多的功能，用FPGA實(shí)現復雜運算會(huì )受到人們越來(lái)越多的青睞。