高建林

(南京航空航天大學(xué) 電子信息工程學(xué)院，江蘇 南京 210016)

?

基于邊緣的角點(diǎn)分類和描述算法

高建林

(南京航空航天大學(xué) 電子信息工程學(xué)院，江蘇 南京 210016)

針對大部分角點(diǎn)算法只關(guān)注角點(diǎn)的位置信息，而忽略了角點(diǎn)分類的問題。文中提出了一種利用邊緣方向?qū)屈c(diǎn)進(jìn)行分類和描述的方法。根據(jù)角點(diǎn)附近邊緣方向的分布情況，對構(gòu)成角點(diǎn)的邊緣方向進(jìn)行二進(jìn)制編碼，從而為角點(diǎn)提供更多的約束。通過比較角點(diǎn)間的二進(jìn)制編碼，可找出相同類型的角點(diǎn)對。實(shí)驗(yàn)表明，該方法可實(shí)現(xiàn)圖片中相同類型角點(diǎn)的匹配，具有較高的正確率。

角點(diǎn)；角點(diǎn)分類；角點(diǎn)描述

角點(diǎn)作為重要的圖像局部特征，其在圖像檢索、三維重建、目標(biāo)識別、運(yùn)動檢測等領(lǐng)域中應(yīng)用廣泛?，F(xiàn)有的角點(diǎn)檢測算法可分為兩類：基于圖像灰度的角點(diǎn)算法[1-7]和基于圖像邊緣輪廓的角點(diǎn)算法[8-15]。

基于圖像灰度的角點(diǎn)檢測算法利用圖像的原始灰度值或灰度值的一階、二階偏導(dǎo)數(shù)來檢測角點(diǎn)。知名基于灰度的角點(diǎn)有Harris[2]、SUSAN[3]、FAST[5-7]等?；诨叶鹊慕屈c(diǎn)的算法通過灰度值的比較來檢測角點(diǎn)。因此，這類算法對圖像的細(xì)節(jié)變化較為敏感,同樣對噪聲也比較敏感。

基于邊緣的角點(diǎn)檢測算法可分為兩步：首先，提取圖像的邊緣輪廓；然后在邊緣輪廓上提取角點(diǎn)。這類算法中，一種重要的方式是通過計算邊緣的曲率來判定角點(diǎn)。Mokhtarian[8]等人提出CSS(Curvature Scale Space)算法，該算法將局部曲率極大值點(diǎn)定義為角點(diǎn)。文獻(xiàn)[9～11]對其進(jìn)行了改進(jìn)。文獻(xiàn)[12]提出了一種基于模板的交匯點(diǎn)檢測算法，文獻(xiàn)[13]提出了一種使用圓形模板篩選角點(diǎn)的算法。相比于基于灰度的角點(diǎn)算法，文獻(xiàn)[14～15]提出了基于各向異性高斯核的角點(diǎn)檢測算法。相比較于基于灰度的角點(diǎn)檢測算法，基于邊緣的角點(diǎn)算法具有更好的抗噪聲能力和更高的定位精度。

大部分角點(diǎn)算法只檢測角點(diǎn)的位置信息。然而，在機(jī)器視覺應(yīng)用中，僅了解角點(diǎn)的位置信息還不夠，角點(diǎn)的類型也是一個重要的特征。文獻(xiàn)[16]基于Harris算法，將角點(diǎn)分為簡單角點(diǎn)和高階角點(diǎn)。文獻(xiàn)[15]在檢測角點(diǎn)的同時，根據(jù)角點(diǎn)的歸一化各向異性方向?qū)?shù)對其進(jìn)行了分類，將角點(diǎn)可分為簡單角點(diǎn)，Y型角點(diǎn)和星型角點(diǎn)。然而這兩種方法均過于簡單，不能對角點(diǎn)進(jìn)行較好的區(qū)分。針對這一問題，本文提出一種新的角點(diǎn)分類和描述方法。本文算法在對角點(diǎn)進(jìn)行分類的同時，還能對構(gòu)成角點(diǎn)的邊緣方向進(jìn)行二進(jìn)制編碼，構(gòu)造出角點(diǎn)的局部特征描述子。

1 CSS角點(diǎn)算法

CSS[6]是由Mokhtarian等人提出的基于曲率空間的角點(diǎn)檢測方法。CSS定義角點(diǎn)為邊緣輪廓上曲率最大值的點(diǎn)。曲率的定義為

(1)

CSS角點(diǎn)檢測算法具體步驟如下：(1)利用Canny邊緣檢測算子從原始圖像中提取圖像邊緣；(2)從邊緣圖像中提取邊緣輪廓并填充邊緣輪廓的缺口；(3)在大尺度下計算曲率,選擇絕對曲率大于某閾值 的點(diǎn)作為候選角點(diǎn)；(4)跟蹤角點(diǎn)到小尺度以提高角點(diǎn)定位。CSS角點(diǎn)算法具有較好的角點(diǎn)提取效果，本文采用CSS算法檢測角點(diǎn)的位置信息。

