基于模板匹配的快速角点检测方法

程希希,张艳玲,田军委

(西安工业大学 a.电子信息工程学院; b.机电工程学院,西安 710021)

0 概述

角点检测[1]是计算机视觉领域中用于提取图像特征的一种重要方法。目前角点仍未有严格的数学定义,一般可认为是某属性上表现突出的点,如二维图像亮度变化强度大的点、多条边缘曲线交汇点或曲线曲率局部极大值点。针对不同的应用场景,也可以对“角点”自行定义,如定义为 “特征点”或“兴趣点”等。角点能够有效保留图像重要特征,剔除冗余信息,提升信息处理速度。这使得角点检测在3D视觉重建、运动目标识别和图像匹配[2]上都得到了很好的应用。

棋盘标定板由于制作简单而被广泛用于标定研究中。角点类型主要有4种,分别是L型[3]、T型、Y型和X型。在已发表的文献中,自动棋盘格角点检测主要分为两类,其中一类是基于灰度强度[4]分布,用角点附近的灰度来判断它是否为棋盘格角点。最初的角点检测算法如Harris[5]和SUSAN算法[6],不能从检测的角点中精确区分棋盘格角点,其后针对这一问题,大量的改进算法被提出。文献[7]改进了SUSAN算法,以小邻域环形模板灰度的跳变次数为依据来判断角点类型。文献[8]则是利用了角点的灰度对称性以及交替性来提取角点。文献[9]结合了文献[7]中的小邻域环形模板和文献[8]中的灰度对称性特点来定位角点。文献[10]利用X角点的方向特性进行亚像素检测定位。文献[11]根据角点周围图像出现强烈的鞍形,通过直线拟合边缘定位鞍点从而获取角点位置。文献[12]利用棋盘纹理和几何特征从Harris候选角点中提取角点。文献[13]提出了基于生长的角点检测算法,该算法会绕开图像遮盖的干扰,以生长出最大的棋盘。另一类算法则是利用边缘或线来进行角点检测。文献[14]在边缘轮廓的基础上,构建多尺度相关矩阵并以不同尺度下的归一化特征值乘积检测角点,文献[15]也采用了相关矩阵。文献[16]利用边缘像素及其左右支撑区域的微分模式之间的相似性来构建角点测度以度量角点。但基于边缘轮廓的角点检测如文献[16]对棋盘格角点的检测仍存在很大的局限,因此,本文在文献[13]的基础上改进该算法以获得更高精度的角点检测结果,并与文献[12]的算法进行对比实验。

本文根据棋盘格角点的构成类型将其分为两种主要类型,即矩形黑白块和三角黑白块环接而成的角点。构建这两种类型的角点模型,并根据卷积原理得到与角点相似度最大的点。通过阈值处理[17]过滤因噪声影响以及复杂环境的干扰而出现的大量非角点,运用非极大值抑制的方法剔除角点附近的伪角点,并利用角点的梯度特性对角点进行亚像素定位。

1 本文算法

1.1 基于模板匹配的角点检测

不同于基于梯度或边缘的方法,基于模板匹配的角点检测方法是直接针对于像素的灰度值[18](像素强度)的。这种方法的一般操作过程是先建立一个模板mask,通过模板来操作或比较图像局部的像素,从而判断其是否为角点。本文方法即基于该思想进行角点检测。

本文方法的信号处理流程如图1所示,主要由角点原型模板的创建、阈值处理、基于方向梯度统计的亚像素定位3个部分组成。

图1 基于模板匹配的角点检测流程

根据角点的不同特征,本文利用棋盘角点位于局部灰度区域交界点处的特点,且灰度区域呈现明显的对称性来检测棋盘内圈角点以及剔除棋盘外圈角点。

1.2 模板构建

笔者对X角点直观分析发现图像在进行测度变换后主要呈现两种不同的模型[13],一种角点与坐标轴平行,另一种角点与坐标轴的夹角为45°,如图2所示。

图2 两种角点原型

根据角点模型定义的上述两种角点原型,对于由透视变换引起的较大范围变形的角点检测而言满足要求。本文将构建的角点子图像遍历棋盘格图像,得到各像素点的响应值。将响应值的大小作为角点相似度的依据,对响应值进行进一步的处理逐步确定角点位置,最终实现角点检测。

