角点检测技术综述①

朱思聪,周德龙

(浙江工业大学 计算机科学与技术学院,杭州 310023)

角点检测是机器视觉和计算机视觉领域的基本课题.关于角点目前还没有精准的数学定义,通常将以下几种点称为角点:一是两条边缘以上的交点,二是图像上各个方向亮度变化足够大的点,三是边缘曲线上的曲率极大值点.角点有时也称为兴趣点和特征点,在简化图像信息数据的同时,还在一定程度上保留了图像较为重要的特征信息,从而方便了图像数据的处理.因此,角点检测在三维场景重建、运动估计、视觉跟踪[1]以及图像配准与图像匹配[2]等计算机视觉领域有着广泛的应用.

本文对现有的角点检测方法进行了分类及阐述,主要分为基于灰度强度的方法、基于边缘轮廓[3]的方法,并将其余类别的角点检测方法也进行了汇总.本文第3部分对现有的角点检测算法的测评技术也进行了汇总.除此之外,本文还搜集了一些最新的角点检测算法在工程中的实际应用案例以供参考.

1 角点检测算法现状分析

根据实现原理不同,现有的角点检测算法大致可以分为3类:基于灰度强度的方法,基于边缘轮廓的方法和基于二值图像的角点检测.其中针对二值图像的角点检测方法并不流行.因此,本节主要针对前两类方法详细阐述大部分典型角点检测算法的核心思想及部分关键的特征提取步骤.

1.1 基于灰度图像的角点检测

基于灰度图像强度的角点检测技术又可大致分为3类,分别是基于梯度、基于模板和基于模板梯度组合.其中基于梯度的方法是通过边缘曲率的计算数值大小来判断角点是否存在但是该方法对噪声十分敏感.另一种基于模板的角点检测方法考虑了像素邻域点的灰度值变化,将与邻近点灰度值差异明显的点定义为角点.相比于直接对灰度图像的像素进行处理,还有一类方法综合了灰度曲率以及模板策略进行角点检测.

1.1.1 Moravec角点检测技术

1977年,Moravec[4]提出了Moravec角点检测算子,其基本思想是通过在图像上移动一个二值矩形窗口来查找最小灰度值变化的最大值.这种方法的缺点是响应值非各向同性,对噪声和边缘敏感,对旋转不具备不变形.Moravec算子作为第一个被广泛使用的角点检测算法,开创了角点检测的新时代.

1.1.2 Harris角点检测技术及相关改进方法

受Moravec角点检测算法启发,Harris和Stephens[5]在1988年提出了著名的Harris角点检测算子,该方法首先计算Harris矩阵M(二阶矩矩阵或自相关矩阵),然后计算该矩阵的特征值 λ1,λ2,这两个特征值表征了Harris矩阵主曲率,再通过构建如下的Harris角点量测函数R来确定角点:

最后对R进行非极大值抑制,所得角点位置在局部梯度最大值处.Harris角点检测方法不仅对噪声不敏感、具有平移和旋转不变性、具有高重复性和高信息量,而且在不同光照条件下具有良好的稳定性,但是该方法不适用于对尺度变化要求高的场合.2014年,Qiao等人[6]提出了一种改进的 Harris亚像素角点检测算法,提高了控制点图像的定位精度针对Harris角点检测算法存在对含有噪声的图像角点检测不准确的问题,卢伟家[7]提出在Harris算法设置的局部移动窗口中加入一种加权系数自适应的加权均值滤波,该方法可有效减少伪角点的形成,同时具有良好精确度和检测速度.2017年,Wang等人[8]针对角点检测算法在提取角点时必须给出合适的阈值问题,提出了一种基于迭代阈值的自适应Harris角点检测算法.

1.1.3 基于SUSAN的角点检测技术

另外一种有名的角点检测算法是1997年Smith和Brady[9]提出的同值分割吸收核(SUSAN,Smallest Univalue Segment Assimilating Nucleus),该算法利用像素邻域的一个圆形模板,判断该点是否属于USAN区域,判别函数如下:

使用如下角点响应函数计算函数值:

如果该函数值大于某个阈值且为局部极大值,则认为该点是角点,其中统计圆形模板中和核心点有相似亮度值的像素个数n公式如下:

