英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
2D 激光雷达SLAM中的实时闭环检测
引言
便携式激光测距仪，称为LIDAR，同时定位和制图（SLAM）是获取竣工楼层平面图的有效方法。实时生成和绘制楼层平面图有助于操作员评估捕获数据的质量和覆盖范围。在有限的计算资源下构建便携式捕获平台是非常有必要的。我们介绍了一种在mapping平台后台使用的方法，该平台以5cm的分辨率实现了实时绘图和闭环检测。为了实现实时闭环检测，我们使用分支上界方法计算scan-to-submap匹配作为约束。我们提供实验结果并与其他众所周知的方法进行比较，这些方法表明，在质量方面，我们的方法与已有技术相比具有竞争力。
1.介绍
建立平面图适用于各种应用。用于收集建筑物管理任务的数据的人工调查通常将计算机辅助设计（CAD）与激光卷尺相结合。这些方法很慢，并且人类对建筑物的偏见会视为直线集合，这并不总是能够准确地描述空间的真实本质。使用SLAM，可以快速准确地调查较大的和复杂程度较高的建筑物，这些建筑物通过手动调查需要花费更长的时间。
在这个领域应用SLAM并不是一个新想法，也不是本文的重点。相反，本文的贡献是一种新的方法，用于降低计算激光范围数据的闭环约束的计算要求。这项技术使我们能够绘制数十万平方米的非常大的楼层，同时为操作员提供实时全面优化的结果。
2.相关工作
scan-to-scan匹配经常用于计算基于激光的SLAM方法中的相对姿势变化，例如[1] -[4]。然而，就其本身而言，scan-to-scan匹配会迅速累积误差。
scan-to-map匹配有助于限制错误的累积。一种使用Gauss-Newton在线性插值地图上找到局部最优的方法是[5]，在存在良好的姿势初始估计的情况下，在这种情况下通过使用足够高的数据速率LIDAR提供，本地优化的scan-to-map匹配是有效且稳健的。在不稳定的平台上，使用惯性测量单元（IMU）将激光扇投影到水平面上来估计重力方向。
像素精确扫描匹配方法，例如[1]，进一步减少局部误差累积。虽然计算成本更高，但这种方法对于闭环检测也有用。一些方法侧重于通过匹配激光扫描中提取的特征来提高计算成本[4]。其他用于闭环检测的方法包括基于直方图的匹配[6]，扫描数据中的特征检测以及使用机器学习[7]。
解决剩余局部误差累积的两种常用方法是粒子滤波器和基于图的SLAM [2]，[8]。
粒子滤波器必须保持每个粒子中完整系统状态的表示。对于基于网格的SLAM，随着地图变大，这很快就会变得非常耗费资源。例如我们的一个测试案例是22,000平方米，收集超过3公里的路程。可以使用较小的维度特征表示，例如[9]，其不需要每个粒子的网格图，以减少资源需求。当需要最新的网格图时，[10]建议计算子图，仅在必要时更新，以便最终的图是所有子图的光栅化。
基于图形的是一种工作于基于位姿和特征的节点集合的方法。图中的边表示从观察中生成的约束。可以使用各种优化方法来最小化由所有约束引入的误差，例如[11]，[12]。在[13]中描述了这种用于室外SLAM的系统，其使用基于图的方法，局部的scan-to-scan匹配以及基于子图特征的直方图的重叠局部图的匹配。
3.系统概述
Google的cartographer提供了一种实时的室内地图解决方案，这种方法是基于激光雷达的，可生成r = 5cm分辨率的2D网格地图。系统的操作员可以看到在建筑物中巡航时创建的地图。激光扫描的数据被插入到最佳估计位置的子图中，这个最佳的位置假定在短时间内足够准确。扫描匹配发生在最近的子图上，因此它仅取决于最近的扫描，并且在世界坐标系中的位姿估计的误差会累积。
综合硬件条件，为了获得良好的性能，我们的SLAM方法不使用粒子滤波器。为了应对错误的积累，我们定期进行位姿优化。当一个子图完成后，就不会再插入新的扫描，它会参与闭环检测中的扫描匹配。所有已完成的子图和扫描都会自动进行闭环检测。如果它们与基于当前位姿估计足够接近，则扫描匹配器尝试在子图中找到对应的扫描。如果在当前估计的位置的周围搜索窗口中找到足够好的匹配结果，则将其作为优化问题的闭环检测的约束条件。通过每隔几秒进行一次闭环检测，按照经验来说是一个位置在被重新访问时就算达到闭环。这会导致软实时约束，即闭环检测扫描匹配必须比添加新的扫描数据到子图中更快地发生，否则它明显落后。我们通过使用分支定界方法，然后对于每个完成的子图有对应的几个预先计算的网格来实现这一点。
4.局部二维的SLAM
我们的系统将单独的局部和全局方法结合到2D SLAM中。 两种方法都优化了位姿，位置的表示euro;=（euro;n，＆y，euro;）由LIDAR观测的平移量（x，y）和9自由度旋转量组成，其称为扫描集（scans）。 在不稳定的平台上，例如我们的平台，采用IMU估计重力方向，将扫描集从水平安装的LIDAR投影到2D平面上。
在我们的局部方法中，使用非线性优化将每个连续的点集与整个地图的一小块（称为子图M）进行匹配，该非线性优化将扫描点集与子图对齐; 该过程称为扫描匹配（scan matching）。 扫描匹配会随着时间累积误差，后来我们通过全局方法将其去除，如第V节所述。
- 扫描集（scans）
子图构造是重复对齐扫描和子图坐标帧的迭代过程，进一步称为帧。由于扫描的原点，我们现在将有关扫描点的信息写为。子图帧中扫描的帧的位姿xi;表示为变换，它将扫描点从扫描帧严格转换为子图帧，定义为
B．子图（submaps）
一个子图是由连续的几个扫描帧（scan）建立的，这些子图是使用概率网格M表示的，M： ，从给定分辨率r（例如5cm）的离散网格点到值的映射。这些值可以被认为是网格点被阻挡覆盖的概率。 对于每个网格点，我们将相应的像素定义为包含了所有靠近这个网格点的扫描点。
每当要将一帧扫描数据加入到概率网格中时，一个包含网格点的hits集合以及一个miss集合都会被重新计算。 对于每次hit，我们将最近的网格点插入到hit集合中。 对于每个miss，我们插入与每个像素相关联的网格点，这些像素与扫描原点和每个扫描点之间的线相交，这些点不包括已经在hit集合中的网格点。 如果在这些集合中的一个里面，则每个以前未观察到的网格点被分配概率。如果已经观察到网格点x，我们更新hits和misses的概率值（hit的修改）：
对于miss的网格点的概率修改也是一样的。
Fig. 1. 网格点和相关联的像素
Fig. 2. 与hit集合（阴影和划掉）和miss集合（仅阴影）相关联的扫描和像素
C. Ceres扫描匹配
在将扫描插入子图之前，使用基于Ceres的扫描匹配器[14]相对于当前本地子图优化扫描位姿。 扫描匹配器负责找到最大化子图中扫描点处的概率的扫描姿势。 我们把它作为一个非线性最小二乘问题：
其中根据扫描位置将从扫描帧变换到子图帧。函数 ： 是局部子图中概率值的平滑版本。我们使用双三次线性差值，可能在区间[0,1]之外存在结果的值，但被认为是没有影响的。
这种平滑函数的数学优化通常比网格的分辨率提供更好的精度。 由于这是局部优化，因此需要良好的初始估计。 能够测量角速度的IMU可用来估计扫描匹配之间位置的旋转分量theta;。 尽管计算量更大，但可以在没有IMU的情况下使用更高频率的扫描匹配或像素精确的扫描匹配方法。
5.闭环的实现
由于扫描集合仅仅与包含少量近期扫描的子图匹配，因此上述方法会慢慢累积错误。 对于仅几十次连续扫描，累积误差很小。
通过创建许多小子图来处理更大的空间，我们的方法可以优化所有扫描和子图的位姿，遵循稀疏姿势调整[2]。 插入扫描的相对姿势存储在存储器中以用于闭环检测优化。 除了这些相对姿势之外，一旦子图不再发生变化，所有其他由扫描和子图组成的对都被认为是闭环。 扫描匹配器在后台运行，如果找到良好匹配，则会将相应的相对姿势添加到优化问题中。
- 优化问题
与扫描匹配一样，循环闭包优化也被公式化为非线性最小二乘问题，允许轻松添加残差以考虑其他数据。 每隔几秒钟，我们使用Ceres [14]计算子图位姿的解决方案
并根据一些约束优化世界中的扫描姿势，这些约束采用相对位姿的形式和相关的协方差矩阵。对于一对子图 I 和扫描 j，位姿描述了扫描匹配的子图坐标系的位置。协方差矩阵可以按照[15]中的方法进行评估，或者使用Ceres [14]和（CS）的协方差估计特征进行局部评估。 这种约束的残差E由下式计算
损失函数p，例如Huber损失，用于减少当扫描匹配为优化问题添加不正确约束时可能出现在（SPA）中的异常值的影响。 例如，这可能发生在局部对称环境中，例如办公室隔间。 异常值的替代方法包括[16]。
B. 分支定界扫描匹配
我们感兴趣的是最佳像素精确匹配
其中ώ是搜索窗口，是M扩展到所有，通过将其参数舍入到最近的网格点，即将网格点的值扩展到相应的像素。 使用（CS）可以进一步提高匹配的质量。
通过仔细选择分辨率来提高效率，我们选择角度步长，使得最大范围处的扫描点移动超过r（一个像素的宽度）。通过余弦定理，我们推出：
我们计算了包含给定线性和角度搜索窗口大小的整数步骤。例如：7m，，
这导致一个有限的集合w形成一个围绕在一个估计为的中心的搜索窗口，
一个找到的简单的算法很容易制定，参见算法1，但对于搜索窗口的大小，我们考虑到这将会很慢。
相反，我们使用分支定界发在较大的搜索敞口上可以有效的计算。有关通用的算法请参见算法2。这种方法首先在混合整数线性程序的背景下提出[17]。关于这个主意的文献很多，见[18]简短概述。
主要思想是将可能性表示为树中的节点，其中根节点表示所有可能的解，在我们的实例中为w。每个节点中的子节点形成其父节点的分区，因此它们一起表示同一组可能性。叶节点是单体；每个代表一个可行的解决方案。请注意，算法是准确的，它提供了与算法1相同的解决方案，只要内部节点c的得分score(c)是其元素得分的上限即可。在这种情况下，每当节点有界时，在该子树中不存在比目前最熟知的解决方案更好的解决方案。
为了得到具体的算法，我们必须决定节点选择，分支和上界计算的方法。
1）节点选择：在没有更好的替代方案的情况下，我们的算法使用深度优先搜索（DFS）作为默认选择：算法的效率取决于被修剪的树的大部分。 这取决于两件事：良好的上限和良好的当前解决方案。 后一部分由DFS帮助，它可以快速评估许多的叶节点。 由于我们不希望将不良匹配作为循环结束约束添加，我们还会引入一个分数阈值，低于该分数阈值表示我们对最优解决方案不感兴趣。 由于实际上不会经常超过阈值，这些降低了节点选择或找到初始启发式解决方案的重要性。 关于在DFS期间访问子节点的顺序，我们计算每个子节点的分数的上限，访问具有最大边界的最有希望的子节点，算法3采用的就是这种方法。
2）分支规则：树中的每个节点描述为整数元组，高度为的节点，最多可组合代表 X 种可能的平移和一种特定的旋转。
叶节点具有高度=0，并且对应于可行解。
在我们的算法3的公式中，包含所有可行解的根节点没有明确的出现并且分支成一组初始节点（固定高度为）覆盖搜索窗口。
对于一个给定的节点c，且gt;1，我们分成最多四个高度为-1的子节点
3）计算上界：分支定界法的剩余部分是计算内部结点上限的有效方式，包括计算工作量和边界质量。我们使用
为了能够有效的计算最大值，我们使用预先计算的网格，预先计算每一个可能高度为的一个网格，允许我们在扫描点的数量上计算得分。请注意，为了能够做到这一点，我们还计算了的最大值，它可以大于，靠近我们搜索空间的边界。
与之前的叶节点一样。需要注意的是与具有相同的像素结构，但是在每个像素中存储的是从那里开始的像素盒的最大值，这种预先计算的网格的一个例子如图三所示。
为了使构建预先计算的网格的计算工作量保持在较低水平，我们要等到概率网格不再接收更新。 然后我们计算一组预先计算的网格，并开始匹配它。
对于每个预先计算的网格，我们计算从每个像素开始的宽为像素的行最大值。使用这个中间结果，然后构造下一个预先计算的网格。
如果按照添加顺序删除值，则可以按O（1）的时间复杂度去保持更新的值集合的最大值。连续最大值保存在一个双端队列中，可以递归地定义为包含当前集合中所有值的最大值，然后是第一次出现最大值后所有值的连续最大值列表。对于空值集合，此列表为空。使用这种方法，可以在O（n）的复杂度中计算预先计算的网格，其中n是每个预先计算的网格中的像素数。
计算上限的另一种方法是计算较低分辨率的概率网格，连续减半分辨率，见[1]。由于我们的方法的额外内存消耗是可接受的，我们更喜欢使用较低分辨率的概率网格，这导致产生比（15）更差的界限，从而对性能产生负面影响。
6.实验结果
在本节中，我们使用在backpack上交互使用的相同的在线算法，从记录的传感器
全文共7860字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[809]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
