一種快速的中值濾波算法

馬運(yùn)強(qiáng)，魏利勝，張平改，吉　濤（.安徽工程大學(xué)電氣工程學(xué)院，安徽蕪湖　24000，2.安徽機(jī)電職業(yè)技術(shù)學(xué)院電氣工程系，安徽蕪湖　24000）

一種快速的中值濾波算法

馬運(yùn)強(qiáng)1，2，魏利勝1?，張平改1，吉濤1
（1.安徽工程大學(xué)電氣工程學(xué)院，安徽蕪湖241000，2.安徽機(jī)電職業(yè)技術(shù)學(xué)院電氣工程系，安徽蕪湖241000）

鑒于中值濾波算法中排序次數(shù)多、程序運(yùn)行效率低的缺點(diǎn)，提出了一種快速的中值濾波算法.首先，利用統(tǒng)計(jì)理論排序法對(duì)濾波窗口的像素全面排序比較；在此基礎(chǔ)上，利用相鄰濾波窗口行列信息之間的相關(guān)性原理，通過(guò)遷出、移入一列新像素，同時(shí)保留剩余列像素的排序信息，從而快速查找到濾波窗口的中值；最后，通過(guò)仿真實(shí)驗(yàn)對(duì)比得出所提算法有效地降低了排序比較次數(shù)和算法的復(fù)雜度，滿(mǎn)足圖像處理的實(shí)時(shí)性.

濾波窗口；中值；排序比較；算法

在數(shù)字圖像處理中，由于背景光照不均、電氣設(shè)備磁場(chǎng)信號(hào)干擾等原因，采集的圖像存在很多隨機(jī)噪聲［1-3］.而隨機(jī)噪聲不僅降低了圖像的質(zhì)量與美感，還影響后期數(shù)字圖像的灰度化、邊緣檢測(cè)、圖像分割、圖像拼接等.為了提高圖像的效果和美感，需要對(duì)圖像進(jìn)行預(yù)處理，如圖像增強(qiáng)、圖像濾波、圖像平滑等.而中值濾波是剔除圖像噪音、改善圖像質(zhì)量最有效措施之一.中值濾波是一種典型的非線(xiàn)性濾波技術(shù)，不但可以有效地抑制多種圖像噪音，而且能有效地保留圖像邊緣細(xì)節(jié)信息，故其得到了廣泛地運(yùn)用和推廣.但是標(biāo)準(zhǔn)的中值濾波算法由于算法排序量大，運(yùn)算速度緩慢，不能實(shí)時(shí)高效地抑制圖像噪音.因此，如何降低中值濾波排序比較次數(shù)具有重要的研究意義.

1　標(biāo)準(zhǔn)的中值濾波算法

標(biāo)準(zhǔn)中值濾波算法原理［10-12］：數(shù)字圖像窗口某點(diǎn)像素領(lǐng)域內(nèi)濾波窗口所有像素按照灰度值大小進(jìn)行排序，排序后中間位置的灰度值即為中值，用中值代替原像素的灰度值.若濾波窗口的像素個(gè)數(shù)為偶數(shù)，則排序后兩個(gè)中間位置灰度值的平均值即為中值.標(biāo)準(zhǔn)中值濾波窗口是N（N取奇數(shù)）維的移動(dòng)的窗口，濾波窗口從左往右，從上往下滑動(dòng).對(duì)于一幅N×M的數(shù)字圖像用矩陣形式表示為F，如式（1）所示：

若3×3濾波窗口的中心元素為（i，j），則3×3濾波窗口用矩陣表示為E（i，j），如式（2）所示：

其中，h（x，y）表示濾波后圖像；f（x，y）表示原圖像；E（i，j）表示濾波窗口；（i，j）表示濾波窗口的中心像素點(diǎn)；i表示濾波窗口水平尺度；j表示窗口垂直尺度.

2　改進(jìn)的中值濾波算法

以上標(biāo)準(zhǔn)的中值濾波算法雖然降低了濾波窗口查找中值的比較次數(shù)，但是比較次數(shù)依然較多.排序算法的優(yōu)劣直接影響著查找中值的效率，為了以更低的比較次數(shù)查找中值，提出一種快速的中值濾波算法.該算法充分利用統(tǒng)計(jì)理論排序法和相鄰窗口行列信息相關(guān)原理進(jìn)行排序，可以更加高效地降低濾波窗口查找中值的比較次數(shù).

