基于四叉树的ORB特征阶梯分布算法

季莘翔，王宇钢，林一鸣

（辽宁工业大学 机械工程与自动化学院，辽宁 锦州 121001）

0 引言

视觉同步定位与建图（Visual Simultaneous Localization And Mapping，V-SLAM）因为其体积小、性价比高、信息丰富的优点，已成为机器视觉的重点研究方向[1-2]。其中ORB算法因其计算速度快的优势，被应用于SLAM当中，对计算相机位姿起着决定性的作用[3-4]。

ORB-SLAM中的ORB算法由Mur-Artal等[5]提出。该算法具有尺度不变性、旋转不变性和计算速度快的优势，但其提取特征点的数量有限，且在图片中分布过于密集，影响匹配精度[6-7]。因此学者基于此算法进行了改进。王通典等[8]采用多尺度网格化的方法提取ORB特征点并利用四叉树均匀分配特征点。姚晋晋等[9]通过对不同的图片灰度值检测，计算出适应不同图片的阈值算法，该算法具有更强的抗干扰能力，但仍需要大量运算时间。于雅楠等[10]提出了一种特征点法视觉里程计自适应优化算法，该算法有助于改善光照条件变化时图像特征的稳定性，但提取的特征点数量不足，特征重叠明显。

针对上述情况，本文提出了一种基于四叉树的ORB特征阶梯算法。采用四叉树算法对图片进行分割，基于特征点分布的疏密程度划分区域，对每个区域设置递减的四叉树深度；通过设置阈值middleThFAST，提取出成阶梯趋势数量的特征点，在保证图片特征点均匀性的同时提升提取效率和特征点数量。此外，本文提出了一种客观评价标准——覆盖均匀度，对图片特征点的分布均匀性进行量化评价。

1 阶梯ORB算法

1.1 传统ORB算法

ORB 算法结构包括oFAST 检测和rBRIEF（rotation BRIEF）描述子计算[11-12]。从FAST算法改进得到的oFAST算法能够使特征点在图像中具有方向信息。该算法通过比较待测像素点p与周围16个像素点的灰度值差值，来判断该点是否为角点。如果16个像素点中有9个以上大于设定的阈值，则判定为角点，如式（1）所示：

式中：I（x）为范围内16个像素点中的任意一个点的灰度值，I（p）为待确定的点的灰度值，t为设定的阈值。

当以设定的阈值（iniThFAST）提取的特征点数量不满足设定值时，会降低阈值至minThFAST再次提取特征点。

使用灰度质心法使特征点具有方向。计算步骤具体如下。

1）在一个图片中，定义点（x，y）邻域矩为

式中：I（x，y）为图像灰度值，n为特征点的邻域。

2）邻域的质心坐标可表示为

图像的几何中心O与特征点邻域内的质心C相连，即得到特征点的方向：

rBRIEF是为了解决BRIEF不具备旋转不变性而改进的二进制描述子，并对角点进行平滑处理。在特征点附近边长为31的正方形像素区域内采用边长为5的正方形子窗口的灰度值之和作为判断描述子的依据，得到描述子分段函数，计算式如（5）：

式中：p（x）为点x的像素灰度值，p（y）为点y处的像素灰度值，τ即为描述子。

此外，为了使描述子具有较好的旋转不变性，再将特征点的方向加入到其中。使得最终描述子公式为

其中，A是对于任意n位置坐标（xi，yi），构造2×n矩阵。

1.2 阶梯ORB算法

针对传统ORB算法在提取时特征点分布不均的问题，采用四叉树算法划分出特征点疏密不同的区域，对特征点集中区域多次分割，使特征点分布在整幅图片上；根据特征点数量，由高至低依次降低分割次数。同时针对分割区域，分别设置两个高数量区域和两个低数量区域，使特征点分布呈阶梯性，从而提高单幅图片的特征点数量和均匀性。

传统ORB算法中minThFAST太低会导致计算次数过多，增加运行时间；minThFAST太高会导致在灰度值差值较小的区域提取不到特征点，特征点数量下降。因此，本文算法在iniThFAST和minThFAST中间加入middleThFAST，实现对划分区域的FAS角点的自适应提取，既能够提取到足够的特征点，又可以提升特征点提取效率。算法步骤如下：

1）设置参数，分别设定iniThFAST、middleThFAST和minThFAST，分割次数i=0；

