Citations： Y. Park and S. Bae.Keeping Less is More: Point Sparsification for Visual SLAM[C].2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).Kyoto, Japan.2022:7936-7943.

Keywords： Bundle adjustment,Performance evaluation,Location awareness,Visualization,Simultaneous localization and mapping,Limiting,Spatial diversity

本文提出了基于最小成本最大流量的的图优化方法对地图点进行稀疏化，在稀疏的同时实现3个目标：点连通性最大化、空间多样性最大化和帧基线长度最大化。在ORB-SLAM2基础上，利用更少的地图点实现更准确的相机位姿估计。在EuRoC，TUM和ScanNet等数据集上进行了评估，实验结果表明运行时间和ATE都明显减少。

摘要

当将同步定位和建图（SLAM） 应用于实际应用（如自动驾驶汽车、无人机和增强现实设备）时，其内存占用和计算成本是限制性能和应用范围的两个主要因素。在基于稀疏特征的 SLAM 算法中，解决此问题的一种有效方法是通过选择可能对局部和全局束平差 （BA） 有用的点来限制地图点大小。本研究提出了一种高效的图优化方法，用于在此类SLAM系统中对地图点进行稀疏化。具体来说，我们将最大姿态可见性和最大空间多样性问题表述为最小成本最大流量图优化问题。所提出的方法作为现有SLAM系统中的附加步骤，因此它可以用于传统或基于学习的SLAM系统。通过广泛的实验评估，我们证明了所提出的方法在大约1/3的地图点和1/2的计算下实现了更精确的相机姿势。

一、介绍

同步定位和建图 （SLAM） 已被广泛研究和应用，例如室内测绘 [31]、无人机 [37]、自动驾驶汽车 [33]、虚拟现实和增强现实 [20]。计算系统的进步以及摄像头和LiDAR中复杂的传感器技术加速了SLAM系统在这些应用中的适配。特别是，视觉SLAM是最常用的建图系统之一，因为它可以嵌入到任何具有低成本视觉传感器的设备上。大多数视觉SLAM系统基于图优化概念，可以分为两组：基于稀疏特征的视觉SLAM从图像中提取特征点，并按图像序列跟踪它们，以计算它们的相机姿势并生成三维地图。然后，使用相机的估计姿势重新投影构成3D地图的地标的位置，并更新以最小化与从图像[25]，[28]跟踪的特征点坐标的距离。直接SLAM是为了从两张图像[13]、[23]中获取有关相机运动和环境的三维信息，将第一幅图像转换为第二位置的图像时，最小化与下一张图像的像素强度差异。它在提取的局部特征不足的同构环境中具有优势，但在许多情况下，基于特征的SLAM由于其卓越的处理速度和计算效率而成为实时性能的首选。 然而，可视化 SLAM 系统的最大缺陷之一是，随着地图大小的增长，内存大小和计算成本呈二次增长。为了解决这种不断增长的资源需求，已经从两个方向进行了一系列努力：一种方法是有效地解决优化问题[39]。许多算法试图通过利用地图拓扑或问题结构来降低计算成本。另一种方法是减少整个SLAM系统的问题大小，包括特征/帧选择，关键帧/ 3D点抽取等。 他们中的大多数都专注于减少数据大小或计算成本，同时适度牺牲位姿精度。为了在现有SLAM系统中同时减少地图大小和计算成本，同时保持姿态定位精度，我们引入了一种高效的点稀疏算法，该算法可以直接合并到任何基于特征的视觉SLAM管道中。我们的贡献包括：

• 建议相机姿势对和 3D 点的图形表示，以实现最大点可见性

• 提出最大化图像空间上 2D 特征的空间多样性的新成本

• 提出一种基于最小成本最大流量的点稀疏算法，用于控制剩余点数

• 提供与各种室内/室外公共数据集的详细姿势精度、点减少和速度改进比较。

