这是用户在 2024-5-5 15:10 为 https://app.immersivetranslate.com/pdf-pro/bbff6302-523a-4b13-a48d-f415675298ee 保存的双语快照页面,由 沉浸式翻译 提供双语支持。了解如何保存?
2024_05_05_a26f94f63bbc037c066bg

 通用-ICP

Aleksandr V. Segal 斯坦福大学
电子邮件: avsegal@cs.stanford.edu

 德克-海内尔 斯坦福大学
电子邮件: haehnel@stanford.edu

 塞巴斯蒂安-特伦 斯坦福大学
电子邮件: thrun@stanford.edu

 摘要


在本文中,我们将 "迭代最邻近点"(ICP)算法和 "点到面 ICP "算法结合到一个单一的概率框架中。


然后,我们利用这一框架,从两次扫描中建立局部平面结构模型,而不是像点到面方法通常那样只建立 "模型 "扫描模型。这可以理解为 "平面到平面"。


新方法通过模拟数据和实际数据进行了测试,结果表明其性能优于标准的 ICP 和点到面方法。


此外,新方法对不正确的对应关系具有更强的鲁棒性,因此更容易调整大多数 ICP 变体中的最大匹配距离参数。


除了已证明的性能改进外,所提出的模型还允许将更具表现力的概率模型纳入 ICP 框架。


广义国际比较方案在保持国际比较方案的速度和简单性的同时,还可以增加离群项、测量噪声和其他概率技术,以提高鲁棒性。

 I.引言


近十年来,测距图像越来越受欢迎,在医学成像、物体建模和机器人等领域的应用也越来越广泛。


由于遮挡和传感器测距范围有限,这些应用大多需要精确的方法将多个测距图像合并成一个模型。


特别是在移动机器人领域,能够快速捕捉整个三维场景的测距传感器的出现大大提高了技术水平。


一个突出的例子是,在 DARPA 大挑战赛中,几乎所有参赛者都依赖快速扫描激光测距仪作为避障、运动规划和绘图的主要输入方法。


虽然 GPS 和 IMU 通常用于计算近似位移,但它们的精度不足以可靠地进行精确定位。


此外,还有许多情况(隧道、停车场、高楼)会阻碍 GPS 接收,进一步降低精确度。为了克服这一缺陷,大多数应用都依靠扫描匹配测距数据来完善定位。


尽管使用范围如此广泛,但解决扫描匹配问题的典型方法自问世以来基本未变。

 II.扫描


ICP 技术最初应用于扫描匹配是在 ,在过去的十五年中,已经提出了许多不同的方案。同期发表的三篇论文概述了目前仍被视为最先进的扫描匹配解决方案。


最常引用的算法分析来自 Besl 和 McKay[1]。[1]直接解决了用几何图形或点云描述的三维图形的注册问题。Chen 和 Medioni[7]则考虑了更具体的对象建模范围数据对齐问题。


他们的方法利用了大多数测距数据局部平面化的趋势,引入了 ICP 的 "点到平面 "变体。


Zhang[5]几乎同时描述了 ICP,但在算法的对应关系选择阶段增加了一种稳健的离群值剔除方法。

迭代双对应[15]和基于度量的 ICP [16]是两个更现代的替代方案。IDC 通过保持两组对应关系来改进点匹配过程。


MbICP 的设计初衷是在初始方向误差较大的情况下提高收敛性,方法是明确地将旋转误差作为距离度量的一部分来最小化。

大多数基于 ICP 的方法的主要优点是使用 kd 树进行闭合点查找时,操作简单,性能相对较快。


其缺点包括隐含的假设,即被匹配的形状完全重叠,以及理论上要求从已知的几何表面取点,而不是测量[1]。


部分重叠的扫描(取自不同位置)违反了第一个假设。第二个假设会造成问题,因为物理表面的离散程度不同,即使在收敛后也不可能获得各个点的精确重叠。


如文献[7]所建议的点到平面,通过不惩罚沿曲面的偏移来解决离散化问题。完全重叠假设通常通过在对应关系中设置最大距离阈值来处理。

除点到平面外,大多数 ICP 变体都使用封闭式解决方案,根据对应关系迭代计算配准。这通常是通过 [10] 或基于两个数据集的交叉相关性的类似技术来实现的。


