傳統(tǒng)中值濾波算法與相關(guān)改進(jìn)算法的特點(diǎn)

張佳晨

（浙江師范大學(xué)）

摘要：中值濾波算法由于算法簡(jiǎn)單方便被廣泛應(yīng)用在圖像去噪中，但傳統(tǒng)中值濾波算法處理圖像過程中需要進(jìn)行的排序次數(shù)較多導(dǎo)致圖像處理速度較慢，在圖像實(shí)時(shí)處理中不能很好的應(yīng)用，因此許多學(xué)者對(duì)該算法中的排序算法進(jìn)行改進(jìn)，并提出了對(duì)中值濾波算法的改進(jìn)算法。本文對(duì)傳統(tǒng)中值濾波算法及幾種快速中值濾波算法的特點(diǎn)進(jìn)行了描述。

關(guān)鍵詞：中值濾波算法；快速中值濾波算法；排序算法

0 引言

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

1傳統(tǒng)中值濾波算法

1.1 傳統(tǒng)中值濾波算法

中值濾波算法是對(duì)圖像 中的每一個(gè)像素點(diǎn)的灰度值進(jìn)行處理，基于統(tǒng)計(jì)學(xué)基礎(chǔ)，對(duì)像素點(diǎn)灰度值進(jìn)行排序達(dá)到去噪目的，具有非線性的特點(diǎn)。其具體過程如下（以二維中值濾波為例）：取一像素點(diǎn)作為中心像素點(diǎn)，并以它為中心確定一個(gè)固定大小的濾波窗口，即確定它的鄰域范圍。

（x，y）為該中心像素點(diǎn)的位置，S_xy為以（x，y）為中心的鄰域，（m，n）即為鄰域中的任意一點(diǎn)，f（m，n）為點(diǎn)（m，n）的灰度值，Med{}即是對(duì)灰度值進(jìn)行大小排序，并取中間值，f（x，y）為（x，y）灰度值，在上面這個(gè)公式中它的值經(jīng)過該算法后將變?yōu)猷徲蛑懈鱾€(gè)點(diǎn)灰度值的中值。以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）這幾個(gè)點(diǎn)灰度值的中值，例如{6，1，2，4，5，0，3，2，3}即取3作為f（x，y）的值。

1.2優(yōu)點(diǎn)

中值濾波算法方式簡(jiǎn)單，根據(jù)脈沖噪聲的特點(diǎn)，這種噪聲像素就會(huì)在排序時(shí)排在兩邊，使這種噪聲像素得以消除。與均值濾波算法相比，不直接將窗口內(nèi)的像素灰度值簡(jiǎn)單的平均，使圖像的部分邊緣、細(xì)節(jié)得以保留。

1.3缺點(diǎn)

從圖像去噪處理速度的角度來(lái)看，傳統(tǒng)中值濾波算法在排序過程中采用冒泡排序，且每次在濾波窗口移動(dòng)后，都要進(jìn)行重新排序。假設(shè)濾波窗口中共有n個(gè)像素點(diǎn)，每排序一次就需要進(jìn)行n（n-1）/2次比較，其時(shí)間復(fù)雜度為O（n2），時(shí)間復(fù)雜度過于復(fù)雜。

從圖像去噪處理效果的角度來(lái)看，根據(jù)其特點(diǎn)，對(duì)于高密度的噪聲去噪效果比較差，很容易將信號(hào)點(diǎn)誤判為噪聲點(diǎn)。

2 快速中值濾波算法

快速中值濾波算法即對(duì)傳統(tǒng)濾波算法中排序算法進(jìn)行優(yōu)化，提高其排序效率以此來(lái)提高對(duì)圖像的處理速度。其中張國(guó)來(lái)提出了一種快速并行中值濾波算法[3]，牛敏等學(xué)者提出了一種基于排序統(tǒng)計(jì)理論的快速中值濾波法[4]，馬運(yùn)強(qiáng)等學(xué)者在牛敏等學(xué)者的基礎(chǔ)上提出了快速中值濾波算法[5]。

2.1三種快速濾波算法的相同點(diǎn)

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

2.2三種快速濾波算法的特點(diǎn)

張國(guó)來(lái)提出的算法中將每列進(jìn)行有序排列后，將這3列的最小值、中間值、最大值分別分在min、med、max這三組中，假設(shè)第一列三個(gè)點(diǎn)按大小順序?yàn)閙in1、med1、max1，第二列三個(gè)點(diǎn)按大小順序?yàn)閙in2、med2、max2，第三列同理，三列中最小、中間、最大值三組中的數(shù)與它們下標(biāo)大小相同，如圖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中產(chǎn)生，僅需要比較出這三個(gè)數(shù)的中值就可以確定中值。因此3列進(jìn)行排序要進(jìn)行9次比較，min中取出最小值需要進(jìn)行2次比較，max中取最大值需要進(jìn)行2次比較，而在med中取出中間值需要3次比較，最后三個(gè)數(shù)中取出中間值需要進(jìn)行3次比較，因此總的比較次數(shù)為19次。

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

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

參考文獻(xiàn)：

[1]沈德海， 侯建， 鄂旭，等. 一種改進(jìn)的加權(quán)均值濾波算法[J]. 現(xiàn)代電子技術(shù)， 2015（10）：1-3.

[2]王松林， 蔣崢. 改進(jìn)的自適應(yīng)加權(quán)中值濾波算法[J]. 傳感器與微系統(tǒng)， 2016， 35（11）：128-131.

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

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

[5]馬運(yùn)強(qiáng)， 魏利勝， 張平改，等. 一種快速的中值濾波算法[J]. 安徽工程大學(xué)學(xué)報(bào)， 2016， 31（4）：63-67.