Figure 1: 上图：由 orb-slam2 生成的地图点。底部：具有建议方法的稀疏地图。在构建地图和在地图上执行定位时，估计的姿态精度略有提高。与顶部相比，底部的地图包含 39% 的点。

据我们所知，这是首次将特征和与框架的关系的多个属性同时集成以稀疏特征图的工作，
也是第一个为稀疏化地图提供本地化性能维护验证的工作。

二、相关工作

随着可视化SLAM成为一个活跃的领域，已经有一系列关于SLAM中优化问题的快速计算以及针对低内存和计算需求的问题空间缩减的研究。它们大致可以分为两个区域。

首先，已经研究了基于图优化以实现快速姿势优化[7]。Joan 等人 [34]， [35] 通过使用因子下降和非循环因子下降减少 KLD（Kullback-Leibler 散度）的迭代优化，提高了 SLAM 的准确性和速度。 保尔等.[29] 通过最小化稀疏化惩罚来制定节点选择问题。使用节点分布，通过将密集分布近似到稀疏分布来选择最佳子节点集，从而最小化 KLD。Huang et al. [22] 通过边缘化旧节点来稀疏节点，同时保留有关剩余节点的所有信息，并制定规范化最小化问题以保持图组合稀疏。王等.[38] 设计了一种重新排序动态变量的方法，并减少了与快速增量 Cholesky 分解的逆排列相关的工作，以在增量和批量更新之间做出决定，从而为增量 SLAM 算法提供计算节省。Frey [26]提出了消除复杂性（EC）度量，这是一种解释全局图结构和计算之间关系的分析工具，并表明通过所提出的度量进行简单的抽取/关键帧可以实现很高的计算效率。雄等.[21] 提出了固定滞后方法，该方法边缘化了 SLAM 问题中的变量，并在图稀疏化过程中最大限度地减少了信息损失。Choudhary等人[6]使用基于信息的方法和最小化问题的增量版本来有效地稀疏地标和姿势的数量，同时保持估计轨迹的准确性。

另一组方法减少了SLAM中的图形几何形状，这会在信息丢失最小的情况下减少特征[8]，点[7]，[10]，帧[12]，[27]。 贝洛等.[2] 提出了一种自适应非极大值抑制 （ANMS） 来快速、均匀地重新分割图像中的关键点。它通过搜索范围的平方近似来抑制不相关的点，从而降低计算复杂度，并通过根据图像维度初始化搜索范围来加快收敛速度。高格利茨等.[14] 通过磁盘覆盖抑制 （SDC） 算法有效地选择一组空间分布的关键点，该算法根据近似的最近邻和贪婪方法对关键点进行聚类。奥登博斯等.[36]提出了一种策略，通过SLAM系统中的跟踪，利用连续帧与加权特征之间的时间相关性，引用多帧来提取有用的特征。

三、提出的方法

我们首先回顾了一个现有的视觉SLAM系统，其中我们提出的方法被集成用于评估。一旦地图点之间的连通性，通过三角测量光线从n>1帧和相机姿势表示为具有流量和成本的图形结构，我们提出了用于点稀疏化的图形表示解决方案。

A. ORB-SLAM2 回顾

自从ORB-SLAM2 [28]被提出以来，由于其实时跟踪性能和改进的单目、立体相机甚至RGB-D传感器的闭环精度，它一直被用作视觉SLAM的参考方法。因此，我们在ORB-SLAM2上评估了所提出的方法性能，尽管所提出的方法可以很容易地适应任何基于特征的单目或立体视觉SLAM。

影响 ORB-SLAM2 和可视化 SLAM 系统中的内存和计算需求的关键因素之一是与地图点关联的地图点和局部兴趣点要素的数量。随着它们的增长，局部和全局BA的大小呈二次增长，这反过来又需要显着增加计算成本。因此，已经研究了两种主要方法：1）仅提取相关的局部特征和点，或2）删除对姿势优化没有太大贡献的特征或点。 在所提方法中，我们着重于抽取点，在提取足够的兴趣点并临时生成地图点后构建一个更简化的BA问题，并通过广泛的评估证明所提方法显著提高了性能。

