快速二維中值濾波算法及其FPGA硬件設計

董恩增，吳東東，佟吉鋼

（天津理工大學 自動化學院 復雜系統控制理論及應用重點實驗室，天津300384）

0 引 言

圖像去噪是圖像處理中重要的一部分，在圖像的采集、傳輸、處理、接收及成像過程中，存在著一定程度的干擾。如相機感光芯片在光電轉換過程中靈敏度的不均勻性、在采集傳輸過程中的系統參數誤差以及人為或周圍環境因素影響等，均會引入一定程度的干擾噪聲。噪聲的引入使圖像的質量變差，圖像中的一些特征被淹沒，給圖像分析工作帶來困難。為了提高圖像的質量以及后續更高層次處理，必須先對噪聲圖像進行恰當的濾波，抑制背景中的噪聲，增強圖像中目標特征的強度，從而提高圖片信噪比［1］。目前應用較多的是3×3中值濾波器，主要應用于復雜背景下的紅外追蹤和目標探測領域。然而當一副圖片的信噪比較低、噪聲密度較高時，3×3中值濾波器的濾波效果并不是很理想，導致目標強度變弱。

本文針對處理噪聲圖片時數據量大、實時性要求較高的問題，從算法比較次數、硬件資源占用、去噪處理后圖像質量方面綜合考慮，在排序過程中引入歸并插入排序算法，用VHDL 語言設計了適合于FPGA 實現的5×5快速中值濾波器。與常規方法相比，該方法減少了比較次數和計算量，節省開發成本，同時也方便在FPGA 上實現。

1 快速二維中值濾波算法

一個大小為N×N（N 為奇數）的濾波窗口W 用于二維圖像像素點｛Xij，（i，j）∈Z2｝，此時中值濾波器可定義為［2］

中值濾波的主要運算就是對濾波窗口中的數值進行排序。其基本單元是2個數值的大小比較然后排序。對于一個m×n的二維濾波采樣窗口，需要設計m×n個寄存器來存儲濾波窗口內待處理的數據，之后再經過排序運算，得到濾波窗口中數據的中值［3］。

本文5×5快速中值濾波器算法流程如圖1所示。

圖1 5×5圖像窗口求取中值流程

（1）將窗口中的25個數先按行沿箭頭方向進行降序排列，如圖1 （a）所示；

（2）再將其按列沿箭頭方向做降序排列，如圖1 （b）所示；

（3）按對角線沿箭頭方向對三列數進行降序排列，如圖1 （d）所示；

（4）完成步驟 （3）后，將最后的3個數沿箭頭方向降序（或升序）排列，得到25個數的中值，如圖1 （c）所示。

在如圖1快速中值濾波器行列降序排列及斜對角線5個數降序排列過程中，本文采用了歸并插入排序算法［7］，該算法能夠將5個數在最少比較次數情況下得出排序結果，算法原理如下：

假設5×5濾波窗口中任一行 （或一列）5個數分別編號x1、x2、x3、x4、x5，x1與x2，x3與x4共比較2 次，假設比較結果x1＞x2，x3＞x4；x1與x3比較需1 次，假設比較結果為x1＞x3，則x1＞x3＞x4。當x1＞x3＞x4時4個元素的有序關系如圖2所示 （連線表示左下元素大于右上元素）。

圖2 x1＞x3＞x4 時4個元素的有序關系

把x5插入x1，x3，x4中，需要比較2 次，有4 種情況，如圖3所示。

圖3 x5 插入x1，x3，x4 后有序關系

對以上任意一種情況，總可以通過兩次比較將x2插入由x1、x3、x4、x5構成的有序隊中。這樣總共需要比較2＋1＋2＋2＝7次。若用分組排序網絡算法或插入法對x1、x2、x3、x4、x5進行排序則需要比較10次。由此可見，將歸并插入算法應用于快速中值濾波器中可進一步減少比較次數，進而提高系統運算速度。

2 算法硬件設計

2.1 5×5采樣窗口模塊

