一種圖像中值濾波的加速算法研究

時慧琨，王 源

淮南師范學(xué)院計算機學(xué)院，安徽淮南，232038

?

一種圖像中值濾波的加速算法研究

時慧琨，王 源

淮南師范學(xué)院計算機學(xué)院，安徽淮南，232038

針對傳統(tǒng)的基于元素選擇算法進行中值濾波速度較慢的缺點，考慮到中值濾波窗口中像素取值具有一定程度的重復(fù)性，在一趟處理過程中，增加了將處理區(qū)域內(nèi)與主元值相同的元素移動到序列兩端的處理，并判斷主元或其重復(fù)值是否為中值：若是則可以提前確定濾波結(jié)果，若不是則可以將其全部排除，從而降低了下趟處理的數(shù)據(jù)量，提高了處理的速度。實驗驗證了該方法在不同噪聲比例、不同濾波窗口及不同圖像下的性能，結(jié)果表明該方法可以加快濾波速度，并且隨著濾波區(qū)域的擴大性能更好。

中值濾波；圖像處理；元素選擇算法

1 問題的提出

圖像噪聲是指圖像在獲取、存儲、處理及傳輸過程中由于內(nèi)部及外部原因而對圖像質(zhì)量的破壞因素。中值濾波是一種典型的非線性濾波方法，其基本思想是對圖像像素鄰域內(nèi)所有點值進行排序，取序列的中值作為濾波后的結(jié)果。該方法能夠去除或者減少隨機噪聲和脈沖干擾，較好地保留圖像的細(xì)節(jié)及圖像邊緣信息，在一定程度上克服線性濾波所帶來的圖像模糊現(xiàn)象，因此被大量應(yīng)用于二維圖像的預(yù)處理過程中。

中值濾波是一種點處理方法，處理時間與處理算法、濾波窗口的尺寸及圖像分辨率三個因素有關(guān)。因此，當(dāng)濾波窗口及圖像尺寸較大時，處理的時間較長，甚至無法達到實時性的要求。為此，出現(xiàn)了許多加快濾波速度的方法，常見的改進方法有：(1)基于后續(xù)窗口與前面窗口部分?jǐn)?shù)據(jù)的重疊特性，利用前一次排序的結(jié)果加快排序過程[1-2]。(2)選點法，即只對鄰域內(nèi)部分點進行濾波處理，從而減少計算量。一種思路是對濾波窗口的大小和形狀進行選擇，除了常規(guī)的正方形窗口外，也可以選擇方形、菱形、十字形和交叉型等不同的濾波窗口[3]。還有一種思路是對噪聲點進行選擇，可以基于視覺特性的噪聲敏感系數(shù)[4]，也可以基于統(tǒng)計學(xué)中的均值或方差[5]等對像素點進行判定，如果判定為圖像像素點則不作處理，如果判定為噪聲點則進行濾波。(3)優(yōu)化排序算法，避免出現(xiàn)最差情況，盡量提前確定中值是優(yōu)化研究的重點，如基于均值查找的中值濾波算法[6]。(4)并行方法。該方法是在FPGA中放入多個硬件處理單元，以加速濾波過程[7]。(5)近似方法。該類方法找到的不是序列的中值，而是與中值接近的“偽中值”[8]。偽中值的計算較為簡單，從而加快了處理速度。在實際應(yīng)用中，可以采用其中的一種或多種方式來提高中值濾波速度。

本文的主要工作是在基于快速排序的中值濾波算法基礎(chǔ)上對其進行優(yōu)化，提高了濾波速度。其改進原理是在快速排序的一趟處理過程中，考慮到濾波窗口中存在像素值相同的元素，增加了將與主元值相同的元素移動到序列的兩端進行處理的步驟，并通過對各個部分長度的計算判斷所求值是否落在主元以及與主元相同元素所在區(qū)間，如果是則直接輸出，如果不是則可以將主元和移動到兩端的元素均排除。與原始的方法相比，可以提前確定中值，減少下趟處理時數(shù)據(jù)區(qū)域的長度，降低了遞歸次數(shù)，加快了處理速度。在本文的最后，對改進后的算法進行了實驗驗證，并分析了實驗結(jié)果。

2 中值濾波算法及改進原理

2.1 基于元素選擇算法的中值濾波