B. 点稀疏的图形表示

图 2 显示了要在BA优化的简化局部地图结构的示例。我们构建了一个有向流图结构来解释它们查看的框架和点之间的关系。在此示例中，有 4 个关键帧连接在一起，它们正在观察 3 个点。为了有效地选择帧对中的点，我们将此点侧和帧侧连接配置为二分图G=（v，e）结构，包括源、汇和两组不同的顶点，如图 2（b） 所示。该方法解决的核心问题是如何在局部和全局BA问题上选择结构变化最小的点子集。它等效于如何选择这样的点，在最小化点数的同时最大化 BA 问题中的约束数。此外，为了调整每帧的6DOF姿态，图像空间上的残差形成了每个相机位姿的误差协方差矩阵，因此均匀分布的残差有助于使协方差得到很好的正则化。简单地说，如果所有的兴趣点都集中在图像空间的一角附近，则姿势调整问题空间具有陡峭的边缘，因此很难有效求解。类似地，两个帧之间较宽的框架基线使得点约束的雅可比值相似。直观地说，如果一个点的两帧的基线角度接近于零，则深度估计变得更加困难，点调整也变得更加困难。这三个观察结果可以概括为点选择问题中的以下三个目标：

• 最大点可见性：共享一个点的帧数最大化。

• 最大空间多样性：影像空间上兴趣点分布多样化。

• 最大帧基线长度：任意两帧之间的相机中心距最大化。

Figure 2:（a） 在 3D 空间中共享三个点的四个关键帧（a、b、c 和 d）的示例。（b） 从（a）中构造的二分图。有 4 层顶点：两个特殊顶点、一组点顶点和一组帧对顶点。在每个边缘的上方，为示例案例编写了容量/成本值。

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

作者考虑以下3个约束：

1. 点连接：考虑一个点与共享该点的兴趣点的帧之间的连通性。具有高连通性的点表示具有强大局部要素的高可见性。
2. 兴趣点的空间多样性：许多研究报告说，使用空间均匀的特征集可以提高图像配准性能，所以要在特征点稀疏化的同时依然保证均匀分布。
3. 帧对基线：我们考虑每个帧对的基线距离。对帧对中观察到的超过一定距离的点进行优化可以更可靠地完成，并且对于补偿关键帧之间累积的漂移误差可能很有用。

C. 最小成本最大流图优化

我们使用最小成本最大流量算法 [11] 来解决上述图问题，以计算来自vSO自vSi这最大限度地减少了总成本：

f(e)是流动在边缘e通过在容量限制下以最小成本计算最佳流量，我们测量点和框架之间边缘的流量，以满足上述三个所需条件的程度。计算流量后，我们只取点p我谁的流动在边缘e(vSO,vp)大于预设阈值θf.戈德堡算法[16]保证了最坏情况下的时间复杂度由O(n2m⋅log（n⋅C))哪里n是顶点的总数和m是边的总数，并且C是最大的投入成本。

四、实验结果

在本节中，我们将评估并演示所提出的方法的性能。我们首先介绍所提方法的实现细节。然后，我们提供了对在各种数据集上进行的广泛实验结果的分析，包括通过与其他现有方法进行比较而提出的相互关联的多个因素的观察。

A. 实施细节