為了便于系統的算法模塊進行流水線處理，必須保證窗口中的25個像素值在同一時刻輸出，本文在5×5采樣窗口硬件設計中，采用了25個寄存器和4個FIFO 存儲器，其中FIFO 是利用FPGA 芯片的IP核生成的，由于本文處理的圖像為480×320的灰度圖像，所以FIFO 位寬設置為8，深度設置為512。并設定為單時鐘同步。4個FIFO 存儲器用來緩存4行的像素點數，而寄存器用來緩存并輸出各行的5個像素點［8，9］。

圖4為5×5方形窗采樣結構框架，在快速中值濾波過程中，先從數據輸入端讀取4 行圖像數據并依次保存在FIFO1～FIFO4存儲器中。在時鐘的上升沿，從數據輸入端讀入一個新的數據，同時方形采樣窗口向右移動一個單位，與此同時上一時刻方形窗中最右邊的像素被置入下一個FIFO 存儲器中等待處理。由于在系統時鐘的控制下4個FIFO 每一個節拍輸出一個新的數據，這就保證了方形采樣窗口在每一個時鐘的控制下可以沿被處理圖像數據的行方向逐個像素滑動［10］。由于5×5 的濾波窗口無法處理位于圖像邊緣最外圍的兩行兩列像素點，考慮到最外圍的像素點對目標，特征影響程度很小，可以忽略不計，所以這些點保持原值輸出。

圖4 5×5方形窗結構框架

圖5 為5×5 方形窗仿真波形圖，可以看到在481400 ns時刻，5行的圖像數據中的每一行都能輸出5位數據且能夠保證無數據丟失和錯位的情況下逐行移動。因此，5×5方形窗的硬件設計達到了預期的要求。

圖5 5×5方形窗仿真波形

2.2 5×5快速中值濾波器算法模塊

該模塊目的是求取25個數的中值，并作為輸出。利用軟件來實現該算法較為簡單，但通常該濾波算法在硬件上實現則需要考慮濾到波器的系統硬件資源占用比例，因此從理論上分析，在達到實驗或工程目的前提下，在硬件系統設計過程中應當盡量使用更少的比較器和寄存器，并且盡可能在得到正確輸出結果的同時減少硬件系統運算量。根據圖1的算法流程，設計了求取中值的VHDL 程序。在該程序設計中調用了11次5個數排序模塊，2次4個數的排序模塊，1次3個數的排序模塊。5個數排序模塊采用歸并插入排序算法。5個數降序排列需要比較7次，4個降序排列數需要比較6次，3個數降序排列需要比較3次。所以該算法模塊總共需要比較次數N＝7×11＋6×2＋3＝92次。該中值濾波算法比常規算法少比較142次。圖6為5個數降序排列模塊的RTL 原理，圖7為5×5快速中值濾波器算法的RTL原理［11，12］。

圖6 5個數降序排列模塊RTL原理

5×5的濾波算法模塊仿真波形如圖8所示。

圖7 5×5快速中值濾波器RTL原理

圖8 中值濾波算法仿真波形

通過圖8可以看出，25個數的中值在第四個時鐘周期就能正常輸出，保證了濾波算法的正確性和實時性。該算法的硬件模塊設計以盡可能的減少運算量為基礎，用VHDL語言設計了適合在FPGA 上實現的行排序和列排序等硬件模塊，達到了設計的要求。

3 實驗結果及分析

在該設計中板型選取的是Xilinx公司的Virtex－II PRO XC2VP30開發板。為了能夠對本文ISE10.0環境下設計的快速中值濾波器硬件系統仿真，驗證硬件系統設計的正確性，首先利用MATLAB將一幅480×320的圖像轉化為激勵文件，將該激勵文件保存在ISE 當前的工程目錄；然后使用ISE Simulator進行仿真，將輸出結果存入＊.txt文件；最后通過MATLAB 調用該＊.txt文件來顯示處理后的圖像［13］。