每种角点原型均由4个滤波核组成,以顺时针方向将模板分为{A,D,B,C}4个部分。滤波核用于后面与图像进行卷积操作,本文的重点就是运用这两种角点原型计算出每个像素与角点的角点相似度,而像素处的角点相似度C是由所有原型以及fippings组合的最大值来定义的。

(1)

(2)

(3)

(4)

(5)

图3 两种flippings

本文方法选定3个模板尺度以满足图像中不同于棋盘尺度的需求,模板角度分别与坐标轴平行和与坐标轴呈现45°夹角。具体模板示例如图4所示。

图4 模板示例图

根据图像卷积原理,当卷积核选择与图像中越相似的部分卷积后,得到的响应值越高,反之越低。当图像受到光照和畸变,4个卷积核的任何一个响应值较小时,角点相似度C变小,由此可以有效区分伪角点和角点。

1.3 阈值处理

通过原图像与角点原型卷积已初步获取角点位置。由于图像含有大量的噪声,仍有大量的伪角点被检测出来。因此,需要对该方法进行进一步的优化。此处将采用阈值处理,具体如下:

(6)

其中,g为选定阈值。拟角点与伪角点之间的差值较大,通过大量实验经验可知,将g的值设定为角点相似度C的一半,即当g=0.5×C时伪角点的剔除效果较好。

通过阈值化后可得到较为清晰的角点相似度图。然而阈值化的结果只能够去除偏值较大的非角点(角点附近仍有大量C值接近的点),如图5所示。

图5 阈值化前后的角点图

为了后续的亚像素定位,需要进一步逼近角点精确的位置以便利后续的角点方向精细化。在此方法中,首先利用非极大值抑制来获得最终的角点位置。由于经过非极大值抑制后的角点位置为像素级的,因此后面的工作主要是对角点位置以及边缘方形进行方向精细化处理。

1.4 亚像素定位及方向精细化

通过上述处理检测到的棋盘角点为非亚像素角点,但是在进行摄像机标定时必须将角点位置精确到亚像素级。对棋盘角点图像分析可知,X角是相邻黑白区域块交界的临界点,黑白区域块的灰度差异较大。角点的方向分析将角点的定位问题转化为方向交点的问题,且能够较为准确地将角点定位到亚像素精度。

在理想情况下,像素点q是角点p局部邻域上的一点,fq为像素点q的图像梯度向量。

1)当像素点q位于平坦区域时,有:

(7)

2)当像素点q位于边界上时,同样有:

(8)

这是因为,当像素点位于平坦区域时,像素的变化为0,梯度向量即为0。而当像素点位于边界上时,像素点梯度向量方向与(q-p)方向相互垂直,因此,可以利用像素点的方向信息对角点进行亚像素定位以及方向的精细化。

以上为理想状态,但实际情况中,由于噪声、曝光、畸变等影响,会造成梯度方向不理想,边缘不够锐利。结合实际情况,本文中角点p位置要求在角点候选集p′的邻域N(p′)内满足下式:

(9)

其中,N表示一个11×11的领域且相邻像素是由梯度大小自动加权的。对式(9)右侧中p′进行求导并令其等于0,得到解析解:

(10)

本文通过寻求对应梯度方向向量上的最小误差来实现改进边缘方向向量e1和e2的准确性:

(11)

(12)

其中,Mi为临近像素的集合,并与模式i的梯度mi=[cos(ai)sin(ai)]T相对齐。进行亚像素定位后的角点图如图6所示。

图6 亚像素定位后的角点图

2 实验结果与分析

2.1 精度和实时性实验

为了验证本文算法的精度和实时性,使用Matlab软件分别与Harris角点检测算法、SUSAN角点检测算法以及文献[12]算法进行对比实验,结果如图7所示。

图7 4种算法检测出的角点图对比

由图7可以看出,不同角点检测算法都能识别角点,但是本文提出的算法在误检率上有着明显的优势。为了进一步对比4种算法在角点检测正确率以及实时性方面的不同,现取3张棋盘图进行检测,棋盘规格分别为9×6、8×6、8×8,格子尺寸为29 mm×29 mm,如图8所示。

