采用多尺度方向微分比率的角點檢測算法

王富平,水鵬朗

(西安電子科技大學雷達信號處理國家重點實驗室, 710071, 西安)

g′(n;θi)=g′(Rθin;σ)

ψ′(n;θi)=ψ′(Rθin;σ,ρ)

?

采用多尺度方向微分比率的角點檢測算法

王富平,水鵬朗

(西安電子科技大學雷達信號處理國家重點實驗室, 710071, 西安)

針對相鄰圖像結構間的相互干擾會導致角點錯檢率升高的問題,提出了一種基于多尺度方向微分比率(MDDR)的角點檢測算法。該算法首先利用Canny邊緣檢測算法提取原始灰度圖像的邊緣輪廓;對于每一個輪廓像素,分別利用各向同性導數和各向異性高斯方向導數濾波器提取主方向及其正交方向上的方向強度微分信息;然后將3個尺度下微分比率融合為MDDR測度;最后進行閾值和非極大值抑制處理獲得最終角點。不同于傳統角點檢測算法中只使用單一濾波器,MDDR算法中使用2種不同類型的濾波器,能在精確提取角點附近不同方向微分信息的同時避免鄰近圖像結構間的相互干擾,從而提高了角點定位準確性并增強了測度的噪聲魯棒性。實驗結果表明,MDDR算法的平均檢測準確率比點到弦距離累積算法提高了27.1%,并且平均錯檢率比殘余面積算法和Gabor算法分別低28.4%和32.4%。

邊緣檢測;多尺度;方向微分比率;角點檢測

在許多圖像處理算法中,如圖像配準、三維重建等,如果使用圖像所有像素的信息,會導致算法計算量十分巨大,而圖像中的角點既包含了圖像中目標的結構信息,又構成了對圖像的稀疏表示,能大大提高圖像處理算法的效率,并且角點在幾何變換和不同光照條件下具有不變性。因此,角點檢測常被作為一些高級圖像處理算法的特征提取部分。已有的角點檢測算法可以大致分為3類:基于模型的檢測算法[1-3]、基于強度的檢測算法[4]和基于邊緣的檢測算法[5-10]。

基于模型的角點檢測算法一般根據特定的角點模板來匹配局部圖像以達到檢測角點的目的。SUSAN算法[1]根據模板中心像素與周圍像素的相似比來檢測角點。FAST算法[2]和文獻[3]則分別利用圓環和雙圓環模板來檢測角點。這類算法計算高效,但模板無法覆蓋所有角點類型。基于強度的角點檢測算法則是根據圖像的強度信息直接檢測角點。Harris算法根據圖像微分自相關矩陣的主曲率在角點與非角點之間的差異來檢測角點。文獻[4]則在邊緣輪廓的基礎上,將多尺度思想融入自相關矩陣中,提高了角點檢測準確率。

上述2類算法容易在平坦區域檢測到偽角點,而基于輪廓的檢測算法則是利用輪廓幾何特征來檢測角點的[5-8]。He利用局部支撐區間和自適應閾值改進了曲率尺度空間(CSS)算法[5],但其對邊緣上的噪聲十分敏感。Awrangjebp則通過計算多個弦長下的點到弦距離累積(CPDA)的乘積來增強算法的噪聲魯棒性[6],但其容易丟失距離很近的角點。為此,Teng根據輪廓像素的空間三角特性提出了2種改進算法[7];Shui在邊緣檢測的基礎上利用各向異性高斯方向導數(ANDD)濾波器來提取輪廓像素的灰度變化信息,并引入歸一化殘余面積(RA)來檢測角點[9];Zhang則利用Gabor濾波器平滑圖像,將獲得的歸一化微分能量作為角點測度來檢測角點[10]。

