摘要
在大规模场景的数据获取过程中，通常需要将多次扫描所获得的信息进行累积。一种常用的方法是利用迭代最近点（Iterative Closest Point, ICP）算法（或其变体）对扫描配对进行局部配准，但该方法要求场景保持静态，且两次扫描之间的运动较小。这一限制使得难以在多个扫描会话之间或不同采集模态（如双目视觉、深度扫描）之间实现数据的累积。另一种选择是采用全局配准算法，允许扫描数据处于任意初始位姿。目前最先进的全局配准算法——4PCS（Four-Point Congruent Sets），其时间复杂度与数据点数量的平方成正比，这极大地限制了其在大规模环境数据采集中的应用。为此，本文提出一种名为 Super 4PCS 的新型全局点云配准算法。该算法具有最优的时间复杂度——线性时间（相对于数据点数量），并且在复杂度上对配准问题的输出具有敏感性，即其计算复杂度取决于扫描配对之间未知的重叠程度。技术上，我们将该问题建模为一个“实例问题”（instance problem），并通过一种智能的索引数据结构实现高效求解。该算法结构简洁、内存效率高，且运行速度快。实验结果表明，Super 4PCS 相较于现有方法实现了显著的加速性能，使得在以往难以实现的大规模场景下，仍能实现无结构、高效的场景数据采集。完整源代码及测试数据集已开放，供科研使用，详见：http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/。