最近,人们开始关注使用通用非线性优化技术,而不是更具体的封闭式方法 [9]。


这些技术的优势在于它们允许使用更通用的最小化函数,而不仅仅是欧氏距离之和。[9]利用非线性优化和稳健统计来显示更宽的收敛盆地。

我们认为,在这些技术中,概率技术是最有发展前景的,因为已有大量理论工作为其提供支持。文献[2]应用了一种概率模型,假设第二次扫描是通过随机过程从第一次扫描中产生的。


[4] 应用光线追踪技术,最大限度地提高对齐概率。

[8]建立了一组兼容的对应关系,然后在此分布上最大化配准概率。[17]引入了一个完全概率框架,其中考虑了运动模型,并允许对配准不确定性进行估计。


该方法的一个有趣之处在于,它采用了广义霍夫变换的采样类似方法来计算对齐,而无需明确的对应关系,同时考虑到二维数据集的两个表面法线。

还有大量文献致力于解决多扫描全局配准问题([18]和许多其他文献)。许多方法(特别是[18])都使用成对匹配算法作为基本组件。


这使得成对匹配的改进也适用于全局配准问题。

我们的方法介于标准 IPC 和全概率模型之间。它基于使用 MLE 作为非线性优化步骤,并使用 kd 树计算离散对应关系。


它的独特之处在于提供了对称性,并结合了 [7] 的结构假设。不过,由于最近点查找是通过欧氏距离完成的,因此 kd 树可以在大型点云上实现快速性能。


完全概率方法通常无法做到这一点,因为这些方法需要对分配计算 MAP 估计值。


与 [8] 不同的是,我们认为数据应假定为局部平面,因为大多数测距数据采样环境都是片状光滑表面。


通过对最小化过程进行概率解释,我们发现很容易将该技术扩展到包括来自两次扫描的结构信息,而不是像 "点到面 "ICP 通常那样只包括一次扫描的结构信息。


我们的研究表明,引入这种对称性可以提高精确度,降低对参数的依赖性。

与 IDC [15] 和 MbICP [16] 算法不同,我们的方法旨在处理大型三维点云。更重要的是,这两种方法在某种程度上与我们的技术是正交的。


虽然 MbICP 提出了另一种距离指标(我们也提出了),但我们的指标旨在考虑结构而非方向。


由于我们的技术并不依赖于任何特定类型(或数量)的对应关系,因此,如果像 IDC 那样加入第二组对应关系,我们的技术很可能会得到改进。

我们的方法与 [17] 的主要区别在于所涉及的计算复杂性。


[17]是为处理平面扫描数据而设计的--所建议的广义 Hough 变换要求将一个扫描中的每个点与另一个扫描中的每个点进行比较(或在采样情况下按比例进行比较)。


我们的方法使用 kd 树进行最近点查找,因此需要 明确的点比较。目前还不清楚如何将 [17] 中的方法有效地推广到本文所考虑的数据集。此外,这两种模型在理念上也存在差异。

本文首先总结了 ICP 算法和点对平面算法,然后介绍了广义 ICP,作为这两种标准方法的自然扩展。然后介绍了实验结果,这些结果凸显了广义-ICP 的优势。

 A.ICP


标准 ICP 算法的关键概念可概括为两个步骤:

  1. 计算两个扫描之间的对应关系。

  2. 计算一个变换,使相应点之间的距离最小。

迭代重复这两个步骤通常会收敛到所需的变换。由于违反了完全重叠的假设,我们不得不添加一个最大匹配阈值 。这个阈值考虑到了有些点在第二次扫描中没有任何对应关系(例如,在扫描 A 边界之外的点)。在大多数 ICP 实现中, 的选择是收敛性和准确性之间的权衡。值越小,收敛性越差(算法变得 "短视");值越大,不正确的对应关系会导致最终配准偏离正确值。标准 ICP 被列为 Alg.1.
input : Two pointclouds: \(A=\left\{a_{i}\right\}, B=\left\{b_{i}\right\}\)
            An initial transformation: \(T_{0}\)
output: The correct transformation, \(T\), which aligns \(A\)
                and \(B\)
