摘? 要: 小波" title="小波">小波分析是信息處理領(lǐng)域的一種重要處理方法,但是小波分解巨大的運(yùn)算量卻嚴(yán)重束縛了其在實(shí)時(shí)處理領(lǐng)域中的應(yīng)用。提出了一種基于FPGA實(shí)現(xiàn)的高速小波分解方法,該方法采用新的小波分解結(jié)構(gòu),使多層分解得以同時(shí)進(jìn)行,從而使小波分解的速度達(dá)到高速輸入圖像的數(shù)據(jù)率;并適當(dāng)選取了數(shù)據(jù)結(jié)構(gòu),使得經(jīng)分解、重構(gòu)" title="重構(gòu)">重構(gòu)后所得圖像的峰值信噪比達(dá)到無窮大。這種方法大大提高了硬件系統(tǒng)進(jìn)行小波分解的速度,在小波分解的性能和硬件實(shí)現(xiàn)的資源消耗上找到了一個(gè)較優(yōu)的結(jié)合點(diǎn)。

　　關(guān)鍵詞: 小波分析? 圖像處理? 圖像壓縮? 實(shí)時(shí)處理? FPGA

?

　　目前,小波分析在許多科學(xué)與工程領(lǐng)域中得到了廣泛研究和應(yīng)用。由其引出的多分辨分析方法,更是成為圖像壓縮、圖像分割、特征提取、語音識(shí)別等方面的一種有力工具。但是,隨著它在實(shí)際工程中應(yīng)用的不斷深入,研究人員發(fā)現(xiàn),在數(shù)據(jù)速率很高的情況下,現(xiàn)有的硬件系統(tǒng)很難承擔(dān)實(shí)時(shí)處理的巨大運(yùn)算量。因此,研究適合硬件實(shí)現(xiàn)的小波分解算法和改進(jìn)小波分解的硬件實(shí)現(xiàn)方法" title="實(shí)現(xiàn)方法">實(shí)現(xiàn)方法,便成為小波分析應(yīng)用于工程實(shí)際的兩大關(guān)鍵課題。

　　本文將闡述一種基于FPGA(現(xiàn)場(chǎng)可編程邏輯陣列)芯片實(shí)現(xiàn)的高速圖像小波分解方法,較好地解決了運(yùn)算量大和要求實(shí)時(shí)處理的矛盾。

1 二維小波分解和重構(gòu)算法

1.1 Mallat算法

　　當(dāng)前,在小波分析的研究領(lǐng)域,通常采用多分辨分解和合成的金字塔算法,即Mallat算法。Mallat算法的基本思想是:將一個(gè)分辨率為1的原始信號(hào)F(n)進(jìn)行N層分解,分解成一個(gè)分辨率為2^-N的低頻信號(hào)和一系列高頻信號(hào)。其流程如圖1所示。

?

?

　　分解算法的公式如下:

　　重構(gòu)算法是分解過程的逆過程,經(jīng)過逆濾波就能恢復(fù)出原始的信號(hào)序列。

　　重構(gòu)算法的公式如下:

1.2 二維Mallat算法

　　在圖像處理領(lǐng)域,需要進(jìn)行處理的通常是二維圖形。因此,將Mallat算法擴(kuò)展到二維空間,適當(dāng)?shù)剡x取一組行和列變換正交的小波系數(shù),對(duì)圖像(或分解后的低頻子圖)分別進(jìn)行行變換和列變換。然后,根據(jù)后續(xù)的具體應(yīng)用對(duì)N次分解所得的圖像在不同的分辨率下進(jìn)行分析、處理或數(shù)據(jù)壓縮。二維Mallat算法的結(jié)構(gòu)如圖2所示。

?

1.3 CDF9/7系數(shù)

　　在進(jìn)行二維Mallat分解時(shí)需選取一組正交的小波系數(shù)。經(jīng)過小波算法研究人員的多年研究,目前已經(jīng)找出了多組小波系數(shù)。其中以CDF9/7系數(shù)應(yīng)用最為普遍,已成為JPEG2000圖形壓縮標(biāo)準(zhǔn)推薦使用的系數(shù)。但是,CDF9/7系數(shù)通常采用浮點(diǎn)進(jìn)行計(jì)算,在進(jìn)行高速處理時(shí)不便于硬件實(shí)現(xiàn)。因此,選取α=0.5的CDF9/7系數(shù),如公式(3)和(4)所示,濾波器的系數(shù)可以表示成分母為2的冪、分子為2的冪之和的形式,在保證小波分解性能的情況下更適合用FPGA實(shí)現(xiàn)。

1.4 圖像的邊緣延拓

