2024-10-12 MIT多功能开源点云配准库KISS-Matcher：保持精度的同时，速度远快于SOTA

“保持简单和可扩展”的全局配准

3D点云配准是一项估计两个部分重叠的点云之间相对位姿的基本问题，与基于迭代最近点（ICP）的方法不同，这类方法具有较小的收敛区域，且仅当初始估计较好的情况下才会收敛到理想解。而全局配准旨在无需初始估计的前提下估计相对位姿。因此，全局配准广泛用于应用场景，通常提供初始对齐，以使ICP方法收敛到更优的解。

先前的研究往往专注于提升特定组件的性能（例如，特征提取、基于图论的修剪或姿态求解器），而忽略了整个配准流程的实时性和更广泛的适用性。尤其是，尽管近期基于深度学习的方法在未训练的场景中展现了较好的泛化能力，一些基于学习的方法忽略了数据预处理所需的时间，或依赖于大量的随机采样一致性（RANSAC）迭代，这些迭代可能耗时数秒甚至数十秒。此外，不仅深度学习方法，一些传统方法也仅限于扫描级别的配准，无法扩展到子地图或地图级别，这限制了它们的应用范围；因此，开发适用于扫描级别和大规模地图级别的可扩展配准方法尤为重要，如图1(a)所示。

本文介绍的KISS-Matcher[1]是一种快速且可扩展的配准系统，将每个配准管道组件的最新进展结合到一个多功能且可随时使用的C++库中。遵循KISS-ICP的理念，重点提升系统的适用性，减少对传感器特定假设或繁琐参数调整的依赖。

从整体角度处理配准问题，特别针对TEASER++管道[2]中的问题进行了改进，尤其是其在地图级匹配场景下无法处理大量对应关系的情况。为了解决这一问题：

通过提出Faster-PFH加速了经典的手工设计描述符——快速点特征直方图(FPFH)
采用基于k-core的图论修剪技术来拒绝错误的对应关系。

系统在速度上比TEASER++快了数倍，同时实现了类似的性能（如图1(b)所示）。

KISS-Matcher的配准管道遵循基于特征的外点鲁棒配准的典型流程，如图3所示。KISS-Matcher由四个组成部分构成：

几何抑制
基于Faster-PFH的特征提取和初始匹配
基于k-core的图论外点拒绝
基于渐进非凸性（GNC）的非最小解算器。

问题定义

几何抑制作为预处理步骤

由于环境中重复图案（如地面、天花板或建筑物平面墙上的点）产生了大量外点（例如，当不同平面上的许多点被错误地识别为匹配时），这些外点会严重影响姿态估计的质量。因此，如果这些点能够被轻松检测到，它们应在预处理步骤中被过滤掉，以使配准过程更加鲁棒。我们将此预处理过程称为几何抑制。几何抑制不仅能防止后续步骤收敛到错误的解，还可以通过提前拒绝冗余和不具区分性的点来提高特征的独特性。此外，它还能通过减少点云的数量显著加速后续步骤。为了保持通用性，继续用P和Q来表示几何抑制后过滤的点云。

Faster-PFH: 提升FPFH速度

为了在点云P和Q之间提取并匹配特征，提出了Faster-PFH，它是FPFH 的更高效变体，同时保持了相似的性能。如图4(a)所示，FPFH的计算过程主要分为三个步骤：

使用邻域点估计每个点的法向量
提取查询点与邻域点之间的角度特征，并计算简化的点特征直方图（SPFH）签名
通过加权平均邻域点的SPFH签名计算FPFH特征。

然而，现有的FPFH特征提取在实时应用中可能不适用。例如，当FPFH应用于使用64通道LiDAR传感器捕获的体素化源点云和目标点云时，点数范围在10K到30K，即使在Intel(R) Core(TM) i9-13900 CPU的多线程环境下，FPFH的计算也需要超过0.1秒。FPFH存在两个主要的计算瓶颈：

首先，由于要多次执行邻域点搜索（即“RS with rnormal”或“RS with rFPFH”，见图4(a)），计算效率低下。
其次，由于现有方案是解耦的，没有检查法向量估计的可靠性，SPFH和FPFH的提取可能会在不可靠的法向量上不必要地执行，从而降低了邻域FPFH特征的表现力。

为了应对这些问题，采用了两种策略。

首先，为了减少不必要的计算开销，我们为每个点仅执行一次邻域点搜索，并重用结果。接着，基于rnormal ≤ rFPFH的事实，我们从rFPFH的邻域点搜索结果中对法向量估计进行子采样。
其次，对于每个点，如果邻域点的数量少于一个预定义的阈值，或法向量线性度过高（通过主成分分析估计法向量时的三个特征值计算得出），则该点将被排除在角度特征、SPFH和FPFH特征的计算之外。这样，我们只为可靠的点生成描述符。

最终，通过这种方法，我们将FPFH的单线程和多线程执行速度分别提高了约4.5倍和2.4倍，同时保持了性能。

基于k-core的图论外点修剪