我们在ORB-SLAM2框架下实现了所提出的方法[28]。详细地说，我们的方法是在 ORB-SLAM2 的局部地图部分的每个局部BA 之前执行的。我们没有使用 ORB-SLAM2 的原始实现，而是以两种方式对其进行修改。首先，我们将现有的多线程处理更改为单线程处理，以便 1） 客观评估总运行时，2） 确定性性能评估，以及 3） 由于处理延迟而禁用优化步骤中的帧丢失。 其次，由于在 ORB-SLAM2 中决定关键帧的条件取决于来自本地建图线程的跟踪点数以及本地建图线程的状态，因此当应用单线程处理或点稀疏化时，本地 BA 执行的数量会发生变化。因此，使用取决于平移和旋转变化量的确定性关键帧插入标准来衡量所提出的点稀疏化的影响。在整个实验过程中，我们设定θf到边缘容量的一半。为了解决最小成本最大流量图问题，我们使用Google优化研究工具[1]，这是一个开源，快速和可移植的软件套件，用于解决组合优化问题。

Figure 3: 与表I相关的EuRoC总运行时间和有效值。

表一： EuRoC序列上的选定点和关键帧比率

B. 评估指标

我们使用绝对轨迹误差 RMS （ATE） [32] 进行姿态精度测量，这意味着通过计算估计姿态和地面真实姿势之间的绝对距离来估计轨迹的全局一致性。由于代表与地面真实姿势的平均偏差的ATE概念比代表轨迹局部精度的相对姿态误差（RPE）更适合评估生成的视觉地图的精度，因此我们评估旋转姿态精度与ATE相同。

表二： 所提方法在多个m上的比较。序列从顶部开始是 tum、icl-nuim 和 scannet。Rms吃的表示为与原始结果的相对差异。低于原始值的错误值以粗体显示。

表三： 立体声模式下使用kitti在户外环境下的实验结果

C. 效果评估

我们在各种数据集上评估了所提出的方法，包括EuRoC [4]，TUM [32]，ScanNet [9] ICL-NUIM [19]和KITTI [15]。EuRoC 是从微型飞行器 （MAV） 收集的流行室内视觉惯性数据集，其中包含同步立体图像、IMU 测量值及其地面实况姿势。每个单独的位置有 3-5 个不同的轨迹;机器大厅（MH），Vicon Room1（VI）和Vicon Room2（V2），它提供了各种序列，可在小型和大型室内环境中进行平稳或激进的运动。在这里，我们使用EuRoC数据集进行立体声实现，不使用IMU传感器数据。请注意，我们从实验中排除了 V2 数据，因为 ORB-SLAM2 由于其严重的旋转运动、运动模糊和照明变化，无法从数据集中产生良好的姿势轨迹。表I和图3显示了立体模式下EuRoC数据集的实验结果。地图点的数量在M参数。在以下情况下： M=100，MH的地图点减少量平均达到76%，这是一个在原始模式下平均生成约20，000个地图点的大地方。对于较小的VI，地图点的数量减少了60%。在M=200和300，观察到少量减少。关键帧的数量也会减少多达 66%，因为减少它们所连接的地图点会导致连通性低于阈值的关键帧自动丢失。

因此，整体处理时间也大大减少，因为通过减少约束数量，束调整和跟踪过程的时间消耗显着增加。图3显示了表I中实验的总运行时间和RMS ATE的图表。结果表明，我们提出的方法将运行时间减少到大约三分之一，同时性能几乎保持不变甚至提高。如果误差与原始错误相比增加，则ATE的差异最多在4厘米以内。为M=300，点/帧/时间略微减少了约20%，但所有套装的表现都优于原版。可以解释为所提出的方法通过不平衡属于姿势的约束，仅成功删除了对优化有负面影响的点。然后，我们使用各种RGB-D室内数据集的子集（包括TUM，ScanNet和ICL-NUIM）评估所提出的方法在各种相机配置中的性能。TUM提供颜色和深度图像，来自Microsoft Kinect传感器的加速度计数据，以及传感器的真实轨迹。我们使用来自TUM的6个序列，这些序列在其他研究中经常使用。ScanNet 是一个大型 RGB-D 数据集，可为各种任务提供详细的标签，包括 3D 对象分类、实例级语义分割。其多样化、逼真的环境和准确的地面事实使其成为视觉 SLAM 的高质量基准。ICL-NUIM数据集包含两种不同合成场景（客厅和办公室场景）的颜色，深度图像和地面测量值。我们使用ICL-NUIM的所有序列。表 II 显示了跨多个 RGB-D 数据集的结果M值。范围M由于与 EuRoC 数据集相比，空间比例不同且生成的地图点较少，因此设置不同。为M=100，地图点减少到平均 40%，关键帧数量减少到 60%，时间减少到 74%。同时，平均 ATE 和一个TEr与原版相比有所下降，即使高于原版，差异也不超过1cm和0.6°。也为M=140，200，误差也会减小，同时占用内存和时间增益。

