提出快速求解固定旋转轴点云配准的全局最优方法
Fast globally optimal Truncated Least Squares point cloud registration with fixed rotation axis
- 设计线性时间凸松弛与收缩算法加速分支定界
- 100点点云配准在半秒内完成全局最优求解
- 适合需要高精度配准且旋转轴已知的场景
最近研究显示，使用截断最小二乘（TLS）公式可将点云配准对异常值的鲁棒性提升至95%。然而，求解该组合优化问题达到全局最优仍具挑战。基于半定规划（SDP）的已有方法对100个点需数百秒。本文提出一种新型线性时间凸松弛及收缩算法，显著加速分支定界（BnB）。当旋转轴已知时，本方法可在不足0.5秒内对两个含100点的3D点云实现全局最优配准。尽管目前仅适用于旋转自由度受限的情况，其速度比最先进的SDP求解器STRIDE快两个数量级。除提供全局最优性形式证明外，还通过对抗实例验证了全局最优性，这些实例中局部极小值接近全局最小。
原文摘要 · Abstract (English)
Recent results showed that point cloud registration with given correspondences can be made robust to outlier rates of up to 95\% using the truncated least squares (TLS) formulation. However, solving this combinatorial optimization problem to global optimality is challenging. Provably globally optimal approaches using semidefinite programming (SDP) relaxations take hundreds of seconds for 100 points. In this paper, we propose a novel linear time convex relaxation as well as a contractor method to speed up Branch and Bound (BnB). Our solver can register two 3D point clouds with 100 points to provable global optimality in less than half a second when the axis of rotation is provided. Although it currently cannot solve the full 6DoF problem, it is two orders of magnitude faster than the state-of-the-art SDP solver STRIDE when solving the rotation-only TLS problem. In addition to providing a formal proof for global optimality, we present empirical evidence of global optimality using adversarial instances with local minimas close to the global minimum.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。