其中（x0,y0），(x,y)分别为模板中心像素点和待比较像素点的坐标，t为相似度阈值，本文该值取整幅图像灰度最大值和最小值差值的1/10。

则与中心点像素相似点的个数为：

本文取图像每11×11领域范围内来搜索CRF为极大值的像素点，当该像素点CRF数值大于控制阈值thresh （本文取13），则将该点标记为角点。

角点是图像很重要的特征,对图像图形的理解和分析有很重要的作用。对灰度图像、二值图像、边缘轮廓曲线的角点检测算法进行综述,分析了相关的算法,并对各种检测算法给出了评价。

角点检测特征点； 综述中图法分类号：TP391

文献标识码：A

文章编号：1001-3695(2006)10-0017-03

Survey on Corner Detection

ZHAO Wen?bin, ZHANG Yan?ning

(Key Lab. of Shanxi Province Computer Graphics, College of Computer, Northwestern Polytechnical University, Xi’an Shanxi 710072, China) Abstract:Corner is important feature in the analysis and understanding of images or computer graphics. This paper attempt to summarize corner detection method in gray?level image, binary image and curve of edge, also to compare with many property of corner detection algorithm.

Key words:Corner Detection; Feature Point; Survey

角点没有明确的数学定义,但人们普遍认为角点是二维图像亮度变化剧烈的点或图像边缘曲线上曲率极大值的点。这些点在保留图像图形重要特征的同时,可以有效地减少信息的数据量,使其信息的含量很高,有效地提高了计算的速度,有利于图像的可靠匹配,使得实时处理成为可能。其在三维场景重建、运动估计、目标跟踪、目标识别、图像配准与匹配等计算机视觉领域起着非常重要的作用。

角点检测算法可以说各种各样。一般使用者仅仅要求得到一个准确的角点检测结果或该检测算法易于编程实现,满足实际后续匹配等应用需要。本文对角点检测按检测目标进行分类,对各种类下的检测算法逐一进行归纳分析。

基于梯度的方法

基于梯度的方法是通过计算边缘的曲率来判断角点的存在性,角点计算数值的大小不仅与边缘强度有关,而且与边缘方向的变化率有关,该方法对噪声比基于模板的角点检测方法对噪声更为敏感。L.Kchen和A.Rosedfeld给出了具体的角点检测算子K,通过检测K在图像某一领域的极大值来达到提取角点的目的。该算子为K=tp?2 rq?2-2spqp?2 q?2,它表现为水平面截线上某点(x,y)的曲率与该点的最大梯度的乘积。但田原和梁德群等人指出K(x,y)在最大梯度方向上并不是极大值点,而是呈现单调变化的,所以在某一个邻域内曲率和该点的最大梯度乘积的极大值并不会出现 在角点上。因此通过计算基于梯度的算法来确定的角点是不合理的。

考虑到角点作为一种重要的信号特征,属于图像的细节,按照Witkin尺度空间理论,该角点应该在较大的尺度空间存在。基于小波多尺度分析的角点检测,通过提出不同尺度上角点的对应关系准则由大尺度跟踪到小尺度上精确的角点位置。设定提取角点的最大尺度2?k、梯度阈值Thg和曲率值Th?c,对图像进行小波变换,得到各个尺度上的小波分量W?x??2??j(x,y)和W?y??2??j(x,y)；利用各个尺度上的小波分量在相应的尺度上提取角点,记录这些角点的位置;从最大的尺度k开始,按照前面所确定的原则寻找较小尺度上的对应角点,直到最小的尺度为止;清除最小尺度上与上一尺度不对应的点,得到最终角点结果。针对文献的错误,就对某一尺度上的角点检测算法,文献指出角点不仅是水平面截线上的曲率极值点,也是该点在最大梯度方向上其最大梯度的模达到极大值，是满足两个条件的点集的交集。

基于模板的方法

基于模板的方法主要考虑像素邻域点的灰度变化,即图像亮度的变化,将与邻点亮度对比足够大的点定义为角点。