表四： 与包括原始结果在内的安姆斯点选择进行比较。吃得最低的均方根以粗体显示。

图1是ScanNet的场景OOOO上保存的地图点的可视化，以及根据估计轨迹获得的场景的三维重建环境。在原始地图中，观察到点分布不成比例的区域，例如地板上的瓷砖接缝、地毯图案和沙发。在同一环境中，采用所提出的稀疏化方法的 SLAM 存在明显差异。在上述密集区域中，点的数量随着点的空间均匀选择而大大减少，因此具有点聚类的区域几乎不在少数。我们在原始地图的某些区域（例如垃圾桶、冰箱或门）中观察到少量点，因为纹理较弱，并且查看这些区域的姿势数量很少。使用所提出的方法，这些点可以很好地保留，因此在跟踪或定位场景时不会放弃该区域。因此，在为原始版本提供强大性能的设置中，即使在低纹理环境中，它也不会失败或没有显着降级。但是，值得考虑通过调整容量进行适度的稀疏M根据视觉场景的特点适当或调整稀疏区间。

Figure 4: 图像上选定关键点的可视化。从上到下，原创，安姆斯，我们的。右下角的图像显示了关键点的覆盖范围和聚类性。

我们使用KITTI数据集进行户外实验。表III显示了实验结果M=100，200 表示三个序列 07、08 和 10。与室内环境在相对较小的空间范围内需要许多地图点和多个连接并具有许多重新查看点不同，关键帧丢弃在室外环境中并不经常发生。时间增益也不像室内那么显着。但是，当像在室内的其他结果一样保守地执行地图点选择时，也会观察到性能改进。

D. 比较

自适应非极大抑制（ANMS）算法[2]通过高效计算[3]，[14]选择要均匀分布的图像上检测到的关键点，从而提高SLAM和图像配准的性能。当选择足够数量的键点时，与topM [30]或存储桶[24]方法相比，ANMS在可视化SLAM上获得了更好的结果。我们研究了选择优先于空间分布的点在点数显著减少时的效果，正如我们在这里所建议的那样。表IV显示了以最低的点选择比率应用ANMS时的结果，以及根据ANMS生成的地图点总数应用我们的方法时的结果。结果显示为第 IV-C 节中使用的四个数据集中每个数据集的平均值，以及术语连接。指每个点的平均连接数。我们的方法显示3个案例中有4个的结果比ANMS和原始结果更好。图4是通过AMS和我们的方法在一个图像中选定的局部兴趣点的可视化。ANMS选择的点均匀分布，如图所示。然而，在选择有限数量的点的过程中，当给定一个具有远程和低连通性的点时，考虑空间分布只会派生出具有高连通性的落点。因此，整体点连通性变弱。这也可以通过关键帧的数量来确认，与 ANMS 相比，我们的方法具有明显更少的关键帧，而地图点的数量几乎相同，因为我们在 ORB-SLAM2 中保留了自动剔除连接数量少于一定数量的关键帧的过程。这意味着仅保留具有主连接的地图点和观察它的关键帧，并且仅看到其他帧未注意到的点的关键帧被所提方法抽取。因此，当考虑到关键帧的内存消耗要高得多时，它不仅在内存增益方面受益匪浅，因为它们包含的信息比地图点多得多，而且还通过修剪点和帧之间的大量匹配来显着降低捆绑调整的成本。在ICL-NUIM的情况下，这是ANMS表现更好的唯一数据集，数据是在小尺度空间中获取的，很少重新查看同一区域，移动相机几乎只有旋转运动，而位置固定在空间的中心。结果，连接的差异。与其他组相比并不大，只需在空间中均匀分配点即可有效地管理比赛。通过这个实验，我们声称连通性是有效减少点数以保持性能的任务的关键因素。