　　對(duì)圖像進(jìn)行行或列分解可以看成是一個(gè)對(duì)有限長序列進(jìn)行濾波的過程,在行變換和列變換時(shí)需要進(jìn)行首尾數(shù)據(jù)延拓。常用的延拓方式包括:對(duì)稱延拓、“0”延拓、恒等延拓、周期延拓等。經(jīng)多次實(shí)驗(yàn)證明,圖像恢復(fù)效果以對(duì)稱延拓為最好,而且實(shí)現(xiàn)也比較方便。

2 普通的FPGA實(shí)現(xiàn)方法

　　在數(shù)據(jù)輸入速率很高(100MHz量級(jí))、系統(tǒng)連續(xù)工作的情況下,要實(shí)時(shí)地完成小波分解,需要即時(shí)完成大量的乘法和加法運(yùn)算、數(shù)據(jù)讀寫操作等。只支持單流水線工作的普通DSP系統(tǒng)在數(shù)據(jù)處理" title="數(shù)據(jù)處理">數(shù)據(jù)處理時(shí)受處理器頻率、數(shù)據(jù)輸入輸出帶寬等因素的限制,而支持并行處理的高性能DSP在算法的分割、數(shù)據(jù)交換上存在較大的困難。因此,在進(jìn)行高速數(shù)據(jù)處理時(shí),通?；贔PGA設(shè)計(jì)一個(gè)可以并行運(yùn)算的專用處理器,從而達(dá)到較高的數(shù)據(jù)處理速度。

　　目前,在工程領(lǐng)域通常采用順序逐級(jí)分解的方法。即在對(duì)圖像進(jìn)行緩沖后,逐次在FPGA中進(jìn)行各級(jí)的行變換和列變換。其系統(tǒng)結(jié)構(gòu)如圖3所示。

?

　　這種結(jié)構(gòu)的主要優(yōu)點(diǎn)是占用的FPGA資源較少。但這種設(shè)計(jì)方法的致命缺陷是,每次處理都必須將各級(jí)分解作完,才能對(duì)下一幀圖像進(jìn)行處理。限于FPGA和RAM的接口帶寬,其處理速度不可能太高,而且占用的外部RAM空間較大。

3 改進(jìn)的FPGA實(shí)現(xiàn)方法

　　針對(duì)普通的順序逐級(jí)分解方法的缺陷,充分利用Xilinx公司VertixE系列FPGA的特性,設(shè)計(jì)一種數(shù)據(jù)串行輸入(不需進(jìn)行幀緩沖)、多級(jí)變換同時(shí)進(jìn)行的結(jié)構(gòu),可以大大提高整個(gè)小波分解系統(tǒng)的數(shù)據(jù)處理速度并節(jié)省大量的外部RAM空間。

3.1 FPGA內(nèi)部的功能劃分

　　本方法主要是利用VirtexE系列FPGA內(nèi)部有大量Block RAM資源和邏輯資源的特點(diǎn),直接在FPGA內(nèi)部進(jìn)行多級(jí)分解。按邏輯功能的不同,FPGA內(nèi)部將實(shí)現(xiàn)如圖4所示的幾個(gè)功能模塊。

?

?

　　全局控制模塊接收外部控制信號(hào)(芯片使能、數(shù)據(jù)時(shí)鐘等),由內(nèi)部計(jì)數(shù)器進(jìn)行計(jì)時(shí)、產(chǎn)生各級(jí)分解模塊的控制信號(hào)(模塊使能、起始終止信號(hào)等)。各級(jí)分解模塊則在全局控制模塊的控制下,對(duì)外部數(shù)據(jù)或前一級(jí)的LL輸出數(shù)據(jù)進(jìn)行鎖存、處理、緩沖、輸出等操作。

　　圖4中的每一級(jí)小波分解模塊需要完成圖像的行和列兩次變換。如果選擇先進(jìn)行完整的行變換再進(jìn)行列變換的方法,將需要大量的緩沖空間并且需要更多的時(shí)鐘周期。因此,必須采用行變換和列變換同時(shí)進(jìn)行的形式,如圖5所示。圖像數(shù)據(jù)輸入到分解模塊的數(shù)據(jù)輸入端,由行數(shù)據(jù)緩沖器進(jìn)行移位、鎖存。鎖存后的數(shù)據(jù)并行輸出到行變換濾波器,進(jìn)行低通和高通濾波,然后進(jìn)行抽樣、緩沖輸出。行濾波器的輸出與存儲(chǔ)在8行數(shù)據(jù)緩沖RAM內(nèi)相同位置的數(shù)據(jù)鎖存到列數(shù)據(jù)緩沖器1中。緩沖器1的輸出與列變換濾波器的輸入相連,時(shí)間靠后的8個(gè)數(shù)據(jù)被鎖存到列數(shù)據(jù)緩沖器2。列數(shù)據(jù)緩沖器2的數(shù)據(jù)將送到內(nèi)部RAM進(jìn)行緩沖,下一個(gè)行周期將前8個(gè)數(shù)據(jù)輸出到列緩沖器1,從而實(shí)現(xiàn)列方向上的數(shù)據(jù)移位。列變換濾波器輸出的LH、HL、HH直接或經(jīng)緩沖后輸出,LL則輸出到下一級(jí)分解模塊進(jìn)行處理。