以上算法中,基于輪廓的算法對邊緣上的噪聲比較敏感[5-6],而結合輪廓和強度的算法中的方向導數濾波器容易受到鄰近其他特征的影響[11]。為了克服上述不足,本文在邊緣輪廓提取的基礎上,根據角點和邊緣像素的方向微分之間的差異,提出了一種多尺度方向微分比率的角點檢測算法,分別利用不同類型的方向導數濾波器精確提取邊緣像素的主方向及垂直方向上的微分信息,并將多個尺度下微分比率的乘積作為最終角點測度。實驗結果表明,新的角點檢測算法能有效避免鄰近特征之間的影響,具有更高的檢測準確率和很好的噪聲魯棒性。

1 各向同性和各向異性方向導數

傳統的高斯微分濾波器由于沿各個方向的尺度都相同,又被稱作各向同性方向導數(IGD)濾波器。笛卡爾坐標系下水平方向和方向為θi的二維IGD濾波器的權值系數可以表示為

(1)

g′(n;θi)=g′(Rθin;σ)

(2)

式中:σ是高斯尺度因子;θi是第i個濾波器的方向;Rθi是方向為θi的旋轉矩陣;K是IGD濾波器的離散方向個數。由于IGD濾波器在提取垂直于邊緣方向上的微分時會出現模糊,因此有學者引入了ANDD濾波器[9],它是沿其主軸及垂直方向上尺度不同的高斯微分算子。笛卡爾坐標系下水平方向和方向為θi的二維ANDD濾波器的權值系數可表示為

(3)

ψ′(n;θi)=ψ′(Rθin;σ,ρ)

(4)

式中:ρ為各向異性因子,ρ越大,濾波器的形狀越狹長,所提取的方向微分信息越精確。圖1給出了8個方向的二維IGD和ANDD濾波器權值系數圖。

2 多尺度方向微分比率的角點檢測

(a)8個方向的二維IGD濾波器權值系數

(b)8個方向的二維ANDD濾波器權值系數圖1 8個方向的二維IGD和ANDD濾波器權值系數圖

結合輪廓和強度的角點檢測算法利用方向導數濾波器提取不同方向上的微分信息[9-10],但當某個角點附近存在其他特征時,提取的微分信息會受到該特征的影響。為了避免這種影響,本文提出了一種新的角點檢測算法,包括2個部分:邊緣輪廓的提取和多尺度微分比率(MDDR)測度的構建。

2.1 邊緣檢測和輪廓修復

本文算法首先利用邊緣檢測算法提取圖像的邊緣,但由于噪聲的影響,提取的邊緣圖可能會出現斷裂,導致角點丟失或者定位精度降低。因此,對已檢測到的邊緣做如下處理。

(1)將圖像中每一條連通的輪廓C以單獨鏈碼的形式存儲,即C={p1,p2,…,pQ}。如果p1=pQ,則輪廓為封閉輪廓,而當p1≠pQ時,輪廓為開輪廓。

(2)對于開輪廓的端點,如果其5×5像素內包含其他輪廓端點,就填充這2個端點之間的間隙,合并這2個輪廓;如果窗口內包含其他輪廓的非端點像素,就將此端點延伸到其他輪廓即可。

對輪廓的修復有助于找回一些丟失角點,同時提高了部分角點的定位精度。

2.2 利用IGD和ANDD的微分比率的角點測度

對于輪廓上的像素n而言,利用K個方向的IGD和ANDD濾波器平滑圖像I(n),得到K個響應就構成了n處的IGD向量IIGD(n)和ANDD向量IANDD(n)

(5)

(6)

(7)

(a)仿真圖 (b)邊緣點p1

(c)角點p2 (d)邊緣點p3圖2 邊緣點和角點的IGD及ANDD向量比較

(8)

小尺度微分濾波器具有好的定位準確性,但對噪聲比較敏感;大尺度濾波器對噪聲比較魯棒,但其會降低角點定位精度。為了融合兩者的優點,本文提出的MDDR測度定義為3個尺度下的γσ的乘積,即

(9)

實際上,MDDR測度所描述的就是像素處主曲率方向上與其垂直方向的微分變化。類似思想最早在Harris中被用到,但在Harris算法中只用到了x,y方向的IGD濾波器的響應,提取的主曲率不夠精確,并且Harris測度對噪聲比較敏感。

