時(shí)慧琨，王 源

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

?

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

時(shí)慧琨，王 源

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

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

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

1 問(wèn)題的提出

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

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

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

2 中值濾波算法及改進(jìn)原理

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

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

//從數(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ù)組分成比主元小的元素子序列、主元及比主元大的元素子序列，并計(jì)算主元在一次排序后的位置，若主元最終的位置正好為i，則直接返回。否則，根據(jù)所求位置i處在前半序列還是后半序列遞歸調(diào)用原函數(shù)即可。對(duì)于中值濾波，只需要取i=(n+1)/2即可。

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

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

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

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

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

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

//p：左邊相同元素的序號(hào), q：右邊相同元素的序號(hào)，

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

{

//將從左向右訪(fǎng)問(wèn)到的等于pivot的元素交換到最左邊

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

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

++lpos;

}

A[rpos]=A[lpos];

}

A[lpos]=pivot;

//判斷i是否落入主元值對(duì)應(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));

}

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證及結(jié)果

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

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

3.1 噪聲比重對(duì)性能的影響

以7*7鄰域?yàn)槔?，?duì)添加了不同比例噪聲的lena圖進(jìn)行中值濾波處理，結(jié)果如表1所示。

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

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

3.2 鄰域大小對(duì)算法性能的影響

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

表2 不同大小濾波窗口時(shí)算法性能對(duì)比

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

3.3 不同圖像對(duì)算法性能的影響

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

表3 不同圖像的算法性能對(duì)比

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

4 結(jié) 語(yǔ)

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

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

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

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

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

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

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

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

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

[9]THOMASHCORMEN,CHARLESELEISERSON．算法導(dǎo)論[M]．潘金貴，譯.北京:機(jī)械工業(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

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

TP311

A

1673-2006(2015)06-0077-04