雷达系列论文翻译（九）：3D Scan Registration Using the Normal Distributions Transform

3D扫描配准采用基于正态分布变换的地面分割与点云聚类方法

注

这篇综述文章是第十篇后续文章的一个概述，在内容上基本一致。在此处所讨论的贪婪聚类即为下一篇文章中介绍的区域生长聚类方法。

摘要

正态分布变换（NDT）扫描配准算法将环境建模为多个高斯分布的集合，并通过离散化处理将环境空间划分为体素区域后生成对应的高斯分布模型。对于传统的NDT方法而言，在初始变换误差较大的情况下其收敛效果欠佳。本研究提出了一种改进型分割贪婪聚类NDT(SGC-NDT)算法，在此方法基础上对NDT算法进行了优化改进。具体而言, 该方法利用环境空间中自然存在的特征对NDT算法进行改进, 并通过将地面部分与剩余特征进行分类处理, 从而构建了一个平滑且连续性的代价函数, 最终使得优化过程能够收敛于较优解点附近区域. 经过实验验证, 在城市和森林等复杂环境中, 该方法较现有的先进算法具有更高的扫描配准精度以及更好的优化收敛性能

引言

在移动机器人地图绘制算法领域中扮演着关键角色的是扫描配准算法。多种传感器通过点云形式提供了有关环境信息，在其中最突出的例子包括RGBD摄像机、LIDAR和双目相机等设备。该算法通过分析两次扫描之间的重叠几何关系来计算它们之间的相对变换。掌握这些变换参数对于整合多处扫描数据具有重要意义，在未知环境中实现自主操作任务至关重要

主流的扫描配准算法通常采用迭代最近点法（ICP）进行实现。该方法由 Besl 与 McKay[1]、Chen 与 Medioni[2] 以及 Zhang[3] 分别提出。ICP 算法旨在通过变换参数实现两组点云之间的最优配准，并使最近邻点对之间的欧氏距离最小化。然而该方法仅考虑了单个点的位置信息而忽略了其表面特征，在实际应用中面临较大的局限性。为了克服这一缺陷 Segal 等人提出了广义 ICP 算法（G-ICP）[4] 该改进版本通过计算各采样点处曲面法线方向增强了算法鲁棒性并引入了局部邻域内的几何约束条件以提高配准效果。尽管 ICP 算法在理论上有较高的收敛速度但在实际应用中由于频繁需要执行复杂的最近邻搜索操作导致计算开销较高

正态分布变换（NDT）是一种替代方案,最初由Biber与Strasser提出,应用于二维场景中的扫描配准与建图[5].随后,Magnusson等人将其拓展至三维点云领域,而Stoyanov等人则进一步发展了这一方法,将其演变为基于分布对齐的问题.NDT算法的优势在于无需显式计算最近邻对应关系,因为它将扫描数据表示为一组高斯分布而非单个点;同时,NDT算法还对底层扫描数据进行了类似处理,并将表面局部建模为生成的高斯分布形式.该方法采用优化手段确定变换参数,最终使得从NDT生成的理论分布能够最佳匹配实际扫描数据的概率最大值

基于NDT的标准公式设计的优化过程具有一定的复杂性，在初始估计明显偏离真实变换的情况下可能会出现较差的收敛效果。基于体素的离散化处理无法完全还原真实环境特征，在这种情况下生成的概率密度分布仅能实现每个栅格单元内点集的局部建模，并可能无法捕捉到扫描数据中更为丰富的特征信息。此外，在优化过程中由于栅格单元边界的交界处会导致目标函数呈现不连续特性。为此，在文献[8]中作者提出了多尺度k-均值聚类NDT(MSKM-NDT)方法，在这种方法中通过多尺度上的聚类操作实现了从粗到细的不同层次优化策略以提高二维激光扫描数据的质量。尽管MSKM-NDT方法能够有效规避局部极小值问题并显著提升了整体收敛效率，并且能够生成平滑连续的目标函数；但这一方法仍然要求聚类数目必须是预先已知确定的参数