?

　　本方法相對(duì)普通實(shí)現(xiàn)方法的主要優(yōu)勢(shì)在于:首先,在分解過程中數(shù)據(jù)的存儲(chǔ)在片內(nèi)進(jìn)行,不受芯片接口帶寬的限制,數(shù)據(jù)交換速度達(dá)到最快;其次,多級(jí)分解同時(shí)進(jìn)行,進(jìn)一步提高了分解的整體速度;再次,中間數(shù)據(jù)不必輸出片外,節(jié)省了外部RAM的空間。此外,在FPGA的設(shè)計(jì)過程中還加入了流水線、分布式算術(shù)^[3～4]等優(yōu)化技術(shù),進(jìn)一步提高了FPGA器件進(jìn)行小波分解的速度。

3.2 中間數(shù)據(jù)動(dòng)態(tài)范圍" title="動(dòng)態(tài)范圍">動(dòng)態(tài)范圍及精度

　　在進(jìn)行FPGA設(shè)計(jì)時(shí),為了保持中間數(shù)據(jù)長度一定,每次變換完成后都必須進(jìn)行數(shù)據(jù)的首尾截取,中間結(jié)果的數(shù)據(jù)動(dòng)態(tài)范圍和數(shù)據(jù)精度將直接影響到分解的效果和硬件的開銷。動(dòng)態(tài)范圍不夠,將出現(xiàn)數(shù)據(jù)溢出,動(dòng)態(tài)范圍選取過大又會(huì)浪費(fèi)硬件資源。保留中間結(jié)果的精度將直接影響到分解后數(shù)據(jù)的有效性。

3.2.1 動(dòng)態(tài)范圍分析

　　根據(jù)公式(3)、(4)中選取的CDF9/7系數(shù)h(n)和g(n),,以最壞的情況計(jì)算,數(shù)據(jù)動(dòng)態(tài)范圍每次變換擴(kuò)大到原來數(shù)據(jù)范圍的1.5倍。經(jīng)8次變換(4層分解,每層兩次變換)后,數(shù)據(jù)的動(dòng)態(tài)范圍將擴(kuò)大到原來的(1.5)8≈25.63倍。若圖像的原始數(shù)據(jù)為8位,要含蓋所有的情況則需要用13位表示整數(shù)。

3.2.2 累計(jì)截尾誤差分析

　　設(shè)每次中間結(jié)果保留n位小數(shù),則截尾引起的誤差為:Δx=2^-(n+1)。經(jīng)過8次變換,每次變換的截尾誤差會(huì)逐級(jí)累加放大,最壞情況的累計(jì)誤差為:Δx⁽⁸⁾=Δx=(1+1.5+1.5²+…+1.57)?？紤]到第一次進(jìn)行運(yùn)算的數(shù)據(jù)小數(shù)部分為0,而且每次變換要除以64(2的6次冪),若小數(shù)位數(shù)大于等于6位，則第一次變換的截尾操作將不會(huì)帶入誤差,因此,Δx⁽⁸⁾=Δx=(1+1.5+1.5²+…+1.5⁶)≈32.2Δx。在小波分解的后續(xù)處理中,往往要先進(jìn)行取整運(yùn)算。因此,若Δx⁽⁸⁾<1,即Δx<32.2^-1<2^-6,n≥5,截尾帶來的累計(jì)誤差將不會(huì)影響后續(xù)處理的精度。

3.2.3 數(shù)據(jù)動(dòng)態(tài)范圍與精度的確定

　　經(jīng)過上述分析,若要同時(shí)保證動(dòng)態(tài)范圍和精度,則中間數(shù)據(jù)需保留13+5=18位。通常數(shù)據(jù)長度選取16、24或32等。顯然,選取后兩種數(shù)據(jù)長度可以滿足要求,但是要消耗更多的硬件資源。而選取16位似乎又不能滿足動(dòng)態(tài)范圍和精度的要求。