图8 测试棋盘格

分别用SUSAN角点检测算法、Harris角点检测算法、文献[12]算法以及本文算法对图8进行角点检测。角点检测个数对比,角点检测正确率对比以及角点检测时间对比分别如表1～表3所示。

表1 角点检测个数对比

表2 角点检测正确率对比

表3 角点检测时间对比

由以上对比可以直观地判断出本文算法能够有效检测出角点,而常规角点检测算法存在误检、重检问题。这是因为高斯卷积的圆角效应[11],使用Harris角点检测算法会在理想角点附近检测出多余的伪角点[19]。而对于SUSAN角点检测算法,它是基于图像的灰度信息提出的低层次[20]图像处理算法,由于该算法无需边缘检测,也无需梯度计算,因此具有较高的效率和较强的抗干扰能力。但是SUSAN算法不能有效区分棋盘内角点和边缘点,导致伪角点的数量大增。文献[12]的角点检测算法结合棋盘格的灰度分布和边缘信息来消除假角,其性能要优于传统的角点检测算法,但当棋盘背景较为复杂时或角点附近的区域块较大时,将造成误检。另外其得到的角点信息为像素级,不能够用于高要求的摄像机标定等工作。因此,本文算法对比上述的角点检测算法都表现出较大的优势。

2.2 适应性实验

实验1光源对角点检测的影响

光源对图像的质量有着极大的影响,不适合的光源将大幅降低图像的质量。例如,阴影会使边缘模糊造成误检,不均匀的光照造成阈值选择困难。选择一组图片,棋盘规格为7×6。在采集照片时,尽可能使得标定板充盈到整个平面,保持每一组图像在采集过程中间距不变,变化的只是光源强度。采集20组图像进行实验,光照值分别为274 Lux和68 Lux,随机抽取一组实验结果进行展示,如图9所示。可以看出,光线强度不同的情况下,本文算法仍能准确定位角点。

图9 光源对角点检测的影响

实验2畸变图像(鱼眼图像)角点检测

传统的棋盘格角点检测方法难以准确提取鱼眼图像边缘处的角点,造成相机标定精度低,为此,本文进行下鱼眼镜头大畸变成像的棋盘格角点检测。同样采集20幅图像进行实验,随机抽取一组实验结果进行展示,如图10所示。实验结果表明,对于鱼眼棋盘图像,棋盘格虽然受到镜头的畸变,但是不同尺度的模版能弥补角点对角线棋盘格尺度不对称现象,从而正确识别角点。

图10 鱼眼图像及检测结果

鱼眼畸变图采用的棋盘规格为6×9,而检测结果漏检0个角点,误检0个角点。以上是由于摄像头畸变造成的图像畸变,现选取非镜头畸变造成的图像畸变,而是由黑白交替的正方形以及不同大小的菱形构成的图像。选取20幅此类型的棋盘图进行实验,随机选取一组显示结果,如图11所示。由图中检测结果可知,本文算法对于非鱼眼镜头的畸变棋盘图像仍然有效。

图11 畸变图像的角点检测

由以上对比图可以直观地判断出本文算法能够有效检测出角点,当棋盘图像受到不同光照,鱼眼镜头下的枕、桶形畸变以及不规则畸变图像的影响时,角点的构成方式并没有改变。不同尺度和角度的模板保障了每一个角点都能够被检测出,而改进的梯度方向统计策略以及非极大值抑制能有效排除冗余信息,达到最终的亚像素角点定位目标。本文算法在不同适应性实验中均表现出较大的优势。

3 结束语

本文提出一种基于模板匹配的快速角点检测方法。通过创建两种角点原型滤波核并与图像进行卷积,得到角点相似度,以此剔除响应值较小的伪角点。在此基础上,进行非极大值抑制,利用角点的方向特性提取角点并实现亚像素定位。实验结果表明,相较于传统的角点检测方法,该方法能够得到更好的检测结果,在畸变影响下也能够准确检测出角点。由于本文方法对过曝光的图像存在一定的漏检率,因此下一步将改进该算法,使其在棋盘图像处于不同光照环境时都能够准确提取角点。