Moos-mann等研究者在三维空间中实现了对 scan 的分割工作，在文献[9]中有详细描述这一过程。该方法通过利用图论方法并结合局部凸性准则对激光数据进行划分以实现对 scan 的分割效果显著提升的同时也有助于提高后续处理效率这一技术方案具有较高的实用价值与推广潜力为此本研究采用了该算法作为主要的技术手段并进行了深入探讨与优化研究

这项工作的贡献是采用分割与聚类方法来提升NDT算法在准确性和收敛性上的表现（尤其是适用于稀疏点云的户外开放环境）。目的是为了将环境中通常独立于地面的自然特征区分开来。这些自然特征被用来构建高斯聚类模型作为NDT算法的基础。这种改进使得仅需少量分布即可实现精确建模。最后的应用结果是将环境划分为地面区域与其他障碍物区域，并利用这些分区进行更高层次的任务处理

为了实现分解目的，在三维激光扫描中应用了基于高斯过程回归[11]与增量采样一致性的地面分割算法。我们提出了一个贪婪聚类方法来将非地面点分类。假设这些非地面点能够被彻底与地面点分离。该贪婪聚类方法生成相应的类别。这些类别被用来构建用于NDT算法的高斯分布模型。我们对所提出的聚类方法进行了优化，并评估了每个产生的候选解的成本函数。通过使用福特校园数据集[14]以及伍斯特理工学院的一个稀疏森林公园中的激光数据进行测试。我们的实验结果表明所提方法在准确性和收敛性方面表现优异。

问题描述

该算法旨在通过寻找两点云扫描即参考扫描与场景扫描之间的最优变换来实现对齐。主要致力于估计两次扫描之间的转换参数以使其尽可能吻合。参考.scan. scan. 该方法通过参数估计p = [t_x, t_y, t_z, φ, θ, ψ]^T ∈ ℝ³ × SO(3)来实现从场景.scan. scan. 到参考.scan. scan. 坐标系的映射关系 T(p,x) = [R_φ R_θ R_ψ]x + ^T T(p,x) = [R_{\varphi} R_{\theta} R_{\psi}]x + ^T 其中R_φ R_{\varphi}为绕x轴旋转角度φ的旋转矩阵 R_θ R_{\theta}为绕y轴旋转角度θ的旋转矩阵 R_ψ R_{\psi}为绕z轴旋转角度ψ的旋转矩阵 ^T [t_x,t_y,t_z]为两次帧之间的平移向量。

本文提出的方法

为了解决提高NDT算法在实际应用中遇到的问题, 本研究提出了一种名为SGC-NDT的新方法.该方法通过将空间划分为多个分片, 并对剩余空间中的点进行分组处理.研究发现, 采用分片后贪心聚类策略能够有效解决不同区域之间的配准问题, 并能将这一技术扩展至不同区域间的配准问题.

NDT算法在以下三个方面进行了修改：

1)

参考第四节所述的技术手段对地面分割方法进行应用后能够有效去除扫描中的基础表面反射点

2）

在第五节中详细说明了贪婪聚类方法后,对该系统中非地面点进行了聚类处理。该系统遵循这一策略,通过遵循特定的聚类步骤,成功将存在于环境中的自然特征(如树木和灌木丛)分类并整合到SGC-NDT模型中,从而生成具有高斯分布特性的数据表示。与此相对应的是,NDT系统采用基于体素的空间离散化方法,构建了一个截断型高斯分布模型,但这种建模方式无法完全准确反映复杂的环境情况

3）

为了适应扫描聚类中的贪婪聚类方法需求，在第七节中对NDT代价的计算进行了优化调整。在被转换点所在的单元内进行高斯分布评估。SGC-NDT算法对被转换点所属的贪婪聚类中的高斯分布进行评估。类似地，在处理分布间匹配问题时，场景中的每个高斯分布在参考扫描的所有相关高斯基础上进行评分。由于在扫描过程中识别出的聚类数量通常少于基于体素离散化生成的相关高斯数目，在所有相关highgauss distributions上的评估在计算上是可行的，并为此提供了连续且可微的成本函数以支持优化过程。

地面分割