首先利用統(tǒng)計(jì)理論排序法查找濾波窗口的中值，然后利用相鄰窗口行列信息相關(guān)性的原理進(jìn)而查找f（i，j）像素濾波窗口的中值.其整體查找中值效率將優(yōu)于以上算法，排序比較次數(shù)更低.利用統(tǒng)計(jì)理論排序法對(duì)濾波窗口進(jìn)行排序，濾波窗口共有9個(gè)像素，排列成3列3行.將3列像素按照向下升序排列得到3組新序列，將3組新序列按照f(shuō)（i，j-1）、f（i，j）、f（i，j+1）像素大小向右升序排組，得到最終排序?yàn)V波窗口.虛線(xiàn)箭頭方向?yàn)樯蚍较?，如圖1所示.

對(duì)最終排序得到濾波窗口進(jìn)行分析，f（i-1，j-1）不可能是中值，因?yàn)閒（i-1，j-1）像素值小于窗口的其他6個(gè)像素值（f（i，j-1）、f（i，j）、f（i，j+1）、f（i+1，j-1）、f（i+1，j）、f（i+1，j+1））.由于f（i，j-1）的像素值小于窗口的其他5個(gè)像素（f（i，j）、f（i，j+1）、f（i+1，j-1）、f（i+1，j）、f（i+1，j+1）），因此f（i，j-1）不是中值.同理可知f（i，j+1）和f（i+1，j+1）也不可能是中值，因?yàn)閒（i，j+1）和f（i+1，j+1）至少大于窗口其他的5個(gè)像素值，因此濾波窗口的中值應(yīng)該在f（i-1，j）、f（i-1，j+1）、f（i，j）、f（i+1，j-1）、f（i+1，j）之中.當(dāng)f（i-1，j+1）和f（i+1，j-1）一個(gè)大于f（i，j），另一個(gè)小于f（i，j）時(shí)，或者f（i-1，j+1）和f（i+1，j-1）同時(shí)等于f（i，j）時(shí)，則f（i，j）為濾波窗口的中值，且比較次數(shù)為2次.當(dāng)f（i-1，j+1）和f（i+1，j-1）同時(shí)大于f（i，j）時(shí)，則f（i，j）、f（i-1，j+1）、f（i+1，j-1）最小值為濾波窗口的中值，或者f（i-1，j+1）和f（i+1，j-1）同時(shí)小于f（i，j）時(shí)，則f（i，j）、f（i-1，j+1）、f（i+1，j-1）的最大值為濾波窗口的中值，且比較次數(shù)為4次.3列像素向下升序排序比較需要9次，3組新序列按照f(shuō)（i，j-1）、f（i，j）、f（i，j+1）像素值大小向右升序排組，排序比較次數(shù)需要3次，因此利用統(tǒng)計(jì)理論排序法進(jìn)行排序最好排序比較次數(shù)需要14次，最壞排序比較次數(shù)需16次.

為了以更低的比較次數(shù)查找窗口中值，利用相鄰窗口行列信息相關(guān)性的原理進(jìn)一步排序，同時(shí)進(jìn)一步降低濾波窗口整體的排序次數(shù).設(shè)當(dāng)前濾波窗口為E（i，j），沿水平方向移動(dòng)后的濾波窗口為E′（i，j+1）.濾波窗口E′（i，j+1）在第j+2列移入一列新像素，同時(shí)移出E（i，j）對(duì)應(yīng)第j-1列像素，如圖2所示.濾波窗口E′（i，j+1）的第j和j+1列像素的排序信息是已知，因此對(duì)于濾波窗口E′（i，j+1）無(wú)需再次排序比較j和j+1列像素，其步驟如下所示：

（1）對(duì)濾波窗口E′（i，j+1）更新的第j+2列像素按照向下升序排序.濾波窗口E′（i，j+1）第j和j+1列像素排序信息未變，只需將第j+2列像素與第j和j+1列像素比較；

