资源描述：
《多种形状窗口下的快速中值滤波算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3期曹治华等:多种形状窗口下的快速中值滤波算法·85·多种形状窗口下的快速中值滤波算法曹治华,宋斌恒(清华大学软件学院,北京100084)摘要:针对各类形状的窗口的对称特性,巧妙设定滤波窗口移动顺序,同时利用两个方向相邻窗口的已有信息将每个新窗口查找中值的比较次数降到很低。对七种常用形状的窗口分别设计了算法,实验证明这一组算法比传统快速排序算法和已有的一些改进算法在速度上均有不同程度的提高。关键词:中值滤波算法;滑动窗口;复杂度;图像处理中图法分类号:TP391.4文献标识码:A文章编号:1001-3695(2006)03-008
2、5-04AFastAlgorithmforMedianFilteringinMultiformWindowCAOZhi-hua,SONGBin-heng(SchoolofSoftware,TsinghuaUniversity,Beijing100084,China)Abstract:Aseriesofalgorithmareproposedinthepapertoperformmedianfilteringquicklyin7kindsofwindow.Theytakeadvantageofthesymmetryoftheshape
3、s,andsetthewindowslidingorderaccordinglytomakeitconvenienttoutilizetheexistentinformationoftheadjacentwindowsintwodirections.Itisprovedthatthenewalgorithmismuchfasterthanthetradi-tionalsortingalgorithm.Keywords:MedianFilterAlgorithm;GlideWindow;Complexity;ImageProcessi
4、ng在数字图像处理中,作为一种典型的非线性滤波方法,中的几种窗口模板的形状,本文提出的七种算法就是分别针对矩值滤波应用得非常广泛,因而对于其算法效率的提高是很有意形和图1所示的六种形状的窗口设计的。设图像第i行第j列义的。文献[2]中对中值滤波的多种形态及其发展有详细的的像素灰度值为f(i,j),一幅M×N的图像用矩阵可表示为ë介绍。传统的中值滤波算法要对每个窗口内的像素进行排序éf(0,0)f(0,1)⋯f(0,N-2)f(0,N-1)êêf(1,0)f(1,1)⋯f(1,N-2)f(1,N-1)ê以求中值,而无论是一般排序还是快
5、速排序,在最坏的情况下,IM×N=êê……………êé其复杂度(以比较次数来衡量)均正比于排序对象个数的平ëf(M-1,0)f(M-1,1)⋯f(M-1,N-2)f(M-1,N-1)方,从而当窗口尺寸增大时,计算量将按四次方增大。造成这种现象的原因是,传统算法根本不能利用相邻窗口间的相关信息。文献[1]中提出了一种针对矩形窗口的快速算法。此算法将窗口内各列分别排序,将排序好的像素以某值为界分成大(a)图形窗口(b)十字形窗口(c)叉形窗口于和小于的两部分;通过边界上像素的调整使得数量较多部分的像素逐个移到数量较少的部分,直到两部分像素
6、数量只差1,这时就可以在边界上找出中值。此算法在窗口横向移动时,每次只需新加入一列排序,其他有序的列以及上个窗口查找中值时遗留下的边界都保留下来,作为新窗口开始查找中值的起(d)框形窗口(e)菱形窗口(f)花形窗口点。此算法相对传统算法有了较大改进,文中矩形窗口的算法就是在此算法基础上改进而来的。图1稀疏分布的5x5中值滤波器1.1矩形窗口1算法介绍设矩形窗口是H行B列的,左上角在第i行第j列的窗口中值滤波的基本原理是把数字图像中一点的值用该点的为W0(i,j),则W0(i,j)的矩阵形式为ë一个领域中各点值的中值代替。领域又称为窗
7、口,其最普遍的éf(i,j)f(i,j+1)⋯f(i,j+B-1)êêf(i+1,j)f(i+1,j+1)⋯f(i+1,j+B-1)ê形状是矩形。根据不同的图像特性以及处于节省时间的目的,W0(i,j)=êê…………êé各种稀疏的窗口模板也得到了不同程度的应用。图1是常用ëf(i+H-1,j)f(i+H-1,j+1)⋯f(i+H-1,j+B-1)中值滤波的结果就是将窗口中心的像素用窗口内H×B收稿日期:2004-12-12;修返日期:2005-04-05个像素值的中值替代。窗口移动的顺序是扫描线顺序,从上至·86·计算机应用研究20
8、06年下逐行移动,每行内部又是从左至右逐列移动。为了能够在窗对一个窗口来说,总的比较次数最多为2lgH+lgH+22口移动过程中很好地利用之前的信息,现将窗口中各列分别排H(B-1)=3lgH+H(B-1),显然比传统算法的O(HB)
