基于图的SLAM点稀疏化方法-稀疏化算法

特征点法的VSLAM系统中，特征点并不是越多越好；相反， 少量 并且 质量高 的点会让这个SLAM系统位姿精度更高，且消耗更少的存储资源和计算资源。本文基于上述情况，提出了一种在SLAM系统中实现地图点稀疏化的有效的图优化方法，进而减少一般特征点SLAM系统中的3D点和关键帧，减少了计算和存储资源，同时提高了位姿估计的精度。

Abstract

当将SLAM用于真实世界中实际的问题（例如自动驾驶、无人机和AR设备）上时，其内存占用和计算成本是限制性能和应用范围的两个主要的因素；在离散的特征点SLAM算法中，解决这个问题的一个有效的方式是通过local BA 和global BA删除点进而限制地图点的规模；本项研究中提出了一种在SLAM系统中 实现地图点稀疏化的有效的图优化方法，具体上作者将最大位姿可见性和最大空间多样性问题表示成一个最小成本最大流量图优化问题。作者所提出的方法可以在现存的SLAM系统中作为额外的一个步骤，因此它可以用于传统 和学习的SLAM系统；通过大量的实验评估证明所提出的方法用 大约1/3的地图点 和 1/2的计算 实现了更精确的相机位姿。

Introduction

Motivation：基于特征点法的VSLAM系统具有较好的处理速度和计算效率从而达到实时的性能，但是VSLAM系统最大的缺陷之一是随着地图大小的增长，内存大小和计算成本会呈二次增长，解决这个日益增长的资源需求有两个方向：一个是高效地求解优化问题[40]，比如许多算法都试图利用地图拓扑或问题结构来降低计算成本；另一个是减小整个SLAM系统的大小，包括特征/帧选择、关键帧/3D点抽取等，它们大多集中于减少数据量或计算成本，同时略微牺牲位姿精度；在现有的SLAM系统中，为了在保持位姿定位精度的同时减少地图大小和计算成本，作者引入了一种有效的点稀疏化算法，该算法可以直接集成到任何特征点的视觉SLAM系统中。

Contribution：

提出了一个 相机位姿对 和 3D点最大的点可见性 的 图表示 方法；

提出了一种新的cost用于最大化图像空间上二维特征的空间多样性；

提出了一种 基于最小代价最大流量（minimum-cost maximum-flow）点稀疏化算法来控制剩余点的数量；

提供了详细的位姿准确性、点减少和各种室内/室外公共数据集的改进速度比较；

据作者所知，本文的工作是第一次将关于特征和帧关系的多个属性同时集成到稀疏化特征图中，也是第一次为稀疏化地图的本地化性能的维护提供了验证。

图1 上方图：ORB-SLAM2生成的地图点；下方图：稀疏化图；在构建地图和在地图上进行定位时，估计位姿精度都有一定的提高；与上方图相比，下方图的地图包含39%的点

Related Work

针对VSLAM优化问题的快速计算和低计算量为目标的问题空间缩减方法可以大致分为两个部分的工作；

第一个部分的工作研究了基于图优化的快速位姿优化方法。[35]和[36]通过使用因子下降法和非循环因子下降法减少KLD (Kullback-Leibler Divergence)的迭代优化，提高了SLAM的准确性和速度；[29]提出了节点选择问题相对于在结果稀疏化中付出的代价；[22]通过边缘化旧节点的稀疏化节点，同时保持剩余节点的所有信息，并给出一个标准化的最小化问题，以保持图组合的稀疏性；[39]设计了一种动态变量重新排序的方法，为快速增量Cholesky分解在增量更新和批量更新之间做出决定减少了与逆排列相关的工作量，为增量SLAM算法提供了节省计算量的方法；[26]提出了一种启发式方法，通过消除复杂性度量来弥合图结构及其计算之间的分析差距，从而减少批量优化和增量优化的计算量；[21]提出固定滞后方法，边缘化SLAM问题中的变量，最小化图稀疏化过程中的信息损失；[6]使用一种基于信息的方法和最小化问题的增量版本来高效地稀疏地标和姿态的数量，而不影响估计轨迹的准确性。

另一个部分的工作对SLAM中的图几何进行了缩减，以最小的信息损失对特征、点、帧进行了抽取。[2]提出了一种自适应的非最大抑制(ANMS)方法，可以快速均匀地重新分割图像中的关键点，该算法通过对搜索范围的平方逼近来抑制无关点，降低了计算复杂度，并根据图像维数初始化搜索范围，收敛速度更快；[15]通过通过 SDC (suppression via disk covering)算法高效地选择一个空间分布的关键点集，该算法基于逼近最近邻和贪婪方法对关键点进行聚类；[37]提出了一种通过SLAM系统跟踪，利用连续帧之间的时间相关性和加权特征，通过多帧引用提取有用特征的策略。

Methods

