基于圆环模板和标志矩阵的角点检测算法

王建卫

(东北林业大学 机电工程学院，黑龙江 哈尔滨 150040)

0 引 言

随着计算机技术的发展，使计算机具有视觉功能进一步得到广泛关注和研究，视觉系统已经成为计算机系统不可或缺的一个重要组成部分，建立通用的计算机视觉系统完成视觉任务一直是计算机视觉领域、图像处理领域的重要研究内容。一般地，视觉任务是以任务初期获取的原始图像的理解为目的，围绕着图像理解的一系列研究也纳入到了计算机研究工作者的视野中。通常，图像理解的关键是通过分割图像获得目标和背景，边缘检测往往是实现目标和背景分割的首选方法。在边缘检测中，存在着边缘点和边缘段同时检出的问题，角点是边缘段的方向属性改变时所标注的特殊的边缘点。角点作为灰度图像稳定的局部特征，包含了图像中的重要结构信息[1]。自从1977年Moravec算法提出以来，研究者们开始研究图像的角点检测理论和方法[2-4]。由于角点检测结果在计算机视觉理论的应用领域都具有重要的作用[5-7]，因此，角点检测理论始终是计算机视觉理论、图像处理领域的研究热点之一。

由于角点检测理论的复杂性，角点很难给出明确的定义，目前将角点描述为二维图像亮度变化剧烈的点，或边缘曲线的曲率局部极大值点或多条边缘曲线的交汇点[8-10]。角点检测算法可分为三类：基于灰度强度的方法、基于边缘轮廓的方法和基于角点模型的方法[11-14]。其中第一种方法可直接在灰度图像上进行，角点为在像素点的周围邻域内有足够多的像素点与该点处于不同的区域。角点是图像各向异性的局部特征[15]，图像像素的局部灰度变化和结构信息的有效提取和描述是基于灰度强度算法的关键，常用的检测方法有Moravec[16]、Harris[17-18]、SUSAN[19]和FAST[20-21]等。Moravec算法在检测出角点的同时，边缘点也会检测出。Harris在平滑后的灰度图像逐一检测像素点是否为角点，检测过程较复杂[17]。SUSAN算子检测出边缘点也是不可避免的[19]。FAST算子是在SUSAN算法的基础上利用机器学习方法提出的，对半径为3的圆周上的像素点进行判决，根据设置的阈值提取角点，关键在于阈值的选取[20-21]。为解决角点检测中边缘点和边缘段同时检出问题，文中提出一种基于圆环模板和角点标志矩阵表示的角点检测算法。

1 FAST角点检测算法的原理

FAST角点检测算法的原理是检测灰度图像的Bresenham圆模板区域中，有足够多的像素点的灰度值大于该点的灰度值或者小于该点的灰度值，关键在于设定的阈值和圆形检测模板的设计[20-21]。

FAST角点检测算法步骤如下：

步骤1：输入灰度图像I，设定阈值t；

步骤2：将图像的左上角的第一个像素点设置为候选角点p，该像素点的亮度值为I(p)；

步骤3：以p为圆心检测如图1所示的Bresenham圆周上的16个像素点x。若有n(n=7,8,9,12)个像素点的像素值小于I(p)+t或者有连续的n个像素I(p)-t，那么该点为角点；

图1 Bresenham圆周上的16个像素点

步骤4：检测图像中p后续的所有像素点。

该算法先检测p点周围的1，5，9，12四个点中是否有三个点超过I(p)+t，如果有，则直接跳过该像素点；如果没有，则继续使用前面的算法，全部判断16个点中是否有12个满足条件。

由于圆周上至少有12个连续点的灰度值与中心点像素有差值变化，12个连续点必然包括圆周上的1、5、9、13这4个位置的像素中的3个，所以先检测位置1和位置9，若它们与中心点像素的灰度差值在规定的阈值范围内，再检测位置5和位置13。若上述4个像素点中至少有3个大于或小于阈值，则保留像素点p，否则选取其他的中心像素点进行检测[21]。图像上的像素点经过初步检测后，符合条件的将成为候选角点。分析FAST算法中16个像素点与检测点所处的位置，可知其实质为半径为3的圆形模板圆周上的像素点，可以考虑将圆形模板扩展为通用模板，如圆形的半径为1，2，4等。当半径为1时，检测点的圆形模板退化为该像素的8邻域。

文中应用半径为4的外圆和半径为2的内圆的圆环模板作为候选角点确立的模板，该模板的28个像素点如图2所示。

图2 28个像素点组成的圆环模板

2 基于圆环模板和角点标志矩阵表示的角点检测算法的设计

2.1 算法原理

文中算法的原理是先设置较小的阈值，通过简单的筛选得到角点的与灰度图像同型的标志矩阵，根据角点在矩阵中所处的行列位置逐步删除孤立的角点、边缘段上的角点。算法的关键在于孤立的角点、边缘段上的角点类型的判断。

算法步骤为：应用圆环模板提取候选角点；记录角点在原图像中的位置，建立与原图像同型的角点标志矩阵；将矩阵按照四叉树结构分解，并删除孤立的角点；删除边缘段上的角点。

2.2 算法步骤

根据上述算法原理，corner_detection算法过程如下：

cor=corner_detection(I)

输入：灰度图像I；

输出：角点集合cor。

步骤1：读入灰度图像I。

步骤2：设置阈值t，选择模板类型(下面以圆环型模板为例设计算法)。

步骤3：以模板结构将图像的边界进行扩充，以免将边界上的角点漏选。文中将边界上像素值设置为0，使对角点的选取结果无影响。

步骤4：根据模板类型和阈值提取较多的灰度图像I的亮度变化点作为角点，建立角点集合cor。