较早的直接基于灰度图像角点检测是文献提出的Kitchen?Rosenfeld算法,通过模板窗口局部梯度幅值和梯度方向的变换率来计算角点度量值C=I?xyI?2?y I?yyI?2?x-2I?xyI?xI?yI?2?x I?2?y,根据C与给定的阈值大小关系来判定该点是否是角点。

Harris等人检测方法考虑的是用一个高斯窗或矩形窗在图像上移动,由模板窗口取得原图像衍生出2×2的局部结构矩阵，M=∑x,yw(x,y)I?2xI?xI?y I?xI?yI?2?y,w(x,y)为窗口函数。对该模板矩阵求取特征值λ?1和λ?2,建立度量函数R=detM-k(traceM)?2,detM=λ?1λ?2,traceM=λ?1 λ?2，根据R是否大于0即可判断该点是否是角点。值得注意的是该方法具有旋转不变性,但检测的角点有较大的冗余,需要根据实际经验来确定R的阈值。

被大多数人所熟悉的KLT角点检测算法[6，7]也是对基于一个计算窗口模板D×D下的图像计算局部结构矩阵，计算其特征值λ?1和λ?2，根据给定阈值λ按照式子min（λ?1,λ?2）＞λ来判定其是否为角点。这里的关键是阈值λ和窗口D的大小的确定，D的大小一般为2~10,太大的窗口会引起角点移动,窗口太小则会丢失相距较近的角点。

USAN或SUSAN角点检测算法得到越来越多的关注，最小亮度变化算法(MIC)[8]、同值分割吸收核(Univalue Segment Assimilating Nucleus，USAN)算法[9]都是基于像素邻域半径为k的圆形模板。该算法基于角点响应函数(CRF),对每个像素基于其模板邻域的图像灰度计算CRF值,如果大于某一阈值且为局部极大值,则认为该点为角点，一般k取1或2。

由算法的实现和相关结果可以看出,KLT算法比Harris算法检测角点的质量高,但KLT算法适用于角点数目不多且光源简单的情况,Harris适用于角点数目较多且光源复杂的情况。除了对单幅图像能进行角点检测以外,KLT算法和Harris算法对图像序列的角点检测效果更好。Kitchen?Rosenfeld算法和USAN算法一般来说不适合序列图像的角点跟踪,对于单幅图像的角点检测,USAN算法要比Kitchen?Rosenfeld算法好得多。但Harris算法的实现公式中有平滑部分,因此具有较强的鲁棒且对噪声也不太敏感。但在实际计算过程中,圆形模板需要离散化,这就带来了较大的量化误差,容易导致边缘点和角点的判断混乱。对于边缘模糊的图像,使用小模板会丢失角点,这就需要动态地判断究竟用哪种模板最优。文献[10]针对此问题提出模糊度的概念,对每一个像素在计算其CRF值之前首先测定其模糊度。若达到模糊的标准,就使用大的模板来计算；若清晰,则选用小的模板来计算。这使得判定的准确性得到很大的提高,减少了虚报概率。

费旭东等人[11]采用基于知识的查表技术来进行角点的快速提取,其特点是便于用硬件来实现,但必须先得到图像的边界链码表示,原则上属于模板匹配。

一般来说,各种角点检测算子要与图像进行卷积运算,所以也应该属于模板类的方法。

文献[12]采用高斯—拉普拉斯二阶微分算子来检测角点。高斯二阶微分函数与离散信号的卷积相当于高斯函数与信号的卷积再求二阶差分,因此对噪声的敏感度较大。文献[13]基于神经细胞(Gauglion Cell，GC)感受野数学模型提出双高斯差(Difference Of Gaussian，DOG)模型来检测角点,指出高斯二阶微分函数是DOG函数在其两个高斯函数相互逼近时的一个极端形式特例。DOG函数与信号的卷积相当于两个高斯函数与信号的卷积结果之差,因此抗噪声的能力较强。

基于模板梯度组合方法