（2）將第j和j+1及j+2列像素按照f(shuō)（i，j）、f（i，j+1）、f（i，j+2）像素值向右升序排列；

（3）最后運(yùn)用上述統(tǒng)計(jì)理論排序法可快速查找到中值，查找濾波窗口E′（i，j+1）中值，第j+2列像素需排序比較3次，3列像素按照行中心值大小需排序比較2次，分析剩余像素排序比較次數(shù)最壞需4次，最優(yōu)需2次.

圖1　3×3濾波窗的排序

圖2　濾波窗口E（i，j）及E′（i，j+1）

3　算法復(fù)雜度的優(yōu)劣對(duì)比

由于所提出算法選取濾波窗口為3×3，可知濾波窗口E′（i，j+1）最壞排序比較次數(shù)需要9次，最優(yōu)排序比較次數(shù)需7次.當(dāng)濾波窗口需要查找某行中的m個(gè)像素的中值，則濾波窗口最壞排序比較需要16+9（m-1）次，最優(yōu)排序比較需要14+7（m-1）次.當(dāng)m趨于無(wú)窮大，則濾波窗口最優(yōu)排序比較需要7m次，最壞排序比較需要9m次.

4　仿真實(shí)驗(yàn)

為了驗(yàn)證所提出算法的可行性，仿真實(shí)驗(yàn)對(duì)3 264×2 248 School圖像和512×512 Lena圖像分別采用所提出的算法和傳統(tǒng)的中值濾波算法進(jìn)行仿真.實(shí)驗(yàn)平臺(tái)計(jì)算機(jī)為Window 7系統(tǒng)，2 GB內(nèi)存，程序運(yùn)行環(huán)境為Matlab 7.11.School和Lena圖像濾波效果分別如圖3和圖4所示.圖3a和圖4a分別為School和Lena源圖像；圖3b和圖4b分別為School和Lena圖像加入20%椒鹽噪音的效果；圖3c和圖4c分別為School和Lena圖像運(yùn)用所提算法處理后效果；圖3d和圖4d分別為School和Lena圖像運(yùn)用Matlab中3×3標(biāo)準(zhǔn)中值濾波算法處理后的效果.通過(guò)圖3b和圖3c對(duì)比可以得出所提出的算法具有良好去噪能力，同時(shí)可以較好地保留細(xì)節(jié)信息；通過(guò)圖4c和圖4d對(duì)比得出所提出的算法可以去除標(biāo)準(zhǔn)中值濾波算法難以過(guò)濾的噪音.

中值濾波算法的復(fù)雜度與算法查找濾波窗口中值的排序次數(shù)成線(xiàn)性關(guān)系，有效降低排序比較次數(shù)，可降低算法的時(shí)間復(fù)雜度.為了進(jìn)一步說(shuō)明所提出方法的優(yōu)越性，算法的復(fù)雜度和效率指標(biāo)如表1所示，由表1可知，查找單個(gè)像素中值冒泡法的復(fù)雜度為36次，文獻(xiàn)［4］方法復(fù)雜度為30次，所提出算法在最優(yōu)情況下復(fù)雜度為14次.查找m個(gè)像素中值冒泡法的復(fù)雜度為36m次，所提出算法在最優(yōu)情況下復(fù)雜度為7m次，效率提高了80.5%.冒泡法處理School圖像所需時(shí)間為1.237 s，所提出算法在最優(yōu)情況下處理School圖像所需時(shí)間為0.572 s，所提出算法處理School圖像時(shí)間復(fù)雜度只有冒泡法的46.24%.因此，所提出算法處理濾波窗口查找中值所需次數(shù)最少.效率最高、算法復(fù)雜度最低.當(dāng)查找中值的像素越多，所提出算法排序次數(shù)越少，效果越明顯，時(shí)間復(fù)雜度越低.

圖3　School圖像濾波效果

圖4　Lena圖像濾波效果

表1　3×3濾波窗口查找中值各算法復(fù)雜度及效率

5　結(jié)論