為了說明MDDR測度的有效性,對圖3a中包含36個真實角點的飛機圖像,利用本文算法計算出每個邊緣像素處的MDDR測度。從圖3c可以看出,該測度在角點處明顯比較大,并且可以區分距離較近的角點,而在非角點處幾乎為0。只需設置合適的閾值,就能檢測出所有角點(如圖3b)。

(a)仿真圖像 (b)本文算法檢測

(c)飛機圖像的MDDR測度圖3 飛機圖像的MDDR測度及檢測結果

2.3 本文算法流程

本文提出的基于多尺度微分比率的角點檢測算法的詳細步驟如下。

步驟1 利用Canny邊緣檢測算法提取灰度圖像的邊緣輪廓,對每一個輪廓進行填充或者延伸修復。

步驟2 構建尺度σ1下K個方向的ANDD濾波器,并平滑輪廓上的每一個像素n,獲得IANDD(n)、OB方向上的平均微分和(n)。

步驟4 將得到的主方向和垂直方向上的微分代入式(8)中,計算尺度σ1下的角點測度γσ1(n)。

步驟6 對于每一個邊緣像素,如果其角點測度η(n)大于設定的閾值t并且是5×5像素窗口內的最大值,就認定其為最終角點,否則將其剔除。

3 實驗結果和分析

為了評價提出的算法的性能,分別通過真實圖像檢測結果、定位誤差及重復率實驗進行評估。對于算法中的ANDD濾波器而言,ρ越小,濾波器的影響范圍越小,其區分鄰近角點的能力就越強,但主方向的精確估計又要求濾波器具有強的各向異性,此時需要ρ>2[12]。為了兼顧兩者,本文使用文獻[12]中的推薦參數ρ=(6)1/2。為了獲得最優的角度分辨率,濾波器方向采樣數K必須滿足[9]

(10)

將ρ=(6)1/2代入式(10)可以計算出最小方向數K≈84。進行局部微分平均時的濾波器方向數2L+1=3。

本文的角點測度與角點兩側直線的夾角δ有關(如圖2a所示):當δ為90°時,角點測度為1;當δ減小至0°或者增加至180°(即理想邊緣)時,測度接近于0。然而,實際中受到邊緣噪聲的影響,非角點處的夾角往往不嚴格等于180°,因此,在CPDA算法[6]中,當邊緣像素處的夾角滿足180°-157°<δ<157°時,該像素就被認定為角點。將該夾角δ代入文獻[9]中的通用角點模型中計算出特定夾角的理想角點,利用式(6)和式(7)計算出本文角點測度的范圍為0.022<η≤1。因此,要檢測出所有角點,閾值t應該在[0,0.022]上取值,但如果閾值過小,錯誤角點檢測率就會增加,為此,本文在實驗中選擇了經驗閾值t=0.02。為了選擇合適的尺度σ,對于圖4a中公認的包含真實參考角點的9幅圖像[5,9],在不同的尺度σ下計算其平均檢測正確率和平均錯檢率。實驗中σ2在區間[1.5,5]上均勻采樣,其他2個尺度則滿足σ1/(2)1/2=σ2=(2)1/2σ3,最終結果如圖4b所示。可以看出,在尺度σ2=2.5時算法獲得了最高的檢測準確率和最小的錯檢率。尺度參數取值區間可以為[2,3],本文中σ2取值為2.5。

(a)實驗圖像 (b)檢測率隨σ2的變化圖4 檢測準確率和錯檢率隨尺度σ2的變化

3.1 算法有效性實驗

(a)CPDA算法 (b)RA算法

(c)Gabor算法 (d)本文算法圖5 4種算法在無噪聲下對飛機圖像的檢測結果

(a)CPDA算法 (b)RA算法

(c)Gabor算法 (d)本文算法圖6 4種算法在無噪聲下對實驗室圖像的檢測結果

(a)CPDA算法 (b)RA算法

(c)Gabor算法 (d)本文算法 圖7 4種算法在含噪聲ε=15下對飛機圖像的檢測結果