该算法具有速度快、定位精度高、高重复性、平移和旋转不变性.但许多特征位于边缘结构而不是真正的角点处,另外对噪声敏感和缺少信息量,且在处理模糊图像时性能较差.在经典SUSAN算法的基础上,He等人[10]采用角点预检测来消除伪角,减少计算量,从而提高算法速度.针对传统SUSAN算子只能在单一尺度下检测图像中角点的不足,王冠群等人[11]提出一种基于高斯变换的多尺度SUSAN角点检测方法.该方法利用高斯变换获得待检测图像的多尺度分层图像,以构建高斯金字塔,结合自适应阈值的SUSAN算子检测出不同尺度下的角点作为候选角点,将其还原到原始图像中的相应位置构成候选角点集,在候选角点集中经小邻域信息筛选获得最终角点,实验结果表明,该方法不仅能够在不同尺度下有效获取有用的角点信息,而且提高SUSAN算子正确率的同时,降低了角点的伪检率.

1.1.4 FAST角点检测技术

1998年Trajkovic和Hedley[12]提出了一种快速角点检测算子,其基本思想是研究在某点邻域内通过该点的任意一条直线上的灰度变化情况.首先计算出水平和垂直方向灰度变化值,然后构建一个角点度量函数来判断角点.2006年Rosten和Drummond[13]提出了高速角点检测算子,其基本思想是利用机器学习来加速角点检测过程.上述两种算法也都对图像尺度变化敏感.近年来,针对当前FAST角点检测算法只能检测单一类型的角点,并且单一阈值作用于整幅图像很难取得理想的效果等问题,Park等人[14]为了解决可穿戴设备的图像分辨率与系统功耗之间存在权衡这一问题,提出了一种新的快速角点检测方法,它在计算性能和可重复性方面优于以前的算法.

1.2 基于轮廓曲线的角点检测

相对于基于梯度和基于模板的检测器,基于轮廓的检测器在角点检测前先进行边缘轮廓检测[15],在轮廓上而不是整幅图像上检测角点,因此有着极低的错误检概率.该方法的角点测度被定义在轮廓上并且区分于轮廓上的光滑像素点.

1.2.1 基于Freeman链码的角点检测技术

二维线条图像可以用方向Freeman链码表示,这种检测方法先分割图像,然后提取图像边界的Freeman链码,将方向改变速率大的点标记为角点.Freeman链码是指相邻两像素连线的八种可能方向值,称为八方位链码.该方法计算步骤简洁,但是检测效果强依赖于图像分割的质量.并且由于需要计算夹角,对于噪声敏感,在进行检测时必须对图像进行去噪预处理.

2014年,曾接贤等人[16]提出了一种曲率尺度空间与链码方向统计相结合的角点检测方法.2017年,Rachmawati等人[17]提出了一种将高速角点检测与Freeman链码相结合的多边形逼近技术.该方法利用一组图像角点构造了一串有序线段的近似多边形,该近似多边形可以进一步用于形状表示和分析领域,作为数字图像的轮廓描述.2018年,刘相湖等人[18]提出了一种对Freeman链码分析的角点检测算法,该方法对Freeman链码发生变化时,通过分析其连续前后多个点的链码是否符合一定的规则来判定角点.

1.2.2 基于CSS的角点检测算法

Mokhtarian等人[19]提出了曲率尺度空间(Curvature-Scale-Space,CSS)的角点检测器,不同角度下的局部曲率被用于角点检测,角度下追踪角点并改善定位准确性.CSS角点检测算法对轮廓的局部变化和噪声高度敏感而且很难选择合适的高斯尺度平滑轮廓和角点阈值.Zhong等人[20]提出了直接曲率尺度空间(DCSS),方法是将平面曲线的曲率与高斯核直接转换而产生的CSS.他们从理论上分析了DCSS在平面曲线拐角检测中的应用.研究了孤立的单角和双角模型的尺度空间行为,定义了若干模型属性,使DCSS图像能够转化为树型组织,从而能够在多尺度意义上进行角点检测.2016年,李伟生等人[21]提出了一种基于曲率多尺度的自适应角点检测算法AMCP (Adaptive Multi-scale Curvature Polynomial),该算法结合了尺度多项式的方法,并构造局部曲率显著度LCCS (Local Corners Curvature Saliency),从而用自适应的阈值代替全局阈值,极大地增强了算法应对尺度,旋转等变化的鲁棒性.

1.2.3 利用弦到点的距离累加的角点检测算法

