基于自适应的AGAST 特征均匀化提取算法

张 猛， 唐清岭， 蒋小菲

（贵州大学大数据与信息工程学院， 贵阳 550025）

0 引 言

即时定位与地图构建（Simultaneous Localization and Mapping， SLAM）作为机器人领域的关键技术，通过传感器即时地获取环境特征，进而完成地图构建和自身定位，是机器人领域的重点研究方向［1］。视觉SLAM 以相机作为传感器，因其成本低，采集图像信息丰富，成为当前的研究热点。 其中，基于特征点法的视觉SLAM 系统的特征提取速度和均匀程度是后续位姿估计和地图构建的重要影响因素［2］。

传统的ORB 算法结合了FAST 角点和BRIEF描述子，具有计算速度快的优势，被广泛应用在SLAM 领域［1］，但算法提取的特征在图像上分布不均匀，不利于后续的跟踪和位姿估计。 Mur-Artal 等学者［3-4］提出了QORB 算法，利用四叉树算法改善了传统ORB 算法特征点提取不均匀的问题，但算法耗时有所增加。 Mair 等学者［5］对FAST 算法进行改进，提出了速度更快， 适应性更强的 AGAST（Adaptive and Generic Accelerated Segment Test）算法。 Tang 等学者［6］将AGAST 角点与BIREF 描述子结合，提出了OARB 算法，提高了特征点的提取速率，但特征点局部密集现象仍然存在。 王辉等学者［7］提出了一种改进的均匀化AGAST 特征提取算法，采用四叉树算法均匀化提取特征点，但固定阈值的提取方式，提取大量冗余特征点，降低了特征点提取速率。 杨弘凡等学者［8］提出一种自适应阈值的提取方法，算法速度得到了提升，但仍需设定自适应参数，不是真正的阈值自适应。

基于以上分析，为了实现特征点的均匀提取，避免冗余点对位姿估计的影响，同时提高特征点提取速率，提出一种基于自适应的AGAST 特征均匀化提取算法。 首先，根据图像灰度信息计算特征点的初始提取阈值，避免提取过多冗余点而降低计算效率；其次，构建图像高斯金字塔，并在金字塔上提取得到多尺度的AGAST 特征点；然后，采用改进的四叉树算法对特征点进行划分和筛选，实现特征点的均匀分布；最后，用灰度质心法计算特征点的方向，实现特征点的旋转不变性。

1 AGAST 算法介绍

AGAST 算法是FAST 算法的一种改进，在速度上得到了提升，且在复杂环境中有更好的鲁棒性［9］。 本文提出的特征提取算法用AGAST 算法检测角点。 FAST 特征提取如图1 所示。 由图1 可看到，与FAST 算法角点检测判据一样， 通过比较圆心像素“p”与Bresenham 圆上的16 个像素的灰度值进行判断。 若有N个连续像素与像素“p”的灰度差的绝对值大于提取阈值，则像素“p”是一个角点。

为了使算法更快，首先将4 个像素（Bresenham圆上的1、5、9 和13）的灰度与“p”进行比较。 4 个像素中至少有3 个应该满足阈值条件，才有可能判定为角点。 满足此条件后，再对剩下的像素进行比较，当N≥12 时，则判定为角点。

AGAST 算法在FAST 算法的基础上扩展了配置空间。 引入“不暗”与“不亮”的状态对配置空间进行更详细的描述。Sp→x为像素x对于像素p的状态，像素状态的分配可按式（1）进行计算：

其中，为前一个像素的状态；Ip→x是像素x的灰度值；u表示该状态仍然未知；t为特征点提取阈值。 原始配置空间被增加到了6N， 而616＝2×1012，所以将可能的节点N设置为16。 与FAST 算法一样，阈值t越大，计算速度越快，检测到的角点越准确，但角点数越少；阈值t越小，计算速度越慢，角点数越多。

FAST 采用的ID3 算法是一种贪婪算法，在寻找最优决策树时表现很差，而AGAST 引入了后向归纳法，通过学习图像的结构化区域和同质化区域，构建出的最优二叉决策树如图2 所示，在树的末端根据叶节点的像素配置进行专用树间的跳转，进而将角点检测问题转换为二叉决策树问题，并结合加速分割算法，提高特征提取效率。 此外，AGAST 算法在构建专用树时，以离线的方式对叶节点进行评估，使得算法在决策树间跳转不需要额外的计算成本。