(a)CPDA算法 (b)RA算法

(c)Gabor算法 (d)本文算法 圖8 4種算法在含噪聲ε=15下對實驗室圖像的檢測結果

本實驗針對飛機和實驗室圖像,分別在無噪聲和含噪聲標準差ε=152的情況下,利用CPDA算法[6]、RA算法[9]、Gabor算法[10]和本文算法檢測圖像角點,統計其配準角點和錯誤角點數目,并計算定位誤差。其他3種算法由原作者提供,參數設置為原文中的默認參數,本文算法的參數是:K=84,ρ=61/2,σ1=2.5×21/2,σ2=2.5,σ3=2.5/21/2,t=0.02。分別采用4種算法在無噪聲時的檢測結果如圖5和圖6所示,含噪聲時的檢測結果如圖7和圖8所示。可以看出,CPDA算法丟失了許多真實角點,主要原因是CPDA算法中使用的3個弦長對CPDA曲率具有平滑作用,當相鄰角點之間的距離小于一定像素時,平滑效果會使得CPDA測度無法區分這2個角點,而基于RA和基于Gabor的2種算法中使用的方向導數濾波器提取的局部微分向量具有很強的角點區分能力,使得圖5b和圖5c中的配準角點數目明顯比CPDA多。然而,由于它們的測度是建立在多個方向微分的基礎上,當濾波器垂直于輪廓方向時,濾波器狹長的空域影響范圍使其容易受到周圍其他輪廓以及邊緣毛刺的影響,從而在邊緣或者圓形輪廓上產生偽角點,而圖5d中本文算法能夠準確地識別鄰近角點,并且檢測出最少的偽角點。這是由于本文算法通過精確估計邊緣像素的主方向,利用空域影響范圍較小的IGD導數濾波器提取主方向上的微分,避免了鄰近圖像的影響,降低了偽角點產生的概率。

表1和表2分別給出了無噪聲和含噪聲情況下的檢測結果統計,其中噪聲情況下的結果是50次檢測結果排序后的中值。從表1中可以看出,無噪聲情況下,CPDA算法的錯誤角點數最少。這主要得益于CPDA測度中多個弦長的平滑效果使得算法對邊緣上的噪聲十分魯棒,但CPDA測度也容易平滑掉相距很近的真實角點,導致其配準角點數很少。RA、Gabor和本文算法的配準角點數比較接近,但RA和Gabor算法中微分濾波器的空域范圍較大,提取的方向微分容易受到鄰近圖像結構的影響,導致偽角點增多,而本文算法中使用大尺度的ANDD濾波器提取垂直于邊緣方向上的微分,其對邊緣上的噪聲比較魯棒,使得檢測的錯誤角點數明顯比RA和Gabor少,同時小尺度下角點測度的定位準確度較高,使得最終融合的角點測度的定位誤差也相對比較小。表2的結果顯示,噪聲情況下,CPDA和本文算法的配準角點和錯誤角點數變化不大,表明算法對噪聲都比較魯棒。與本文算法相比,RA算法的錯誤角點數增多,Gabor算法的配準角點數減少,錯誤角點數增多。本文算法在提取垂直于邊緣方向上的微分時使用了大尺度的ANDD濾波器,使其對圖像中的噪聲比較魯棒。為了驗證算法的噪聲魯棒性,對于圖4a中的9幅圖像,分別在不同標準差的零均值高斯噪聲下,計算4種算法的配準率和錯檢率。實驗中,噪聲標準差ε在 [2,20]上等間隔采樣,進行50次實驗的平均檢測結果如圖9所示。從圖9a中可以看出,隨著噪聲的增加,本文算法和CPDA算法的平均錯檢率都增加的比較少,而RA和Gabor的錯檢率明顯增加。對于圖9b中的平均配準率而言,本文算法、CPDA和RA算法的配準率下降得都比較少,而Gabor算法的配準率明顯下降。相比之下,CPDA算法的配準率和錯檢率變化都最小。綜上所述,CPDA算法的噪聲魯棒性最好,其次是本文算法,RA算法次之,而Gabor算法對噪聲比較敏感。

