基于边缘的角点分类和描述算法

高建林

(南京航空航天大学 电子信息工程学院，江苏 南京 210016)



基于边缘的角点分类和描述算法

高建林

(南京航空航天大学 电子信息工程学院，江苏 南京 210016)

针对大部分角点算法只关注角点的位置信息，而忽略了角点分类的问题。文中提出了一种利用边缘方向对角点进行分类和描述的方法。根据角点附近边缘方向的分布情况，对构成角点的边缘方向进行二进制编码，从而为角点提供更多的约束。通过比较角点间的二进制编码，可找出相同类型的角点对。实验表明，该方法可实现图片中相同类型角点的匹配，具有较高的正确率。

角点；角点分类；角点描述

角点作为重要的图像局部特征，其在图像检索、三维重建、目标识别、运动检测等领域中应用广泛。现有的角点检测算法可分为两类：基于图像灰度的角点算法[1-7]和基于图像边缘轮廓的角点算法[8-15]。

基于图像灰度的角点检测算法利用图像的原始灰度值或灰度值的一阶、二阶偏导数来检测角点。知名基于灰度的角点有Harris[2]、SUSAN[3]、FAST[5-7]等。基于灰度的角点的算法通过灰度值的比较来检测角点。因此，这类算法对图像的细节变化较为敏感,同样对噪声也比较敏感。

基于边缘的角点检测算法可分为两步：首先，提取图像的边缘轮廓；然后在边缘轮廓上提取角点。这类算法中，一种重要的方式是通过计算边缘的曲率来判定角点。Mokhtarian[8]等人提出CSS(Curvature Scale Space)算法，该算法将局部曲率极大值点定义为角点。文献[9～11]对其进行了改进。文献[12]提出了一种基于模板的交汇点检测算法，文献[13]提出了一种使用圆形模板筛选角点的算法。相比于基于灰度的角点算法，文献[14～15]提出了基于各向异性高斯核的角点检测算法。相比较于基于灰度的角点检测算法，基于边缘的角点算法具有更好的抗噪声能力和更高的定位精度。

大部分角点算法只检测角点的位置信息。然而，在机器视觉应用中，仅了解角点的位置信息还不够，角点的类型也是一个重要的特征。文献[16]基于Harris算法，将角点分为简单角点和高阶角点。文献[15]在检测角点的同时，根据角点的归一化各向异性方向导数对其进行了分类，将角点可分为简单角点，Y型角点和星型角点。然而这两种方法均过于简单，不能对角点进行较好的区分。针对这一问题，本文提出一种新的角点分类和描述方法。本文算法在对角点进行分类的同时，还能对构成角点的边缘方向进行二进制编码，构造出角点的局部特征描述子。

1 CSS角点算法

CSS[6]是由Mokhtarian等人提出的基于曲率空间的角点检测方法。CSS定义角点为边缘轮廓上曲率最大值的点。曲率的定义为

(1)

CSS角点检测算法具体步骤如下：(1)利用Canny边缘检测算子从原始图像中提取图像边缘；(2)从边缘图像中提取边缘轮廓并填充边缘轮廓的缺口；(3)在大尺度下计算曲率,选择绝对曲率大于某阈值 的点作为候选角点；(4)跟踪角点到小尺度以提高角点定位。CSS角点算法具有较好的角点提取效果，本文采用CSS算法检测角点的位置信息。

2 角点附近边缘方向计算

如图1所示，边缘点p处的方向可由梯度的水平分量Gy的垂直分量Gx进行计算。基于边缘的角点检测算法的第一步是提取图像的边缘轮廓。而在提取边缘轮廓时，梯度的水平分量垂直分量已计算完成。因此，边缘的方向可轻易获得，无需额外进行计算。点P的边缘方向可表示为

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

(2)

图1 边缘方向示意图

3 角点分类和描述

大多数的角点检测算法只关注角点的位置，而忽略了形成角点周边的图像特征，比如角点的类型、构成角点的边缘信息。文献[10]将角点分为简单角点和高阶角点。文献[9]根据构成边缘的条数将角点分为简单角点，Y型角点和星型角点。然而这两种角点的分类方法都过于简单，其只统计了构成角点的边缘数目，而未考虑边缘的方向，这并不能对角点进行有效区分。如图2所示，其均属于Y型角点，但构成其的边缘方向却各不相同。所以仅按边缘的数目对角点进行分类，并不能对角点的类型进行较好的区分。

图2 几种不同的Y型角点

为了对角点的类型进行更准确的分类，文中将构成角点的边缘方向进行编码，形成一个16位的二进制位串。首先，将边缘方向等分成16个区间，分区编号如图3(a)所示。当边缘方向位于这一区间时，将二进制位串的对应位置1。如边缘方向位于1区时，将二进制码的第一位编为1，则对应的二进制码为[0000 0000 0000 0001]。如图3(b)中的角点，该角点由三条边缘相交所成，边缘方向如图3(c)中箭头所示，将三条边缘的方向进行编码后，可得该角点的二进制描述子为[0010010100000000]。二进制码中1的个数表示构成角点边缘的数目，1的位置表示边缘的方向。通过统计二进制码中1的个数，便可得知角点的类型。按文献[9]的角点类型定义，个数为2时，为简单角点，个数为3时，为Y型角点；个数为4时，为星型角点。

图3 边缘方向编码

此外，二进制编码中还保留了边缘的方向信息，这些方向信息可为角点提供更多的特征约束。应用到图像匹配中，可利用该二进制码作为描述子对角点的类型进行匹配。将不同角点的二进制码进行异或操作，当结果为零时，表示角点具有相同的边缘方向，角点的类型也相同。具体方法为：

(1)将两幅待匹配图像记为T1，T2。取T1中某一角点的坐标，记为p，二进制码记为τp；

(2)在T2中，取以坐标p为中心，半径为R的圆形区域。将该区域内所有角点的二进制码与τp进行异或操作。当结果为零，表示这两个角点的类型相同，其组成一个匹配对；

(3)对T1中所有角点重复步骤(1)和步骤(2)。

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

图4 角点类型匹配示意图

对二进制码进行扩展后，便可对二进制码的相似性进行计算，定义二进制码的相似性测度为

(3)

4 实验结果分析

图5所示为CSS算法的角点取效果图。图6所示为用本文提出的角点描述子对两幅图像中的角点进行匹配之后的效果图。图5中，匹配的角点总数为17个，其中匹配正确的角点个数为15个，匹配率达88%，说明本文提出的角点特征描述子是有效，其可实现图片中相同类型角点的匹配。本文提出的角点特征描述子采用二进制编码的方式，通过异或操作的方式，可提高匹配的速度。

图5 角点提取效果图

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

5 结束语

提出了一种利用边缘方向对角点进行分类和描述的方法，对构成角点的边缘的方向进行二进制编码，形成16为的二进制位串，可实现角点的分类。对角点的二进制编码进行扩展，通过异或操作计算不同角点二进制编码的相似程度，能实现图片中相同类型角点的匹配。由于本文提出的特征描述子只保留了构成角点的边缘的方向信息，而未保留角点邻域的灰度信息；因此对视角变化和旋转的图片，匹配效果较差。后续工作将研究将角点邻域的灰度分布情况加到该二进制码中，使其适合各种图像变化条件下的匹配。

[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-)，男，硕士研究生。研究方向：数字图像处理。

TP391.41

A

1007-7820(2016)12-081-04