图2 AGAST 算法示意图Fig. 2 Schematic diagram of the adaptive and generic accelerated segment test

2 基于自适应的AGAST 特征均匀化提取

传统视觉SLAM 算法采用FAST 算法对角点进行检测。 因为AGAST 算法的速度在FAST 的基础上得到了提升，但特征提取阈值仍依靠经验设定，提取的特征点存在密集的现象。 本文提出了一种基于自适应的特征均匀化提取算法，首先，根据图像灰度信息自适应计算提取阈值，提高算法在不同图像上的适应性和提取效率；其次，构建图像金子塔，并在每层金子塔上利用四叉树算法均匀化提取具有尺度不变性的AGAST 特征点；然后，用灰度质心法计算特征点方向，并生成BRIEF 描述子，实现特征点的旋转不变描述，为匹配提供支持。 算法结构如图3 所示。

图3 算法结构Fig. 3 Algorithm structure

2.1 自适应提取阈值

AGAST 角点与FAST 角点都是以提取像素与其周围像素的灰度差作为特征检测和提取的依据。 但无论是传统提取算法、还是Mur-Artal 等学者［3］提出的提取算法的提取阈值均基于人工设定，每帧图像的提取阈值相同，并没有考虑图像的灰度信息，提取效率降低。 若阈值设定较大，算法在纹理较弱和对比度较低的图像上无法提取到足量的特征点［10］。因此为了在不同图像上均能提取到足量特征点，通常传统提取算法的提取阈值设定较低，而低阈值的提取方式虽能在不同图像上提取到足量特征点，但对于纹理强和对比度高的图像，算法会提取过多冗余特征点，降低了提取效率。

鉴于此，本文对特征点提取阈值进行改进，采用自适应的方式根据图像灰度信息计算特征点提取阈值，在保证提取足量特征点的同时，避免以低阈值在高对比度和高纹理图像上提取过多冗余点，从而提高算法的提取效率。 设计的自适应阈值计算方式见式（2）：

其中，iniTH为自适应计算所得的初始提取阈值；I（x） 表示第x个像素灰度值；为图像上各像素灰度平均值；ni表示图片像素总个数。 通过式（2）可以根据不同图像信息计算出不同的提取阈值，使得算法有更好的适应性和计算效率。

2.2 构建图像金字塔

AGAST 算法并不具备尺度不变性，这里通过对同一图像采样得到一组不同分辨率的图像集合，构建高斯金字塔，在每层高斯金字塔上提取特征点，得到具有尺度不变性的特征点。 此处构建了8 层金子塔，同时为了在每层图像上合理提取特征点，根据金字塔尺度因子计算得到每层图像期望提取的特征点数。通过式（3）即可计算得到每层期望提取的特征点数：

其中，M为图像需提取的特征点总数；s表示尺度因子；N表示第0 层期望提取的特征点数。

2.3 网格划分提取特征点

为了均匀提取特征点，对每层图像进行网格划分，并在网格中提取特征点，从而保证在图像各个区域都能提取到特征点。 根据输入图像分辨率，以30像素为边长的正方形作为初始划分依据，计算划分后网格的行数与列数。 由此推得的公式见如下：

其中，R为求得的网格列数，width为图像像素宽度。

此外，因为实际获取的图像为矩形，还需根据划分后的网格行数与列数，计算得到实际网格像素高度和像素宽度。 如式（5）所示：

其中，w为划分后的网格宽度；round（） 函数的作用是对结果取整。

网格划分结束后，采用由式（2）计算得到的初始阈值iniTH对每个网格进行特征点检测，提高特征点检测效率。 若某网格内检测不到特征点，则将阈值降低为iniTH/2，继续检测；若网格内还无法检测到特征点，则采用最低阈值minTH＝7 检测。 自适应阈值和最低阈值相结合，不仅提高了算法的提取效率，还保证了在每个网格中都能提取到特征点。

2.4 四叉树均匀化筛选