2 角點(diǎn)附近邊緣方向計算

如圖1所示，邊緣點(diǎn)p處的方向可由梯度的水平分量Gy的垂直分量Gx進(jìn)行計算?；谶吘壍慕屈c(diǎn)檢測算法的第一步是提取圖像的邊緣輪廓。而在提取邊緣輪廓時，梯度的水平分量垂直分量已計算完成。因此，邊緣的方向可輕易獲得，無需額外進(jìn)行計算。點(diǎn)P的邊緣方向可表示為

α(p)=tan-1(Gy/Gx)

(2)

圖1 邊緣方向示意圖

3 角點(diǎn)分類和描述

大多數(shù)的角點(diǎn)檢測算法只關(guān)注角點(diǎn)的位置，而忽略了形成角點(diǎn)周邊的圖像特征，比如角點(diǎn)的類型、構(gòu)成角點(diǎn)的邊緣信息。文獻(xiàn)[10]將角點(diǎn)分為簡單角點(diǎn)和高階角點(diǎn)。文獻(xiàn)[9]根據(jù)構(gòu)成邊緣的條數(shù)將角點(diǎn)分為簡單角點(diǎn)，Y型角點(diǎn)和星型角點(diǎn)。然而這兩種角點(diǎn)的分類方法都過于簡單，其只統(tǒng)計了構(gòu)成角點(diǎn)的邊緣數(shù)目，而未考慮邊緣的方向，這并不能對角點(diǎn)進(jìn)行有效區(qū)分。如圖2所示，其均屬于Y型角點(diǎn)，但構(gòu)成其的邊緣方向卻各不相同。所以僅按邊緣的數(shù)目對角點(diǎn)進(jìn)行分類，并不能對角點(diǎn)的類型進(jìn)行較好的區(qū)分。

圖2 幾種不同的Y型角點(diǎn)

為了對角點(diǎn)的類型進(jìn)行更準(zhǔn)確的分類，文中將構(gòu)成角點(diǎn)的邊緣方向進(jìn)行編碼，形成一個16位的二進(jìn)制位串。首先，將邊緣方向等分成16個區(qū)間，分區(qū)編號如圖3(a)所示。當(dāng)邊緣方向位于這一區(qū)間時，將二進(jìn)制位串的對應(yīng)位置1。如邊緣方向位于1區(qū)時，將二進(jìn)制碼的第一位編為1，則對應(yīng)的二進(jìn)制碼為[0000 0000 0000 0001]。如圖3(b)中的角點(diǎn)，該角點(diǎn)由三條邊緣相交所成，邊緣方向如圖3(c)中箭頭所示，將三條邊緣的方向進(jìn)行編碼后，可得該角點(diǎn)的二進(jìn)制描述子為[0010010100000000]。二進(jìn)制碼中1的個數(shù)表示構(gòu)成角點(diǎn)邊緣的數(shù)目，1的位置表示邊緣的方向。通過統(tǒng)計二進(jìn)制碼中1的個數(shù)，便可得知角點(diǎn)的類型。按文獻(xiàn)[9]的角點(diǎn)類型定義，個數(shù)為2時，為簡單角點(diǎn)，個數(shù)為3時，為Y型角點(diǎn)；個數(shù)為4時，為星型角點(diǎn)。

圖3 邊緣方向編碼

此外，二進(jìn)制編碼中還保留了邊緣的方向信息，這些方向信息可為角點(diǎn)提供更多的特征約束。應(yīng)用到圖像匹配中，可利用該二進(jìn)制碼作為描述子對角點(diǎn)的類型進(jìn)行匹配。將不同角點(diǎn)的二進(jìn)制碼進(jìn)行異或操作，當(dāng)結(jié)果為零時，表示角點(diǎn)具有相同的邊緣方向，角點(diǎn)的類型也相同。具體方法為：

(1)將兩幅待匹配圖像記為T1，T2。取T1中某一角點(diǎn)的坐標(biāo)，記為p，二進(jìn)制碼記為τp；

(2)在T2中，取以坐標(biāo)p為中心，半徑為R的圓形區(qū)域。將該區(qū)域內(nèi)所有角點(diǎn)的二進(jìn)制碼與τp進(jìn)行異或操作。當(dāng)結(jié)果為零，表示這兩個角點(diǎn)的類型相同，其組成一個匹配對；

(3)對T1中所有角點(diǎn)重復(fù)步驟(1)和步驟(2)。

τp1=[0100 0000 0000 1000]τp=[0100 0000 0000 0100]τp2=[0101 0000 0000 0000]

圖4 角點(diǎn)類型匹配示意圖