\(T \leftarrow T_{0} ;\)
while not converged do
    for \(i \leftarrow 1\) to \(N\) do
        \(m_{i} \leftarrow\) FindClosestPoint \(\operatorname{InA}\left(T \cdot b_{i}\right)\);
        if \(\left\|m_{i}-T \cdot b_{i}\right\| \leq d_{\max }\) then
            \(w_{i} \leftarrow 1\)
        else
            \(w_{i} \leftarrow 0 ;\)
        end
    end
    \(T \leftarrow \underset{T}{\operatorname{argmin}}\left\{\sum_{i} w_{i}\left\|T \cdot b_{i}-m_{i}\right\|^{2}\right\} ;\)
end

算法 1:标准 ICP

 B.点对平面


ICP 的点到平面变体通过利用表面法线信息来提高性能。该技术最初由 Chen 和 Medioni[7] 提出,在 范围数据时,作为标准 ICP 的一种更稳健、更精确的变体而得到广泛应用。点到平面算法不是最小化 ,而是最小化沿表面法线(即 在表面法线所跨子空间上的投影)的误差。这一改进是通过修改 Alg.1 的第 11 行实现的。1 的第 11 行进行如下修改:

其中 处的表面法线。

 III.概括性 ICP

 A.推导


广义-ICP 的基础是在 Alg.1 第 11 行的最小化步骤中附加一个概率模型。1.该技术保持算法的其他部分不变,以降低复杂性并保持速度。


值得注意的是,对应关系的计算仍采用标准欧氏距离,而非概率测量。


这样做是为了在查找最近点时使用 kd 树,从而保持 ICP 相对于其他全概率技术的主要优势--速度和简单性。

由于只有第 11 行是相关的,因此我们将推导范围限制在这一行。为简化符号,我们假设已经执行了最近点查找,并且两个点云 根据其对应关系进行了索引(即 对应)。在本节中,我们还假设已从数据中删除了与 的所有对应关系。

在概率模型中,我们假设存在一组基本点,即 ,根据 生成 。在这种情况下, 是与测量点相关的协方差矩阵。如果我们假设完全对应(几何上一致,不存在由于遮挡或采样造成的误差),并进行正确的变换,即 ,我们可以知道

对于任意刚性变换 ,我们定义 ,并考虑 的分布。由于 假设来自独立的高斯分布、

应用公式 (1)。

现在,我们使用 MLE 来迭代计算 ,方法是设置

上述公式可简化为

这就是广义-ICP 算法的关键步骤。

通过设置

在这种情况下,(2) 变为

这正是标准的 ICP 更新公式。

然而,有了广义 IPC 框架,我们就可以更自由地模拟这种情况;我们可以自由地为 选择任意一组协方差。作为一个激励性的例子,我们注意到,点到平面算法也可以从概率的角度来考虑。

点到面 ICP 的更新步骤为

其中 的表面法线在跨度上的投影。这使得 及其表面法线所定义的平面的距离最小。由于 是正交投影矩阵,因此 。这意味着 可以重新表述为二次方形式:

按照这种格式计算(4),我们可以得到

通过观察上文与 (2) 的相似性,可以发现点到面 ICP 是广义 ICP 的极限情况。在这种情况下

严格来说, 是不可反的,因为它的秩是有缺陷的。但是,如果我们用一个可逆的 来近似 ,Generalized-ICP 就会像 一样接近点到平面。我们可以直观地将这种限制行为解释为 沿着平面法向量受限,而对其在平面内的位置一无所知。


B.应用:平面到平面


为了提高点到面的性能并增加模型的对称性,可以使用广义-ICP 来考虑两次扫描的表面信息。


最自然的方法是将第二次扫描的局部表面信息纳入 (7)。这种方法能抓住情况的直观本质,但在数学上并不可行,因为所涉及的矩阵是奇异的。


相反,我们利用点到面的直觉来激发一个概率模型。

点到平面算法的精髓在于,我们的点云不仅仅是 3 空间中任意点的集合,它实际上是测距传感器采样的曲面集合。这意味着我们要处理的是

图 1. 平面到平面的说明

3 空间中的采样 2-manifold。由于现实世界中的曲面至少是片断可微的,因此我们可以假设我们的数据集是局部平面的。


