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

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

?

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

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

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

1.1 Mallat算法

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

?

?

　　分解算法的公式如下:

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

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

1.2 二維Mallat算法

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

?

1.3 CDF9/7系數(shù)

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

1.4 圖像的邊緣延拓

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

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

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

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

?

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

3 改進的FPGA實現(xiàn)方法

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

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

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

?

?

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

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

?

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

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

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

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

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

3.2.2 累計截尾誤差分析

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

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

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

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

?

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

3.3? 設計,、實現(xiàn)與測試

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

　　用VHDL語言描述的設計版本,共消耗了

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

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

　　用Xilinx公司例化元件的設計版本,共消耗了

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

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

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

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

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

?

?

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

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

?

?

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

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

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

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

?

參考文獻

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ù).成都:電子科技大學出版社,2000

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