改进的均匀化AGAST特征提取算法

王 辉，袁 杰

(新疆大学电气工程学院，乌鲁木齐 830000)

0 引言

同步定位与建图(Simultaneous Localization and Mapping，SLAM)技术因无人驾驶、机器人等应用而逐步走入大众视野。作为机器人底层技术，通过传感器对周围环境信息进行采集，并进行实时定位与建图，是当前机器人研究领域的重要研究方向[1-2]。其中，采用视觉传感器的视觉SLAM技术由于具有更低的成本及更好的普适性而成为当前的研究热点。基于特征点的视觉SLAM算法，特征点提取的均匀度和提取速率将直接影响SLAM位姿估计效果。

LOWE[3]提出了尺度不变特征变换(SIFT)算法，该算法具有尺度、旋转、亮度不变性，具有较高的精度，但其计算量大、运行时间长，不适合实时SLAM；BAY等[4]提出了加速鲁棒特征(SURF)算法，该算法性能优于SIFT算法并具有更快的速度，但仍需要较长时间构建描述子，实时性较差，不具备构建SLAM系统的条件；RUBLEE等[5]提出了定向FAST角点与旋转BRIEF描述(Oriented FAST and Rotated BRIEF，ORB)算法，该算法基于加速段检验特征(FAST)角点和rBRIEF(rotation-aware BRIEF)描述子，具有非常快的计算速度，并具备旋转不变性及描述子，但该算法提取的特征点存在严重的局部密集现象，在相机发生高速移动的情况下，易发生跟踪丢失；MUR-ARTAL等[6-7]提出了基于四叉树的ORB特征均匀(QORB)算法，与传统ORB算法相比,其主要优势在于提取的特征点更加均匀；MAIR等[8]提出了加速段检验的自适应通用角点检测(Adaptive and Generic Accelerated Segment Test，AGAST)算法，该算法是对FAST算法的一种改进，主要提升了速度与亮度变化下的鲁棒性，但没有解决尺度不变性；TANG等[9]提出的几何关联网络2代(Geometric Correspondence Network v2，GCNv2)算法是一种基于深度学习的特征提取算法，实时性较高，但对硬件平台有较高要求；柴江龙等[10]提出变尺度因子的改进ORB算法，提高特征点提取效率，但未对特征点进行均匀化，特征点较为集中；禹鑫燚等[11]提出改进的ORB均匀化特征提取方法，采用四叉树方法进行特征点均匀化，但所用四叉树结构较为传统，实时性较差。

基于以上分析，为了实现特征点提取的均匀化，改善特征点的局部聚集问题，避免冗余点对位姿估计的影响，同时具有较高的特征点提取速率，拥有更高的实时性，提出一种改进的AGAST特征提取算法。通过对图像构建高斯金字塔，实现特征点尺度不变性，采用四叉树方法对AGAST算法提取的特征点进行管理，实现特征点在图像上的均匀分布，根据期望特征点数限制每层金字塔相应四叉树深度，减少冗余特征点，提高整体运行效率。

1 改进的AGAST算法

AGAST算法属于FAST角点检测算法的一种改进，具有更高的特征点提取速率和更好的场景适应性。但同时，该算法并没有实现尺度及旋转不变性，同时不生成描述子，无法进行特征点匹配。本文采用四叉树方法实现对AGAST特征点的均匀化提取，通过对输入图像构建图像金字塔，在构建的图像金字塔上逐层提取特征点并进行四叉树管理；采用灰度质心法对每个特征点计算方向，提供特征点的旋转不变描述；对每个最终选定的特征点生成与该点匹配的Brief描述子，为特征匹配提供支持。

1.1 特征点提取

FAST特征检测算法是当前特征点视觉SLAM方法中提取效率较高的算法[12]。AGAST特征检测算法是针对FAST的一种改进算法，具有更快的速度，在复杂场景图像中有更好的表现[13]。如图1所示，FAST算法将像素“p”与bresenham圆上的16个像素点进行比较，选择周围半径为3。若在bresenham圆上的16个像素点中存在连续的Num个像素，其灰度值与p点灰度值差的绝对值不小于所设定的阈值t，则认为该点为特征点，一般取Num=12。

图1 特征点检测Fig.1 Feature point detection

作为FAST算法的改进，AGAST算法提供了一种更详细的配置空间,它采用“非较亮”与“非较暗”对原配置空间进行扩展。采用以下概念：Sn→x表示n→x的像素对于核n的状态，分配如下

(1)