用于这项工作的地面分割算法的基础首先由 Douillard 等人[12]提出。他们的方法基于稀疏点云的二维高斯过程(GP)模型执行地面分割, 该模型利用增量采样一致性(INSAC)方法构建了识别地物点的概率框架。Tongtong 等人[15]提出了一种对 Douillard 地面分割算法的改进版本。以减少计算量, Tongtong 基于径向栅格 bin 将扫描区域划分为多个扇区, 并分别对每个扇区进行地物分割处理。高斯过程回归被表述为基于每个扇区内部点集的近似。Tongtong 的方法被证明较二维的方法运行更快, 同时在分割效果上具有可比性。本文采用了参考文献[15]中提出的 1 维近似 ground segmentation 方法, 并在本节中进行了简明扼要地阐述

在执行径向栅格绑定的过程中，在激光坐标系中进行激光扫描操作时，在XY平面内首先将扫描区域划分为NsN_s个扇形区域；每个扇形区域又被划分为NbN_b个基于线性间距的子区域；最终，在扫描结果中落在第ii个扇区第jj个子区域内对应的点构成了(s_i^j)Y集合；而 SYS_Y则表示这些独立点集(s_i^j)Y的整体集合，并由函数τ(Y)返回相应的径向栅格划分结果。

三维点云的地面分割目标是将每个点归类为属于地面点或非地面点，在这项研究工作中采用高斯过程回归技术完成这一任务，在地形建模过程中使用非参数模型来学习地物特征，在Vasudevan等人的文献[11]中对此进行了详细讨论。研究采用了[15]中所描述的近似高斯过程回归方法，并通过图1展示了激光扫描中具有代表性的地物分类实例

该函数被定义为接受参数 SYS_Y 并输出相应的非地物点集 Y' 满足关系式 Y' ⊂ χ(S_Y)，其中 χ(S_Y) 表示与输入相关的某种计算结果。

对非地面点进行聚类

一旦地面点已经被分割完毕，则剩余未被分割的部分需要被进行聚类处理以实现SGC-NDT算法的应用。针对扫描YY的操作流程而言，在该场景下我们定义一个聚类ω⊂Y，并将其归入集合ΩY={ω₁,…, ω_N_Ω}。这里N_Ω表示总的聚类数量，在此之前其数值尚未确定。这些聚类均是从均匀分布U中随机采样得到的一个初始bin配置。具体而言，在SY空间中选取初始bin时满足s~ij服从该均匀分布。值得注意的是，在本研究中 SYS_Y 被视为由3D雷达扫描所得非地面点径向分桶所构成的空间区域。

s_{ij\tilde{s}_i^j的最近邻居生成并添加到最近邻居bin的有序列表QnnQ_{nn}中。可以将QnnQ_{nn}中一个bin与s}ij\tilde{s}i^{j进行比较，以确定两者是否可以合并。使用Φ(s~ij,Qnnk)\Phi(\tilde{s}_i}j,Q{nn}^k)函数来决定是否合并bin、其中Φ：SY×SY→{0,1}\Phi：S_Y \times S_Y \to {0,1}以及QnnkQ_{nn}^k是QnnQ_{nn}列表的第kk个元素。如果两个bin可以被合并则函数Φ\Phi返回1，否则返回0。在Φ\Phi函数中，不同的度量可以用来比较点集bin，例如bin中包含的点的平均值之间的欧几里得距离，每个bin内高斯分布之间的L2L_2距离，或者高斯拟合的测试。如果这些bin可以被组合，则邻居bin被添加到bin的开放列表Qo\mathcal{Q}{o}中。邻居bin也被从所有bin的集合SYS_Y中移除，并被添加到当前聚类CcurC{cur}中。探索和评估了来自QoQ_{o}中bin最近的邻居。当一个bin被探索时，它最近的邻居也会根据评估函数Φ\Phi被添加到QoQ_{o}中。一旦QoQ_{o}为空，这意味着没有其他的最近邻居可以被分配到当前的聚类中，所以从SYS_Y中选取一个新的bin，并且重复该过程。整个过程一直持续到将SYS_Y中的所有bin配给一个聚类。贪婪聚类完成后的高斯分布示例如图2所示。