除了直接对灰度图像的像素操作以外,罗斌等人[14]采用了变换的方法,用电磁场理论中矢势的鞍点检测来代替角点的检测,是一种综合了模板角点检测和灰度曲率角点检测的方法。通过高斯模板和图像的卷积获得Canny边缘映射图,再计算梯度和边缘矢量就得到了矢势。对于矢势计算高斯曲率和平均曲率来判定是否是鞍点,对应的应该是图像的角点。因为涉及到了曲率的计算,也有人将该方法归到边缘曲线的角点检测。

刘文予等人[15]提出一种基于形态骨架的角点检测方法,该方法将原始图像看作一个多边形,则多边形的角点一定在骨架的延长线上,且角点所对应的骨架点的最大圆盘半径应该趋于0,检测骨架中的最大圆盘为0的点,即为角点。因为在二值图像阶段处理,计算量并不是很大,所以保证了计算的实时性。应该指出的是,虽然将二值图像作为一个单独的检测目标列出来,但是基于灰度图像的各种处理方法对此仍然有效。二值图像处于灰度和边缘轮廓图像的中间步骤,所以专门针对此类图像的角点检测方法并不多见。

计算角点强度k

早在1975年，Rosenfeld A等人[16]和Freeman H等人[17]就提出通过计算角点强度k来提取角点,不过这种方法虽然简单，但容易受噪声干扰，效果不是很理想。为了将干扰去除,减少边缘毛刺干扰，Asada等人[18]提出首先对边缘采用高斯平滑,即减少了将局部弯曲度突然增大而误判为角点的概率。但角点强度k是预先确定还是根据曲线的弯曲度自适应调节,对于检测的结果影响很大。文献[19]指出自适应的弯曲度测定实际上是要自适应地确定曲线段支持区域的大小,支持区域的选择应该能够根据曲线的弯曲程度自适应地调整,在此支持区域上求取的曲线弯曲度才能较为准确地反映平面对象边界曲线的平滑和弯曲程度。文献[20]提出采用自适应弯曲度求取算法计算曲线上任意点所在位置的曲线弯曲度,将曲线边界点集中满足限定条件的点组成候选角点集合,增加平滑参数开始新的循环,直到达到预先设定的最大平滑因子为止,最后将所有候选角点集合中出现次数满足一定门限的边界点定义为角点。

文献[21]认为数字化曲线是离散的,是基于像素基础的,这样隐含的一个假设就是数字化曲线上相邻两个像素之间的距离是一个常数,但在实际中该假设并不成立,因此质疑早先对角点的估计方法是否可拟合稳定。基于这个发现,文章提出了基于曲线累加弦长的角点检测方法,主要是在确定支持域时充分考虑相邻像素点之间的实际距离,即相邻的距离应该是1和2,并由此出发提出隐式精化数字化曲线的策略,推导出了一种新的角点强度计算公式。利用该公式可以对如尖角和圆角进行区别,检测结果具有旋转不变性。该方法被认为是在数字化图像处理中引入了纳米技术。

计算曲线曲率的极值

对于曲线曲率的计算,一种是直接对离散的曲线进行计算,另一种是用某类函数对原始曲线分段拟合,然后根据拟合后的曲线分段方程,计算曲线曲率极值得到角点的位置。

文献[22]使用了三次多项式来拟合离散的数据点,文献[23]提出了B样条来拟合曲线,由于要事先实现计算曲线的拟合方程,其运算量比较大。文献[21]提出算法根据曲线上任意点的弯曲度,结合模糊识别的方法来检测对象边界曲线的角点。而文献[24]认为既然角点是曲线上曲率较大的点,角点检测的关键是估计当前轮廓点前后曲线的方向,该方向的度量采用定义的一个方向差角d?θ=180°-min{|θ?1-θ?2|,360°-|θ?1-θ?2|},差角越大,表示曲率越大。其中基于距离误差的直线拟合可以自适应地调整拟合窗口,很好地减少了边缘噪声的干扰。在文献[25]中除了像文献[24]对角点两侧的点构成向量的夹角继续关注以外,还对曲线角点的特征进行了多方位的考虑,同时引用模糊集合的概念,采用隶属度对点领域的四个特征进行描述。这四个特征分别为角点前后点组成的向量与角点的距离特征、角点前后向量夹角特征、角点的前向直线特征、角点的后向直线特征。采用隶属度描述后,对真实角点的相邻点有很强的抑制作用,检出的角点符合人类视觉感知规律。但该算法仅考虑了角点的局部特性,没有考虑全局特征,因此存在一定的漏检现象。在关注角点细节特征的同时,如何能有效地考虑全局整体特征,应该是该算法需要完善的地方。