AGAST算法通过在扩展的结构空间中寻找最优决策树，结合加速分割算法，提高了特征点提取速率，如图2所示。其中：小圆圈为当前特征提取区域的像素，不同颜色表示像素之间的差异，白色为差异最小，黑色为差异最大；线条表示计算过程中连接关系。

图2 自适应分割Fig.2 Adaptive segmentation

通过在满二叉构型的树中寻找最优树的方法，根据当前图像信息进行决策树动态分配，提高提取效率，可以动态适应场景。AGAST算法提取的特征点可重用性高、较为稳定，有利于提高位姿估计精度。

1.2 四叉树均匀化

AGAST算法依然是角点检测算法，同FAST算法类似，其提取的特征点依然存在一定程度的局部密集情况，为了使所提取的特征点更加均匀地分布于整幅图像上，为后续的匹配操作提供更好的数据支撑，本文选用四叉树方法对特征点提取过程进行均匀化操作。

通过对同一幅图像提取不同的空间尺度信息，得到图像局部和全局尺度上的一系列多分辨率图像集合，构建高斯金字塔，再对每一层进行AGAST角点检测，从而解决AGAST算法本身没有尺度不变特性的问题。算法流程如图3所示。

图3 算法流程Fig.3 Flow chart of the algorithm

具体计算过程如下。

1)为了实现特征的尺度不变性，对输入的图像进行高斯金字塔构建，此处选取金字塔层数为8。

2)对图像进行初始结构划分，首先以边长30像素的正方形作为初始划分的依据，同时根据输入图像的实际分辨率，计算划分后的行数与列数，即

c=w/30

(2)

式中：c为所求列数;w为图像横向分辨率。由于实际视觉传感器多为矩形，根据所得行数与列数分别计算网格的高和宽，即

W=round(w/c)

(3)

式中，W为划分网格宽度。划分后，遍历所有网格进行特征点提取；若在某一个网格中无法提取到特征点，则对起始阈值Tinit进行降低，直到降低至预设的最低阈值Tmint。此处取Tinit=20，Tmint=10。

3)步骤2)中所获取的特征点存在局部密集现象，这些点之间位置接近、描述相似，称为冗余特征点。使用四叉树方法对特征点进行管理，获取均匀化特征提取结果。

初始化节点O，将图像分为4个区域，获得初始四叉树结构，称为4个子节点；对每个子节点内的特征点数量进行统计，若子节点内特征点数量大于1，则对该子节点继续进行分割；若子节点内特征点数量小于1，则对该子节点进行保存，称为父节点。对各子节点不断分割，直到父节点数量达到所设定的预期特征点数量，则停止分割。如图4所示。

图4 四叉树特征点管理Fig.4 Feature point management by quadtree

根据预期提取特征点数，由设定的金字塔层数和尺度因子可计算得到每层相应的预期特征点数。通过预期特征点数，对四叉树深度进行限制，即

(4)

式中：Dl为四叉树分割深度；l为第l层金字塔；F为预期特征点数；s为尺度因子。

通过对四叉树深度进行限制，避免了四叉树过度分割，可降低冗余点的产生，提高运行效率。

1.3 特征点方向及描述子计算

同FAST特征点相同，AGAST特征提取算法不具备旋转不变性，为了解决这个问题，采用灰度质心法对经过筛选的特征点进行角度计算，增加旋转描述。

特征点方向计算过程如下。

1)选取特征点，以该点为中心的图像块B的矩mp q为

(5)

式中：pq为矩的阶数的系数；x和y为图像块B中像素点坐标；I(x,y)为此像素点(x,y)处的灰度值。

2)由该点的矩mp q可得到该点的质心C的坐标为

(6)

式中：m00为图像块0阶矩；m01和m10分别为图像块关于x轴与y轴的1阶矩。

(7)

通过以上步骤得到特征点方向，实现特征点的旋转不变性。

为实现特征匹配，需要为特征点匹配相应描述子，BRIEF描述子[14]的核心思想是对选定的某一个特征点，选取该特征点的邻域P，在邻域P内选取n个点对，并对各点对之间的灰度值进行比较，进而转化为二进制字符串，每个特征点均有相对应的二进制字符串，即为此特征点的描述子。由于在构造时只考虑到单个像素处的像素值，因此对噪声较为敏感，使用数字平滑技术对图像进行处理。通过高斯滤波方法对邻域P进行处理，可降低噪声干扰，提高描述子的稳定性和可重复性。

1)选取的特征点为中心、大小为S×S的邻域P(S取31);

2)对邻域P进行高斯滤波，取标准差σ1=2，窗口大小为9×9;

3)在邻域P内共选取n个点对N(x,y)，并定义τ为