表1 無噪聲下4種算法對飛機和實驗室圖像的檢測結果比較

注:黑體數據為最優檢測結果。

表2 含噪聲標準差ε=15下4種算法對飛機和實驗室圖像的檢測結果比較

(a)平均錯檢率 (b)平均配準率圖9 不同噪聲下4種算法的檢測結果

3.2 重復率實驗

重復率也是衡量算法性能的一個重要指標。假設原始和變換后圖像中檢測到的角點數為N0和NT,其中重復角點數為Nr,則角點重復率Ra=(Nr/N0+Nr/NT)/2。實驗中計算文獻[10]中的24幅圖像在3種仿射變換和噪聲干擾下的平均重復率。具體包括:旋轉變換中角度在[-90°,90°]上采樣;一致尺度變換中對X、Y坐標進行相同尺度縮放的尺度因子在[0.5,2]上采樣;非一致尺度變換中對Y坐標進行縮放的尺度因子在[0.5,2]上采樣;高斯噪聲干擾中標準差在[1,15]上采樣。

4種算法的平均重復率如圖10所示,由于旋轉變換沒有改變局部圖像的強度分布,使得檢測得到的邊緣幾乎不變,因此4種算法在旋轉變化下重復率變化不大。一致尺度變換改變了圖像大小,對邊緣檢測結果產生了影響,導致4種算法的平均重復率都下降了,而本文算法融合了多尺度下的信息,具有一定的尺度魯棒性,其重復率一直最高。非一致尺度變換下,角點處的邊緣輪廓的夾角發生了變化,這使得4種算法的重復率都有明顯的下降,其中邊緣輪廓的改變對于只利用輪廓幾何信息的CPDA算法影響最大,使其重復率最低,而且大的非一致尺度變換使得鄰近輪廓更接近,此時RA和Gabor算法更容易受到角點周圍其他結構的影響,導致偽角點產生。本文算法利用空域影響范圍較小的IGD濾波器提取主方向上的微分,不易受到周圍其他輪廓的影響,并且由于本文算法只利用了像素的主方向及其垂直方向上的微分信息,對非一致尺度變換不敏感,從而具有最高的重復率。在高斯噪聲干擾下,Gabor算法的重復率最低,這是由于Gabor濾波器對于噪聲導致的邊緣毛刺和灰度不均勻都比較敏感,導致提取的歸一化能量容易在非角點處產生強響應,其他3種算法的重復率比較接近。綜合結果表明,本文算法具有較好的檢測重復率。

(a)旋轉變換 (b)一致尺度變換

(c)非一致尺度變換 (d)噪聲干擾圖10 3種仿射變換和噪聲干擾下4種算法的平均重復率比較

4 結 論

本文在提取輪廓的基礎上,提出了一種融合多尺度方向微分比率的角點檢測算法。算法根據邊緣和角點處微分特性的不同,充分利用了IGD和ANDD濾波器的優勢來精確提取局部微分信息,增強了角點測度的穩定性。通過將多尺度思想融合到最終角點測度中,提高了角點定位準確性并增強了噪聲魯棒性。對角點配準率、錯檢率、噪聲魯棒性和重復率等的實驗結果表明,本文算法具有較高檢測準確率、更小的錯檢率和較好的噪聲魯棒性。

[1] SMITH S M, BRADY J M. SUSAN-A new approach to low level image processing [J]. International Journal of Computer Vision, 1997, 23(1): 45-78.

