一种图像中值滤波的加速算法研究

时慧琨，王 源

淮南师范学院计算机学院，安徽淮南，232038



一种图像中值滤波的加速算法研究

时慧琨，王 源

淮南师范学院计算机学院，安徽淮南，232038

针对传统的基于元素选择算法进行中值滤波速度较慢的缺点，考虑到中值滤波窗口中像素取值具有一定程度的重复性，在一趟处理过程中，增加了将处理区域内与主元值相同的元素移动到序列两端的处理，并判断主元或其重复值是否为中值：若是则可以提前确定滤波结果，若不是则可以将其全部排除，从而降低了下趟处理的数据量，提高了处理的速度。实验验证了该方法在不同噪声比例、不同滤波窗口及不同图像下的性能，结果表明该方法可以加快滤波速度，并且随着滤波区域的扩大性能更好。

中值滤波；图像处理；元素选择算法

1 问题的提出

图像噪声是指图像在获取、存储、处理及传输过程中由于内部及外部原因而对图像质量的破坏因素。中值滤波是一种典型的非线性滤波方法，其基本思想是对图像像素邻域内所有点值进行排序，取序列的中值作为滤波后的结果。该方法能够去除或者减少随机噪声和脉冲干扰，较好地保留图像的细节及图像边缘信息，在一定程度上克服线性滤波所带来的图像模糊现象，因此被大量应用于二维图像的预处理过程中。

中值滤波是一种点处理方法，处理时间与处理算法、滤波窗口的尺寸及图像分辨率三个因素有关。因此，当滤波窗口及图像尺寸较大时，处理的时间较长，甚至无法达到实时性的要求。为此，出现了许多加快滤波速度的方法，常见的改进方法有：(1)基于后续窗口与前面窗口部分数据的重叠特性，利用前一次排序的结果加快排序过程[1-2]。(2)选点法，即只对邻域内部分点进行滤波处理，从而减少计算量。一种思路是对滤波窗口的大小和形状进行选择，除了常规的正方形窗口外，也可以选择方形、菱形、十字形和交叉型等不同的滤波窗口[3]。还有一种思路是对噪声点进行选择，可以基于视觉特性的噪声敏感系数[4]，也可以基于统计学中的均值或方差[5]等对像素点进行判定，如果判定为图像像素点则不作处理，如果判定为噪声点则进行滤波。(3)优化排序算法，避免出现最差情况，尽量提前确定中值是优化研究的重点，如基于均值查找的中值滤波算法[6]。(4)并行方法。该方法是在FPGA中放入多个硬件处理单元，以加速滤波过程[7]。(5)近似方法。该类方法找到的不是序列的中值，而是与中值接近的“伪中值”[8]。伪中值的计算较为简单，从而加快了处理速度。在实际应用中，可以采用其中的一种或多种方式来提高中值滤波速度。

本文的主要工作是在基于快速排序的中值滤波算法基础上对其进行优化，提高了滤波速度。其改进原理是在快速排序的一趟处理过程中，考虑到滤波窗口中存在像素值相同的元素，增加了将与主元值相同的元素移动到序列的两端进行处理的步骤，并通过对各个部分长度的计算判断所求值是否落在主元以及与主元相同元素所在区间，如果是则直接输出，如果不是则可以将主元和移动到两端的元素均排除。与原始的方法相比，可以提前确定中值，减少下趟处理时数据区域的长度，降低了递归次数，加快了处理速度。在本文的最后，对改进后的算法进行了实验验证，并分析了实验结果。

2 中值滤波算法及改进原理

2.1 基于元素选择算法的中值滤波

在中值滤波的实现方法中，基于快速排序的方法是目前最常用的方法，尽管快速排序在最差情况下的复杂度为O(n2)，但可以通过随机化等方式使得复杂度降为O(nlog2n)。将快速排序应用到中值滤波上时，可以进一步降低复杂度。因为在实际应用中需要的并不是一个排序后的序列，而只是需要该序列中的中值，这在算法中属于元素选择问题[9]。即给定一个线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素的问题。对于中值问题，k=(n+1)/2，这个问题可以在快速排序的基础上解决。常见的基于快速排序的元素选择方法的代码如下：