表五： 在 tum 数据集上以部分和全部成本消除姿势精度。越高C,F和S，越好。吃得越低越好。每个数据序列的所有成本的最佳值以粗体显示。

E. 消融研究

我们评估了第 IV-C 节中提出的三项费用的有效性：cc是为了最大化姿势连接，cs是为了最大化空间多样性，以及cb用于最大化关键帧对的姿势基线长度。 为了了解每种成本的有效性，我们在表V中提供了对TUM数据集进行的额外实验。特别是，我们考虑四种情况：所有成本，cc只cc+cs和cc+cb因为主要的制约成本是cc如第四-D节所述。对于每个序列，除了 ATE 之外，我们还观察到以下属性：

C： 每个点具有关键帧的平均连接数

F： 点上连接的关键帧之间的最大顺序差

S： 大小为 64x48 的图像网格上按点划分的空间占用率平均百分比

如表五所示，当cs与cc，ATE降低量明显大于cc只。此外，与cc、性能cc+cs比cc+cb.有了这个，我们可以观察到，正如其他研究表明的那样，空间分布在很大程度上有助于减少误差。cc+cb有助于选择强特征并保持多个帧之间的联系，因此与cc并且帧序列间隔最大化。当使用这三种成本时，通过在较大的基线上更多地使用帧，同时最大限度地提高姿势连通性和空间多样性，可以实现最低的 ATE。

F. 本地化测试

所提方法的点稀疏化能力和位姿轨迹估计性能在前几节中进行了说明。更进一步，我们使用从同一场景中收集的两组序列，根据原始地图和稀疏地图检查姿势定位精度。 我们使用来自EuRoC数据集的MH01和MH02以及来自ScanNet的sceneOOOO_OO和sceneOOOO_Ol。MH01和sceneOOOO_OO用于以两种模式构建参考图，原始模式和稀疏模式，用于使用MH02进行定位，sceneOOOO_Ol。序列MH02和sceneOOOO_Ol相对于两个图谱的定位结果如表VI所示。在MH01的情况下，与原始地图相比，稀疏地图仅包含23.9%的点和34.4%的关键帧。由于地图加载时间、初始位置搜索时间和匹配时间的增加，总定位时间减少到 68.4%。尽管计算时间和地图大小都有显著减少，但查询序列MH02的每个帧姿态计算的RMS ATE甚至有所减少。同样，与原始地图相比，sceneOOOO仅使用38.6%的点和59.1%的关键帧，并且姿势误差也减少了。

表六： 本地化准确性评估

五、结论

我们为SLAM引入了一种基于图的点稀疏化方法。该方法在点稀疏化过程中同时实现了三个目标：点连通性最大化、空间多样性最大化和帧基线长度最大化。 以ORB-SLAM2为基准，我们提出的方法提供了更小的地图尺寸，同时保持甚至提高了局部建图过程中的姿态跟踪精度。我们进行了广泛的评估，并证明了所提出的方法可以有效地构建尺寸显著减小的特征图，并且其他框架可以针对稀疏化图进行准确的定位。我们提出的方法可用于地图创建后的后压缩或全局束平差之前的预处理。它通常适用于本地特征基础 SLAM 系统，包括多传感器 SLAM，并提供有效的地图抽取和加速，适用于其他计算具有挑战性的环境，如可穿戴设备。本研究的未来方向包括用于快速优化的边际图优化，以及除了3D特征多样性之外还考虑2D点的空间密度。

code——>experiment——>paper