作者在ORB-SLAM2上融合了本文所提出的方法；一旦通过n > 1帧的三角化估计的地图点之间的连通性和相机姿势被表示为一个具有流量和成本的图结构，作者提出了一个点稀疏化的图表示的解决方案。

A. ORB-SLAM2 Overview

ORB-SLAM2中影响内存和计算需求的关键因素之一是地图点的数量和与地图点相关的局部兴趣点特征，随着BA的增长，local和global BA的规模呈二次增长，这反过来又需要显著增加的计算成本；所以主要研究方向有两个：

（1）只提取相关的局部特征和点

（2）剔除这些对位姿优化贡献不大的特征或点；在提出的方法中，在提取到足够的特征点和临时生成地图点之后，作者着重于抽取点来建立一个更简化的BA问题，并且通过大量的实验验证了该方法的有效性。

B. Graph Representation for Point Sparsification

图2 （a）四个关键帧(A、B、C和D)共享3D空间中的三个点的事例；（b）由(a)构造二分图；一共有4层顶点:两个特殊顶点，一组点顶点，一组帧对顶点；在每个边的上面，为示例写了容量/成本值

图2显示了要在 BA 中优化的简化局部地图结构的示例，这里作者建立一个有向流图结构来解释帧和它们所看到的点之间的关系，该方法解决的核心问题是如何在local 和 global BA 问题中选择结构变化最小的点子集，它相当于如何选择这样的点，使BA问题中的约束数量最大化，同时使点的数量最小化；此外，在调整每帧6DOF位姿时，图像空间上的残差构成了每个相机位姿的误差协方差矩阵，残差均匀分布有助于使协方差得到很好的正则化，相反，如果所有的特征点都聚集在图像空间的一个角落附近，姿态调整问题空间的边缘都很陡峭，导致很难有效地解决；同样，两帧之间的帧baseline越宽，各点约束的雅可比矩阵值也就越相似。直观上看，如果一个点的两帧基线角度接近于零，深度估计会变得困难，点调整也会变得困难。

有以上三点观察结果可以概括为选点的三个目标：

最大点可见性:最大限度地共享一个点的帧数（选择在多帧之间观测到多次的点）；

最大空间多样性:特征点在图像空间上的分布是多样化的（要求点分布均匀）；

最大帧baseline长度:使任意两帧之间的相机中心距离最大化（这个是关键帧选择）。

为了集成一个算法解决上述问题，作者提出一种基于有向图表示的新方法，即节点对应于点和位姿对；在此图中，利用节点之间的成本和容量能力，将节点的实际点可见性、空间多样性和基线转化为最小成本最大流量的二部分图。

1）Point Connectivity：首先考虑一个点和共享该点的特征点的frames之间的连通性，连通性高的点表示高可见性，具有鲁棒的局部特征，这种高度可见的点容易被选择，因为它们在位姿图上的多个位姿提供了强约束；将Vso 与点vpi 之间的边的代价函数cc 定义为具有高连通性的vpi 的较低的代价值：

2）Spatial Diversity of Interest Points：ORB- slam2在ORB特征提取步骤中包含了空间均匀分布的兴趣点选择过程，但是兴趣点的初始均匀分布并不能保证在下面的步骤(包括点稀疏化)中得到相似的兴趣点分布；这里定义了边缘e(vP, vF)的空间代价cs，以确保在点稀疏过程中特征分布保持甚至改善：

3）Frame Pair Baseline：这里考虑了每一帧对的基线距离；对帧对中观测到的超过一定距离的点进行优化可以更可靠地进行，并可能对补偿关键帧之间累积的漂移误差有用；基线代价cb 应用于vF 和vsi 之间的边：

C. Minimum Cost Maximum Flow Graph Optimization

上面 B. Graph Representation for Point Sparsification 将整个有向图构建出来了，本节描述如何计算这个有向图。作者使用最小代价最大流算法[11]来解决上述图问题去计算从 Vso 到 Vsi 的最大流量，进而使总的代价最小：

其中 f(e) 是边 e 上的流量；通过计算在容量约束下成本最小的最优流量，能测量点和帧之间边上的流量，与上述定义的三个理想条件的满足程度有关；计算流量后，只取e边( Vso, Vpi)上流量大于预先设定阈值θf的点pi；Goldberg算法[17]保证最差情况下的时间复杂度限制在:

其中n是顶点总数，m是边总数，C是最大的输入成本。

Experiment

实验部分先是给出了所提出的方法的实现细节，然后将该方法在各种数据集上进行实验并对结果进行分析。

A. Implementation Details

本文的系统建立在ORB-SLAM2上。具体的，本文的方法在ORB-SLAM2 的 local mapping部分每个 local BA 之前执行；作者使用两种方式修改了ORB-SLAM2，首先是将现有的多线程处理改为单线程处理，目的如下：

（1）对总运行时间的客观评估

（2）确定效果评估

