傳統中值濾波算法與相關改進算法的特點

張佳晨

（浙江師范大學）

摘要：中值濾波算法由于算法簡單方便被廣泛應用在圖像去噪中，但傳統中值濾波算法處理圖像過程中需要進行的排序次數較多導致圖像處理速度較慢，在圖像實時處理中不能很好的應用，因此許多學者對該算法中的排序算法進行改進，并提出了對中值濾波算法的改進算法。本文對傳統中值濾波算法及幾種快速中值濾波算法的特點進行了描述。

關鍵詞：中值濾波算法；快速中值濾波算法；排序算法

0 引言

圖像在成像、編碼及傳輸等過程中，經常會受到各種干擾而形成噪聲。這些噪聲破壞了圖像中一些像素點的原有灰度值，使得圖像不能真實地反映客觀景象，圖像質量下降，嚴重影響了后續的處理效果。因此，在對圖像進行相關處理之前必須要進行濾波，以減小噪聲的干擾。[1]中值濾波算法是一種常見的去噪算法，相對于其他線性平滑濾波的方法而言，中值濾波在處理隨機噪聲方面具有很強的降噪濾波能力。[2]而這種算法在處理質量、速度方面都存在著不足，國內外學者對其研究并優化，本文介紹了張國來、牛敏、馬運強提出的三種改進后的快速中值濾波算法。

1傳統中值濾波算法

1.1 傳統中值濾波算法

中值濾波算法是對圖像 中的每一個像素點的灰度值進行處理，基于統計學基礎，對像素點灰度值進行排序達到去噪目的，具有非線性的特點。其具體過程如下（以二維中值濾波為例）：取一像素點作為中心像素點，并以它為中心確定一個固定大小的濾波窗口，即確定它的鄰域范圍。

（x，y）為該中心像素點的位置，S_xy為以（x，y）為中心的鄰域，（m，n）即為鄰域中的任意一點，f（m，n）為點（m，n）的灰度值，Med{}即是對灰度值進行大小排序，并取中間值，f（x，y）為（x，y）灰度值，在上面這個公式中它的值經過該算法后將變為鄰域中各個點灰度值的中值。以3*3的窗口大小為例，f（x，y）的值就是f（x-1，y），f（x-1，y-1），f（x-1，y+1），f（x，y），f（x，y-1），f（x，y+1），f（x+1，y），f（x+1，y-1），f（x+1，y+1）這幾個點灰度值的中值，例如{6，1，2，4，5，0，3，2，3}即取3作為f（x，y）的值。

1.2優點

中值濾波算法方式簡單，根據脈沖噪聲的特點，這種噪聲像素就會在排序時排在兩邊，使這種噪聲像素得以消除。與均值濾波算法相比，不直接將窗口內的像素灰度值簡單的平均，使圖像的部分邊緣、細節得以保留。

1.3缺點

從圖像去噪處理速度的角度來看，傳統中值濾波算法在排序過程中采用冒泡排序，且每次在濾波窗口移動后，都要進行重新排序。假設濾波窗口中共有n個像素點，每排序一次就需要進行n（n-1）/2次比較，其時間復雜度為O（n2），時間復雜度過于復雜。

從圖像去噪處理效果的角度來看，根據其特點，對于高密度的噪聲去噪效果比較差，很容易將信號點誤判為噪聲點。

2 快速中值濾波算法

快速中值濾波算法即對傳統濾波算法中排序算法進行優化，提高其排序效率以此來提高對圖像的處理速度。其中張國來提出了一種快速并行中值濾波算法[3]，牛敏等學者提出了一種基于排序統計理論的快速中值濾波法[4]，馬運強等學者在牛敏等學者的基礎上提出了快速中值濾波算法[5]。

2.1三種快速濾波算法的相同點

以3*3的濾波窗口為例，傳統濾波算法通過冒泡排序求得中值，需要通過36次比較。這幾種算法都通過先將這個濾波窗口的每行或者每列進行一個有序排列，在有序排列的基礎上通過每個點可能大于或小于其它點數的個數來確定不可能為中值的點，從而減少之后要進行比較的點，使最終比較次數減少，提高算法效率。