在中值濾波的實現(xiàn)方法中，基于快速排序的方法是目前最常用的方法，盡管快速排序在最差情況下的復(fù)雜度為O(n2)，但可以通過隨機化等方式使得復(fù)雜度降為O(nlog2n)。將快速排序應(yīng)用到中值濾波上時，可以進一步降低復(fù)雜度。因為在實際應(yīng)用中需要的并不是一個排序后的序列，而只是需要該序列中的中值，這在算法中屬于元素選擇問題[9]。即給定一個線性序集中n個元素和一個整數(shù)k，1≤k≤n，要求找出這n個元素中第k小的元素的問題。對于中值問題，k=(n+1)/2，這個問題可以在快速排序的基礎(chǔ)上解決。常見的基于快速排序的元素選擇方法的代碼如下：

//從數(shù)組A[low..high]中找出第i小的元素

int select(int A[ ],int low,int high,int i)

{

int lpos,rpos,k,pivot;

lpos=low;rpos=high;

if(low==high) return A[low];

pivot=A[lpos];

while(lpos

{

while(lpos=pivot)

--rpos;

A[lpos]=A[rpos];

while(lpos

++lpos;

A[rpos]=A[lpos];

}

A[lpos]=pivot;

k=lpos-low+1;

if(i==k)

return A[lpos];

else if(i

return select(A,low,lpos-1,i);

else

return select(A,lpos+1,high,i-k);

}

在以上代碼中，從一維數(shù)組的“A[low]..A[high]”中選取按數(shù)組從小到大排序位于第i位置的元素，以“A[low]”為主元(pivot)，利用快速排序的一趟排序?qū)⒃瓟?shù)組分成比主元小的元素子序列、主元及比主元大的元素子序列，并計算主元在一次排序后的位置，若主元最終的位置正好為i，則直接返回。否則，根據(jù)所求位置i處在前半序列還是后半序列遞歸調(diào)用原函數(shù)即可。對于中值濾波，只需要取i=(n+1)/2即可。

以上算法簡單高效，在平均情況下可以在O(n)即線性時間內(nèi)完成，在最壞情況下，可能需要O(n2)時間內(nèi)完成，但可以通過隨機化選擇主元等方式消除最壞情況。

2.2 中值濾波改進算法

在圖像的中值濾波中，可以采用如上的方法。由于中值濾波是一種點處理方法，因此對處理大型圖像數(shù)據(jù)時執(zhí)行效率低，速度慢。另外，對圖像中像素取值的統(tǒng)計分析可知，盡管圖像的尺寸可以很大，但圖像像素取值即像素的灰度種類是有限的，在像素某個鄰域內(nèi)出現(xiàn)的像素灰度種類也是有限的，很多位置的像素灰度值是相同的?？紤]到圖像像素鄰域內(nèi)存在相同的灰度值因素后，將上述的select算法改進如下：

//從數(shù)組A的[low..high]中選取其中第i小的元素

int improvedSelect (int A[ ],int low,int high,int i)