2008年,Awrangjeb等人[22]提出了利用弦到点的距离累加(CPDA)的角点检测算法,该方法在对图像中的角点进行定位的同时产生最小的定位误差,该算法有效的避免了CSS算法中存在的主要问题,却存在着以下问题:一是邻近角点被合并,二是钝形角点被误删除,三是无法有效剔除圆形角点.2014年,Jin等人[23]针对基于弦对点距离积累、定位精度低、检测时间复杂度高等缺点,采用先得到单尺度下的候选角点,保持相邻角点,然后计算了多尺度下候选角的特征值,有效地消除了伪角.2017年,Hossain等人[24]提出了一种基于CPDA改进的角点检测算法CADT.该方法的预处理和改进步骤与CPDA相似,但是有效的减少了定位误差和提高了平均重复性,降低了角点的伪检率.

1.2.4 基于角度(Angle)的角点检测算法

基于Angle的角点检测算法出根据边缘点与左右邻域内的其他点形成的夹角最小值来标志该边缘点,把Angle值固定在一定的范围之内,其值大小与角点的尖锐度成正比,可以有效避免了基于CSS,CPDA 的算法中存在的问题.但是还存在以下不足:不能检测出邻近角点,无法有效去除圆形角点、虚假角.2012年,Sadat等人[25]结合了角探测器CPDA和高曲率点探测器IPAN99,为不同的图像变换提供了鲁棒的角点位置.2017年,金亦挺等人[26]提出基于角度累加的角点检测算法,在获取图像边缘后定义反映边缘点特征的角度累加概念,并在“单弦”下计算边缘点角度累加值,以此作为角点初始响应,获取到候选角点;然后构造候选角点的局部自适应阈值来去除圆形角点,并通过实验来确定其支撑邻域范围和比例系数;再在“三弦”下获取角点特征值,构造全局阈值来去除伪角点;最后对曲线端点和T 交叉点进行检测,得到最终角点检测结果.

1.2.5 多尺度Gabor滤波器的角点检测

2004年,Gao等人[27]提出的基于Gabor小波的角点检测算子.多尺度Gabor滤波器的角点检测算法克服了在不同图像上的尺度选择问题.该算法首先对图像进行边缘轮廓的提取,进而用一组构建好的4个尺度8个方向Gabor滤波器的虚部对图像进行平滑处理,并计算每个像素在其相同尺度下各个方向上Gabor滤波器虚部响应的归一化的和.最后将每个边缘像素点在所有尺度下的乘积作为新的角点测度,当角点测度大于预设阈值时,则认定该点为角点.2014年,Zhang等人[28]研究提出了一种基于轮廓的角点检测器,该检测方法利用Gabor滤波器虚部在轮廓上的幅值响应.与传统的通过分析边缘轮廓形状和搜索平面曲线上的局部曲率极大值来检测角点的方法不同,该角点检测器结合了边缘轮廓的像素及其相应的灰度变化信息.2016年,田子怡等人[29]也提出了提出了一种基于边缘轮廓线的多尺度Gabor滤波器的角点检测算法.2017年,高华[30]提出了一个既利用到图像边缘轮廓信息又利用到图像灰度信息的基于Log-Gabor梯度方向一致性的角点检测算法,以提高角点检测器的检测性能.

1.3 其他的角点检测技术

此外许多研究人员也各自提出或改进了基于角点的检测算子.2008年,He和Yung[31]提出了一种使用自适应曲率阈值从初始列表中删除圆角的角点检测方法.刘文进等人[32]提出一种基于AP聚类角点提取优化的双边滤波(BF)角点检测改进算法.2015年,孔祥楠等人[33]

提出了一种基于各向异性高斯方向导数表示的角点检测器和分类器.该角点检测器融合了基于轮廓和灰度强度的检测思想,提出了一种像素处表示是定向角度的函数,从而表征了像素周围的局部方向灰度变化.2016年,Xing等人[34]基于局部区域的自适应阈值,提出了一种新的带填充环和外环的掩码来检测图像中的角点.该方法先利用内填充圆作为响应函数,对图像角领域、目标边缘以及平坦区域等非角区域进行滤波.然后利用复杂的响应函数,同时考虑内圈和外环的边缘,并采取相关算法检测位于薄带、噪声和突出像素上的虚假角点.2017年,Cho等人[35]提出了一种新的基于非角度测量的角点检测方法.该非角函数消除了位于平坦区域的像素并删除了沿任意方向沿边缘的像素.

各种角点技术综合性能总结以及优缺点在表1有详细的展示.

2 角点检测算法的测评技术

由于角点没有精准的定义,因此角点的确认是一个非常主观的二值化过程.一般由算法测评者根据实际应用需求自行给出,由此影响了测评结果的客观性.现有的测评技术主要依赖于理论分析,基于标定的参考角点,以及基于一致性判定,常用的主要为后两者 其中比较经典的基于标定的参考角点方法由2003年Rockett[36]提出.该方法通过一组具有参考角点的图像集,然后对图形进行不同算法的角点检测,利用ROC曲线对检测器的性能进行评价.

