Maximizing robustness of point-set registration by leveraging non-convexity

Abstract

Point-set registration is a classical image processing problem that looks for the optimal transformation between two sets of points. In this work, we analyze the impact of outliers when finding the optimal rotation between two point clouds. The presence of outliers motivates the use of least unsquared deviation, which is a non-smooth minimization problem over non-convex domain. We compare approaches based on non-convex optimization over special orthogonal group and convex relaxations. We show that if the fraction of outliers is larger than a certain threshold, any naive convex relaxation fails to recover the ground truth rotation regardless of the sample size and dimension. In contrast, minimizing the least unsquared deviation directly over the special orthogonal group exactly recovers the ground truth rotation for any level of corruption as long as the sample size is large enough. These theoretical findings are supported by numerical simulations.

arXiv comment38 pages, 6 figures; Fix typos

References in corpus (5)

• Discontinuous Dynamical Systems: A tutorial on solutions, nonsmooth analysis, and stability
• Semidefinite descriptions of the convex hull of rotation matrices
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Convex Relaxations of SE(2) and SE(3) for Visual Pose Estimation
• Exact Camera Location Recovery by Least Unsquared Deviations

Cited by in corpus (2)

• Riemannian Perspective on Matrix Factorization
• One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers