基于ＦＰＧＡ的快速中值濾波算法

（大連理工大學 計算機科學與技術系， 遼寧 大連 116023）

摘 要：針對傳統中值濾波算法排序量多、速度慢的缺點，提出了一種基于FPGA的中值濾波快速算法。充分利用兩個相鄰濾波窗口中的相關排序信息，隨著一列新像素的移入，同時更新已有的排序信息，從而完成中值濾波處理。該算法將每個窗口查找中值的比較次數降到很低，達到了快速抑制噪聲及保持圖像細節的目的。

關鍵詞：現場可編程門陣列；中值濾波；Verilog；實時圖像處理

中圖分類號：TP391 文獻標志碼：A

文章編號：10013695(2009)01022403

FPGAbased algorithm of fast median filter

WANG Yuxin，HE Yuanyuan，GUO He，LONG Zhu

（Dept. of Computer Science Technology， Dalian University of Technology， Dalian Liaoning 116023， China）

Abstract:In order to solve the problem that the speed of classical median filter was slow because of a lot of sorting，this paper proposed a new algorithm of median filter based on FPGA. It made full use of the coherence of data adjacent windows and completed the median filter processing by adding the new column of pixels while updating the rest of the arranged pixels. The algorithm can reduce the number of comparisons， and achieve the goal of noise suppression and image details keeping in a fast speed.

Key words:FPGA; median filter; Verilog; realtime image processing

中值濾波是一種非線性濾波方法，既可以消除隨機噪聲和脈沖干擾又可以很大程度地保留圖像的邊緣信息，近年來在圖像平滑和數據分析與處理等多個領域中得到廣泛應用。隨著微電子技術與工藝的迅猛發展，現場可編程門陣列(FPGA)以其可編程性、低成本性、高邏輯密度和高可靠性，得到了越來越廣泛的應用。本文介紹了一種高效中值濾波器的設計及其在FPGA上的實現方案，并用Xilinx公司的開發工具ISE 8.2和Verilog硬件開發語言進行了仿真驗證。

1 傳統中值濾波原理

傳統中值濾波算法[1，2](TMF)的基本原理是通過對一幅圖像中每一個合法像素點鄰域中的像素按灰度級進行排序，然后選擇該組的中間值作為輸出像素值。傳統中值濾波可以定義為

g(x，y)=median{f(x-i，y-j)} (i，j)∈W

其中：g(x，y)和f(x-i，y-j)分別為輸出和輸入像素灰度值；W為模板窗口。模板窗口W可以取線狀、方形、十字形、圓形等。

在傳統算法中，需要對鄰域內所有像素進行排序獲得其中值。排序的過程就是對像素進行比較和交換的過程。序列中像素之間的比較次數是影響排序速度的重要原因。傳統中值濾波算法隨著窗口的移動，需要大量的比較運算。對于一個像素數為N的窗口數列，需要執行N(N-1)/2次像素比較操作，時間復雜度為O(N2)。以3×3方形窗為例，對一幅128×128的灰度圖像進行中值濾波處理，共需要處理16 384個像素，對每個像素點及其鄰域取中值需要進行36次比較排序運算。可見，傳統中值濾波算法雖然比較簡單，但是運算量大，在FPGA中實現時需要消耗大量片上資源，速度慢，無法滿足實時性要求。

2 算法分析

針對傳統實現中值濾波方法的缺點，文獻[3]中應用快速排序算法，以濾波窗口中所有元素值的平均值為界進行劃分(FSMF)。每次選取大集合以其均值進行劃分，直到分解的兩個集合元素個數均小于濾波子窗口總元素個數的一半，再對兩個子集合之一進行快速排序。雖然可以減少比較次數，但時間復雜度仍然是O(N ln N)。

朱捷等人[4]提出了一種不完全排序的思想(NSMF)。對窗口像素排序時采用冒泡排序，當比較到中間位置即第n/2個像素時停止排序即可獲得中值。對于3×3方形窗，每次對窗口中的9個元素排序到第5個停止，需要8+7+6+5+4=30次比較次數。

文獻[5，6]提出了基于統計思想的中值濾波算法(SMF)。將包含n個像素模板中的某一個灰度值D0與其他所有值相比較，統計出大于D0和小于D0的像素個數分別表示為large和little，如果兩者相等則可確定該值即為所求中值，否則選擇下一個像素值重復上述過程，直到找到中值為止。該算法在進行統計過程中，需要將待判斷像素與窗口中的所有其余像素都進行比較，利用硬件資源的可重復性定義9個比較統計單元并行計算，但該過程仍然需要9個時鐘周期才能得到統計值，不適合用于實時性要求比較高的場合。文獻[5]中的統計法設置了閾值threshold，滿足|large-little|≤threshold則可認為該值為中值近似值。雖然可以減少比較次數，但找出的像素值并不一定是濾波子窗口真正中間值，從而在提高速度的同時帶入了誤差。

付昱強[7]提出了一種快速算法(FMF)，將有m×m像素的二維陣列的每一列進行排序，再對每一行排序，最后取對角線像素的中值即為所求的中值。對于3×3方形窗，列排序運算需要3×3=9次比較，行排序也同樣需要9次比較，將對角線上的三個像素進行比較取中值需要3次比較運算。對一組9個像素取中值一共需要進行21次比較運算。

文獻[8，9]提出了利用相鄰窗口間相關信息的快速算法(NWMF)，充分利用當前窗口W(i， j)其左邊和上邊相差一個像素位置的已排序窗口W(i， j-1)和W(i-1， j)中的信息獲得當前窗口W(i， j)的中值。將W(i， j)內的像素分為G1和G2，分別為含有其值最小的(m2+1)/2個像素及其值最大的(m2-1)/2個像素的集合。將新輸入的一列像素進行排序，并將它們按W(i-1， j)的中值為界歸入G1和G2中，再對兩集合中的邊界像素進行比較調整，直到兩集合像素個數相差1即可找到中值。對于3×3方形窗，最壞情況下可以將比較次數降低到20次。但是應用到FPGA中時，需要消耗大量的硬件資源來記錄W(i， j-1)和W(i-1， j)的排序信息。

3 中值濾波快速算法

為了以最少的比較次數找到中值，可以充分利用已排序窗口中原有像素的序列值。本文只利用左邊前一個窗口中的排序信息，通過移出一列舊像素和移入一列新像素，保留原窗口中剩余像素的排序信息，將新移入的像素與剩余像素進行比較的同時更新原窗口中剩余像素的排序信息，從而完成中值濾波處理。

設WW代表濾波窗口的寬度，WH代表濾波窗口的高度，window代表窗口中的像素個數，則window=WW×WH。為了記錄原窗口中像素的排序序列，在讀入新像素時能夠利用已有排序序列減少比較次數，為濾波窗口中的每一個像素都附加了一個序列值寄存器CR[window-1…0]，用來保存當前窗口中不比它小的像素個數，新像素的序列值存放在CN寄存器中。窗口中像素序列值的變化范圍是從1(代表最小的像素)到window(代表最大的像素)。隨著新像素進入濾波窗口，已存在于窗口中的像素和對應的序列值同時移動。寄存器D[window-1…0]存放當前窗口中的像素，寄存器ND存放新讀入的像素，比較寄存器C[window-1…0]存放新像素與窗口中的相應像素的比較結果。

當窗口讀入一個新像素CN時，將原窗口中的每一個像素D[window-1…0]與新像素進行比較，若不小于CN則相應的比較寄存器C[window-1…0]賦值為1；否則為0。根據比較結果，更新序列值寄存器CN和CR[window-1…0]。CN的最低位置為1，其余位由C[window-1…0]的逆序生成。CR[window-1…0]的最低位由對應的C[window-1…0]寄存器提供，其余位由前一個像素的CR[window-1…0]提供，即

CR[k]={CR[k-1](window-2:0)，C[k]}

其中：(:)代表位選擇；{}代表組合。這樣，在任意時刻數據寄存器D[k]和對應的序列寄存器CR[k]分別存儲了一個輸入像素的值和它與窗口中其他像素的比較結果。計算CR[k]寄存器的各位之和就可以得到對應像素D[k]的排序信息，從而輸出中值。

圖1表明了window=5時在一個周期內各個寄存器的變化情況，新像素從右側輸入，表中所示為寄存器(ND，D)的內容和對應的比較結果寄存器(CR，CN)的變化情況。寄存器D[4…0]存儲了當前窗口中的像素值，當讀入新像素ND=5時，將原窗口中每一個像素均與新像素進行比較，若D[i]不小于5，則寄存器C[i]=1；否則C[i]=0。C[3…0]提供了序列值寄存器CR[4…1]的最低位，其余位由CR[3…0]的高8位提供。CN的最低位置為1，其余位由C[3…0]的逆序構成。

4 硬件實現

41 總體設計方案

為了便于在FPGA硬件上實現中值濾波，本文以3×3窗口(WW=3，WH=3，window=9)處理128×128×8的灰度圖像為例進行了硬件設計實現。設計方案包括四個主要部分，如圖2所示。

42 窗口產生模塊

