本文共 1289 字，大约阅读时间需要 4 分钟。

摘要

这篇文章提出第一个快速且可证明的算法（TEASER），用于在存在大量外点对应的情况下对两组3D点进行配准。通过重新建模配准问题，使用截断最小二乘（TLS）代价函数，使得算法对大量假对应点不敏感。我们提供了一个通用的图理论框架，将尺度、旋转和平移估计解耦，级联求解三个变换。尽管每个子问题仍然是非凸和组合的，但通过adaptive voting机制在多项式时间内求解TLS尺度和分量形式平移估计。TLS旋转估计被松弛为紧的半定规划问题（SDP），并在极端外点率情况下保持松弛。图理论框架通过寻找最大派系显著修剪外点。分成了两个算法：TEASER和TEASR++。后者使用渐进非凸性求解旋转子问题，并借助Douglas-Rachford Splitting高效证明全局最优性。在标准benchmarks测试中，显著优于RANSAC、branch-&-bound和启发式算法，并在多个数据集上验证了其鲁棒性和速度优势。TEASR++具备毫秒级运行速度，是目前最快的鲁棒配准算法。

主要贡献

首次提出可证明的算法解决3D配准问题，特别是在存在大量外点的情况下。通过截断最小二乘代价函数重新建模配准问题，提出了解耦尺度、旋转和平移的框架。该框架包括四个核心创新：发展不变测量量、形式化不变测量量的解耦、提供通用图理论框架推导不变测量量、利用最大派系修剪外点。这使得问题分解为级联求解三个子问题。证明了TLS估计问题可在多项式时间内精确求解，以及松弛紧的SDP求解旋转。提供理论结果验证估计质量，并开发TEASR++算法解决旋转估计问题。发布开源代码实现，并在实际应用中验证了算法的鲁棒性和高效性。

算法流程

1. 使用截断最小二均值代价函数重新建模配准问题，以降低对假对应点的敏感度。 2. 通过图理论框架解耦尺度、旋转和平移变换，实现级联求解。 3. 采用TEASER算法分别求解尺度、旋转和平移，利用松弛的SDP求解旋转。 4. TEASR++算法使用非凸优化求解旋转，结合Douglas-Rachford Splitting证明最优性，显著提升计算效率。

主要实验结果

在标准benchmarks测试中，与FGR、GORE和RANSAC等算法相比，TEASER和TEASR++显著超越。TEASR++实现毫秒级运行，是最快的鲁棒配准算法。该算法对应点未知问题表现优异，可比ICP更精确且速度更快。结合深度学习的关键点检测与匹配，TEASR++进一步提升配准性能。实验结果显示，TEASR++能够估计正确的旋转和平移，有效解决对称场景中的多解问题。代码公开提供C++、Python和Matlab实现，便于研究和应用。

总结

本文提出了一种快速可证明的鲁棒配准算法，解决了极端外点率下的3D配准问题。通过结合几何、图理论和优化技术，实现了高效鲁棒配准。TEASR++算法显著提升了计算效率和可证明性，成为鲁棒配准领域的重要进展。本文基于先前的研究成果，整合了不变测量、四元数优化和图理论方法，形成了完整的算法框架。该工作在理论和实验验证中均取得了显著成果，是多学科交叉研究的典范。