//从数组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);

}

在以上代码中，从一维数组的“A[low]..A[high]”中选取按数组从小到大排序位于第i位置的元素，以“A[low]”为主元(pivot)，利用快速排序的一趟排序将原数组分成比主元小的元素子序列、主元及比主元大的元素子序列，并计算主元在一次排序后的位置，若主元最终的位置正好为i，则直接返回。否则，根据所求位置i处在前半序列还是后半序列递归调用原函数即可。对于中值滤波，只需要取i=(n+1)/2即可。

以上算法简单高效，在平均情况下可以在O(n)即线性时间内完成，在最坏情况下，可能需要O(n2)时间内完成，但可以通过随机化选择主元等方式消除最坏情况。

2.2 中值滤波改进算法

在图像的中值滤波中，可以采用如上的方法。由于中值滤波是一种点处理方法，因此对处理大型图像数据时执行效率低，速度慢。另外，对图像中像素取值的统计分析可知，尽管图像的尺寸可以很大，但图像像素取值即像素的灰度种类是有限的，在像素某个邻域内出现的像素灰度种类也是有限的，很多位置的像素灰度值是相同的。考虑到图像像素邻域内存在相同的灰度值因素后，将上述的select算法改进如下：

//从数组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是否落入主元值对应的区间

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));

}

以上算法以快速排序为基础，但与select算法不同的是：在从右向左以及从左向右搜索的过程中，将找到的与主元相同的元素分别与序列的最右边及最左边元素进行互换，从而将与主元相同的元素汇集到序列的两侧，最后得到了如图1的结构。

图1 算法一趟执行后数据分布

当一趟搜索完成后，整个序列分成5个部分：从左向右搜索找到的同主元相同的元素“A[low..p]”，小于主元的元素“A[p+1..lpos-1]”，主元“A[lpos]”，大于主元的元素“A[lpos+1..q-1]”，从右向左搜索找到的同主元相同的元素“A[q..right]”。通过以上信息可以计算出小于、等于、大于主元的像素子序列的长度(注意等于主元的元素长度由三个部分相加得到)，如果要寻找的第i个元素的序号在等于主元元素的范围内，则可以直接返回。否则，分别在小于或大于主元元素的部分里递归查找。

在以上算法中，与select算法只能对主元是否为中值进行判断不同的是，improvedSelect算法可以对所有等于主元值的元素进行判断，即一次对一种灰度值是否为中值进行判断。因此，算法性能同像素邻域内的灰度值种类有关。假设图像邻域大小为N，邻域内灰度种类为C，则改进后的算法在平均情况下的复杂度为O(C)，而C≤N，从而使性能得到改进。假设图像高度为H，宽度为W，图像中的像素点为I(x,y)，邻域大小为N，位置(x,y)邻域内的灰度值种类数为C(x,y)，则定义指标图像灰度多样度IGMR(Image Gray Multiplicity Ratio)为:

该指标描述了图像邻域内灰度的变化程度，指标值越小，表明邻域内灰度的重复率越高，算法改进的效果越好。若处理序列中所有的元素均不相同，则算法的性能同原有算法一致，并不会降低算法的性能。

3 实验验证及结果

在实验指标方面，衡量执行速度常用的是执行时间，本文统计了原算法及改进后算法对图像执行中值滤波的运行时间。除此之外，因为原算法及改进算法均使用了递归调用，递归次数的多少跟运行性能有很大的相关性，因此，还比较了改进前后递归次数的变化情况。

实验中，采用了数字图像处理中常用的lena图及baboon图，采用原图及在图中分别加入了5%、10%、20%及30%的椒盐噪声，采用3*3、5*5和7*7三种不同大小的邻域，然后分别使用2.1的原算法及上文2.2部分的改进算法对图像进行中值滤波，得到的实验结果如下。

3.1 噪声比重对性能的影响

以7*7邻域为例，对添加了不同比例噪声的lena图进行中值滤波处理，结果如表1所示。

表1 不同噪声比例情况下算法性能对比