2.2三種快速濾波算法的特點

張國來提出的算法中將每列進行有序排列后，將這3列的最小值、中間值、最大值分別分在min、med、max這三組中，假設第一列三個點按大小順序為min1、med1、max1，第二列三個點按大小順序為min2、med2、max2，第三列同理，三列中最小、中間、最大值三組中的數與它們下標大小相同，如圖1中所示，可以判斷min1一定為最小值，min2至少小于min3、med3、max3，med2、max2，max3一定為最大值，max2至少大于max1、med1、min1、med2、min2，med1至少小于med2、med3、max1、max2、max3，med3一定大于min3、min2、min1、med2、med1，因此中值只可能在min3、max1、med2中產生，僅需要比較出這三個數的中值就可以確定中值。因此3列進行排序要進行9次比較，min中取出最小值需要進行2次比較，max中取最大值需要進行2次比較，而在med中取出中間值需要3次比較，最后三個數中取出中間值需要進行3次比較，因此總的比較次數為19次。

牛敏等學者提出來的算法將每行進行從小到大依次排序，之后與張國來不同之處在與將排序所得的三行的中值在按照從小到大依次排序，排序如圖2所示按照箭頭從小到大進行排序。由于將三行的中值也進行依次排序，幾個數之間的相互關系有了更大的聯系，與張國來在三組數中再次求出需要比較的點的思考方式不同，牛敏通過有序性這一特點進行比較。首先從圖3中明顯可以看到1、2點至少小于3、5、8、6、9，而8、9至少大于7、2、5、1、4，因此只需要在3、4、5、6、7這幾個點中得出中值，由于此時4、5、6已經為有序排列，因此只需要將3、7與5比較，若3、7一個大于5，一個小于5，顯然5為中值，若3、7同時小于5，那么中值將是4、3、7中的最大值，同時大于的情況也是同理。因此三行排列需要9次，中值的排列需要3次，3、7與5的比較需要2次，則最好情況為14次，若要進行最大值或者最小值的比較也需要2次，則最壞情況為16次，較之前張國來所提出的算法次數又一次進行了優化。

馬云強等學者所提出的算法中對于濾波窗口中像素點排序的比較方法與牛敏一文中所提出的算法基本相同。而在這一基礎上，馬云強通過相鄰窗口的相關性對相鄰窗口間的中值比較進行了優化。以3*3的窗口為例，假設當前濾波窗口為E（xy），則將其水平平移向右移動一個像素點后，窗口變為E（x2y+1），而窗口中像素點只是最左列消除多增加了最右列，原來窗口中的兩行不變，如圖4所示。已知j、j+1列已經經過排序，因此只需要在對j+2列進行排序，而j、j+1列的中值已經按從小到大的順序排列，因此對于j、j+1、j+2三行中的中值按從小到大排序只需要比較2次即可，之后按牛敏一文中的方法，通過有序性進行比較，最好情況一共需要7次，而最壞情況需要9次，若要對某一行中n個像素點進行中值處理時，在原來的算法要需要16n-14n之間，而改進后只需要9n-7n（n趨向于無窮大時），這大大提高了算法的效率。

參考文獻：

[1]沈德海， 侯建， 鄂旭，等. 一種改進的加權均值濾波算法[J]. 現代電子技術， 2015（10）：1-3.

[2]王松林， 蔣崢. 改進的自適應加權中值濾波算法[J]. 傳感器與微系統， 2016， 35（11）：128-131.

[3]張國來. 快速并行中值濾波的探討[J]. 電子世界， 2014（18）：407-408.

[4]牛敏， 鄔戰軍， 牛燕雄，等. 一種基于排序統計理論的快速圖像中值濾波法[J]. 電子測量技術， 2015（6）：60-63.

[5]馬運強， 魏利勝， 張平改，等. 一種快速的中值濾波算法[J]. 安徽工程大學學報， 2016， 31（4）：63-67.