表1 各种角点技术综合性能总结

本文主要针对基于一致性[37]的判定的角点检测评价技术进行详细介绍.主要有两个指标:一是角点重复率,二是角点定位误差.该方法先是对给定图片进行角点的提取,角点数记为Nc.然后对图形进行如下操作:旋转变换,尺度变化,仿射变换,Jpeg压缩等.提取变化后的角点数量Nm,最后对两者进行匹配得到配对数Nr.其中,角点重复率函数如下:

角点定位误差函数如下:

为了避免数据展示的冗杂,本文选取了一定数量的图片,以及几种角点检测算法,对其性能进行了评测,大致展示了这几种算法的角点重复率及角点定位误差.实验数据部分采用了CPDA,He ＆Yung,CSS,FastCPDA等较为新颖的角点检测算法进行了测试.其中CPDA利用弦到点的距离累加;He ＆Yung使用自适应曲率阈值从初始列表中删除圆角;CSS利用了曲率尺度空间;FastCPDA是一种改进算法.具体结果如图1和图2所示.具体细节鉴于篇幅不再赘述.所展示的图片检测效果则是采取了几种常见的角点检测算子以供参考,如图3和图4所示.

图1 角点重复率示意图

图2 角点定位误差示意图

图3 角点较少图像的检测示例

图4 角点较多图像的检测示例

3 角点检测算法的实际应用

洪磊等人[38]针对Hessian算子在棋盘格角点检测过程中边缘局部区域角点检测失败的问题,提出一种恢复角点识别的修正算法.Lin等人[39]提出了两种新的三维网格数据角点检测算法,分别研究了在多尺度空间中曲面的几何性质以及利用简单三角形原理检测网格角点的方法.谢志峰等人[40]在深度神经网络的烟码智能识别方法中采用角点检测进行图像块的切割.Li等人[41]针对高光谱图像提出了极限约束空间谱角(ECSSC)的定义并设计了一种基于ECSSC和并行计算的图像级HSI分类框架.该算法能够从HIS角点特征中检测出丰富的角点特征,具有较高的重现性,基于ECSSC的图像级HSI检测精度明显高于现有的算法.Wang等人[42]针对传统角点检测在视频图像复杂场景中角点检测精度低、实时性差的问题,提出了一种基于ORB特征提取和群SAC算法的快速角点检测算法.该算法应用于光照变化、尺度变化、旋转变化、遮挡图像等复杂场景的视频图像中具有较高的精度和较低时间复杂度,具有较强的鲁棒性.刘妍等人[43]提出了一种基于SAR快速角点检测的SAR图像配准方法,该方法是一种自定义的基于加速段测试(FAST)特征的SAR图像配准方法.该方法表明了快速合成孔径雷达能够检测出足够数量的角点,具有较高的重复性和稳定性,在应用于图像配准时也能得到较好的配准结果.

4 结论与展望

本文对现有的角点检测技术进行了分类和归纳,详细阐述典型角点检测算法的关键步骤,表1对基本的角点检测算法进行了归纳和总结.本文也对近几年来各类角点检测算法发展与改进提出了一点建议.

总的来说,角点检测算法的研究改进工作主要有以下几个方面:(1)根据实际工程的需求出发,角点检测技术的一些指标如快速性、准确性、鲁棒性等有着不同的定量指标,所以选取的角点检测算法需要从业人员进行全局的分析.(2)从算法角度来看,直接基于灰度图像强度的角点检测基本上是全局搜索,可以进行局部搜索优化算法;基于边缘轮廓的角点检测一般采用了多分辨分析并行处理,从灰度图像得到边缘轮廓曲线要经过两次以上的全局搜索,计算复杂度高,对此进行算法复杂度的优化,可以提高检测的检测度.(3)角点检测测评技术的研究亟待完善,现在还没有公认的大规模关于角点检测的数据集,而且角点测评技术的维度也十分有限.后续研究者可以在这两方面着力研究.

除此之外,本文还搜集了一些最新的角点检测算法在工程中的实际应用案例.角点检测在三维场景重建、运动估计、视觉跟踪、机器人定位、视觉跟踪、图像全景拼接以及图像配准与匹配等领域有着广泛的应用前景.角点检测技术仍在发展,本文罗列的一些较新的方法及经典方法的改进策略,意在期望更多研究人员推动这一课题更快发展.文章中必然存在的一些不当的问题,我们欢迎对这些观点进行批判和纠正.