（3）由于处理延迟，在优化步骤中禁用帧丢失；第二点是因为ORB-SLAM2中确定关键帧的条件与来自local mapping线程的跟踪点数量和 local mapping线程的状态有关，因此当应用单线程处理或点稀疏化时，local BA执行的数量会发生变化，所以这里作者使用基于平移和旋转变化量的确定性关键帧插入准则用来衡量所提出的点稀疏化的影响。

整个实验中，作者设置 θf 为边缘容量的一半，同时使用Google Optimization Research Tools解决最小成本最大流图问题。

B. Performance Evaluation

作者在EuRoC、TUM、ScanNet、ICL-NUIM和KITTI数据集上进行了评估，使用RMS ATE度量位姿精度，通过计算估计位姿与gt位姿之间的绝对距离来表示估计轨迹的全局一致性；下面是在各个数据集上的实验情况及说明。

表1 在EuRoC序列上选择点和关键帧的比例

图3 EuRoC上的总运行时间和RMS ATE与表I相关

表 1 和图 3 为双目模式下EuRoC数据集的实验结果，参数 M 代表；特征点减少的同时，关键帧也会减少，因为它们有连接的映射点的减少会导致连接低于阈值的关键帧自动退出，总体处理时间也大大减少，因为通过减少约束的数量，BA和跟踪过程；图 3 显示了表I中实验的总运行时间和RMS ATE的图，结果显示所提出的方法减少了 1/3 的运行时间并且性能上几乎保持甚至提高，ATE差值最多在4cm以内；参数M不同 ，证明所提出的方法不平衡属于一个位姿的约束成功地删除了只对优化有负面影响的点；

表2 通过多个不同的M值对所提出的方法进行比较；序列依次为TUM，ICL-NUIM和ScanNet

作者将所提方法在TUM，ICL-NUIM和SCANNET数据集上也进行了实验对比；因为与EuRoC数据集相比，空间比例尺不同，生成的地图点更少，所以M的取值范围不同；图1是ScanNet在scene0000上保存的地图点的可视化，以及根据估计轨迹得到的场景的三维重建环境。

表3 在双目式下使用KITTI对室外环境的实验结果

作者使用KITTI数据集对室外环境进行了验证，表 3 是M=100 和M=200的实验结果，与室内环境不同的是，它在一个相对较小的空间尺度上采用了许多地图点和多个连接，并有许多重新审视的点，关键帧丢失在室外环境中并不常见；时间的增加也不像在室内那样显著；然而，当地图点选择像室内其他结果一样保守执行时，也可以观察到性能的提高。

C. Comparisons

图4 图像上选定的关键点的可视化；从上到下，原来的方法，ANMS，作者的方法；右下图显示了关键点的覆盖范围和聚类情况

表4 与ANMS点选择的比较包括原始结果；最低的RMS ATE用粗体表示

自适应非最大抑制(ANMS)算法[2]通过高效计算选择待均匀分布的图像上检测到的关键点，提高了SLAM和图像配准性能；表IV显示了在点选择比例最低的情况下应用ANMS和根据ANMS产生的地图点总数应用作者的方法时的结果，作者的方法4例中有3例的结果优于ANMS和原方法；图4是通过ANMS和作者的方法对一幅图像中选定的局部感兴趣点的可视化。

D. Ablation Study

表5 在TUM数据集上以部分和全部成本降低姿态精度

该部分评估了三种代价的有效性；当使用所有这三种成本时，最低的ATE是通过在大基线下更多地使用帧来实现的，同时最大限度地提高位姿连接和空间多样性。

E. Localization Test

本节通过从相同场景中收集的两组序列来检验原始地图和稀疏地图的位姿定位精度；使用 EuRoC dataset的MH01 & MH02 和 ScanNet的scene0000 00 & scene0000 01 进行测试；对MH01和scene0000 00分别采用原始和稀疏两种模式构建参考地图，对MH02, scene0000 01进行定位。

表6 定位精度评价

具体结果如上所示，MH01序列的稀疏化地图相比原始地图只包含了23.9%的点和34.4%的关键帧，同时计算时间和地图大小有显著性减小，但是位姿精度上升了；与原始地图相比，scene0000只使用了38.6%的点和59.1%的关键帧，姿态误差也减少了。

Conclusion

本文介绍了一种基于图的SLAM点稀疏化方法，该方法在点稀疏化过程中同时实现了3个目标:最大点连通性（maximizing the point connectivity）、最大空间多样性（maximizing the spatial diversity）和最大帧基线长度（ maximizing frame baseline length）；以ORBSLAM2为baseline，提出的方法在保持甚至提高局部映射过程中姿态跟踪精度的同时，大大减小了地图尺寸；提出的方法可以用于地图创建后的后压缩或global BA前的预处理，它通常适用于基于局部特征SLAM系统，包括多传感器SLAM，并提供了有效的地图抽取和加速，可用于其他具有计算挑战性的环境，如可穿戴设备。

未来的研究方向包括边缘图优化的快速优化，以及考虑三维点的空间密度和二维特征多样性。