应用图2的圆环模板检测I的像素点，外圆环的像素点数为n1=20，内圆环的像素点数为n2=8，I的候选角点集合cor元素p的响应函数为：

当f1(x)∈{9,10,11,12,13,14,15}且f2(x)∈{4,5,6}时，p∈cor。

步骤5：记录角点在原图像中的位置，并将原图像的对应像素值设置为1，其他像素设置为0，建立角点标志矩阵M。

将角点标志矩阵按照四叉树结构进行分解，即分成N×N(N=2n)的子矩阵Mi，一般地N=32,64,128,256。考虑到图像子块的相关性，文中以N=128为例进行后续步骤。

在传统的小学语文教学中，大多教师局限于“书本”二字，使学生的视野被限制于语文教材当中，学生只能通过课堂教学获取一定的信息和资源。再加上语文教材更新的周期长，许多深受学生喜爱的、紧跟时代发展的童话被排斥在语文教材之外，导致教材中的童话对学生逐渐丧失了吸引力。因此，为充分发挥童话的审美功能，教师应当适当拓展教学内容，通过课下进行互联网阅读、构建图书角、组织阅读课的形式，适时拓展一些课外童话读物，增加学生的阅读容量，进而开阔学生的视野，充分发挥童话的审美功能，让学生在学习过程中逐渐提高童话鉴赏能力。

下面逐一分析各角点标志子矩阵Mi(128×128)。分析角点标志矩阵，将孤立的1设置为0，即删除该角点。

步骤7：分析角点标志矩阵，通过距离计算分析将孤立的1设置为0，即删除该角点。

设Mi(h,w)为Mi的h行w列的元素1，若该元素与该子块中其他元素1的D4距离(行坐标之差的绝对值和列坐标之差的绝对值之和)的最小值大于3，则该角点为孤立角点，删除该角点。

步骤8：删除水平和垂直边缘段上的连续角点。

对各个子矩阵Mi按照行的方式进行行程编码，保留连续1序列的第一个1，后续的置为0，结果矩阵为MRi。删除策略为同一行的各矩阵元素为128个由0或1组成的随机序列，保留连续的1序列中的第一个1，其他的删除。

例：设数据data为X=[0 1 0 0 0 1 1 1 1 0 1 0]，编码rle为两个长度相同的行向量：

data=[0 1 0 1 0 1 0]

rle=[1 1 3 4 1 1 1]

其中，结合data，分析3的含义是3个0,4的含义是4个1，处理后的X为：

X=[0 1 0 0 0 1 0 0 0 0 1 0]

同理，得到按列的方式处理的结果子矩阵MCi。

步骤9：依次读取MRi和MCi的元素，若同行同列的元素为1，则置M的相应元素为1，否则为0。

步骤10：记录矩阵M中矩阵元素为1的行号和列号，在图像I中将该行列的像素点标记为角点。

3 实验结果与分析

为验证该算法在计算机视觉系统中的通用性，在Windows7系统MATLAB 2016环境下编程实现上述算法，并选取了具有不同性质目标的、目标数目不同的以建筑物和树叶目标为主的两类图像做了分析和比较。

例1采用以建筑物为主的scene_categories的灰度图像image_0001.jpg作为测试图像[12]，原图像为256×256的灰度图像，分别采用Moravec算法、SUSAN算法、Harris算法、FAST算法和文中算法进行了角点检测。

为了更好地进行比较，该例中采用的是固定阈值。角点检测结果如图3所示，角点检测数据如表1所示。

表1 image_0001.jpg角点检测数据

由表1的数据可知，Moravec算法得到的角点数目较少，且定位不够准确；SUSAN算法在角点集中的区域有角点聚集的现象，算法的执行时间也较长；Harris算法得到的角点数目较少，有漏检现象，算法的执行时间也较长；FAST算法得到的角点数目较多，有聚集的现象，算法的执行时间较短；文中算法检测出的角点具有相应次数较低、无重复的优点，较好地达到了精确检测角点的目的，其中外环的参数为15，内环的参数为6，执行时间与Moravec算法和Harris算法接近。

例2采用对比度较低的以树叶目标为主、背景较复杂的灰度图像image_leaf.jpg作为测试图像[12]，原图像为256×256的灰度图像。角点检测结果如图4所示。

图3 图像image_0001.jpg的角点检测结果

图4 图像image_leaf.jpg的角点检测结果

由图4可知，Moravec算法的角点定位不够准确；SUSAN算法在角点集中的区域有角点聚集的现象；Harris算法有漏检的现象；FAST算法与Harris算法类似，角点数目较少，有漏检的现象；文中算法适用于背景部分的角点检测，其中外环的参数为10，内环的参数为5，候选角点数为1 820，经过筛选后得到的角点数为920，执行时间与Moravec算法接近。

上述实验结果表明，与Moravec、SUSAN、Harris与FAST等算法相比较，文中算法通过二次筛选保证了提取的角点数目，在一定程度上解决了角点数目过少或过多导致角点聚集的问题。

4 结束语

文中以角点检测算法的改进为主要研究内容，为计算机视觉理论的图像边缘检测中的角点检测问题提供了一种较合理的解决方法，对计算机视觉系统的实现具有一定的实践意义。

实验证明，该算法具有执行速度快、角点检测准确的优点，可以检测出较复杂的三类图像的各种角点，而且适用面较广、通用性较强，也在图像分割研究领域为建立通用的计算机视觉系统完成视觉任务提供了新的思路。

该算法的不足之处在于参数较多，因此还需进一步研究像素值与参数值之间的内在关系，以实现更准确的提取。