通过网格划分提取的特征点还存在局部聚集现象，这里采用四叉树的方法对其筛选使得特征点均匀分布在图像上。 此处四叉树算法以原始图像作为初始节点，并将初始节点划分成4 个子节点得到初始四叉树结构；接着计算每个子节点中的特征点数量，若大于1 则将此节点继续划分为4 个子节点，并删除该节点；若等于1 则标记该节点并不再对其划分。 如此重复直到被标记的节点数达到期望特征点数时，停止四叉树划分。

上述划分步骤中没有对四叉树深度进行限制，造成四叉树的过度分裂。 为了提高运行效率，这里根据每层金字塔图像期望提取的特征点数计算最大划分深度，从而限制四叉树深度。 具体数学计算公式见式（6）：

其中，Di为四叉树的最大划分深度；i表示图像金字塔的第i层；Ni为第i层图像期望提取的特征点数；s为图像金字塔的尺度因子。

2.5 特征点方向和描述

AGAST 算法与FAST 算法一样，均无旋转不变性，为了增加特征点在方向变化下的鲁棒性，采用灰度质心法为每个由四叉树均匀化筛选后的特征点计算方向。 计算步骤如下：

（1）以待计算方向的特征点为中心，选取图像块B，并计算出图像块的矩mpq，计算公式为：

其中，p和q表示图像块矩的阶系数，I（x，y）为图像中坐标是（x，y） 的像素灰度值。

（2）根据图像块B的各阶矩，定义图像块的质心C，可推得：

其中，m10和m01为一阶矩，m00为零阶矩。

（3）连接图像块B的几何中心O与质心C得到向量，向量朝向即为特征点的方向，定义特征点方向θ为：

通过上述步骤为特征点增加了方向信息，实现了旋转不变性。

在对特征点计算方向以后，采用BRIEF 描述子［11］对特征点进行描述，方便后续的匹配。 BRIEF是一种由多个0 和1 组成的二进制向量。 其思想是在以特征点为中心选取的领域P内，按某种固定的模型选取n对点（n通常取256），通过比较每个点对的灰度值大小，使得该特征点生成了一个相对应的二进制字符串，将此二进制字符串作为特征点的描述子。 具体步骤如下：

（1）以特征点为中心，选取边长为S的领域P（S通常取31） 。

（2）为了降低图像噪声对描述子的干扰，对领域P进行高斯滤波。

（3）在邻域P内共选取n个点对N（x，y） ，并定义τ如下：

其中，p（x）、p（y） 分别为点x和点y处的像素灰度值，τ为描述子的值。

（4）选取n个点对后，根据式（10）计算每个点对的τ值，并将每个点对的τ值依次从最低位到最高位排列成一个二进制字符串，此二进制字符串即为特征点的描述子。

3 实验结果与分析

为验证本算法的优越性，使用传统ORB 算法、QORB 算法以及本文提出的QOARB 算法，采用Mikolajczyk 等学者［12］创建的图集中的4 组图像对算法进行测试，依次对算法的特征提取速率、均匀化程度及匹配正确率进行比较。 测试图集如图4 所示。其中，Bikes 图集是一组模糊程度不同的图像，Leuven图集是一组对比度不同的图像，Ubc 图集是一组压缩程度不同的图像，Graf 图集是一组视角变换的图像。为了避免实验的随机性，对所有实验进行5 次测试，以平均值作为实验结果。

图4 测试图集Fig. 4 Test image set

本实验在Ubuntu18.04 操作系统，计算机CPU为Intel（R）Core（TM）i5-7200U CPU ＠ 2.50 GHz，12 GB 内存条件下完成。

3.1 提取速率实验

为了核验本算法在特征点提取速率上的提升，使用ORB 算法、QORB 算法、本文提出的QOARB 算法在Leuven、Graf、Ubc 和Bikes 四组图集上进行特征提取，设置提取特征点数量为1 000 个。 用单点提取时间对特征点提取速率进行衡量。 不同算法在4 组图像集上的特征提取实验结果见表1。

表1 特征提取速率Tab. 1 Feature extraction rate

从表1 可以看出，在4 组对比实验中，本文提出的QOARB 算法相较于未对特征点均匀化处理的ORB 算法在提取速率上有更长的计算时间，但提取速率优于QORB 算法。 这是因为QORB 算法与QOARB 算法均引入了四叉树方法均匀管理特征点，增加了计算复杂度，但QOARB 算法根据图像灰度自适应提取特征点，提取耗时明显低于QORB 算法。

