一種多尺度輪廓方向變化率的角點(diǎn)檢測(cè)算法

一種多尺度輪廓方向變化率的角點(diǎn)檢測(cè)算法

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