多尺度角点检测

滤波器的尺度选择并不是一件容易的事情,要求在滤掉噪声的同时保持边界曲线的基本形状特征。同时曲线上各角点均有着不同尺度的支撑域,无法事先定义出一个最优的分辨率来进行角点检测。在使用多尺度分析后求取不同尺度的空间时,轮廓曲线已经被不同的小波函数所平滑,所以能最大限度地减少边缘毛刺噪声。

Witkin[20]和Koenderink[26]提出基于尺度空间的图像分析理论后,多尺度曲线分析成为解决该问题的主要方法,在曲线尺度空间中,随着曲线尺度由小变大,一直保持较高弯曲度的点必定是所要求取的角点。基于此,文献[27]提出基于尺度空间的角点检测思想,文献[28]对采用二阶导数零交叉边缘检测算子和围线跟踪算法得到的边缘曲线,使用一组自相似二进Gabor小波变换的滤波器将整个频域从高频到低频分为多个子带,对两个不同尺度下的滤波器输出求差并取模,根据结果即可判定该点是否是角点。

在上面的多尺度检测中,仅考虑了角点的位置信息,文献[29]提出在利用角点的位置信息时不能忽略有关角点的幅度信息。在选定小波为高斯函数的一阶导数后,对图像轮廓的Freeman链码C={P?i=(x?i,y?i),i=1,…,n}投影成函数φ(i)=arctg[(y?i q-y?i-q)/(x?i q-x?i-q)],对φ(i)进行小波变换,在不同的尺度上,角点的小波变换幅值始终是最大的,位置始终是不变的。如果有噪声,那么噪声的幅值只存在于有限的尺度空间上,结合幅值判据和位置判据就能够很好地确定角点,剔除伪角点,结果的准确性很高。同时结合不同的角点模型,还可以对角点是单角、双角、三角的属性作出判别。

角点作为图像上的特征点,包含有重要的信息，在图像融合和目标跟踪及三维重建中有重要的应用价值。但是基于实际应用需求,从角点检测的快速性、准确性、鲁棒性等要求出发,可以看出上面对各种角点检测算法的分析各有利弊。直接基于图像的角点检测基本上是全局搜索；基于边缘轮廓的角点检测数据量较少,可以采用多分辨分析并行处理,从灰度图像得到边缘轮廓曲线要经过两次以上的全局搜索,速度并不是很快,但对角点的误检和漏检要比直接基于图像的方法好得多。如果在得到轮廓曲线的过程中应用一些其他的变换方法,就计算的速度而言,下降不少，所以一般快速的、较准确的角点检测使用直接基于图像模板的方法完全可以满足需要,但如果对角点的完备性要求较高,那么使用基于轮廓线的多尺度分析方法应该给予考虑。

Deriche R,Giraudon G. A Computational Approach for Corner and Vertex Detection[J]. Computer Vision, 1993,10(2):101?124. L Kitchen, A Rosenfeld. Gray Level Corner Detection[J]. Pattern Recognition Letters, 1982,3(1):95?102.

田原,梁德群,吴更石.直接基于灰度图像的多尺度角点检测方法[J].信号处理,1998,14(7?11):6-9.

L Kitchen, A Rosenfeld. Analysis of Gray Level Corner Detection[J]. Pattern Recognition Letters, 1999,20(2):149?162.