提取速率对比如图5 所示，QOARB 算法与QORB 算法相比，在不同图像组上的单点提取速率分别提高了6.80%、12.44%、14.70%、7.13%，平均提取速率提高10.65%。

图5 提取速率对比Fig. 5 Extraction rate comparison

由以上实验数据可以看出，本文提出的QOARB算法相较于QORB 算法，特征点提取速率更高，证明算法在特征点提取速率上的优势。

3.2 均匀度实验

为了量化均匀度，采用以下计算方法［13］：首先将图片沿水平、竖直、左斜、右斜及中心与外围五个方向，将图像平均划分为10 个区域；其次，根据每个区域内的特征点数量计算方差V；最后，根据评价函数公式（11）来计算均匀度u：

该数值越小，则划分的各个区域中的特征点数目越接近，均匀程度越好。

对每个图像组中的第一幅图使用ORB 算法、QORB 算法和QOARB 进行均匀度对比实验，如图6所示。

图6 特征提取结果Fig. 6 Feature extraction results

由图6 可看出，QORB 算法与QOARB 算法提取的特征点均匀化效果明显；传统ORB 算法提取的特征点主要集中在图像纹理密集的位置，出现了特征点局部聚集现象，均匀度差。

进一步对图像均匀度进行量化统计，通过上述的特征点均匀度评价函数计算特征点在图像上的均匀度，实验结果见表2。

表2 特征点均匀度Tab. 2 Uniformity of feature points

由表2 分析可知，QORB 算法与QOARB 算法相较于传统ORB 算法在特征的均匀度上有明显的提高，QORB 算法与QOARB 算法在特征的均匀度上相差不大，平均相差约2.9%；相对于传统ORB 算法，QORAB 算法均匀程度平均高16.4%。

3.3 特征匹配实验

对图像特征的提取是为了通过图像的匹配完成位姿估计，因此匹配正确率（Correct Matching Rate，CMR）［14-15］也是衡量算法优越性的重要指标，匹配正确率计算公式如下：

其中，mc是由数据集中所包含的各个图像间的变换矩阵计算得到的正确匹配个数，m为最近邻与次近邻距离算法筛选的匹配个数。CMR值越大，表示匹配效果越好。

本文对每个图像组的图片用ORB 算法、QORB算法及QOARB 算法进行匹配正确率测试，验证本文提出的QOARB 算法在匹配正确率方面的有效性。 匹配效果见图7 ，匹配正确率对比见表3。

表3 特征匹配正确率Tab. 3 Correct matching rate

图7 部分匹配结果Fig. 7 Partial matching results

由图7 和表3 可知，3 种算法在图像集上的特征匹配正确率相差不大，QOARB 算法较ORB 算法提高约0.59%，较QORB 提高约1.01%。 ORB 算法的正确匹配数均高于QORB 算法和QOARB 算法，但是ORB 算法的匹配对聚集在纹理强的区域，特征匹配对冗余，不利于后期的位姿估计。 QOARB 算法与QORB 算法的匹配对均匀分布在图像上，且本算法正确匹配数较QORB 算法提高约6%。

综合以上实验，本文提出的QOARB 算法提高了特征点的提取速率，实现了特征点的均匀化提取，同时在特征匹配上也具有优势。

4 结束语

本文提出了一种基于自适应阈值的AGAST 特征均匀化提取算法，为了提升传统视觉SLAM 算法的特征提取速率，改善特征点局部密集问题。 首先，根据图像灰度信息自适应计算特征点提取阈值，并在生成的图像金字塔上提取具有尺度不变性的AGAST 特征点；接着，采用限制深度的四叉树算法将特征点均匀分布在图像上；然后，计算特征点的方向并生成BRIEF 描述子。 在Mikolajczyk 等学者［12］的4 组特征对比实验图集上，对ORB 算法、QORB算法和本文提出的QOARB 算法进行了对比实验，实验结果表明：相较于传统ORB 算法，QOARB 算法的特征点均匀度提高了16.4%；相较于QORB 算法，QOARB 算法特征点提取时间减少了10.65%，同时匹配正确率和正确匹配数分别提升1.01%和6%。证明了QOARB 算法具有一定优势，可进一步应用到SLAM 算法中。