　　上述動(dòng)態(tài)范圍和精度分析都是考慮到最壞的情況。而實(shí)際情況并非如此,最壞情況出現(xiàn)概率微乎其微。表1是幾幅標(biāo)準(zhǔn)圖像的動(dòng)態(tài)范圍統(tǒng)計(jì)。

?

　　可見,實(shí)際圖像的處理中數(shù)據(jù)的動(dòng)態(tài)范圍并不大。9位(±256)已經(jīng)可以滿足絕大多數(shù)應(yīng)用,而小數(shù)部分要求n≥5,各保留1 位的余量(即10位整數(shù)、6位小數(shù)),16位數(shù)據(jù)長度正好可以滿足需要。

3.3? 設(shè)計(jì)、實(shí)現(xiàn)與測(cè)試

　　基于Virtex E 系列的XCV600E-7芯片,設(shè)計(jì)了一套512×512象素圖像的四級(jí)小波分解系統(tǒng)。XCV600E器件內(nèi)部共有6912個(gè)Slices(邏輯功能塊)、13824個(gè)Registers(寄存器)、13824個(gè)4 Input LUT(四輸入查找表)和72個(gè)Block RAM,適用于較復(fù)雜的處理器設(shè)計(jì)。芯片的接口速率達(dá)到200MHz(Xilinx數(shù)據(jù)手冊(cè)提供的數(shù)據(jù)),能提供足夠的輸入輸出帶寬。經(jīng)過設(shè)計(jì)、仿真與實(shí)現(xiàn),完成小波分解的資源消耗和性能基本達(dá)到了預(yù)想的效果。

　　用VHDL語言描述的設(shè)計(jì)版本,共消耗了

　　Slices: 6344個(gè)(91%)， Register: 4970個(gè)(35%),

????4 Input LUT: 10311個(gè)(74%)， Block RAM: 40個(gè)(55%)。

　　用Xilinx公司例化元件的設(shè)計(jì)版本,共消耗了

　　Slices: 3524個(gè)(51%)， Register: 4668個(gè)(34%),

　　4 Input LUT: 6345個(gè)(46%)， Block RAM:40個(gè)(55%)。

　　從資源的消耗情況來看,該芯片完全可以進(jìn)行1024×1024大小圖像的分解以及進(jìn)行第5級(jí)分解。

通過對(duì)系統(tǒng)進(jìn)行的實(shí)際測(cè)試可知,系統(tǒng)的數(shù)據(jù)處理速率高達(dá)120MHz;根據(jù)仿真的波形可知,最大的數(shù)據(jù)不穩(wěn)定時(shí)間≤2.5ns。而系統(tǒng)正常穩(wěn)定工作時(shí)要求數(shù)據(jù)的不穩(wěn)定時(shí)間小于工作周期的一半,因此系統(tǒng)的工作頻率完全可以提升到200MHz甚至更高。在實(shí)際的系統(tǒng)中,此項(xiàng)性能主要受限于FPGA的接口速率,若選用更高檔的芯片,將達(dá)到更好的效果。

　　經(jīng)過FPGA的分解和重構(gòu),得到的結(jié)果如圖6所示。經(jīng)測(cè)試,重構(gòu)圖像在進(jìn)行取整運(yùn)算后,重構(gòu)圖像與原始圖像完全無失真,即峰值信噪比PSNR為無窮大。可見,由于設(shè)計(jì)中正確地選取了數(shù)據(jù)的動(dòng)態(tài)范圍和數(shù)據(jù)精度,在節(jié)省了中間存儲(chǔ)器空間的同時(shí)使分解和重構(gòu)運(yùn)算的截尾誤差未給圖像的恢復(fù)帶來損失。

?

?

3.4 改進(jìn)后的FPGA實(shí)現(xiàn)方法的顯著優(yōu)勢(shì)

　　為了對(duì)改進(jìn)后的方法進(jìn)行性能比較,采用普通的FPGA實(shí)現(xiàn)方法設(shè)計(jì)了一套512×512圖像的4級(jí)小波分解系統(tǒng)。經(jīng)過測(cè)試,得到表2所示數(shù)據(jù)。

?

?

　　由表2的前兩項(xiàng)數(shù)據(jù)可見,需要設(shè)計(jì)8個(gè)相同的濾波器,而普通方法只需設(shè)計(jì)一個(gè)16位的濾波器和幾個(gè)控制模塊,因此前者比后者消耗了更多的FPGA資源;改進(jìn)方法將中間數(shù)據(jù)在芯片內(nèi)作緩沖,消耗了40個(gè)Block RAM塊。改進(jìn)方法在資源的消耗上雖然不及前者,但是在大規(guī)模FPGA芯片成為設(shè)計(jì)主流載體的今天,資源的消耗問題已經(jīng)不象以往那樣至關(guān)重要。