由实验结果可以看出，从整体上来说，考虑像素灰度的重复性后，改进后的算法在性能方面均得到了提升。对改进算法来说，考虑重复性后大大降低了递归次数，但是交换同主元相同像素到序列两端增加了开销，因此，实际性能提升并没有像递归次数降低的那么多。对不同噪声比重的图像来说，当加入到图像中的噪声逐步增加时，滤波所需递归次数逐步增加，其原因是椒盐噪声的值与图像内容中灰度值不同，加入噪声后图像中的灰度种类数增加，加上椒盐噪声一般是离散分布，算法无法得到充分利用，因此，当噪声增加后，算法中递归次数比值逐步增加。另一方面，算法性能的改变并没有像噪声比重那么明显，显示改进算法对于不同比重噪声图像滤波性能具有一定的稳定性。在极端情况下，例如噪声比重达到70%以上，此时算法的性能反而得到提高，因为此时像素邻域内绝大多数都是噪声，算法一次或两次即可确定中值，但此时图像不能用普通的中值滤波处理。

3.2 邻域大小对算法性能的影响

对lena图加入5%椒盐噪声后，使用不同的滤波窗口对图像进行中值滤波处理，结果如表2所示。

表2 不同大小滤波窗口时算法性能对比

由实验结果可以看出，窗口越大，对算法性能的提升越多，执行需要的时间相对也越短。从表2中可以看出，滤波窗口越大，IGMR值越小，邻域内像素重复度越高。因此，当滤波窗口增大时，改进后的方法性能更好。

3.3 不同图像对算法性能的影响

通过对lena图和baboon图中加入5%的椒盐噪声，使用7*7的邻域，利用改进后的算法进行滤波处理结果，如表3所示。

表3 不同图像的算法性能对比

上面2.2部分提出的IGMR指标可以对图像邻域中的灰度种类多少进行衡量，IGMR值越小，则滤波区域内图像灰度重复性越高，算法带来的性能提升越明显。与lena图相比，baboon图具有更多的图像灰度细节及变化，因此，计算出的IGMR值较大，算法带来的性能提升不明显。因此，灰度变化比较平缓，细节及边缘较少的图像获得的性能提升会更明显。

4 结 语

本文对基于快速排序的元素选择算法作了改进，利用排序序列中的元素的重复值，在快速排序的一趟中通过将同主元相同的元素交换到序列的左右两端，将原序列分成小于、等于以及大于主元的三个部分，通过对等于主元部分的长度及范围进行判断，可以提前确定中值，减少后趟处理的区间长度。实验表明，将本改进算法应用到灰度图像的中值滤波过程中，在一定程度上能够缩小中值滤波的时间，提高中值滤波的效率。本方法可以进一步改进为非递归的形式，并且可以同其他的基于快速排序的中值滤波改进方法结合使用，以达到更好的效果。

[1]朱冰莲，潘哲明，李单单．一种中值滤波的快速算法[J]．信号处理，2008,24(4):684-686

[2]刘立宏，胡可刚，刘立欣．目标检测中的快速中值滤波法[J]．吉林大学学报，2004,22(3):232-235

[3]曹治华，宋斌恒．多种形状窗口下的快速中值滤波算法[J]．计算机应用研究，2006,3:85-88

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

[5]宋琼琼，贾振红．基于人眼视觉特性的自适应中值滤波算法[J]．光电子·激光，2008,19(1):128-130

[6]鲍华，樊瑜波，饶长辉，等．基于均值查找的快速中值滤波算法[J]．四川大学学报:工程科学版，2011,43(2):76-79

[7]蒋涛，李自勤．基于FPGA的实时图像中值滤波算法及实现[J]．微计算机信息，2012,28(10):196-197

[8]徐国保，尹怡欣，谢仕义．基于改进伪中值滤波器的道路图像滤波算法[J]．计算机应用研究，2011,28(6):2395-2397

[9]THOMASHCORMEN,CHARLESELEISERSON．算法导论[M]．潘金贵，译.北京:机械工业出版社，2006：109-111

(责任编辑：汪材印)

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