該模塊用于生成窗口數據，實現了圖像數據的串入并出。在FPGA中定義了9個寄存器(w11，w12，w13，w21，w22，w23，w31，w32，w33)組成了3×3窗口寄存器組來暫時存放3×3窗口中的數據。原理圖如圖3所示。

在圖3中，r代表移位寄存器；FIFO代表先進先出存儲器。圖像數據按時鐘節拍從數據輸入端Din依次輸入，FIFO用來存儲一行的數據，以便使w11，w12，…，w33存放的正好是3×3模板所對應的圖像數據。當數據流不斷從數據輸入端輸入時，3×3模板對應的圖像數據不斷地跟著變化，這就可以對圖像的所有像素都進行3×3模板處理。

43 中值濾波模塊

中值濾波模塊的原理圖如圖4所示。算法已在第1章中進行了說明。隨著新像素從ND輸入，窗口像素及其對應的序列值依次左移。當一列3個新像素輸入完畢后，此時輸出有效中值數據。對于3×3的方形窗，每次窗口移動有3個新數據讀入，3個舊數據移出，只需將3個新數據和原窗口中剩余6個數據比較，比較次數減少為3×6=18次。

44 計數模塊

當中值濾波執行到圖像邊緣時，用3×3的模板無法蓋住圖像或會蓋住圖像外的一部分，這樣無法正確執行中值濾波模塊，需要計數模塊對濾波操作進行行列計數控制，在窗口移動到圖像邊緣時，置輸出為0。通過該模塊可以確定一幅圖像是否到達邊緣或者是否傳輸完畢，從而進行邊緣控制。模塊結構如圖5所示。

圖5中，RSTn為復位信號與全局復位信號相連；EN為使能端；CLK為時鐘輸入端；ColPos為圖像列標志；RowPos為圖像行標志。該模塊只起到計數功能，用來確定數據在圖像中的陣列位置。

5 測試結果及分析

本文采用Xilinx的Spartan3E開發板XC3S500E芯片完成算法的設計。將本文的快速算法與文中提到的幾種方法在最壞情況下的比較次數進行了比較。結果如圖6所示。

本文對軟硬件處理同一幅128×128的圖片進行了對比分析。硬件板上使用50 MB的時鐘；軟件上在Pentium4 CPU，時鐘頻率為2.8 GHz，RAM為512 MB的系統上采用MATLAB仿真實現。比較結果如表1所示。

表1 中值濾波的性能比較

處理器時鐘頻率/MHz處理時間/ms

Spartan3E500.333

Intel Pentium42 79030

仿真濾波效果如圖7所示。通過比較，該快速濾波算法達到了比較好的濾波效果，圖像邊緣設置為0，所以有一圈黑線。

6 結束語

本文首先介紹了傳統中值濾波算法以及已有的一些改進算法，并對它們進行了分析。在此基礎之上提出了一種利用相鄰窗口中的排序信息得出中值的方法，將時間復雜度由O(N2)降到O(N)，對于每個3×3窗口僅需要18次比較便可得出中值，避免求中值過程中繁瑣的排序過程，提高了中值濾波的計算速度，易于在FPGA中實現，適合于實時圖像處理。本設計現僅應用于3×3模板，可以進行大模板的測試，如5×5窗口。今后可以將該算法應用到實時圖像處理應用中，以提高中值濾波的處理速度。

參考文獻：

［1］

ANTHONY E N.Implementation of image processing algorithms on FPGA hardware[D].Nashville:Vanderbilt University， 2000.

［2］李雷鳴，張煥春，張波. 一種基于FPGA 的圖像中值濾波器的硬件實現[J].電子工程師，2004，30(2):4850.

［3］張麗，陳志強，高文煥，等.均值加速的快速中值濾波算法[J].清華大學學報，2004，44(9):11571159.

［4］朱捷，朱小娟，賀明.基于FPGA的實時性的圖像處理中值濾波器設計實現[J].計算機測量與控制，2007，15(6):798800.

［5］李元帥，張勇，周國忠，等.圖像中值濾波硬件算法及其在FPGA中的實現[J].計算機應用，2006，26(6):6263，75.

［6］董付國，原達，王金鵬.中值濾波快速算法的進一步思考[J].計算機工程與應用，2007，43(26):4849，64.

［7］付昱強.基于FPGA的圖像處理算法的研究與硬件設計[D].南昌:南昌大學，2006.

［8］CHEN Tao，WU Hongren.Application of partitionbased median type filters for suppressing noise in images[J].IEEE Trans on Image Processing，2001，10(6):829836.

[9]劉立宏，胡可剛，劉立欣.目標檢測中的快速中值濾波法[J].吉林大學學報，2004，22(3):232235.