快速二維中值濾波算法及其FPGA硬件設(shè)計(jì)

董恩增，吳東東，佟吉鋼

（天津理工大學(xué) 自動(dòng)化學(xué)院 復(fù)雜系統(tǒng)控制理論及應(yīng)用重點(diǎn)實(shí)驗(yàn)室，天津300384）

0 引 言

圖像去噪是圖像處理中重要的一部分，在圖像的采集、傳輸、處理、接收及成像過(guò)程中，存在著一定程度的干擾。如相機(jī)感光芯片在光電轉(zhuǎn)換過(guò)程中靈敏度的不均勻性、在采集傳輸過(guò)程中的系統(tǒng)參數(shù)誤差以及人為或周?chē)h(huán)境因素影響等，均會(huì)引入一定程度的干擾噪聲。噪聲的引入使圖像的質(zhì)量變差，圖像中的一些特征被淹沒(méi)，給圖像分析工作帶來(lái)困難。為了提高圖像的質(zhì)量以及后續(xù)更高層次處理，必須先對(duì)噪聲圖像進(jìn)行恰當(dāng)?shù)臑V波，抑制背景中的噪聲，增強(qiáng)圖像中目標(biāo)特征的強(qiáng)度，從而提高圖片信噪比［1］。目前應(yīng)用較多的是3×3中值濾波器，主要應(yīng)用于復(fù)雜背景下的紅外追蹤和目標(biāo)探測(cè)領(lǐng)域。然而當(dāng)一副圖片的信噪比較低、噪聲密度較高時(shí)，3×3中值濾波器的濾波效果并不是很理想，導(dǎo)致目標(biāo)強(qiáng)度變?nèi)酢?/p>

本文針對(duì)處理噪聲圖片時(shí)數(shù)據(jù)量大、實(shí)時(shí)性要求較高的問(wèn)題，從算法比較次數(shù)、硬件資源占用、去噪處理后圖像質(zhì)量方面綜合考慮，在排序過(guò)程中引入歸并插入排序算法，用VHDL 語(yǔ)言設(shè)計(jì)了適合于FPGA 實(shí)現(xiàn)的5×5快速中值濾波器。與常規(guī)方法相比，該方法減少了比較次數(shù)和計(jì)算量，節(jié)省開(kāi)發(fā)成本，同時(shí)也方便在FPGA 上實(shí)現(xiàn)。

1 快速二維中值濾波算法

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

中值濾波的主要運(yùn)算就是對(duì)濾波窗口中的數(shù)值進(jìn)行排序。其基本單元是2個(gè)數(shù)值的大小比較然后排序。對(duì)于一個(gè)m×n的二維濾波采樣窗口，需要設(shè)計(jì)m×n個(gè)寄存器來(lái)存儲(chǔ)濾波窗口內(nèi)待處理的數(shù)據(jù)，之后再經(jīng)過(guò)排序運(yùn)算，得到濾波窗口中數(shù)據(jù)的中值［3］。

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

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

（1）將窗口中的25個(gè)數(shù)先按行沿箭頭方向進(jìn)行降序排列，如圖1 （a）所示；

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

（3）按對(duì)角線沿箭頭方向?qū)θ袛?shù)進(jìn)行降序排列，如圖1 （d）所示；

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

在如圖1快速中值濾波器行列降序排列及斜對(duì)角線5個(gè)數(shù)降序排列過(guò)程中，本文采用了歸并插入排序算法［7］，該算法能夠?qū)?個(gè)數(shù)在最少比較次數(shù)情況下得出排序結(jié)果，算法原理如下：

假設(shè)5×5濾波窗口中任一行 （或一列）5個(gè)數(shù)分別編號(hào)x1、x2、x3、x4、x5，x1與x2，x3與x4共比較2 次，假設(shè)比較結(jié)果x1＞x2，x3＞x4；x1與x3比較需1 次，假設(shè)比較結(jié)果為x1＞x3，則x1＞x3＞x4。當(dāng)x1＞x3＞x4時(shí)4個(gè)元素的有序關(guān)系如圖2所示 （連線表示左下元素大于右上元素）。

圖2 x1＞x3＞x4 時(shí)4個(gè)元素的有序關(guān)系

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

圖3 x5 插入x1，x3，x4 后有序關(guān)系

對(duì)以上任意一種情況，總可以通過(guò)兩次比較將x2插入由x1、x3、x4、x5構(gòu)成的有序隊(duì)中。這樣總共需要比較2＋1＋2＋2＝7次。若用分組排序網(wǎng)絡(luò)算法或插入法對(duì)x1、x2、x3、x4、x5進(jìn)行排序則需要比較10次。由此可見(jiàn)，將歸并插入算法應(yīng)用于快速中值濾波器中可進(jìn)一步減少比較次數(shù)，進(jìn)而提高系統(tǒng)運(yùn)算速度。

2 算法硬件設(shè)計(jì)

2.1 5×5采樣窗口模塊

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

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

圖4 5×5方形窗結(jié)構(gòu)框架