{ //lpos：遍歷左指針, rpos：遍歷右指針，pivot：主元

//p：左邊相同元素的序號, q：右邊相同元素的序號，

int lpos,rpos,j,k,p,q,pivot;

if(low==high) return A[low];

lpos=low;rpos=high;p=low-1;q=high+1;

pivot=A[lpos];//主元取最左邊的元素

while(lpos

{

while(lpos=pivot)

{

//將從右向左找到等于pivot的元素交換到序列最右邊

if(A[rpos]==pivot&&(--q!=rpos))

swap(A[rpos],A[q]);

--rpos;

}

A[lpos]=A[rpos];

while(lpos

{

//將從左向右訪問到的等于pivot的元素交換到最左邊

if(A[lpos]==pivot&&(++p!=lpos))

swap(A[lpos],A[p]);

++lpos;

}

A[rpos]=A[lpos];

}

A[lpos]=pivot;

//判斷i是否落入主元值對應(yīng)的區(qū)間

if(i>lpos-p-1&&i<=high-q+lpos-low+2)

return A[lpos];

else if(i

return improvedSelect(A,p+1,lpos-1,i);

else return

improvedSelect(A,lpos+1,q-1,

i-(high-q+lpos-low+2));

}

以上算法以快速排序為基礎(chǔ)，但與select算法不同的是：在從右向左以及從左向右搜索的過程中，將找到的與主元相同的元素分別與序列的最右邊及最左邊元素進行互換，從而將與主元相同的元素匯集到序列的兩側(cè)，最后得到了如圖1的結(jié)構(gòu)。

圖1 算法一趟執(zhí)行后數(shù)據(jù)分布

當(dāng)一趟搜索完成后，整個序列分成5個部分：從左向右搜索找到的同主元相同的元素“A[low..p]”，小于主元的元素“A[p+1..lpos-1]”，主元“A[lpos]”，大于主元的元素“A[lpos+1..q-1]”，從右向左搜索找到的同主元相同的元素“A[q..right]”。通過以上信息可以計算出小于、等于、大于主元的像素子序列的長度(注意等于主元的元素長度由三個部分相加得到)，如果要尋找的第i個元素的序號在等于主元元素的范圍內(nèi)，則可以直接返回。否則，分別在小于或大于主元元素的部分里遞歸查找。

在以上算法中，與select算法只能對主元是否為中值進行判斷不同的是，improvedSelect算法可以對所有等于主元值的元素進行判斷，即一次對一種灰度值是否為中值進行判斷。因此，算法性能同像素鄰域內(nèi)的灰度值種類有關(guān)。假設(shè)圖像鄰域大小為N，鄰域內(nèi)灰度種類為C，則改進后的算法在平均情況下的復(fù)雜度為O(C)，而C≤N，從而使性能得到改進。假設(shè)圖像高度為H，寬度為W，圖像中的像素點為I(x,y)，鄰域大小為N，位置(x,y)鄰域內(nèi)的灰度值種類數(shù)為C(x,y)，則定義指標(biāo)圖像灰度多樣度IGMR(Image Gray Multiplicity Ratio)為:

該指標(biāo)描述了圖像鄰域內(nèi)灰度的變化程度，指標(biāo)值越小，表明鄰域內(nèi)灰度的重復(fù)率越高，算法改進的效果越好。若處理序列中所有的元素均不相同，則算法的性能同原有算法一致，并不會降低算法的性能。

3 實驗驗證及結(jié)果

在實驗指標(biāo)方面，衡量執(zhí)行速度常用的是執(zhí)行時間，本文統(tǒng)計了原算法及改進后算法對圖像執(zhí)行中值濾波的運行時間。除此之外，因為原算法及改進算法均使用了遞歸調(diào)用，遞歸次數(shù)的多少跟運行性能有很大的相關(guān)性，因此，還比較了改進前后遞歸次數(shù)的變化情況。

實驗中，采用了數(shù)字圖像處理中常用的lena圖及baboon圖，采用原圖及在圖中分別加入了5%、10%、20%及30%的椒鹽噪聲，采用3*3、5*5和7*7三種不同大小的鄰域，然后分別使用2.1的原算法及上文2.2部分的改進算法對圖像進行中值濾波，得到的實驗結(jié)果如下。

3.1 噪聲比重對性能的影響

以7*7鄰域為例，對添加了不同比例噪聲的lena圖進行中值濾波處理，結(jié)果如表1所示。

表1 不同噪聲比例情況下算法性能對比

由實驗結(jié)果可以看出，從整體上來說，考慮像素灰度的重復(fù)性后，改進后的算法在性能方面均得到了提升。對改進算法來說，考慮重復(fù)性后大大降低了遞歸次數(shù)，但是交換同主元相同像素到序列兩端增加了開銷，因此，實際性能提升并沒有像遞歸次數(shù)降低的那么多。對不同噪聲比重的圖像來說，當(dāng)加入到圖像中的噪聲逐步增加時，濾波所需遞歸次數(shù)逐步增加，其原因是椒鹽噪聲的值與圖像內(nèi)容中灰度值不同，加入噪聲后圖像中的灰度種類數(shù)增加，加上椒鹽噪聲一般是離散分布，算法無法得到充分利用，因此，當(dāng)噪聲增加后，算法中遞歸次數(shù)比值逐步增加。另一方面，算法性能的改變并沒有像噪聲比重那么明顯，顯示改進算法對于不同比重噪聲圖像濾波性能具有一定的穩(wěn)定性。在極端情況下，例如噪聲比重達到70%以上，此時算法的性能反而得到提高，因為此時像素鄰域內(nèi)絕大多數(shù)都是噪聲，算法一次或兩次即可確定中值，但此時圖像不能用普通的中值濾波處理。

3.2 鄰域大小對算法性能的影響

對lena圖加入5%椒鹽噪聲后，使用不同的濾波窗口對圖像進行中值濾波處理，結(jié)果如表2所示。

表2 不同大小濾波窗口時算法性能對比

由實驗結(jié)果可以看出，窗口越大，對算法性能的提升越多，執(zhí)行需要的時間相對也越短。從表2中可以看出，濾波窗口越大，IGMR值越小，鄰域內(nèi)像素重復(fù)度越高。因此，當(dāng)濾波窗口增大時，改進后的方法性能更好。

3.3 不同圖像對算法性能的影響

通過對lena圖和baboon圖中加入5%的椒鹽噪聲，使用7*7的鄰域，利用改進后的算法進行濾波處理結(jié)果，如表3所示。

表3 不同圖像的算法性能對比

上面2.2部分提出的IGMR指標(biāo)可以對圖像鄰域中的灰度種類多少進行衡量，IGMR值越小，則濾波區(qū)域內(nèi)圖像灰度重復(fù)性越高，算法帶來的性能提升越明顯。與lena圖相比，baboon圖具有更多的圖像灰度細(xì)節(jié)及變化，因此，計算出的IGMR值較大，算法帶來的性能提升不明顯。因此，灰度變化比較平緩，細(xì)節(jié)及邊緣較少的圖像獲得的性能提升會更明顯。

4 結(jié) 語

本文對基于快速排序的元素選擇算法作了改進，利用排序序列中的元素的重復(fù)值，在快速排序的一趟中通過將同主元相同的元素交換到序列的左右兩端，將原序列分成小于、等于以及大于主元的三個部分，通過對等于主元部分的長度及范圍進行判斷，可以提前確定中值，減少后趟處理的區(qū)間長度。實驗表明，將本改進算法應(yīng)用到灰度圖像的中值濾波過程中，在一定程度上能夠縮小中值濾波的時間，提高中值濾波的效率。本方法可以進一步改進為非遞歸的形式，并且可以同其他的基于快速排序的中值濾波改進方法結(jié)合使用，以達到更好的效果。

[1]朱冰蓮，潘哲明，李單單．一種中值濾波的快速算法[J]．信號處理，2008,24(4):684-686

[2]劉立宏，胡可剛，劉立欣．目標(biāo)檢測中的快速中值濾波法[J]．吉林大學(xué)學(xué)報，2004,22(3):232-235

[3]曹治華，宋斌恒．多種形狀窗口下的快速中值濾波算法[J]．計算機應(yīng)用研究，2006,3:85-88

[4]HSIASC．Afastefficientrestorationalgorithmforhigh-noiseimagefilteringwithadaptiveapproach[J]．JournalofVisualCommunicationsandImageRepresentation，2005,16(3):379-392

[5]宋瓊瓊，賈振紅．基于人眼視覺特性的自適應(yīng)中值濾波算法[J]．光電子·激光，2008,19(1):128-130

[6]鮑華，樊瑜波，饒長輝，等．基于均值查找的快速中值濾波算法[J]．四川大學(xué)學(xué)報:工程科學(xué)版，2011,43(2):76-79

[7]蔣濤，李自勤．基于FPGA的實時圖像中值濾波算法及實現(xiàn)[J]．微計算機信息，2012,28(10):196-197

[8]徐國保，尹怡欣，謝仕義．基于改進偽中值濾波器的道路圖像濾波算法[J]．計算機應(yīng)用研究，2011,28(6):2395-2397

[9]THOMASHCORMEN,CHARLESELEISERSON．算法導(dǎo)論[M]．潘金貴，譯.北京:機械工業(yè)出版社，2006：109-111

(責(zé)任編輯：汪材印)

An Accelerated Algorithm of Image Median Filtering

SHI Huikun，WANG Yuan

School of Computer,Huainan Normal University,Huainan Anhui,232038,China

Median filtering is one of the commonly used nonlinear filtering methods in image processing.Considering the low speed of median filtering based on element selection algorithm and repeatability of pixel data of median filtering window,this paper moves the elements equal to the pivot to both ends of sequence and judges whether these elements or the repeated value are the median or not. If they are the median, the filtering result can be determined; if not, these elements can be excluded in next procedure. It can reduce the amount of data in the following processing steps and improve processing speed. Experiments verify the performance of this method with different noise ratio, different filtering window sizes and different images. The result shows that this method can accelerate the filtering speed and improve its performance with the expansion of filtering area.

median filtering;image processing;element selection algorithm

10.3969/j.issn.1673-2006.2015.06.021

2015-03-11

時慧琨(1975-)，安徽淮南人，碩士，講師，主要研究方向：信息處理，人工智能。

TP311

A

1673-2006(2015)06-0077-04