此外,由于我们是从两个不同的角度对流形进行采样,因此一般来说,我们不会对完全相同的点进行采样(即对应关系永远不会是精确的)。从本质上讲,每个测量点只提供了沿其表面法线的约束。


为了模拟这种结构,我们认为每个采样点沿其局部平面的协方差很大,而沿表面法线方向的协方差很小。如果一个点的表面法线为 ,则协方差矩阵为

其中 是一个小常数,代表沿正态线的协方差。这相当于以极高的置信度知道沿正态分布的位置,但不确定其在平面上的位置。我们将 都建模为从这种分布中提取。

明确地说,给定 - 以及 上各自的法向量,通过旋转上述协方差矩阵来计算,这样 项就代表了沿表面法线的不确定性。让 表示变换基向量 的旋转之一,设

然后通过 (2) 计算出转换结果

图 1 展示了算法在极端情况下的效果。在这种情况下,沿着绿色扫描垂直部分的所有点都错误地与红色扫描中的一个点相关联。


由于表面方向不一致,平面到平面将自动忽略这些匹配:每个对应关系的最终求和协方差矩阵将是各向同性的,相对于细小且定义清晰的对应关系协方差矩阵而言,对目标函数的贡献非常小。


对这种行为的另一种看法是将其视为每个对应关系的软约束。不一致的匹配允许红色扫描点沿 - 轴移动,而绿色扫描点则可沿 - 轴自由移动。因此,不正确的对应关系对整体配准形成了非常微弱且无信息的约束。

计算表面协方差矩阵需要与两个扫描中的每个点相关联的表面法线。


从点云中恢复表面法线的技术有很多,而法线的精度自然对算法的性能起着重要作用。


在实施过程中,我们对每个扫描点最近的 20 个点的协方差矩阵进行了 PCA 分析。在这种情况下,与最小特征值相关的特征向量与表面法线相对应。


这种方法可用于计算点到平面和广义-ICP 的法线。对于广义-ICP,旋转矩阵的构造是使 分量的方差与表面法线一致。

 IV.成果


我们对所有三种算法进行了比较,以测试所提技术的性能。虽然 在标准 ICP 中存在高效的闭式解,但我们使用共轭梯度实现了最小化,以简化比较。在两次扫描之间引入已知偏移量后,我们根据向正确解的收敛情况对性能进行了分析。


我们将标准 ICP 的测试限制在最多 250 次迭代,其他两种算法的测试限制在 50 次迭代,因为通常在此之前(如果有的话)就已经收敛了。

模拟数据(图 3)和真实数据(图 4)都被用来展示理论和实际性能。模拟数据集还允许在更广泛的环境中以绝对已知的地面实况进行测试。


室外模拟环境与收集到的数据不同,主要体现在遮挡的程度和地表的丘陵特征。


真实世界的室外测试还展示了更详细的特征和更具代表性的测量噪声的性能。

模拟数据是通过对安装在旋转关节上的 SICK 扫描仪进行光线跟踪生成的。在室内(图 2(a))和室外(图 2(b))创建了两个三维环境,以测试绝对地面实况的性能。


室内环境以办公室走廊为基础,室外环境则反映了建筑物周围的典型景观。在这两种情况下,我们都模拟了一个装有激光扫描仪的机器人沿着一条轨迹行进,并在沿途的固定点进行测量。


为了使测试更加真实,还加入了高斯噪声。

此外,还对一辆装有仪器的汽车记录的真实数据进行了测试。这些日志包括车顶安装的 Velodyne 测距仪记录的数据,当时汽车在郊区环境中行驶了一圈,并标注了 GPS 和 IMU 数据。


这使得应用基于成对约束的 SLAM 技术生成地面实况成为可能。
 (a) 室内场景
 (b) 户外场景

图 2. 仿真 3D 环境
 (a) 室内场景
 (b) 户外场景

图 3. 射线跟踪扫描 - 扫描 A 显示为绿色,扫描 B 显示为红色

图 4.Velodyne 扫描 - 扫描 A 显示为绿色,扫描 B 显示为红色

定位。虽然(标准)ICP 本身用于成对匹配以生成地面实况,但用于 SLAM 方法的扫描间距要小一个数量级。


相比之下,用于测试的扫描对是以更大的间距(15-20 多米)提取的,以解决更具挑战性的问题。