2）用四叉树算法分割图片，按照特征点数量确定两个高数量区域和两个低数量区域，分割次数i=i+1；

3）对两个高数量区域，根据iniThFAST 和middleThFAST分别按38%和32%提取特征点，对两个低数量区域，根据middleThFAST和minThFAST阈值分别按17%和13%提取特征点；

4）判断是否为高数量区域，如果是则转到步骤5），否则转到步骤6）进行图像拼接；

5）分割次数i是否小于4，如果是则执行步骤2），对高数量区域进行再次分割，否则不再分割图片，转到步骤6）；

6）将步骤4）和步骤5）的图片分割区域进行拼接，构建描述子。

经试验确定，当本文算法分割次数大于3次时提取特征点分布结果不再明显变化，但运算时间会随分割次数显著增加。因此，本文将最大分割次数设定为3次。算法流程如图1所示。

2 覆盖均匀度

文献[13]提出了一种基于区域统计信息计算特征点分布均匀性的方法，即分布均匀度评价标准。研究表明该标准可以客观反映特征点的分布均匀程度，分布均匀度越低，说明特征点越均匀地分布在图片中。目前此标准已被广泛用于特征点分布均匀性评价。

但在部分图片中，该标准无法准确反映图像特征点的分布均匀性。以相框图片为例，当相框按照1.50、1.00、0.75的比例缩放时，图2为对应特征点提取结果。图2中（a）、（b）和（c）的特征点在图幅中面积占比分别是47%、25%和20%。

从主观判断，图2（a）的特征点均匀性最好，图2（b）和图2（c）相近。由表1可知，图2（a）和图2（c）分布均匀度数值相近，图2（b）分布均匀度数值比图2（a）和图2（c）低50%。由于图2（b）的特征点恰好密集地分布在各个区域的分界线上，导致特征点虽然密集，但分布均匀度的数值却很低，因此没有反映出特征点分布均匀性特征。

因此，本文提出了一种新的特征点分布均匀性评价标准——覆盖均匀度，即从分布均匀度和覆盖面积两个方面对图片特征点分布均匀性进行综合评价。覆盖均匀度越低，表明分布均匀性越好。覆盖均匀度计算过程如图3所示。

图3 覆盖均匀度计算过程

1）将图片分为10个区域，分别为上、下、左、右、右上、左下、左上、右下、中心和外围，统计各区域特征点数量的方差，得到分布均匀度，计算式为

式中：U为分布均匀度，v为方差。

2）对特征点进行膨胀，将所有距离相近的特征点相连，再进行图片腐蚀，把每个特征点膨胀后多余的面积腐蚀掉，得到覆盖面积。最后统计覆盖面积覆盖的像素。

3）分布均匀度与特征点覆盖面积的比值即为覆盖均匀度，计算式为

式中：P为覆盖均匀度，U为分布均匀度，np为被覆盖特征点像素，na为图片总像素。

由表1可知，图2（b）的分布均匀度是最低的，图2（a）和图2（c）的分布均匀度基本一致；图2（a）覆盖均匀度为最低，图2（b）次之，图2（c）为最大。覆盖均匀度结果真实反映了图片特征点的分布均匀性，也与人的主观判别是一致的，而分布均匀度未能有效评价特征点的分布均匀性。因此覆盖均匀度比分布均匀度评价结论更客观。

3 试验与分析

试验运行环境：操作系统为VM 虚拟机Ubuntu18.04LTS，CPU为Intel(R)Core(TM)i7-10875H，主频为2.30 GHz，内存为8G，开发语言为C++。本文采用Mikolajczyk数据库进行试验验证，选取其中在特征点分布具有代表性的5组数据集：模糊程度不同的数据集（bike）、对比度不同的数据集（leuven）、单一背景且占用大部分图幅的数据集（bark）、环境复杂且占用大部分图幅的数据集（trees）和不同压缩程度的数据集（ubc）[14]。

针对以上数据集分别采用传统ORB算法、Mur-Artal算法（MA算法）和本文的阶梯ORB算法进行对比试验，以验证本文算法有效性。试验参数：特征 点 提 取 数 量 为500；iniThFAST、middleThFAST、minThFAST值分别为8、14、20。对每组数据集进行24次试验，去掉其中两个最大值、两个最小值，取剩余20组数据的平均值作为试验结果。

