資源描述：
《多種形狀窗口下的快速中值濾波算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第3期曹治華等:多種形狀窗口下的快速中值濾波算法·85·多種形狀窗口下的快速中值濾波算法曹治華,宋斌恒(清華大學(xué)軟件學(xué)院,北京100084)摘要:針對各類形狀的窗口的對稱特性,巧妙設(shè)定濾波窗口移動順序,同時利用兩個方向相鄰窗口的已有信息將每個新窗口查找中值的比較次數(shù)降到很低。對七種常用形狀的窗口分別設(shè)計(jì)了算法,實(shí)驗(yàn)證明這一組算法比傳統(tǒng)快速排序算法和已有的一些改進(jìn)算法在速度上均有不同程度的提高。關(guān)鍵詞:中值濾波算法;滑動窗口;復(fù)雜度;圖像處理中圖法分類號:TP391.4文獻(xiàn)標(biāo)識碼: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在數(shù)字圖像處理中,作為一種典型的非線性濾波方法,中的幾種窗口模板的形狀,本文提出的七種算法就是分別針對矩值濾波應(yīng)用得非常廣泛,因而對于其算法效率的提高是很有意形和圖1所示的六種形狀的窗口設(shè)計(jì)的。設(shè)圖像第i行第j列義的。文獻(xiàn)[2]中對中值濾波的多種形態(tài)及其發(fā)展有詳細(xì)的的像素灰度值為f(i,j),一幅M×N的圖像用矩陣可表示為?介紹。傳統(tǒng)的中值濾波算法要對每個窗口內(nèi)的像素進(jì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ù)雜度(以比較次數(shù)來衡量)均正比于排序?qū)ο髠€數(shù)的平?f(M-1,0)f(M-1,1)?f(M-1,N-2)f(M-1,N-1)方,從而當(dāng)窗口尺寸增大時,計(jì)算量將按四次方增大。造成這種現(xiàn)象的原因是,傳統(tǒng)算法根本不能利用相鄰窗口間的相關(guān)信息。文獻(xiàn)[1]中提出了一種針對矩形窗口的快速算法。此算法將窗口內(nèi)各列分別排序,將排序好的像素以某值為界分成大(a)圖形窗口(b)十字形窗口(c)叉形窗口于和小于的兩部分;通過邊界上像素的調(diào)整使得數(shù)量較多部分的像素逐個移到數(shù)量較少的部分,直到兩部分像素
6、數(shù)量只差1,這時就可以在邊界上找出中值。此算法在窗口橫向移動時,每次只需新加入一列排序,其他有序的列以及上個窗口查找中值時遺留下的邊界都保留下來,作為新窗口開始查找中值的起(d)框形窗口(e)菱形窗口(f)花形窗口點(diǎn)。此算法相對傳統(tǒng)算法有了較大改進(jìn),文中矩形窗口的算法就是在此算法基礎(chǔ)上改進(jìn)而來的。圖1稀疏分布的5x5中值濾波器1.1矩形窗口1算法介紹設(shè)矩形窗口是H行B列的,左上角在第i行第j列的窗口中值濾波的基本原理是把數(shù)字圖像中一點(diǎn)的值用該點(diǎn)的為W0(i,j),則W0(i,j)的矩陣形式為?一個領(lǐng)域中各點(diǎn)值的中值代替。領(lǐng)域又稱為窗
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)ê形狀是矩形。根據(jù)不同的圖像特性以及處于節(jié)省時間的目的,W0(i,j)=êê…………êé各種稀疏的窗口模板也得到了不同程度的應(yīng)用。圖1是常用?f(i+H-1,j)f(i+H-1,j+1)?f(i+H-1,j+B-1)中值濾波的結(jié)果就是將窗口中心的像素用窗口內(nèi)H×B收稿日期:2004-12-12;修返日期:2005-04-05個像素值的中值替代。窗口移動的順序是掃描線順序,從上至·86·計(jì)算機(jī)應(yīng)用研究20
8、06年下逐行移動,每行內(nèi)部又是從左至右逐列移動。為了能夠在窗對一個窗口來說,總的比較次數(shù)最多為2lgH+lgH+22口移動過程中很好地利用之前的信息,現(xiàn)將窗口中各列分別排H(B-1)=3lgH+H(B-1),顯然比傳統(tǒng)算法的O(HB)