對二進(jìn)制碼進(jìn)行擴(kuò)展后，便可對二進(jìn)制碼的相似性進(jìn)行計算，定義二進(jìn)制碼的相似性測度為

(3)

4 實(shí)驗(yàn)結(jié)果分析

圖5所示為CSS算法的角點(diǎn)取效果圖。圖6所示為用本文提出的角點(diǎn)描述子對兩幅圖像中的角點(diǎn)進(jìn)行匹配之后的效果圖。圖5中，匹配的角點(diǎn)總數(shù)為17個，其中匹配正確的角點(diǎn)個數(shù)為15個，匹配率達(dá)88%，說明本文提出的角點(diǎn)特征描述子是有效，其可實(shí)現(xiàn)圖片中相同類型角點(diǎn)的匹配。本文提出的角點(diǎn)特征描述子采用二進(jìn)制編碼的方式，通過異或操作的方式，可提高匹配的速度。

圖5 角點(diǎn)提取效果圖

圖6 本文描述子匹配效果圖

5 結(jié)束語

提出了一種利用邊緣方向?qū)屈c(diǎn)進(jìn)行分類和描述的方法，對構(gòu)成角點(diǎn)的邊緣的方向進(jìn)行二進(jìn)制編碼，形成16為的二進(jìn)制位串，可實(shí)現(xiàn)角點(diǎn)的分類。對角點(diǎn)的二進(jìn)制編碼進(jìn)行擴(kuò)展，通過異或操作計算不同角點(diǎn)二進(jìn)制編碼的相似程度，能實(shí)現(xiàn)圖片中相同類型角點(diǎn)的匹配。由于本文提出的特征描述子只保留了構(gòu)成角點(diǎn)的邊緣的方向信息，而未保留角點(diǎn)鄰域的灰度信息；因此對視角變化和旋轉(zhuǎn)的圖片，匹配效果較差。后續(xù)工作將研究將角點(diǎn)鄰域的灰度分布情況加到該二進(jìn)制碼中，使其適合各種圖像變化條件下的匹配。

[1] Moravec H. Rover visual obstacle avoidance[C].Vancouver, Canada：In International Joint Conference on Artificial Intelligence,1981.

[2] Harris C, Stephens M.A combined corner and edge detector[C].Toronto:Proceedings of the 4th Alvey Vision Conference,1988.

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

[4] Bae S C, Kweon I S, Yoo C D. Cop:a new corner detector[J].Pattern Recognition Letters,2002,23(11):1349-1360.

[5] Rosten E,Porter 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.

[6] Rosten E, Drummond T. Machine learning for high-speed corner detection[C].Duberlin:Computer Vision-ECCV, 2006.

[7] Elmar Mair,Gregory D Hager,Darius Burschka,et al.Adaptive and generic corner detection based on the accelerated segment test[C].Wels:In Proceedings of the European Conference on Computer Vision,2010.

[8] Mokhtarian F, Suomela R.Robust image corner detection through curvature scale space[J].IEEE Transactions on Patt. Anal. Mach. Intell.,1998,12(12):1376-1381.

[9] He X,Yung N.Corner detector based on global and local curvature properties[J].Optical Engineering, 2008, 47(5):1-12.

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

[11] Awrangjeb M, Lu G.An improved curvature scale-space corner detector and a robust corner matching approach for transformed image identification[J].IEEE Transactions on Image Processing, 2008(17):2425-2441.

[12] Sinzinger E D. A model-based approach to junction detection using radial energy[J]. Pattern Recognition, 2008, 41(2):494-505.

[13] Elias R , Laganiere R. JUDOCA: junction detection operator based on circumferential anchors[J].IEEE Transactions on Image Processing,2012,21(4): 2109-2118.

[14] 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.

[15] Shui L,Zhang W C, Corner detection and classification using anisotropic directional derivative representations[J].IEEE Transactions on Image Processeding, 2013, 22(8):3204-3218.

[16] JRyu J B,Park H H,Park J.Corner classification using harris algorithm[J].Electronic Letter, 2011, 47(9):536-538.

Contour-based Corner Classification and Description

GAO Jianlin

(School of Electronic Information Engineering,Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)

Corners in image are important features which widely used in computer vision systems. But most of contour-based corner detectors only detect the locations of corners, but neglect the type of those points. In this paper, we proposed a corner classification and description method based on edge direction. The proposed method can encode the edge direction into binary stringaccording to the edge directiondistribution near the corner, which preserves more information for the corners. By comparing the binary codeof the corner, we can find the cornerswhich belong to the same type. Experimental results show that the method can implement the matching of corners in same type witha high accuracy rate.

corner; corner classification; corner description

10.16180/j.cnki.issn1007-7820.2016.12.023

2016- 02- 18

高建林(1991-)，男，碩士研究生。研究方向：數(shù)字圖像處理。

TP391.41

A

1007-7820(2016)12-081-04