(8)

式中,p(x)为x点的像素值大小，综合性能及效果考虑，选取n=256;

4)在选取n对特征点之后，对选取的每个特征点进行计算，将256个结果从最低位到最高位依次排列成字符串fnd(p)，即

(9)

最终得到一个256位的二进制字符串，即为选定特征点的描述子。

根据特征点的描述子，选择汉明距离作为度量，实现特征点初次匹配，获得初始匹配集。对某特征点，选取与汉明距离最短的一个特征点形成匹配对，遍历所有特征点，得到匹配对集合。

由于噪声等干扰因素存在，获取的粗匹配集中不可避免地存在一些错误匹配的情况。采用随机一致性检测(RANSAC)来剔除错误匹配对。对于一个包含错误数据的集合，RANSAC算法将其中的数据分为“内点”与“外点”，通过估算该数据集合的数学模型，剔除其中的错误数据“外点”，保留“内点”，实现数据集的优化筛选。

2 实验分析

为验证采用四叉树改进的均匀化AGAST算法(QAGAST算法)的优越性，使用AGAST,QORB特征提取算法，在Mikolajczyk特征检测评估数据集下的4组图像对算法进行评估。分别对提取速率及特征点均匀化程度进行比较，如图5所示。

图5 测试图集Fig.5 Test atlas

本实验在Ubuntu 16.04操作系统，CPU i5-10600KF-4.1 GHz，32 GiB内存条件下完成。

2.1 提取速率实验

使用AGAST,QORB,QAGAST特征提取算法对Boat,Graf,Bikes,Trees 4组数据集图像进行特征提取，设定预期提取特征点数为1000。

使用每点提取耗时来对特征点提取速率进行衡量，如表1所示。

表1 特征点提取耗时Table 1 Time cost of feature point extraction μs

从表1可以看出，在4组对比实验中，改进后的QAGAST算法提取相较于未进行均匀化处理及方向、描述子计算的AGAST算法需要更长的计算时间，但提取速率优于QORB算法。

将QAGAST算法与QORB算法的5组实验数据进行绘制得到如图6所示提取耗时对比情况，图中，纵坐标为算法提取单个特征点的平均耗时。

图6 提取耗时对比Fig.6 Comparison of extraction time cost

如图6所示，在4组图像中，QAGAST算法相比于QORB算法，每个特征点提取速率分别快24.01%，4.27%，10.10%，9%，平均提取速率提高12.31%。

由上述实验可以看出，相较于QORB算法，改进后的QAGAST算法具有更高的特征点提取速率，证明其高效性。

2.2 均匀度实验

(10)

式中，L为均匀度指数,该数值越低，则表示均匀度越好。

使用上述4个图像测试组分别对AGAST算法、QORB算法、QAGAST算法进行均匀度对比实验，如图7所示。

图7 均匀度对比实验Fig.7 Homogenization comparison experiment

统计图像数据，并使用均匀度评价函数进行计算，得到如表2所示均匀度指数。

表2 均匀度指数Table 2 Homogenization index

通过实验数据可以看出，采用了改进四叉树均匀化处理的QAGAST算法，在特征点提取均匀度上较未改进的AGAST算法提升47.12%，较传统四叉树算法的QORB算法提升7.8%。

2.3 特征匹配实验

传统特征点提取算法仅采用汉明距离进行特征匹配，存在较多误匹配情况，较多的匹配对数量也会对算法效率造成影响。为了实现更精确的特征匹配，采用RANSAC算法对特征匹配进行筛选，可以有效剔除错误匹配对，保留正确匹配对，降低在SLAM位姿估计时的误差。通过使用QAGAST算法、QORB算法及AGAST算法对Boat图像进行特征匹配实验，实验结果如图8所示。

图8 特征匹配实验Fig.8 Feature matching experiment

通过RANSAC算法实现了对特征匹配对的筛选，获得了准确度较高的匹配对集合。

3 结束语

本文针对特征点提取中存在的特征点局部密集问题，提出了一种改进的AGAST特征提取算法。通过对AGAST算法进行高斯金字塔构建，实现特征点的尺度不变性；使用四叉树方法对特征点进行管理，实现了均匀度较高的特征点分布；根据不同预期特征点数和金字塔层数，对四叉树深度进行限制，减少了冗余点，提高了提取效率。通过与QORB算法进行实验对比，结果表明，QAGAST算法特征点提取速率提高12.31%、均匀度提高了7.8%。采用RANSAC算法有效剔除了错误匹配，获取精确匹配集。实验数据表明所提算法具有一定的优越性。