[2] ROSTEN E, POTER R, DRUMMOND T. Faster and better: a machine learning approach to corner detection [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(1): 105-119.

[3] LAN J, ZHANG M. Fast and robust corner detector based on double-circle mask [J]. Optical Engineering, 2010, 49(12): 1-8.

[4] 王浩, 周祚峰, 曹劍中, 等. 基于邊緣輪廓上多尺度自相關矩陣的角點檢測 [J]. 系統工程與電子技術, 2014, 36(6): 1220-1224. WANG Hao, ZHOU Zuofeng, CAO Jianzhong, et al. Corner detection via multi-scale autocorrelation matrix on edge contours [J]. Systems Engineering and Electronics, 2014, 36(6): 1220-1224.

[5] HE X C, YUNG N H C. Corner detector based on global and local curvature properties [J]. Optical Engineering, 2008, 47(5): 1-12.

[6] AWRANGJEB M, LU G J. Robust image corner detection based on the chord-to-point distance accumulation technique [J]. IEEE Transactions on Multimedia, 2008, 10(6): 1059-1072.

[7] TENG S W, SADAT R M, LU G J. Effective and efficient contour-based corner detectors [J]. Pattern Recognition, 2015, 48(7): 2185-2197.

[8] 邢遠秀, 章登義, 趙儉輝. 利用多尺度弦角尖銳度累積的自適應角點檢測算子 [J]. 武漢大學學報: 信息科學版, 2015, 40(5): 617-622. XING Yuanxiu, ZHAO Dengyi, ZHAO Jianhui. An adaptive threshold corner detector based on multi-scale chord-angle sharpness accumulation [J]. Geomatics and Information Science of Wuhan University, 2015, 40(5): 617-622.

[9] SHUI P L, ZHANG W C. Corner detection and classification using anisotropic directional derivative representations [J]. IEEE Transactions on Image Processing, 2013, 22(8): 3204-3218.

[10]ZHANG W C, WANG F P. Corner detector using Gabor filters [J]. IET Image Processing, 2014, 8(11): 639-646.

[11]章為川, 水鵬朗, 朱磊. 利用各向異性高斯方向導數相關矩陣的角點檢測方法 [J]. 西安交通大學學報, 2012, 46(11): 91-97. ZHANG Weichuan, SHUI Penglang, ZHU Lei. A corner detection algorithm using anisotropic Gaussian directional derivatives autocorrelation matrix on edge contours [J]. Journal of Xi’an Jiaotong University, 2012, 46(11): 91-97.

[12]ZHANG W C, SHUI P L. Contour-based corner detection via angle difference of principal directions of anisotropic Gaussian directional derivatives [J]. Pattern Recognition, 2015, 48(9): 2785-2797.

(編輯 劉楊)

A Corner Detection Algorithm Based on Multi-Scale Directional Differential Ratio

WANG Fuping,SHUI Penglang

(National Key Lab of Radar Signal Processing, Xidian University, Xi’an 710071, China)

A new corner detection algorithm using multi-scale directional differential ratio (MDDR) of images is proposed to solve the problem that the interference between adjacent image structures may lead to the increase of the false detection ratio. The algorithm firstly extracts the image edge contour of an original grayscale image using the Canny edge detection algorithm. The differential information along the principal direction and its perpendicular direction of each contour pixel is extracted by using the isotropic Gaussian directional derivative filter and the anisotropic Gaussian directional derivative filter, respectively. Then, the differential ratios at three scales are fused into the MDDR corner measure. Final corners are then obtained through thresholding the fused measure followed by the non-maximum suppression. The MDDR algorithm is different from traditional corner detection algorithms that use a single filter, it uses two different kinds of filters to precisely extract the differential information along different directions around the corners and to avoid the interference between adjacent image structures. Thus, the corner localization accuracy is improved, and the noise-robustness of corner measures is enhanced. Experimental results and a comparison with the chord-to-point distance accumulation algorithm show that the average detection accuracy of the proposed algorithm increases by 27.1%, and the average false detection ratio of the proposed algorithm is 28.4% and 32.4% lower than those of the residual area and Gabor detection algorithms, respectively.

edge detection; multi-scale; directional differential ratio; corner detection

2015-09-10。 作者簡介:王富平(1987—),男,博士生;水鵬朗(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61271295)。

時間:2016-01-13

10.7652/xjtuxb201604011

TN911.7

A

0253-987X(2016)04-0068-08

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160113.1958.006.html