一種快速的中值濾波算法

馬運強，魏利勝，張平改，吉　濤（.安徽工程大學電氣工程學院，安徽蕪湖　24000，2.安徽機電職業技術學院電氣工程系，安徽蕪湖　24000）

一種快速的中值濾波算法

馬運強1，2，魏利勝1?，張平改1，吉濤1
（1.安徽工程大學電氣工程學院，安徽蕪湖241000，2.安徽機電職業技術學院電氣工程系，安徽蕪湖241000）

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

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

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

1　標準的中值濾波算法

標準中值濾波算法原理［10-12］：數字圖像窗口某點像素領域內濾波窗口所有像素按照灰度值大小進行排序，排序后中間位置的灰度值即為中值，用中值代替原像素的灰度值.若濾波窗口的像素個數為偶數，則排序后兩個中間位置灰度值的平均值即為中值.標準中值濾波窗口是N（N取奇數）維的移動的窗口，濾波窗口從左往右，從上往下滑動.對于一幅N×M的數字圖像用矩陣形式表示為F，如式（1）所示：

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

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

2　改進的中值濾波算法

以上標準的中值濾波算法雖然降低了濾波窗口查找中值的比較次數，但是比較次數依然較多.排序算法的優劣直接影響著查找中值的效率，為了以更低的比較次數查找中值，提出一種快速的中值濾波算法.該算法充分利用統計理論排序法和相鄰窗口行列信息相關原理進行排序，可以更加高效地降低濾波窗口查找中值的比較次數.

首先利用統計理論排序法查找濾波窗口的中值，然后利用相鄰窗口行列信息相關性的原理進而查找f（i，j）像素濾波窗口的中值.其整體查找中值效率將優于以上算法，排序比較次數更低.利用統計理論排序法對濾波窗口進行排序，濾波窗口共有9個像素，排列成3列3行.將3列像素按照向下升序排列得到3組新序列，將3組新序列按照f（i，j-1）、f（i，j）、f（i，j+1）像素大小向右升序排組，得到最終排序濾波窗口.虛線箭頭方向為升序方向，如圖1所示.

對最終排序得到濾波窗口進行分析，f（i-1，j-1）不可能是中值，因為f（i-1，j-1）像素值小于窗口的其他6個像素值（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個像素（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）也不可能是中值，因為f（i，j+1）和f（i+1，j+1）至少大于窗口其他的5個像素值，因此濾波窗口的中值應該在f（i-1，j）、f（i-1，j+1）、f（i，j）、f（i+1，j-1）、f（i+1，j）之中.當f（i-1，j+1）和f（i+1，j-1）一個大于f（i，j），另一個小于f（i，j）時，或者f（i-1，j+1）和f（i+1，j-1）同時等于f（i，j）時，則f（i，j）為濾波窗口的中值，且比較次數為2次.當f（i-1，j+1）和f（i+1，j-1）同時大于f（i，j）時，則f（i，j）、f（i-1，j+1）、f（i+1，j-1）最小值為濾波窗口的中值，或者f（i-1，j+1）和f（i+1，j-1）同時小于f（i，j）時，則f（i，j）、f（i-1，j+1）、f（i+1，j-1）的最大值為濾波窗口的中值，且比較次數為4次.3列像素向下升序排序比較需要9次，3組新序列按照f（i，j-1）、f（i，j）、f（i，j+1）像素值大小向右升序排組，排序比較次數需要3次，因此利用統計理論排序法進行排序最好排序比較次數需要14次，最壞排序比較次數需16次.

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

（1）對濾波窗口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（i，j）、f（i，j+1）、f（i，j+2）像素值向右升序排列；

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

圖1　3×3濾波窗的排序

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

3　算法復雜度的優劣對比

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

4　仿真實驗

為了驗證所提出算法的可行性，仿真實驗對3 264×2 248 School圖像和512×512 Lena圖像分別采用所提出的算法和傳統的中值濾波算法進行仿真.實驗平臺計算機為Window 7系統，2 GB內存，程序運行環境為Matlab 7.11.School和Lena圖像濾波效果分別如圖3和圖4所示.圖3a和圖4a分別為School和Lena源圖像；圖3b和圖4b分別為School和Lena圖像加入20%椒鹽噪音的效果；圖3c和圖4c分別為School和Lena圖像運用所提算法處理后效果；圖3d和圖4d分別為School和Lena圖像運用Matlab中3×3標準中值濾波算法處理后的效果.通過圖3b和圖3c對比可以得出所提出的算法具有良好去噪能力，同時可以較好地保留細節信息；通過圖4c和圖4d對比得出所提出的算法可以去除標準中值濾波算法難以過濾的噪音.

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

圖3　School圖像濾波效果

圖4　Lena圖像濾波效果

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

5　結論

鑒于標準中值濾波算法查找中值排序工作量大、運算速度慢、不能滿足圖像處理實時性，首先介紹了標準的中值濾波算法和一些改進中值濾波算法，進而提出一種快速的中值濾波算法.所提出算法首先利用統計理論排序法對濾波窗口像素排序，在此基礎上利用濾波窗口行列信息相關性原理進一步進行排序比較.最后通過仿真實驗得出所提算法抑制噪聲能力強，濾波效果比較滿意，算法時間復雜度較低.

［1］趙君愛，魏艷春.基于改進中值濾波的圖像噪聲去除算法的研究［J］.浙江農業學報，2015，27（6）：1 078-1 082.

［2］鐘濤，張建國，左俊彥.一種改進的中值濾波算法及其應用［J］.云南大學學報：自然科學版，2015，37（4）：505-510.

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

［4］朱捷，朱小娟，賀明.基FPGA的實時性的圖像處理中值濾波器設計實現［J］.計算機測量與控制，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的圖像處理系統［J］.華中科技大學學報：自然科學版，2015，2（2）：119-123.

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

［8］陳元朝，李麗宏.自適應濾波算法在車輛寬高檢測系統中的應用研究［J］.中國測試，2014，40（2）：40-43.

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

［10］牛敏，鄔建軍，牛燕雄，等.一種基于排序統計理論的快速圖像中值濾波法［J］.電子測量技術，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

國家自然科學基金資助項目（61203033）

馬運強（1989-），男，安徽亳州人，碩士研究生.

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