　　目前大家最關(guān)心的問題,也是改進(jìn)后方法的主要優(yōu)勢(shì),就是對(duì)圖像的處理效率高、節(jié)省了外部的存儲(chǔ)器資源。在圖像數(shù)據(jù)連續(xù)進(jìn)入系統(tǒng)的情況下,普通的方法為了解決中間數(shù)據(jù)在外部RAM中的存儲(chǔ)問題,只有設(shè)計(jì)多條(3條以上)單獨(dú)的數(shù)據(jù)通道和多塊獨(dú)立的RAM來分別完成數(shù)據(jù)的緩沖、中間結(jié)果存儲(chǔ)、結(jié)果緩存。由于圖像處理的中間結(jié)果都要緩沖到外部存儲(chǔ)器并要多次通過分解模塊進(jìn)行處理,若要實(shí)時(shí)地完成數(shù)據(jù)處理,就要求器件的工作頻率以及與存儲(chǔ)器的接口速率能夠達(dá)到圖像數(shù)據(jù)輸入速率2.5倍左右。而改進(jìn)后的方法,在處理圖像數(shù)據(jù)時(shí)將中間結(jié)果存儲(chǔ)于FPGA內(nèi)部,而且中間數(shù)據(jù)依次通過各級(jí)分解模塊,FPGA的工作頻率只要和圖像數(shù)據(jù)的輸入速率一致即可以滿足要求。當(dāng)圖像的輸入速率達(dá)到100MHz量級(jí)時(shí),普通方法要求FPGA的工作頻率和存儲(chǔ)器接口速率都要達(dá)到250MHz,這對(duì)大多數(shù)FPGA和RAM都是難以突破的瓶頸。因此,在器件相同的情況下,改進(jìn)后的系統(tǒng)可達(dá)到普通系統(tǒng)處理速度的2.5倍。

　　由此可見,普通方法適合于圖像數(shù)據(jù)率比較低、對(duì)系統(tǒng)的成本要求比較嚴(yán)格的情況,改進(jìn)方法則適合應(yīng)用于對(duì)性能要求很高而對(duì)成本要求不高的情況。

　　本文提出的基于FPGA的高速圖像小波分解實(shí)現(xiàn)方法比傳統(tǒng)的實(shí)現(xiàn)方法在處理速度方面有了很大的提高。特別是在對(duì)連續(xù)圖像進(jìn)行處理時(shí),可以不進(jìn)行圖像數(shù)據(jù)的分割和緩沖而進(jìn)行連續(xù)的處理,節(jié)省了分塊緩沖的時(shí)間和存儲(chǔ)空間。在圖像重構(gòu)系統(tǒng)中采用同樣的結(jié)構(gòu)即可連續(xù)地恢復(fù)出原始圖像。在實(shí)際的應(yīng)用中,小波分解模塊并不是孤立存在的,經(jīng)過小波分解后的數(shù)據(jù)還要進(jìn)行數(shù)據(jù)壓縮、數(shù)據(jù)融合、邊緣檢測(cè)等處理。根據(jù)后續(xù)模塊實(shí)現(xiàn)方案的具體情況,在FPGA中設(shè)計(jì)與后續(xù)處理模塊匹配的數(shù)據(jù)通道,小波分解模塊即可方便地與相應(yīng)的圖像處理系統(tǒng)進(jìn)行級(jí)聯(lián)。因此,本文提出的高速小波分解模塊可以廣泛應(yīng)用于基于小波分解的各種圖像處理算法的實(shí)時(shí)處理系統(tǒng),使小波分解部分不再成為整個(gè)圖像處理系統(tǒng)的瓶頸。

?

參考文獻(xiàn)

1 Thomas W. Fry. Hyperspectral Image Compression on Reconfigurable Platform. Washington University,2000

2 Jonathan B. Ballagh. An FPGA Run-time Reconfigurable 2-D Discrete Wavelet Transform Core. Virginia， June 2001

3 K. Chapman.Fast Integer Multipliers Fit in FPGAs. Electronic Design News， May 12， 1994

4 Spaniol. Computer Arithmetic: Logic and Design,John Wiley & Sons,1981

5 Xilinx. Xilinx VirtexE Data Book.San Jose CA,2000

6 李在銘.數(shù)字圖像處理、壓縮與識(shí)別技術(shù).成都:電子科技大學(xué)出版社,2000

7 Castleman,K. R著，朱志剛譯.數(shù)字圖像處理.北京:電子工業(yè)出版社,1998