圖5 為5×5 方形窗仿真波形圖，可以看到在481400 ns時(shí)刻，5行的圖像數(shù)據(jù)中的每一行都能輸出5位數(shù)據(jù)且能夠保證無(wú)數(shù)據(jù)丟失和錯(cuò)位的情況下逐行移動(dòng)。因此，5×5方形窗的硬件設(shè)計(jì)達(dá)到了預(yù)期的要求。

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

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

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

圖6 5個(gè)數(shù)降序排列模塊RTL原理

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

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

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

通過(guò)圖8可以看出，25個(gè)數(shù)的中值在第四個(gè)時(shí)鐘周期就能正常輸出，保證了濾波算法的正確性和實(shí)時(shí)性。該算法的硬件模塊設(shè)計(jì)以盡可能的減少運(yùn)算量為基礎(chǔ)，用VHDL語(yǔ)言設(shè)計(jì)了適合在FPGA 上實(shí)現(xiàn)的行排序和列排序等硬件模塊，達(dá)到了設(shè)計(jì)的要求。

3 實(shí)驗(yàn)結(jié)果及分析

在該設(shè)計(jì)中板型選取的是Xilinx公司的Virtex－II PRO XC2VP30開(kāi)發(fā)板。為了能夠?qū)Ρ疚腎SE10.0環(huán)境下設(shè)計(jì)的快速中值濾波器硬件系統(tǒng)仿真，驗(yàn)證硬件系統(tǒng)設(shè)計(jì)的正確性，首先利用MATLAB將一幅480×320的圖像轉(zhuǎn)化為激勵(lì)文件，將該激勵(lì)文件保存在ISE 當(dāng)前的工程目錄；然后使用ISE Simulator進(jìn)行仿真，將輸出結(jié)果存入＊.txt文件；最后通過(guò)MATLAB 調(diào)用該＊.txt文件來(lái)顯示處理后的圖像［13］。

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

圖9 不同處理后圖片效果對(duì)比

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

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

表2 中值濾波器硬件資源使用情況、比較次數(shù)及時(shí)鐘延遲情況對(duì)比

4 結(jié)束語(yǔ)

針對(duì)較高密度的噪聲數(shù)字圖像，本文從中值濾波器的去噪性能、運(yùn)算速度以及硬件資源占用多方面綜合考慮，設(shè)計(jì)了一種5×5快速中值濾波器，在該濾波器中，應(yīng)用了歸并插入排序算法。相比常規(guī)算法，該算法能夠使中值濾波器的比較次數(shù)進(jìn)一步減少，提高了運(yùn)算速度。在ISE10.0環(huán)境下，本文算法的硬件設(shè)計(jì)達(dá)到要求，該算法結(jié)構(gòu)簡(jiǎn)單，系統(tǒng)實(shí)時(shí)性高，硬件資源占用較少，去噪效果明顯，且易在FPGA 上實(shí)現(xiàn)。為復(fù)雜背景下的紅外追蹤和目標(biāo)探測(cè)領(lǐng)域提供了一定的技術(shù)參考。

［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］.計(jì)算機(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）.［萬(wàn)海軍，何東建，徐尚中.基于FPGA 的圖像中值濾波算法硬件實(shí)現(xiàn) ［J］.微計(jì)算機(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ìn)的中值濾波圖像去噪方法研究 ［J］.計(jì)算機(jī)工程與設(shè)計(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í)分組排序網(wǎng)絡(luò)的實(shí)時(shí)大窗口二維中值濾波器設(shè)計(jì) ［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 的實(shí)時(shí)圖像自適應(yīng)中值濾波器設(shè)計(jì) ［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ìn)型中值濾波研究 ［J］.電子測(cè)試，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）.［吳偉娜，孫仕鵬，楊風(fēng)，等.常用排序算法的比較與分析 ［J］.電腦知識(shí)與技術(shù)，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）.［李國(guó)燕，候向丹，顧軍華，等.快速中值濾波算法的改進(jìn)及其FPGA 實(shí)現(xiàn) ［J］.電子技術(shù)應(yīng)用，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 的快速中值濾波器設(shè)計(jì)與實(shí)現(xiàn) ［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）.［沈?qū)W利，王肅國(guó).基于FPGA 的改進(jìn)型中值濾波算法研究 ［J］.微電子學(xué)與計(jì)算機(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ìn)的快速中值濾波算法在圖像去噪中的應(yīng)用 ［J］.測(cè)繪工程，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）. ［楊晶，王元慶.實(shí)時(shí)高速實(shí)現(xiàn)改進(jìn)型中值濾波算法 ［J］.計(jì)算機(jī)與現(xiàn)代化，2013 （8）：30－32.］

［13］ZHAN Xianning，TIAN Geng.VHDL development solutions and example analysis ［M］.Beijing：Electronic Industry Press，2009 （in Chinese）. ［詹仙寧，田耘.VHDL 開(kāi)發(fā)精解與實(shí)例剖析 ［M］.北京：電子工業(yè)出版社，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）.［李旭，趙文杰，楊凱達(dá).一種改進(jìn)的中值濾波算法 ［J］.中國(guó)體視學(xué)與圖像分析，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］.計(jì)算機(jī)與現(xiàn)代化，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 的圖像中值濾波器設(shè)計(jì) ［J］.微型機(jī)與應(yīng)用，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設(shè)計(jì)權(quán)威指南［M］.北京：清華大學(xué)出版社，201.］