角点检测算法综述

角点检测算法综述范娜，俞利，徐伯夏（中国航天科工集团第三研究院8357所天津300308）摘要：角点作为图像的一个重要特征，它保留了图像绝大部分的特征信息。角点在三维场景重建、运动估计、目标跟踪以及图像配准与图像匹配等计算机视觉领域有着重要的作用。本文对角点检测算法的类别进行总结，对各类算法进行了详细介绍，并对近几年来各类算法发展与改进进行了总结。关键词：特征信息；计算机视觉；角点检测SurveyofCornerDetectionAlgorithmsFANNa,YULi,andXUBo-xia(The8357ResearchInstituteoftheThirdResearchAcademyofCASICTianjin300308)Abstract：Asamoreimportantfeatureofimage,cornercontainsvoluminousinformationofimagefeatures.Inthedomainofcomputervision,suchasthree-dimensionalreconstruction,motionestimation,objecttracking,imageregistrationandimagematching,cornerofimageplayanimportantrole.thispaperattempttosummarizeanddetailedlyintroducecornerdetectionalgorithms,andsummarizethedevelopmentsofthesealgorithmsinrecentyears.Keywords:FeatureInformation；ComputerVision；CornerDetection1引言角点并没有明确的定义，一般将图像中亮度变化剧烈的点或图像边缘上曲率取极大值的点认为是角点。从形态上来说，角点包括L、T、Y、X和箭头型角点等。角点作为图像的重要特征，保留了图像的绝大部分的特征信息，又有效地减少了信息的数据量，从而有效地提高了运算速度以及匹配的可靠性。总结现有的角点检测算子的评价方法，总体上有以下几个标准[1]：(1)稳定性：即同一场景图像在亮度、对比度等因素变化的情况下，检测出的角点数目及位置应当稳定(2)可靠性：即在算子的可变参数改变情况下，不影响生成的角点的质量，只改变检测出角点的数目；检测到的角点具有平移、旋转、伸缩不变性(3)鲁棒性：即算法的抗噪性能，在一定的噪声干扰下，算子仍然具有很强的角点检测能力(4)准确性：主要指不发生误检测以及角点位置定位准确(5)高效性：是指算法的计算速度快慢，算法速度必须足够快以满足图像处理系统的要求经过几十年的研究与探索，产生了许多检测角点的方法，但大致可以分为四类：基于灰度图像的角点检测算法、基于二值图像的角点检测算法、基于边缘特征的角点检测算法以及支持矢量机角点检测算法。本文中对上述四类方法进行了阐述，并详细的介绍了这四类方法中典型的具有代表性的角点检测算法。2角点检测算法研究现状2.1基于灰度图像的角点检测2.1.1Harris角点检测算法Harris角点检测算法是C.Harris和M.J.Stephens于1988年提出的一种基于信号特征提取算子，它是对Moravec角点检测算法的改进。Harris算子利用角点与自相关函数的曲率特性有关这一特点，定义自相关函数，自相关函数描述了局部图像灰度的变化程度，可表示为：2,,(,)(,)(,)uvuvExywfxuyvfuv利用泰勒公式将上式展开，化简上式可得：,u,2,2,(,)[](,)(,)uvvTuvuvEXYwuXvYXXYwuvuvXYY其中,uvw为高斯窗口在(,)uv处的系数，fXx，fYx，X、Y是一阶方向微分，反映了图像中每个像素点的灰度变化方向。定义M为像素点(,)xy的自相关矩阵，则22XXYMXYY，为了避免矩阵M进行特征值分解，方便运算，则将角点响应函数表示为：2(,)det(,)(,)RxyMxyktrMxy其中1、2为矩阵M的特征值，k为经验值，一般在0.04-0.06之间取值。只要在某一点(,)xy处，(,)Rxy超过某一设定的阈值，即认为该点为角点。阈值的设置是Harris角点检测算法的关键，阈值设置过大会产生伪角点，阈值过小则会漏掉角点。文献[2]中首先应用一定规则进行备选角点预筛选，然后对提取到的备选角点进行Harris角点检测。Harris算法中的阈值利用自适应的方法得到，即将每一幅图像角点响应函数最大值的p倍定义为阈值。文献[3]在进行非极大值抑制时采用双阈值法检测角点，消除了一些伪角点；最后利用SUSAN算法的思想消除剩余的伪角点。文献[4]用Harris算法求得角点响应函数，利用双掩膜来定义进行非极大值抑制的局部范围，然后结合K均值聚类方法进行非极大值抑制，最终通过像素点的角点响应函数是否满足预设角点判定条件来确定角点。2.1.2SUSAN角点检测算法SUSAN角点检测算法是1997年由英国牛津大学的S.M.Smith和J.M.Brady提出的一种低层次图像处理小核值相似区的方法。该方法的原理是定义一个圆形模板对图像中的像素进行覆盖，将圆形模板的中心像素（定义其为‘核’）与同一模板中的其他像素分别进行灰度值的比较，当灰度值之差少于某一设定阈值t时，认为该像素与核具有相同或相似的灰度值并把由这些像素组成的区域定义为核值相似区(UnivalueSegmentAssimilatingNucleus，USAN)。当圆形模板处于图像背景或图像内部时，USAN区域的面积最大；当模板开始与图像边缘重叠时，USAN区域的面积变小，当模板的中心像素位于角点处时，USAN区域面积达到最小。文献[5]中用在响应圆域内与核像素点灰度值相同，且与核像素点邻接连通的区域来代替SUSAN核同值吸收区，避免了传统SUSAN方法中漏检和误检的问题。文献[6]中首先将图像的像素点分为边缘点、内部点和背景点，在此基础上对边缘点进行SUSAN算法处理，然后检查提取到的角点，分别对真角点附近的伪角点以及边缘轮廓上的伪角点采用不同的方法进行去除。2.1.3基于模板匹配的角点检测算法基于模板匹配的角点检测算法利用一个nn的二维矩阵作为角点检测的模板，分析常见角点的类型，根据角点的类型对模板内的各像素进行编码；然后利用模板与待测图像作相关匹配，让模板在待测图像中逐点移动，在每一点处，计算角点响应函数，角点响应函数值越大说明相似性越高，则该检测图像与该模板越相似。基于模板匹配的角点检测方法中模板的半径越大，能够检测到的角点类型越多，但同时计算量也大大增加。针对上述特点，文献[7]中扩大模板半径，同时对算法进行改进，简化模板，在增加可检角点类型的同时也提高了计算速度。2.2基于二值图像的角点检测二值图像角点检测的形态骨架法[8]是刘文予等人提出的一种基于二值图像和形态骨架的角点检测方法，该方法中将二值图像看成是一个多边形，则多边形的角点一定在骨架的延长线上，并且角点所对应的骨架点的最大圆盘应该趋于0，检测骨架点中最大圆盘为0的点，即为角点。同时为了获得凹角点，对原图像求补，为了克服原图与补图的边界不一致问题，对补图做一次膨胀运算；最后利用文献中提出的算子求出凹角点。将原图和补图获得的角点进行异或操作，得到全部角点。二值图像处于灰度和边缘轮廓图像的中间步骤，所以专门针对此类图像的角点检测方法并不多见。2.3基于边缘特征的角点检测方法2.3.1基于边缘链码的角点检测基于边缘链码的角点检测算法是在20世纪七十年代末FreemanH等人提出的，是最早的基于边缘的角点检测算法。该算法是沿着数字曲线或边界像素以8或4邻接的方式移动，对每一个移动方向进行数字编码；然后根据相邻码值之间的差别确定角点和可疑角点。对于可疑角点，通过曲率大小进一步判断是否为真正的角点。20世纪九十年代，Bribiesca对Freeman链码进行了两次改进：用小直线段的斜率对其进行编码以及顶点链码的方式。顶点链码中的每个码的码值表示该码元有几个顶点是区域边界的顶点。基于边界链码的角点检测方法主要包括图像预分割、对预分割后得到的图像的边界轮廓进行顺序编码和根据边缘轮廓链码对图像中的角点进行提取三个步骤[9]。2.3.2基于小波变换的角点检测基于小波变换的角点检测方法的思想是：首先用边缘检测算子提取目标边缘，选取具有极大值检测能力的小波，在多个尺度下进行小波变换，求取小波系数的模极大值点得到角点的候选点集；然后使用一定的筛选规则，选出正确的角点集。文献[10]基于协方差矩阵和小波变换来提取角点，该方法中利用协方差矩阵来构建方向角函数；然后对该方向角函数在不同尺度下进行小波变换，最终根据小波变换的响应值确定角点。2.3.3基于曲率尺度空间的角点检测在Witkin和Koenderink提出的尺度空间的图像分析理论的基础上，Mokhtarian及Suomela提出了基于曲率尺度空间（CurvatureScaleSpace，CSS）的角点检测算法。该算法首先使用canny算子在原图像中检测边缘，计算不同尺度下边缘曲线的曲率值；然后将高尺度下的局部曲率极值点作为候选角点，最后逐步减小尺度，在多个低尺度处跟踪定位角点。文献[11]提出了一种以CSS角点检测为基础，在较小的尺度检测出所有的局部极值点的方法，并根据曲率的局部性质构造自适应阈值，先获得候选角点；然后计算出候选角点的角度，根据角度大小来决定真伪角点并去除伪角点。基于CSS算法的角点检测精度依赖于尺度选择的好坏，以及自适应阈值的CSS算法在小尺度下阈值和夹角的计算受离散数据引起的噪声的影响，文献[12]提出一种基于多尺度曲率乘积的角点检测算法（MSCP），该算法的思想是利用canny算子提取边缘轮廓；然后计算多个尺度下的曲率乘积，以此来增强角点曲率，抑制噪声曲率；最后通过一个全局阈值来提取角点。文献[13]提出一种基于多尺度曲率多项式的角点检测方法，该方法的基本思想是首先获得不同尺度下轮廓上各点的曲率值，然后针对不同尺度下局部极大值点计算曲率的加权和；对于非极值点计算曲率积，最终利用多尺度曲率积和多尺度曲率和与设定的判定凹凸角点的阈值进行比较来获取角点。2.4基于支持向量机角点检测算法在Vapnik等人提出的支持向量机机器学习方法的基础上，夏辉[14]等人提出一种基于支持向量机的角点检测算法来检测标定模板中模式固定的角点。该算法在确定角点和非角点数目后，分别以他们为中心选取77的邻域，，将邻域内所有像素点的灰度值构成一个49维的灰度向量来反应角点和非角点灰度值的区域分布特征；规定角点为正类，非角点为负类，用y1,1i来表示；将训练集表示为11((,),...,(,))nnSxyxy，在训练集S中随机选取角点和非角点训练支持向量机，并利用核函数来解决非线性不可分问题；最后利用训练好的支持向量机进行角点检测。文献[15]中首先利用Harris角点检测算法对两幅以上的无噪声图像提取角点，然后将提取的角点作为支持向量机的训练样本，构造支持向量机；最后利用训练好的支持向量机实现角点检测。3展望就角点提取算法的发展状况而言，要构造出高精度的角点检测算法，还有很大的发展空间，进一步的研究方向可以归纳如下：（1）构造更有效的角点检测方法，根据角点特征合理的选择角点提取算法，以克服高精度与算法复杂性之间的矛盾。（2）合理选择角点判断准则以及进行算法改进，以解决稳定性、可靠性、鲁棒性、准确性、高效性以及角点类型多样化等问题。（3）综合利用各学科中的优秀算法应用于角点提取方法当中，以实现角点检测的高效以及高精度化。4总结本文对现有的角点检测算法进行了分类介绍，并对近年来对各算法的改进进行了概述。对各算法进行详细分析，根据角点提取算法的发展状况提出角点检测算法以后可能的研究方向。角点作为图像的一个重要特征在三维场景重建、运动估计