Chris Harris, Mike Stephens. A Combined Corner and Edge Detector[C]. Manchester: Proceedings of the 4th Alvey Vision Conference, 1988.147?151.

C Tomasi, T Kanade. Detection and Tracking of Point Features[R]. Carnegie Mellon University, 1991.

J Shi, C Tomasi. Good Features to Track[C]. CVPR’94, 1994.593-600.[8]Miroslav T, Mark H. Fast Corner Detection[J]. Image and Vision Computing, 1998,16(1):75-87.

[9]Smith S M, Brady J M.SUSAN: A New Approach to Low Level Image Processing[J]. Int. Journal of Compuer Vision, 1997,23(1):45-78. [10]杨莉,初秀琴,李玉山.最小亮度变化角点自适应检测算法研究[J].西安电子科技大学学报,2003,30(4):530-533.

[11]费旭东,荆仁杰.基于知识的快速角点提取[J].计算机学报,1994,17(1):30-36.

[12]G Giraudon, R Derich. On Corner and Vertex Detection[J]. Computer Vision and Pattern Recognition, 1991,3(6):650-655.

[13]陈燕新,戚飞虎.一种新的提取轮廓特征点的方法[J].红外与毫米波学报,1998,17(3):171?176.

[14]罗斌,E R Hancock.图像角点检测的矢量场方法[J].中国图像图形学报,1998,3(10):832-835.

[15]刘文予,朱光喜.二值图像角点检测的形态骨架法[J].信号处理,2000,16(3):276-280.

[16]Rosenfeld A, Weszka J S. An Improved Method of Angel Detection on Digital Curves[J]. IEEE Trans.Computers,1975,C?24(9):940-941.

[17]Freeman H, Davis L S. A Corner Finding Algorithm for Chain Coded Curves[J]. IEEE Trans. Computers, 1977,26(3):297-303.

[18]Asada H, Brady M. The Curvature Primal Sketch[J]. IEEE Trans. PAMI,1986,8(1):2?14.

[19]肖茜,鲁宏伟.基于高斯平滑的自适应角点检测[J].计算机辅助设计与图形学学报,2003,15(11):1358?1361.

[20]Witkin A P. Scale Space Filtering[C]. Karlsruhe: Proceedings of the 8th International Joint Conference on Artificial Intelligence, 1983.1019?1021.

[21]钟宝江,廖文和.基于精化曲线累加弦长的角点检测技术[J].计算机辅助设计与图形学学报,2004,16(7):939-943.

[22]Langridge D J. CurveEncodingand the Detection of Discontinuities[J]. CVGIP, 1982,20(1):58-71.

[23]Mediono G, Yasumoto Y. Corner Detection and Curve Representation Using Cubic B?splines[J]. Computer Vision, Graphics and Image Processing, 1987,39(3):267-278.

[24]乔宇,黄席樾,柴毅.基于自适应直线拟合地角点检测[J].重庆大学学报,2003,26(2):29-31.

[25]邱卫国,昂海松.基于隶属度特征的曲线角点检测方法[J].重庆大学学报,2004,27(11):43-46.

[26]Koenderink J J. The Structure of Image[J]. Biological Cybernetics, 1984,50(5):363-370.

[27]Anothai Rattarangsi, Chin Roland T. Scale?based Detection of Corners of Planar Curves[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(4):430-449.

[28]王展,黄埔堪,万建伟.基于多尺度小波变换的二维图像角点检测技术[J].国防科技大学学报,1999,21(2):46-49.

[29]戚飞虎,刘健峰.一种有效的不变性角点检测方法[J].上海交通大学学报,1995,29(6):112?116.

作者简介：

赵文彬(1974-),男,助教,博士,主要研究方向为医学图形图像处理、医学三维重建与识别、虚拟手术.

张艳宁（1967-），女，中国电子学会信号处理分会委员，中国体视学学会理事及图像分析分会秘书长，IEEE会员，主任，教授，博导，博士，主要研究方向为信号与信息处理、图像处理与模式识别等。