定义接受非地面点Y′Y^{′}并返回集聚类集合ΩY\Omega_{Y}的函数，ΩY=β(Y′)\Omega_{Y} = \beta(Y^{'})。

正态分布变换

正态分布变换是一种技术手段，在这种技术手段下对空间进行离散采样以实现三维场景的数据处理与重建目标。NDT（Normal Distributions Transform）配准算法首先将参考扫描占据的空间细分为一组栅格单元CC（cells）。位于栅格单元Ci中的参考扫描数据集由元素yi构成，并满足如下条件：对于所有i属于{1,…,NC}, yi ∈ Ci. 每个栅格Ci内的数据集服从均值向量μi和协方差矩阵Σi的多元正态（高斯）分布在空间中以采样形式近似表示该区域的概率密度函数特性。

基于高斯分布的分段连续与分段可微特性构建的点云模型上

Stoyanov等人提出了一个改进型NDT方法[7]。该方法生成了两个扫描位置的NDT表示，并进而比较各扫描位置的分布情况以实现点对点配准[7]。在该研究中，默认情况下仅评估最邻近区域内的高斯分量以减少计算开销[7]。然而，在Stoyanov的研究中，默认情况下仅评估最邻近区域内的高斯分量以减少计算开销[7]这导致总代价函数出现不连续性[7]。当场景中的扫描点跨越栅格单元边界时此不连续性同样存在于点到分布距离计算中[7]。Magnusson等采用三线性插值方法来处理此问题[17]尽管如此但插值并不能完全消除此问题因为代价函数仍然存在不连续现象[17]

需要注意的是，在点到分布匹配的情况下，我们定义了两个用于计算梯度ηg\eta_{g}和海塞矩阵ηH\eta_{H}的分析表达式。这些表达式分别对应场景扫描中的一个点与变换参数之间的关系，并用于计算相关梯度及海塞矩阵的贡献。从参数估计p_0开始进行优化，在满足梯度范数小于用户指定阈值∣∣ηg∣∣∈R||\eta_g|| \in \mathbb{R} 的条件下（即∇f(p)=0\nabla f(p)=0），优化过程将终止。Stoyanov采用了线搜索拟牛顿法[7]来解决这一优化问题，在实际应用中还可以采用BFGS等更新方法进行求解

分割贪婪聚类

基于由贪婪聚类生成的高斯分布对NDT算法进行了优化或改进，并将其用于计算所有这些高斯分布所对应的代价函数。算法1详细总结了SGC-NDT-P2D的方法。

对于SGC-NDT-D2D系统，在实现其功能时采用了与P2D版本相仿的策略。然而，在D2D场景中（即设备对设备传输）情况下，则对两个激光扫描分别进行了分割和聚类处理，并通过比较各扫描所得高斯分布集合来进行配准操作。

实验结果

该研究引入了基于SGC-NDT的方法，在不同环境下采集点云数据进行评估分析，并与其他扫描配准算法展开对比研究。在本研究中所涉及的对比算法包括Iterative Closest Point（ICP）、Neighborhood-based Distance Transform (NDT)以及Generalized ICP (G-ICP)等方法。为了确保对比结果的有效性与可靠性，在实验过程中采用了上述三种算法对应的点云库（Point Cloud Library, PCL）实现[18]。其中，在应用ICP算法时，默认设置最大关联距离为10 \times 10m²；而针对NDT算法，则采用了3 \times 3m²的栅格尺寸作为基本单元来进行空间分割处理。此外，在所有基于优化的方法中，默认设置了梯度范数或步长范数小于1 \times 10^{-6}作为终止条件设定。

A. 户外城市环境中的精度

为了比较SGC-NDT与其他扫描配准方法在准确性上的差异,基于由福特校园视觉系统和LIDAR数据构建的[14号]数据集进行实验研究。该数据集是由Velodyne HDL-64E激光雷达系统按一定间隔采集生成的,其中地面参考标准是通过整合Applanix POS-LV 420提供的高质量速度与加速度测量数据以及Trimble GPS定位结果得到的。实验中发现,当采用地面参考标准对齐扫描时,其方位角配准精度优于1度,而在位置精度方面则达到厘米级别。每个算法均基于激光雷达每隔一定间隔采集的连续10个扫描帧进行配准初始化,并采用初始平移为零向量、初始旋转为单位矩阵的方式设定基准参数。随后通过计算配准结果与真实测量值之间的误差分布情况来评估各算法性能

应该注意的是，箱线图的上下相邻的白边代表数据的1.5×四分位距范围。

图3所示的误差分布情况表明，在与地面真值对比时，在线段配准过程中基于球体拟合（SGC）与非扇区积分变换（NDT）两种方法均能获得较好的配准效果；其中，在较大平移范围内的误差分布情况则显示出了该优化过程存在收敛至局部极小值的趋势；而基于迭代最近点（ICP）的方法则在较低水平上的平移与旋转精度表现得更为突出；但整体而言，在精确度上而言该方法仍略显不足

为了更深入地评估扫描配准的质量, 通过将成对配准的扫描数据整合到全球地图中来进行分析

清晰度度量显示，在SGC-NDT算法和G-ICP算法中均有较高的表现。受累计配准误差的影响下使用ICP算法所得地图效果较差。

B.稀疏森林中环境中的准确性

为了验证我们提出的方法具有良好的鲁棒性特征，在模拟稀疏森林场景中生成了相应的数据集，并通过该数据集完成了实验研究。这些数据集源自于WAPI「NASA 采样返回机器人挑战赛」的比赛场景。用于激光扫描的设备是 velodyne hdL-32e激光雷达，并将其安装于专为完成此挑战设计的独特底盘上进行操作。实验场景的主要组成部分包括多样化的树木、丰富的树叶以及一个方正的小凉亭区域。由于树冠复杂且覆盖面积广，在配准过程中面临诸多困难。

为了评估不同环境类别下的鲁棒性表现，本研究主要基于先前城市场景实验中效果最优的两种算法——改进型空间网格法（SGC-NDT）和改进型广域定位算法（G-ICP）。需要注意的是，在这项实验中仅考虑ICP与NDT这两种方法的原因是它们无法实现一致性的收敛过程，并且无法提供有效的全局比较依据。该实验采用了与城市场景实验相似的设计流程，在此框架下采用竞争性算法对 scan data 进行配准处理。随后将配准后的 scan data 整合成一个全局地图模型。在机器人缓慢移动的过程中，默认情况下每个算法都会每隔50次激光雷达扫描进行一次配准计算，并采用零平移与零旋转参数作为初始估计值配置。通过图4可以看出配准结果的整体趋势

本实验验证了里程计在高度估计不准确情况下的性能表现，并列举了几种典型的适用场景：例如，在GPS信号失效的情况下，在车轮打滑或其他因素导致车辆状态难以精确估计的情况下等。由于WPI数据集缺乏对真实地面状况的精确测量能力，因而仅采用清晰度指标作为全局地图评估的主要依据。WPI数据集的具体清晰度指标数值可见表一

评估结果表明，在SGC-NDT算法的基础上，G-ICP无法实现准确的扫描配准。

结论

这项工作开发了一种名为分割贪婪聚类NDT的新算法。我们通过贪心聚类方法对非地面点进行分组，并将每个聚类建模为高斯分布。与标准NDT算法不同的是，在本算法中使用聚类后的高斯分布进行配准。SGC-NDT方法不仅适用于点对点配准（point-to-point NDT），也适用于基于分布的配准（distribution-to-distribution NDT），并且在城市环境以及稀疏森林环境中均表现优异。未来的研究方向包括利用高斯聚类作为扫描初始配准的特征提取、优化算法实现使其更适合实时应用、全面评估计算复杂度，并探索其在更大规模环境中的适用性

总结以下：三个亮点：1.地面分割，这个确实是相当有用的，尤其是在森林场景中。2.贪婪聚类算法，也就是下一篇论文中的区域生长聚类，也可以理解为简化版的DBSCAN聚类，解决了固定尺寸栅格聚类导致的计算复杂性高和无法建模较大的自然特征的问题。3.使用所有的聚类生成的高斯分布来评估代价函数，实现了代价函数在整个变换参数空间上的连续和可导性质，保证了收敛性，同时由于第二点的存在，在计算效率上也可以保证。