圖9中 （a）、（b）、 （c）、 （d）為實驗結果前后對比圖。圖9 （a）為原始圖像；圖9 （b）為加入45%的椒鹽噪聲圖像，圖9 （c）為3×3中值濾波器處理后圖像，圖9 （d）為本文5×5快速中值濾波器處理后圖像。表1 為圖9 （c）與 （d）兩幅圖的均方誤差 （MSE）和峰值信噪比 （PSNR）值的對比［14，15］。表2為不同類型5×5中值濾波器在硬件資源占用、排序比較次數以及時鐘延遲個數方面的對比。

圖9 不同處理后圖片效果對比

由圖9和表1 可知，歸并插入排序算法應用到5×5快速中值濾波器的硬件系統設計正確，對于同一幅加噪圖像，經過兩個不同類型中值濾波器去噪處理后，通過比較圖9中 （b）和 （c）兩幅圖片的MSE、PSNR 值，可以發現5×5中值濾波器比3×3 中值濾波器對噪聲有更好的抑制效果。由表2可以看出本文設計的5×5快速中值濾波器硬件資源消耗較少，并最終減少了比較次數和時鐘延遲個數，提高了運算的速度，保證了數據處理的實時性。

表1 圖9 （c）、圖9 （d）兩幅圖的MSE、PSNR 值

表2 中值濾波器硬件資源使用情況、比較次數及時鐘延遲情況對比

4 結束語

針對較高密度的噪聲數字圖像，本文從中值濾波器的去噪性能、運算速度以及硬件資源占用多方面綜合考慮，設計了一種5×5快速中值濾波器，在該濾波器中，應用了歸并插入排序算法。相比常規算法，該算法能夠使中值濾波器的比較次數進一步減少，提高了運算速度。在ISE10.0環境下，本文算法的硬件設計達到要求，該算法結構簡單，系統實時性高，硬件資源占用較少，去噪效果明顯，且易在FPGA 上實現。為復雜背景下的紅外追蹤和目標探測領域提供了一定的技術參考。

［1］ZHU Shihu，HUANG Zhi.A novel filtering algorithm of high density salt and pepper noise ［J］.Computer Engineering，2012，38 （18）：207－210 （in Chinese）.［朱士虎，黃智.一種新的高密度椒鹽噪聲濾波算法 ［J］.計算機工程，2012，38（18）：207－210.］

［2］WAN Haijun，HE Dongjian，XU Shangzhong.The realization of image median filter algorithm based on FPGA ［J］.Microcomputer Information，2008，24 （7）：3 （in Chinese）.［萬海軍，何東建，徐尚中.基于FPGA 的圖像中值濾波算法硬件實現 ［J］.微計算機信息，2008，24 （7）：3.］

［3］LI Yanjun，SU Hongqi，YANG Feng，et al.Improved algorithm study about removing image noise ［J］.Computer Engineering and Design，2009，30 （12）：2995－2997 （in Chinese）.［李彥軍，蘇紅旗，楊峰，等.改進的中值濾波圖像去噪方法研究 ［J］.計算機工程與設計，2009，30 （12）：2995－2997.］

［4］LUO Haibo，SHI Zelin，HUI Ying，et al.Real－time large window－sized 2D median filter based on multi－phased grouping and sorting network ［J］.Infrared and Laser Engineering，2008，37 （5）：935－939 （in Chinese）. ［羅海波，史澤林，惠穎，等.基于多級分組排序網絡的實時大窗口二維中值濾波器設計 ［J］.紅外與激光工程，2008，37 （5）：935－939.］

［5］BO Zhentong.Design of real－time image adaptive median filter based on FPGA ［J］.Electronic Sci ＆ Tech，2014，27 （1）：121－124 （in Chinese）.［薄振桐.基FPGA 的實時圖像自適應中值濾波器設計 ［J］.電子科技，2014，27 （1）：121－124.］

［6］YU Mingjing，GU Jun.Research on the advanced median filter based on FPGA ［J］.Electronic Test，2011，12 （12）：50－53（in Chinese）.［尉明靖，古軍.基于FPGA 的改進型中值濾波研究 ［J］.電子測試，2011，12 （12）：50－53.］