图4为3种算法在bark数据集的部分提取结果，图中不同大小的圆和红点为提取的特征点位置。由图可知，传统ORB算法提取特征点时，提取到的特征点数量有限，主要集中在图片中间的石头缝隙部分，绿色树叶提取到的特征点却很少，分布极不均匀；本文算法提取到的特征点比传统ORB算法和MA算法更多，而且分布在整幅图片上，对绿色树叶也提取到更多数量的特征点。

图4 bark数据集img1、3、4提取结果

算法对bark数据集的试验结果如表2所示。由表2可知，在bark数据集中，本文算法运算时间比MA算法平均节省18%；提取的特征点数量比传统ORB算法平均多出15%，比MA算法平均多2%；在均匀性方面，本文算法分布均匀度要比传统OEB算法平均低14%，覆盖均匀度比传统ORB算法平均低28%，比MA算法平均低3%。因此本文算法对单一背景图片能提取出更多的特征点，运算效率更高，特征点分布更均匀。

表2 bark数据集试验结果

图5为高模糊数据集bikes的img5和img6图片提取结果。由图5可知，传统ORB算法提取的特征点不仅集中在摩托车区域附近，而且特征点数量少。本文算法提取的特征点既均匀分布在整幅图片，数量又远高于传统ORB算法。

图5 bikes数据集img5和img6提取结果

表3为bike数据集的试验结果。由表3可知，在时间方面本文算法比MA算法平均节省18%；在特征点数量方面，对序号1～4的低模糊图片，本文算法和MA算法的特征点提取数量比传统ORB算法平均多6%，对序号5和6的高模糊图片，本文算法特征点提取数量比传统ORB算法平均多110%；在均匀性方面，本文算法分布均匀度比传统ORB算法平均低10.3%；覆盖均匀度比传统ORB算法平均低53%，比MA算法平均低5%。因此本文算法对高模糊图片有更强的抗干扰能力，能提取出更多的特征点，运行效率更高，特征点分布更均匀。

表3 bike数据集试验结果

数 据 集leuven、ubc、trees分别包含6张图片，在运行时间、特征点提取数量、分布均匀度和覆盖均匀度的试验结果分别如图6～图9所示。

图6 运行时间的试验结果

由图6可知，在运算时间方面，本文算法比传统ORB算法有所增加，但与MA算法相比大幅减少。如图6 所示，对leuven、ubc和trees数据集，本文算法分别平均减少20.57%、25.74%和15.32%。

由图7可知，特征点提取数量因为trees数据集纹理平均，3种算法所提取到的数量相差不到6%。在ubc和leuven数据集中，本文算法特征点数量比传统ORB平均多10.45%，比MA算法平均多3.22%。

图7 特征点提取数量的试验结果

在均匀性方面，由图8可知，因为本文算法具有阶梯性，所以每组数据集的分布均匀度比MA算法平均高4.23%，比传统ORB算法平均低14.66%。由图9可知，因为综合了分布均匀度和覆盖面积，本文算法的覆盖均匀度比传统ORB算法平均低20%。虽然本文算法在均匀性上略高于MA算法，但在时间和特征点数量上表现优异。用少量的均匀性提高换取计算效率和匹配精度的提高是极具性价比的。

图8 分布均匀度的试验结果

图9 覆盖均匀度的试验结果

综上所述，对不同条件下的图片数据集，本文算法的均匀性比传统ORB算法平均低17%；特征点提取数量平均多10.45%。与应用广泛的MA算法相比，运算时间大幅降低了20.54%。在特征分布均匀性方面，覆盖均匀度的评价结果与分布均匀度的评价结果基本一致，表明本文算法比传统ORB算法和MA算法均有提升。

4 结语

为了解决传统ORB算法特征点数量不足、特征点分布呈集中性的问题，本文提出一种基于四叉树的ORB特征阶梯分布算法。对于特征点疏密不同的区域，设置呈阶梯性的分割次数和特征点数量。试验结果表明，本文算法比传统ORB算法提取的特征点平均多10.45%，特征点的分布均匀性平均低30%，运行时间比MA算法平均降低了20.54%。本文算法提取的特征点数量更多，分布更均匀，计算效率更高。因此，本文算法对SLAM后续的位姿估计以及建图具有实际应用价值。