一種多尺度輪廓方向變化率的角點檢測算法

一種多尺度輪廓方向變化率的角點檢測算法

0基于局部極值設(shè)計的角點檢測算法角點是圖像的一個重要局部特征之一，決定圖像中的目標形狀。因此，角點檢測對圖像的構(gòu)成、運動跟蹤、目標識別和其他領(lǐng)域非常重要。另一方面,尺度空間作為表示圖像特征信息的一種重要思想方法,它在圖像特征信息處理模型中引入尺度參數(shù),通過尺度參數(shù)的連續(xù)變化獲得不同尺度下的視覺特征信息,然后綜合這些特征信息就可以深入挖掘圖像的本質(zhì)特征。所以,尺度空間方法是研究角點特征點提取及其性質(zhì)的一種重要方法。例如,經(jīng)典的Harris角點檢測算法把圖像看成一個三維的幾何曲面,而角點被定義為曲面上兩個主曲率都較大的點,從而根據(jù)反映曲面主曲率的自相關(guān)矩陣構(gòu)造了角點的響應(yīng)函數(shù),但該算法缺乏多尺度檢測特性。于是,陳白帆等人通過高斯尺度空間引入尺度參數(shù)使Harris算法獲得了多尺度檢測的能力。Mokhtarian等人和Rattarangsi等人都把角點定義為輪廓曲率的局部極值點,并分別提出了基于高斯曲率尺度空間的角點檢測算法。他們所提出的角點算法首先提取圖像輪廓,并用不同尺度的高斯核對輪廓做演化,得到在各個尺度下的輪廓演化版本。然后把高尺度下的圖像輪廓曲率的局部極值點作為候選角點,并從高尺度到低尺度對候選角點進行跟蹤定位,從而得到準確的角點位置。文獻分析了Mokhtarian算法的不足,并利用角點處的局部信息改進了該算法。Lee等人提出了基于小波變換的多尺度角點檢測方法,該方法對圖像的輪廓方向做小波變換,并把小波變換模極大值點作為候選角點。Quddus等人運用SVD方法進一步確定了小波變換檢測角點的最優(yōu)尺度問題。值得注意的是,這些方法雖然都運用了多尺度方法,但存在共同的缺點:確定候選角點時,僅使用了單一尺度,并沒有有機地融合各個尺度的特征信息。這使得確定候選角點時,尺度過大容易丟失真實角點,尺度過小容易受噪聲的影響。本文基于輪廓方向和B-樣條尺度空間理論以及多尺度乘積思想提出了一種新的角點檢測算法。該算法首先利用B-樣條尺度空間的優(yōu)良特性構(gòu)造了輪廓方向變化率多尺度表示,然后在此基礎(chǔ)上定義了輪廓方向變化率的多尺度乘積,并把多尺度乘積的局部極值點作為候選角點。所定義的多尺度乘積包含了多個尺度的特征信息,使得候選角點檢測真正實現(xiàn)了多尺度檢測,從而有效地解決了候選角點檢測的單一尺度問題。論文不但分析了多尺度乘積算法的檢測定位性能,而且通過對比實驗驗證了多尺度乘積的有效性。1b-樣本的多尺度表示輪廓方向的變化率本章將依據(jù)B-樣條尺度空間理論逐步構(gòu)造基于B-樣條尺度空間的輪廓方向變化率多尺度表示。1.1輪廓方向的估計設(shè)C(u)表示從圖像中提取出來以u為參數(shù)的一條輪廓,即:C(u)=(x(u),y(u))(1)其中,x(u)和y(u)分別表示以u為參數(shù)的輪廓橫坐標和縱坐標,輪廓上第i個離散點可以由ui來表示。則,由式(1)表示的輪廓在任意點處的輪廓方向φ(u)可以定義為:φ(u)=arctan(dy/dudx/du)(2)φ(u)=arctan(dy/dudx/du)(2)在文獻,為了計算輪廓方向,使用一階差分替代式(2)的導(dǎo)數(shù),但輪廓方向的分辨率僅為π/4。為了提高輪廓方向的分辨率,將任意點ui處的輪廓方向定義為:φ(ui)=arctan(y(ui+q)-y(ui-q)x(ui+q)-x(ui-q))(3)φ(ui)=arctan(y(ui+q)?y(ui?q)x(ui+q)?x(ui?q))(3)式中,整數(shù)q≥1,q越大表示輪廓方向的分辨率越大。文獻直接對輪廓方向φ(ui)做B-樣條小波變換,并把大尺度下的大于給定閾值的小波變換模極大值點定義為候選角點。為了提高角點的定位精度,從大尺度到小尺度對候選角點進行跟蹤定位,從而得到小尺度下的角點的精確位置。但該方法明顯地存在以下幾個缺點:受輪廓噪聲和量化噪聲的影響,式(3)容易出現(xiàn)奇異或病態(tài)值,使得輪廓方向極其不穩(wěn)定;檢測候選角點的尺度只在單一的尺度下進行,其尺度的選擇存在如下的矛盾,尺度大容易丟失真實角點,尺度小產(chǎn)生偽角點;參數(shù)q的決定依賴于兩個相互矛盾的因素,也就是輪廓方向的分辨率和角點的辨別能力。q的取值越大,輪廓方向的分辨率越高,角點辨別能力卻越低。1.2bmbng在圖像的輪廓模型式(1)中引入尺度參數(shù),讓其在B-樣條尺度空間中演化,,從而形成B-樣條的輪廓尺度空間。設(shè)n階尺度為m的離散B樣條函數(shù)為:Bnm=n+1?B0m*B0m*?*B0m(4)Bnm=B0m*B0m*?*B0mue150ue151ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154n+1(4)其中,B0m0m=(1/m)[1,1,…,1]表示寬為m的歸一化的采樣脈沖。那么,輪廓C(u)在不同尺度下的演化版本就可以通過與B-樣條函數(shù)做卷積而得到:C(u,m)=(X(u,m),Y(u,m))(5)式中,X(u,m)=x(u)*Bnmnm,Y(u,m)=y(u)*Bnmnm,Bnmnm表示n階尺度為m的離散B-樣條函數(shù),*表示卷積算子。通常把式(5)叫作輪廓的B-樣條尺度空間,注意該空間的特性與熱擴散方程驅(qū)動的高斯尺度空間非常相似。這是由于,當B-樣條的階數(shù)n趨于無窮時,根據(jù)中心極限定理,B-樣條將逼近高斯函數(shù)。而且,根據(jù)文獻,式(5)的高計算復(fù)雜度的卷積運算可以轉(zhuǎn)化為復(fù)雜度僅為O(N)的加法運算,所以本文使用B-樣條來表示輪廓的多尺度演化版本,從而可以獲得有效計算方法。1.3輪廓方向變化率多尺度當輪廓用B-樣條尺度空間來表示時,基于式(5)的輪廓C(u)在尺度m下的輪廓方向φ(u,m)可以表示為:φ(u,m)=arctan(dY(u,m)/dudX(u,m)/du)(6)φ(u,m)=arctan(dY(u,m)/dudX(u,m)/du)(6)顯然,與式(2)的區(qū)別在于式(6)的輪廓方向包含了尺度信息。由式(6),輪廓方向變化率就等于關(guān)于參數(shù)u的導(dǎo)數(shù)D(u,m):D(u,m)=dφ(u,m)du=X¨Y?-Y¨X?X?2+Y?2(7)D(u,m)=dφ(u,m)du=X¨Y??Y¨X?X?2+Y?2(7)式中,X·=dX(u,m)/du,X¨=d2X(u,m)/du2,Y·=dY(u,m)/du,Y¨=d2Y(u,m)/du2。我們知道,信號與B-樣條函數(shù)的一階和二階導(dǎo)數(shù)的卷積就是信號的一階和二階小波變換。于是,輪廓與B-樣條函數(shù)的一階和二階導(dǎo)數(shù)就可以分別定義為輪廓演化版本的一階和二階小波變換W1C(u,m)、W2C(u,m),則有:{W1C(u,m)=?uC(u,m)W2C(u,m)=?2uC(u,m)(8){W1C(u,m)=?uC(u,m)W2C(u,m)=?2uC(u,m)(8)如果定義?uf(u,m)=f(u+12,m)-f(u-12,m)?uf(u,m)=f(u+12,m)?f(u?12,m),則式(8)所表示的一階和二階小波變換是光滑輪廓C(u,m)的一階和二階差分。根據(jù)式(8)的定義,我們進一步可以得到離散點ui在尺度mj下的輪廓方向變化率多尺度小波表示:D(ui,mj)=W2X(ui,mj)W1Y(ui,mj)-W1X(ui,mj)W2Y(ui,mj)(W1X(ui,mj))2+(W1Y(ui,mj))2(9)D(ui,mj)=W2X(ui,mj)W1Y(ui,mj)?W1X(ui,mj)W2Y(ui,mj)(W1X(ui,mj))2+(W1Y(ui,mj))2(9)我們把式(7)或式(9)叫作輪廓方向變化率的B-樣條多尺度表示。式(9)與由式(3)的差分計算輪廓方向變化率相比,其思想有根本的改變,式(9)把輪廓進行演化之后再做小波變換,這樣使得輪廓噪聲和量化噪聲在演化的過程中得到抑制,從而計算輪廓方向變化率將變得更加穩(wěn)定。而式(3)直接使用邊界輪廓離散點,這非常容易受量化噪聲和輪廓隨機噪聲的影響,從而導(dǎo)致輪廓方向變化率的計算極不穩(wěn)定。更為重要的是,式(9)表示了不同尺度下的輪廓方向變化率,而式(3)只是單一尺度下的輪廓方向變化率。2基于多尺度積的角點檢測算法本章將在前面所構(gòu)造的基于輪廓方向變化率B-樣條多尺度表示的基礎(chǔ)上,提出一種基于多尺度積的角點檢測方法,并對算法的定位性能進行了分析和比較。2.1輪廓方向變化率多尺度積的檢測當輪廓從小尺度到大尺度進行演化時,受輪廓噪聲和量化噪聲干擾的輪廓邊界點的特征信息將得到抑制,而真實角點的特征信息將保留下來。圖1中的(a)和(b)分別是人工圖像和它的邊緣圖像。圖2表示圖1(b)的輪廓方向變化率,其中,圖2(a)表示了輪廓沒有演化的輪廓方向變化率,從該圖中可以看出,輪廓方向變化率極容易受到輪廓量化噪聲的影響。而圖2(b～d)分別表示mj等于4,5,6的輪廓方向變化率。顯然,輪廓方向變化率從小尺度到大尺度的變化規(guī)律是:輪廓的重要幾何特征不但保留了下來,而且輪廓的噪聲隨著尺度的增加得到了抑制,但輪廓重要的幾何特征的位置發(fā)生了小移位。輪廓方向變化率的這種特性,與文獻中所分析的邊緣特征信息的變化特性極其相似。而該文獻充分利用圖像邊緣特征信息的這種多尺度特性,構(gòu)造了多尺度乘積的方法,使得邊緣特征信息增強,同時抑制噪聲的影響。于是,本文利用輪廓方向變化率的特征信息,構(gòu)造如下的多尺度乘積:Μ(u)=S∏j=1D(u,mj)(10)M(u)=∏j=1SD(u,mj)(10)式中,S表示離散B-樣條函數(shù)的尺度數(shù)目,M(u)表示輪廓方向變化率多尺度積。根據(jù)B-樣條尺度空間的因果性,輪廓重要幾何特征不會隨尺度的遞增而增加,并且噪聲在大尺度下會被迅速減弱,而真正的角點處的變化率會因為乘積而相對增大,從而多尺度乘積可以很好地檢測出真實角點,且保持了角點的位置和對噪聲良好的魯棒性。圖3表示了圖1(b)輪廓的多尺度乘積,明顯地,M(u)可以增強角點的輪廓方向變化率,同時極大地抑制其他點的輪廓方向變化率。這樣,用一個全局閾值就可以獲得全部的真實角點。圖1中(c)中的角點,是通過取閾值等于0.002,mj(j=1,2,3)分別選取4,5,6而得到的好的檢測結(jié)果。于是,由輪廓方向變化率多尺度乘積的特性,可以建立一種新的角點檢測方法。該方法首先提取圖像的輪廓,然后在B-樣條尺度空間中對輪廓進行多尺度演化,得到不同尺度下輪廓的演化版本,最后,利用式(10)計算輪廓方向變化率多尺度積,并把它的絕對值的局部極大值點作為候選的角點。算法步驟如下:1)運用Canny算法提取圖像的邊緣輪廓C(u);2)根據(jù)式(5),計算輪廓在不同尺度下的演化版本C(ui,mj),1≤i≤N,1≤j≤S,其中N表示原始輪廓的采樣點數(shù),S表示所選擇的尺度數(shù)目;3)根據(jù)式(10)計算輪廓方向變化率多尺度積;4)把輪廓方向變化率多尺度積的絕對值的局部極大值且大于給定的全局閾值t的點作為角點。2.2方向變化率的曲線圖放在乘積M(u)中,融入了幾個尺度下的輪廓方向變化率,把M(u)的局部極大值定義為角點,該角點的檢測就自然包含了各個尺度的特征信息。這樣,算法既保留了小尺度的精確定位特征,又有大尺度的抗噪性能,從而可以有效地抑制單一尺度下引入的噪聲,提高了算法的魯棒性,如圖3所示。為了分析該檢測算法的定位性能,可以把輪廓方向變化率的曲線圖放大。例如,圖4表示了圖2(b～d)的輪廓離散點從500到650的輪廓方向變化率。從該圖可以觀察到這樣一個事實,相鄰尺度之間的同一個幾何特征的位置偏移量變化很小,可以假設(shè)|Δuj|≤1(1<j≤S);同時,角點鄰域內(nèi)的局部曲線近似于高斯函數(shù)的曲線,于是第j個尺度下任意角點u處的局部鄰域的輪廓方向變化率可以表示為bjexp(-(x-u-Δuj)2/aj),其中,常數(shù)aj隨B-樣條尺度因子增大而增大,則在該點u處鄰域上的多尺度乘積可以表示為:Μ(x)=S∏j=1bj[exp(-(x-u-Δuj)2/aj]=Bexp(-S∑j=1[(x-u-Δuj)2/aj])=Bexp(-(x-u-ΔU)2/A+C)(11)其中,S表示離散B-樣條函數(shù)的尺度數(shù)目,B=S∏j=1bj,而ΔU,A,C是把高斯函數(shù)的指數(shù)配方之后的值。顯然,角點定位精度就由ΔU來確定。角點定位的最壞情形是,Δuj=1而且aj相等。此時可以得到,當S=3時,ΔU=1,這表明定位誤差不會大于一個像素,從而證明了所提出算法的定位準確性。3實驗結(jié)果與分析為了說明所提出算法的優(yōu)越性,下面將通過對比實驗來驗證。這些實驗包括了Plessey、Kitchen、SUSAN、CSS和增強CSS等算法。為了敘述方便,本文所提出的算法用MSM(Multi-ScaleMultiplication)來表示。為了驗證算法,我們做了大量的實驗,但本文只給出了方塊和房屋圖像的檢測結(jié)果,這兩幅圖像被廣泛地用于展示角點檢測的實驗結(jié)果,其中房屋圖像擁有很多的細節(jié)和紋理特征。MSM算法中的邊緣提取直接使用了Matlab中所提供Canny邊緣檢測函數(shù),其參數(shù)選取為默認值。MSM算法的尺度參數(shù)因子mj(j=1,2,3)分別選取了4,5,6。而閾值t選取0.0001至0.0005之間的任意值。其他算法檢測結(jié)果都是通過調(diào)節(jié)參數(shù)達到的最好結(jié)果。實驗結(jié)果顯示MSM檢測器都獲得了6種檢測器中的最佳效果。木塊圖像的角點檢測較為復(fù)雜,從圖5中可以看到前面三個檢測器的效果不太理想,后三者均能檢測出較多的正確角點,不過與MSM相比,CSS