鑒于標(biāo)準(zhǔn)中值濾波算法查找中值排序工作量大、運(yùn)算速度慢、不能滿(mǎn)足圖像處理實(shí)時(shí)性，首先介紹了標(biāo)準(zhǔn)的中值濾波算法和一些改進(jìn)中值濾波算法，進(jìn)而提出一種快速的中值濾波算法.所提出算法首先利用統(tǒng)計(jì)理論排序法對(duì)濾波窗口像素排序，在此基礎(chǔ)上利用濾波窗口行列信息相關(guān)性原理進(jìn)一步進(jìn)行排序比較.最后通過(guò)仿真實(shí)驗(yàn)得出所提算法抑制噪聲能力強(qiáng)，濾波效果比較滿(mǎn)意，算法時(shí)間復(fù)雜度較低.

［1］趙君愛(ài)，魏艷春.基于改進(jìn)中值濾波的圖像噪聲去除算法的研究［J］.浙江農(nóng)業(yè)學(xué)報(bào)，2015，27（6）：1 078-1 082.

［2］鐘濤，張建國(guó)，左俊彥.一種改進(jìn)的中值濾波算法及其應(yīng)用［J］.云南大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，37（4）：505-510.

［3］董恩增，吳東東，佟吉鋼.快速二維中值濾波算法及其FPGA硬件設(shè)計(jì)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2015，36（7）：1 752-1 756.

［4］朱捷，朱小娟，賀明.基FPGA的實(shí)時(shí)性的圖像處理中值濾波器設(shè)計(jì)實(shí)現(xiàn)［J］.計(jì)算機(jī)測(cè)量與控制，2007，15（6）：798-800.

［5］P J Wei，L Zhang.Fast Median Filtering Algorithm Based on FPGA［C］//Signal Processing（ICSP）2010 IEEE 10th International Conference on，USA：IEEE Press，2010：426-429.

［6］楊帆，張皓，馬新文，等.基于FPGA的圖像處理系統(tǒng)［J］.華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，2（2）：119-123.

［7］王宇新，賀圓圓，郭禾.基于FPGA的快速中值濾波算法［J］.計(jì)算機(jī)應(yīng)用研究，2009，26（1）：224-226.

［8］陳元朝，李麗宏.自適應(yīng)濾波算法在車(chē)輛寬高檢測(cè)系統(tǒng)中的應(yīng)用研究［J］.中國(guó)測(cè)試，2014，40（2）：40-43.

［9］曾志剛，楊海，黃望軍.基于自適應(yīng)濾波與模糊PID的移動(dòng)機(jī)器人導(dǎo)航研究［J］.控制工程，2015，22（5）：953-957.

［10］牛敏，鄔建軍，牛燕雄，等.一種基于排序統(tǒng)計(jì)理論的快速圖像中值濾波法［J］.電子測(cè)量技術(shù)，2015，38（6）：60-63.

［11］X Geng，X G Hu.Quatertion Switching Filter for Impulse Noise Rsdution in Color Image［J］.Signal Processing Letters，2012，92（1）：150-162.

［12］H Yuan.Blind Forensics of Median Filtering in Digital Images［J］.IEEE Transactions on Information Forensics and Security，2011，6（4）：1 335-1 345.

A Fast Algorithm of Median Filter

MA Yun-qiang1，2，WEI Li-sheng1?，ZHANG Ping-gai1，JI Tao1
（1.College of Electrical Engineering，Anhui Polytechnic University，Wuhu 241000，China；2.Department of Electrical Engineering，Anhui Technical College of Mechanical and Electrical Engineering，Wuhu 241000，China）

A fast median filtering algorithm was proposed to improve complex sorting and low efficiency in the Median filtering algorithm.First of all，the pixels of filter window were sorted by the order statistics theory.Based on this，the median of filter window was quickly found by using the relationship between the adjacent filtering window category information.And a new pair of pixels was migrated，while the ordering information of the remaining column pixels was reserved.Finally，the results of contrast experiment were presented to verify the high efficiency of the proposed method.

filter window；median；comparison；algorithm

TP391

A

1672-2477（2016）04-0063-05

2016-01-10

國(guó)家自然科學(xué)基金資助項(xiàng)目（61203033）

馬運(yùn)強(qiáng)（1989-），男，安徽亳州人，碩士研究生.

魏利勝（1978-），男，安徽巢湖人，副教授，博士.