英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
二维激光雷达SLAM中的实时环路闭合
摘要
便携式激光测距仪（又称激光雷达）和同步定位与绘图（SLAM）是获取竣工平面图的有效方法。实时生成和可视化平面图有助于操作员评估采集数据的质量和覆盖范围。构建便携式捕获平台需要在有限的计算资源下操作。我们介绍了在我们的背包映射平台中使用的方法，该平台以5厘米的分辨率实现实时映射和循环闭合。为了实现实时的循环关闭，我们使用一种分支定界的方法来计算子映射匹配作为约束的扫描。我们提供了实验结果，并与其他众所周知的方法进行了比较，这些方法表明，在质量方面，我们的方法与现有技术具有竞争力。
1引言
竣工平面图可用于各种应用。收集这些数据用于建筑管理任务的人工测量通常将计算辅助设计（CAD）与激光磁带测量相结合。这些方法是缓慢的，并且，通过将人类对建筑物的先入为主的观念作为直线的集合，并不总是准确地描述空间的真实性质。使用SLAM，可以快速、准确地测量建筑物的大小和复杂程度，而人工测量则需要更长的时间。
在这一领域应用SLAM并不是一个新的想法，也不是本文的重点。相反，本文的贡献是一种新的方法，减少了从激光测距数据计算回路闭合约束的计算要求。这项技术使我们能够绘制非常大的楼层，几万平方米，同时为运营商提供实时的完全优化结果。
2相关工作
扫描与扫描点的匹配经常用于计算基于激光的SLAM方法中的相对位置变化，例如[1]–[4]。然而，扫描与扫描点的匹配本身很快积累了错误。
扫描与扫描到地图上的匹配有助于限制错误的累积。其中一种方法是[5]，它使用高斯牛顿在线性插值图上找到局部最优。假如在存在良好的位置初始估计的情况下，通过使用足够高的数据率激光雷达，局部优化扫描地图匹配是有效和稳健的。在不稳定的平台上，激光风扇投射到使用惯性测量单元（IMU）的水平面估计重力方向。
像素精确扫描匹配方法，如[1]，进一步减少了局部误差积累。虽然计算成本更高，但这种方法对于环路闭合检测也很有用。一些方法侧重于通过匹配从激光扫描中提取的特征来提高计算成本[4]。环闭合检测的其他方法包括基于直方图的匹配[6]、扫描数据中的特征检测和使用机器学习[7]。
解决剩余局部误差累积的两种常见方法是粒子滤波和基于图的SLAM[2]，[8]。
粒子过滤器必须在每个粒子中保持完整系统状态的表示。对于基于网格的SLAM，随着地图变大，这很快变得资源密集；例如，我们的一个测试案例是在3公里的轨道上收集到22000平方米的空间。较小的尺寸特征表示，例如[9]，不需要为每个粒子绘制网格图，可以减少资源需求。当需要最新的网格地图时，[10]建议计算子地图，只有在必要时才更新子地图，这样最终的地图就是所有子地图的光栅化。
基于图的方法可以处理表示姿势和特征的节点集合。图中的边是由观测生成的约束。可以使用各种优化方法来最小化所有约束带来的误差，例如[11]、[12]。这样一个使用基于图形的方法、本地扫描到扫描匹配和基于子映射特征直方图的重叠本地映射匹配的室外SLAM系统在[13]中进行了描述。
3系统概述
谷歌地图绘制者提供了一个实时的室内地图绘制解决方案，它是一个配备传感器的背包，可以生成分辨率为r=5厘米的二维网格地图。该系统的操作员可以在穿过建筑物时看到正在创建的地图。激光扫描被插入到一个最佳估计位置的子图中，这假设是足够准确的短期时间。扫描匹配产生在最近的子图上，因此它只依赖于最近的扫描，并且在整体帧中位置估计的误差会累积。
为了在适当的硬件要求下获得良好的性能，我们的SLAM方法不使用粒子过滤器。为了应对误差的累积，我们定期进行位置优化。当一个子映射完成后，即不再插入新的扫描，它将参与循环关闭的扫描匹配。所有完成的子图和扫描都会自动关闭循环。如果根据当前的位置估计，它们足够接近，扫描匹配器将尝试在子映射中查找扫描。如果在搜索窗口中围绕当前估计的位置找到一个足够好的匹配，那么它将作为循环关闭约束添加到优化问题中。通过每隔几秒钟完成一次优化，操作员的经验是，当重新访问某个位置时，立即关闭循环。这导致了软实时约束，即循环闭合扫描匹配必须比添加新的扫描更快地进行，否则就会明显落后。我们通过使用分支绑定方法和每个完成的子映射的几个预计算网格来实现这一点。
4局部二维同步定位与绘图
我们的系统结合了分离局部和整体方法来处理二维同步定位与绘图。这两种方法都优化了由激光雷达观测的（x，y）平移和旋转组成的位置，，进一步称为扫描。在一个不稳定的平台上，比如我们的背包，IMU被用来估计从水平安装的激光雷达向二维世界投射扫描的重力方向。
在我们的局部方法中，每一个连续的扫描都与整体上的一小块区域（称为子图M）匹配，使用非线性优化将扫描与子图对齐；这个过程进一步称为扫描匹配。扫描匹配会随着时间的推移累积错误，这些错误随后会被我们的全局方法消除，这在第五节中进行了描述。
A扫描
子图构造是重复对齐扫描和子贴图坐标帧(也称为帧)的迭代过程。扫描原点为，我们现在将扫描点的信息写成子图帧中扫描帧的姿势表示为变换，它将扫描点从扫描帧硬转换为子帧，定义为
B.子映射
几个连续的扫描用于构建子映射。几个连续的扫描用于构建子映射。这些子网格采用概率网格M:的形式，它从给定分辨率r（例如5 cm）的离散网格点映射到值。这些值可以被认为是一个网格点被阻塞的概率。对于每个网格点，我们定义相应的像素，由最接近该网格点的所有点组成。
图1 网格点和相关像素
每当扫描插入概率网格时，都会计算出一组命中网格点和一组不相交的未命中网格点。对于每次命中，我们都将最近的网格点插入命中集。对于每一次未命中，我们插入与每个像素相关的网格点，该像素与扫描原点和每个扫描点之间的一条光线相交，不包括已经在命中集中的网格点。如果每个以前未观察到的网格点位于其中一个集合中，则会分配一个概率或。如果已经观察到网格点x，我们将命中和未命中的几率更新为
和未命中的同等。
图2与点击（阴影和划线）和未命中（仅阴影）相关的扫描和像素
C.CERES扫描匹配
在将扫描插入子映射之前，使用基于ceresbased[14]的扫描匹配器，相对于当前的本地子映射优化扫描姿势xi;。扫描匹配器负责找到一个扫描姿势，该扫描姿势最大化了子映射中扫描点的概率。我们把这看作一个非线性最小二乘问题。
其中根据扫描姿势将从扫描帧转换为子帧。函数是局部子映射中概率值的平滑版本。我们使用双三次插值。因此，可以出现间隔[0，1]之外的值，但被认为是无害的。
这种平滑函数的数学优化通常比网格的分辨率更精确。因为这是一个局部优化，所以需要很好的初始估计。能够测量角速度的IMU可以用来估计扫描匹配之间位置的旋转分量theta;。在没有IMU的情况下，可以使用更高的扫描匹配频率或像素精确的扫描匹配方法，尽管计算量更大。
5闭合回路
由于扫描只与包含最近几次扫描的子图匹配，因此上面描述的方法慢慢积累了错误。只有几十次连续扫描，累积误差很小。
较大的空间是通过创建许多小的子对象来处理的。我们的方法，优化所有扫描和子扫描的位置，遵循稀疏位置调整[2]。插入扫描的相对位置存储在内存中，以用于循环关闭优化。除了这些相对位置之外，一旦子位置不再变化，所有其他由扫描和子位置组成的对都将被视为循环闭合。在后台运行一个扫描匹配器，如果发现匹配良好，则将相应的相对位置添加到优化问题中。
A.优化问题
循环闭合优化，如扫描匹配，也被表述为一个非线性最小二乘问题，它允许很容易地添加残差来考虑额外的数据。每隔几秒钟，我们使用CERES[14]计算一个解决方案:
在给定一些约束条件下，对整体上的子映射和扫描
位置进行了优化。这些约束形式为相对位置和相关协方差矩阵。对于一对子图 i和扫描j，位置描述了子图坐标系中扫描匹配的位置。协方差矩阵可以按照[15]中的方法进行评估，也可以使用CERES[14]WITH(CS)的协方差估计特性进行局部评估。这种约束的剩余E是由下面的式子计算出来的
损失函数，例如Huber损失，用于减少扫描匹配为优化问题添加不正确约束时（SPA）中可能出现的异常值的影响。例如，这可能发生在局部对称的环境中，例如办公室隔间。异常值的替代方法包括[16]。
B分支与绑定扫描匹配
我们对最佳的像素 精确匹配感兴趣，其中W是搜索窗口，是M点通过将它的参数四舍五入到最近的网格点（即将网格点的值扩展到相应像素）扩展到所有。使用（CS）公式可以进一步提高比赛的质量。
通过仔细选择台阶尺寸，提高了效率。我们选择了角度台阶尺寸，以便在最大范围处的扫描点移动不超过r，即一个像素的宽度。利用余弦定律，我们得出
我们计算一个包含给定线性和角度搜索窗口大小的积分步数，例如
和
这将导致形成搜索窗口的有限集W在其中心的估算值附近，
找到xi;的一个简单算法可以很容易地被公式化，参见算法1，但是对于搜索窗口的大小，就会考虑到它会太慢。
算法1：
相反，我们使用分支绑定方法在更大的搜索窗口上有效地计算。通用方法见算法2。这种方法首先是在混合整数线性规划的背景下提出的[17]。有关这一主题的文献非常广泛；请参阅[18]以获得简要概述。
主要思想是将可能的子集表示为树中的节点，其中根节点表示所有可能的解决方案，在我们的例子中是W。每个节点的子节点构成其父节点的一个分区，以便它们一起表示相同的可能性集。叶节点是单例的；每个节点表示一个可行的解决方案。注意算法是精确的。只要内部节点c的分值（c）是元素得分的上界解决方案就与naive方法相同的。在这种情况下，只要一个节点是有界的，这个子树中比就不会存在目前已知解更好的解。
为了得到一个具体的算法，我们必须确定节点选择、分支和上界计算的方法。
节点选择：在没有更好的选择的情况下，我们的算法使用深度优先搜索（DFS）作为默认选择：算法的效率取决于被修剪的树的很大一部分。这要看两个事情：一个好的上限，一个好的当前解决方案。后一部分由DFS提供帮助，它可以快速评估许多叶节点。由于我们不想将较差的匹配作为循环关闭约束，因此我们还引入了一个分数阈值，低于该阈值，我们对最优解不感兴趣。由于在实践中通常不会超过阈值，因此这降低了节点选择或查找初始启发式解决方案的重要性。关于在DFS期间访问子节点的顺序，我们计算每个子节点得分的上限，首先访问最大边界的最常见子节点。这种方法是算法3。
2）分支规则：分支规则：树中的每个节点都由整数元组描述，即。高节点可以组合多达的可能转换，但表示特定的旋转：
叶节点高度，对应于可行解
在算法3的公式中，包含所有可行解的根节点没有显式出现，而是在覆盖搜索窗口的固定高度上分支到一组初始节点中。
在的给定节点处，我们将分支为最多四个子高度
计算上界：分支定界方法的其余部分是计算内部节点上界的一种有效方法，无论是计算工作量还是边界的质量。
为了能够有效地计算最大值，我们使用了预先计算的网格。预先计算每个可能高度的一个网格允许我们努力计算分数。扫描点的数量是线性的。为了能够做到这一点，我们还计算了上的最大值，该值在搜索空间边界附近可能大于
叶节点的xi;c与之前一样,注和具有相同的像素结构，但在每个像素中，存储从该像素开始的像素框的最大值。这种预计算网格的示例如图3所示。
图3 尺寸为1、4、16和64的预计算网格
为了使构建预计算网格的计算工作量保持在较低的水平，我们等待一个概率网格不会收到进一步的更新。然后我们计算一组预先计算的网格，并开始与之匹配。
对于每个预先计算的网格，我们计算从每个像素开始的像素宽行的最大值。使用这个中间结果，可以构造下一个预计算网格。
如果按照增加值的顺序删除值，则可在摊余O（1）中保持最新值的变化集合。连续最大值保存在一个双端队列中，该双端队列可以递归定义为包含集合中当前所有值的最大值，然后是最大值第一次出现后所有值的连续最大值列表。对于值的空集合，此列表为空。使用这种方法，可以在O（n）中计算预计算网格，其中n是每个预计算网格中的像素数。
另一种计算上界的方法是计算低分辨率概率网格，依次将分辨率减半，见[1]。由于我们的方法额外的内存消耗是可以接受的，因此我们更喜欢使用比（15）更低分辨率的概率网格，这会导致比（15）更差的界限，从而对性能产生负面影响。
6实验结果
在本节中，我们介绍了我们的SLAM算法的一些结果，这些结果是使用在背包上交互使用的相同在线算法根据记录的传感器数据计算得出的。首先，我们展示了使用传感器收集的数据得出的结果图4。德国博物馆二楼制图员地图。我们的制图者背包在慕尼黑的德国博物馆。第二，我们证明了我们的算法通过使用机器人真空吸尘器传感器收集的数据，可以很好地与便宜的硬件协同工作。最后，我们使用Radish数据集[19]显示结果，并将自己与发布的结果进行比较。
图4 德国博物馆二楼制图地图
A.现实世界实验：德国博物馆
利用在德国博物馆收集的1913个传感器数据或2253米的数据（根据计算结果），我们计算了图4所示的地图。在Intel Xeon E5-1650的3.2GHz工作站上，我们的SLAM算法使用1018s CPU时间，最多使用2.2GB内存和4个后台线程进行循环关闭扫描匹配。它在36世纪60年代的墙上时钟时间后完成，这意味着它实现了5.3倍的实时性能。
所生成的环闭合优化图由11456个节点和35300个边组成。每次将几个节点添加到图中时，都会运行优化问题（SPA）。一个典型的解决方案大约需要3次迭代，大约需要
全文共9642字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[2746]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