［7］WU Weina，SUN Shipeng，YANG Feng，et al.Compare and analysis of frequently－used sorting algorithms ［J］.Computer Knowledge and Technology，2013，9 （9）：2146－2148 （in Chinese）.［吳偉娜，孫仕鵬，楊風，等.常用排序算法的比較與分析 ［J］.電腦知識與技術，2013，9 （9）：2146－2148.］

［8］LI Guoyan，HOU Xiangdan，GU Junhua，et al.Implementation of the improved fast median filtering algorithm based on FPGA ［J］.Computer Technology and its Application，2013，39（2）：137－140 （in Chinese）.［李國燕，候向丹，顧軍華，等.快速中值濾波算法的改進及其FPGA 實現 ［J］.電子技術應用，2013，39 （2）：137－140.］

［9］LI Yibo，LI Xiaobing，ZHOU Xian.Design and realization of fast median filter based on FPGA ［J］.Liquid Crystals and Displays，2010，25 （2）：292－295 （in Chinese）.［李軼博，李小兵，周嫻.基于FPGA 的快速中值濾波器設計與實現 ［J］.液晶與顯示，2010，25 （2）：292－295.］

［10］SHEN Xueli，WANG Suguo.Research of the advanced median filtering algorithm based on FPGA ［J］.Microelectronics＆Computer，2014，31 （1）：21－24 （in Chinese）.［沈學利，王肅國.基于FPGA 的改進型中值濾波算法研究 ［J］.微電子學與計算機，2014，31 （1）：21－24.］

［11］YANG Ming，SONG Lihua.The application of an improved fast algorithm of median filter on removing image noise ［J］.Engineering of Surveying and Mapping，2011，20 （3）：65－69（in Chinese）.［楊明，宋麗華.改進的快速中值濾波算法在圖像去噪中的應用 ［J］.測繪工程，2011，20 （3）：65－69.］

［12］YANG Jing，WANG Yuanqing.Implementation of improved median filtering algorithm in real－time and high－speed ［J］.Jisuanji Yu Xiandaihua，2013 （8）：30－32 （in Chinese）. ［楊晶，王元慶.實時高速實現改進型中值濾波算法 ［J］.計算機與現代化，2013 （8）：30－32.］

［13］ZHAN Xianning，TIAN Geng.VHDL development solutions and example analysis ［M］.Beijing：Electronic Industry Press，2009 （in Chinese）. ［詹仙寧，田耘.VHDL 開發精解與實例剖析 ［M］.北京：電子工業出版社，2009.］

［14］LI Xu，ZHAO Wenjie，YANG Kaida.An improved method of median filtering algorithm ［J］.Chinese Journal of Stereology and Image Analysis，2013，18 （1）：7－11 （in Chinese）.［李旭，趙文杰，楊凱達.一種改進的中值濾波算法 ［J］.中國體視學與圖像分析，2013，18 （1）：7－11.］

［15］GENG Shuai，WANG Xichang.An image denoising algorithm based on median filter ［J］.Jisuaji Yu Xiandaihua，2011 （11）：90－92 （in Chinese）.［耿帥，王希常.一種基于中值濾波的圖像去噪算法 ［J］.計算機與現代化，2011（11）：90－92.］

［16］WANG Hong，TIAN Shasha，DING Lin.Design of image median filter based on FPGA ［J］.Microcomputer Applications，2012，31 （13）：46－48 （in Chinese）. ［汪紅，田莎莎，丁林.基于FPGA 的圖像中值濾波器設計 ［J］.微型機與應用，2012，31 （13）：46－48.］

［17］Rafael C Gonzalez，Richard E Woods.Digital image processing ［M］.3rd ed.Beijing：Beijing Publishing House of Electronics Industry，2011.

［18］HE Bin.Xilinx FPGA design authority guidelines［M］.Beijing：Tsinghua University Press，2012 （in Chinese）. ［何賓.Xilinx FPGA設計權威指南［M］.北京：清華大學出版社，201.］