这并不是一个完美的生成地面实况的方法,但我们相信,它为算法之间的比较提供了一个合理的基准。

为了衡量性能,所有算法都在三个数据集的扫描对上运行。对于每一对扫描,初始偏移量都被设置为真实偏移量,并添加了统一生成的误差项。误差项设置在 范围内。通过对特定算法的所有扫描对的平均定位误差来衡量性能。在所有测试案例中,旋转误差都可以忽略不计。

如前所述, 的选择对 ICP 的收敛起着重要作用。图 5 显示了 不同值的平均误差;该图显示了所有扫描对的平均性能。图 9 显示了基于 理想值的单个扫描对的平均值;它显示了误差在扫描对范围内的分布情况。与图 5 不同的是,图 9 的每个数据点平均包含了大量随机初始偏移量,用于对可能的偏移量空间进行采样。图 9


在图 5 中,对每个扫描对运行了随机生成的 10 个初始位置的算法。对于图 9 中的曲线图,每个数据点都是使用最佳情况下的 ,以 50 个随机初始位置生成的。在所有情况下,误差条均按 计算。

图 5 中的曲线图显示,建议的算法对匹配阈值的选择更加稳健,总体性能更好。


这是意料之中的,因为它能更完整地模拟环境,并根据场景结构自动排除许多不正确的匹配。特别是,图 1 和图 2


5 表明,在模拟环境中,算法的准确性对高估的 值并不敏感。对于真实数据,由于 的平均误差斜率较小,广义-ICP 的敏感性仍然较低。模拟数据和真实数据之间的差异可以用它们各自频率分布的不同来解释。模拟环境中只有建模的高级特征,而真实环境中只有建模的低级特征。
 (a) 模拟室内
 (b) 模拟室外
 (c) Velodyne 数据

图 5. 平均误差与下列参数的关系
 (a) 初步对齐
 (b) 点对平面
 (c) 通用国际比较方案

图 6.31 号测速仪扫描对的结果示例
 (a) 初步对齐
 (b) 点对平面
 (c) 通用国际比较方案

图 7.速度扫描对 #45 的结果示例


(a) 扫描对 31 号,视图 1


(b) 扫描对 31 号,视图 2


(c) 扫描对 #45,视图 1


(d) 扫描对 #45,视图 2

图 8.透视显示的 31 号和 45 号 Velodyne 扫描对,以说明场景的复杂性
 (a) 模拟室内
 (b) 模拟室外

(c) Velodyne 数据 #1 - #26

(d) Velodyne 数据 #27 - #51

图 9. 理想值的平均误差,使图 5 最小化


而真实世界的数据包含更详细的高频数据。这就增加了具有共同表面方向的错误对应的可能性,而我们的算法并没有考虑到这种情况。


尽管如此,即使将广义-ICP 的 最差预测值与点到平面的最佳预测值进行比较,广义-ICP 的表现也大致相当。

如第二节所述, 对 ICP 的性能起着重要作用。设置较低的值会降低收敛几率,但会提高准确率。设置过高的值会增加收敛半径,但会降低准确度,因为会出现更多错误的对应关系。


本文提出的算法通过扣除错误对应关系的影响,大大减少了选取较大 值的惩罚。这样,无需为每种环境手动选择 的值,就能更容易地在各种环境中获得良好的性能。

除了精度提高之外,新算法在计算变换时对两个扫描结果给予了同等的考虑。图 6 和图 7 显示了两种情况,在这两种情况下,使用两个扫描的结构消除了点到平面时出现的局部最小值。


这些是相距约 30 米并对齐的速度计扫描记录的自上而下的视图。图 8 显示了相同扫描对的其他一些视图,以更好地说明场景结构。


在室外环境中,从路上行驶的汽车看过去,扫描范围为距离传感器 70-100 米。

由于这种最小化仍是在 ICP 框架内进行的,因此这种方法既有标准算法的速度和简便性,又有完全概率技术(如 EM)的一些优点。


理论框架还允许采用标准的稳健性技术。例如,高斯核可以与均匀分布混合,以模拟异常值。


高斯 RV 也可以用一种分布来代替,这种分布考虑了匹配中的一定松弛度,以明确模拟不精确的对应关系(通过在 附近的某个区域赋予 分布一个恒定的密度)。尽管我们已经考虑了其中的一些变化,但它们都没有明显的封闭形式,很容易最小化。这使得它们过于复杂,无法纳入当前工作,但却是未来研究的一个好课题。

 V.结论


在本文中,我们提出了一种 ICP 算法的推广方案,它在概率模型中考虑到了两个扫描的局部平面结构。


ICP 框架的大部分内容未作修改,以保持该类算法的速度和简洁性,这也是该类算法在实践中广受欢迎的原因;拟议的泛化只涉及变换的迭代计算。


我们假定所有测量点都来自以真实点为中心的高斯分布,而真实点被假定为完全对应。然后使用 MLE 来迭代估计用于对齐扫描的变换。


在一系列模拟和真实世界的实验中,Generalized-ICP 被证明可以提高准确性。同时,使用来自两个扫描的结构信息减少了错误对应的影响。


因此,选择最大匹配距离作为对应阶段的参数对性能的影响就变得不那么重要了。


这些修改保持了 ICP 的简单性和速度,同时提高了性能,消除了通常与参数选择相关的权衡。

 致谢


本研究部分由雷神萨科斯有限责任公司(Raytheon Sarcos LLC)和美国国防部高级研究计划局(DARPA)作为主要赞助商签订的分包合同(合同编号:HR0011-04-C-0147)支持。

 参考文献


[1] P. Besl, N. McKay."A Method for Registration of 3-D Shapes," IEEE Trans. on Pattern Analysis and Machine Intel.,vol.14,no.2,pp.239-256,1992.

[2] P. Biber、S. Fleck、W. Strasser。"A Probabilistic Framework for Robust and Accurate Matching of Point Clouds," Pattern Recognition, Lecture Notes in Computer Science, vol. 3175/2004, pp.

[3] N. Gelfan、L. Ikemoto、S. Rusinkiewicz、M. Levoy。"Geometrically Stable Sampling for the ICP Algorithm," Fourth International Conference on 3-D Digital Imaging and Modeling, p. 260, 2003.

[4] D. Haehnel, W. Burgard."用于 3D 扫描注册的概率匹配》,2002 年 VDI-Conference Robotik 会议论文集。

[5] Z. Zhang."自由曲面注册的迭代点匹配》,IRA Rapports de Recherche,计划 4:机器人、图像和视觉,第 1658 期,1992 年。

[6] D. Hahnel、W. Burgard、S. Thrun。"用移动机器人学习室内外环境的紧凑 3D 模型》,《机器人与自主系统》,第 44 卷,第 15-27 页,2003 年。

[7] Y. Chen, G. Medioni."1992 IEEE 机器人与自动化国际会议论文集》,第 2724-2729 页,1991 年。

[8] L. Montesano、J. Minguez、L. Montano。"Probabilistic Scan Matching for Motion Estimation in Unstructured Environments," IEEE Intl.Intelligent Robots and Systems, pp.

[9] A. Fitzgibbon."三维和三维点集的稳健注册》,《图像与视觉计算》,第 21 卷,第 13-14 期,第 1145-1153 页,2003 年。

[10] B. Horn."使用单位四元数的绝对方位闭式解法》,《美国光学学会期刊 A》,第 4 卷,第 页 .

[11] S. Rusinkiewicz, M. Levoy."Efficient Variants of the ICP Algorithm," Third International Conference on 3-D Digital Imaging and Modeling, p. .

[12] G. Dalley, P. Flynn."Pair-Wise Range Image Registration:A Study in Outlier Classification," Computer Vision and Image Understanding, vol. 87, pp.

[13] S. Kim , Y. Hwang , H. Hong , M. Choi."An Improved ICP Algorithm Based on the Sensor Projection for Automatic 3D Registration," Lecture Notes in Computer Science, vol. 2972/2004 pp.642-651, 2004.

[14] J.-S.Gutmann, C. Schlegel, "AMOS: Compare of scan matching approaches for self-localization in indoor environments," eurobot, p.61, 1st Euromicro Workshop on Advanced Mobile Robots (EUROBOT), 1996.

[15] F. Lu, E. Milos."通过匹配二维范围扫描在未知环境中估算机器人姿态》,《智能机器人系统杂志》第 18 期:pp.