ARCS: Accurate Rotation and Correspondence Search

This paper is about the old Wahba problem in its more general form, which we call "simultaneous rotation and correspondence search". In this generalization we need to find a rotation that best aligns two partially overlapping 3D point sets, of sizes m and n respectively with m≥ n. We first propose a solver, textttARCS, that i) assumes noiseless point sets in general position, ii) requires only 2 inliers, iii) uses O(mlog m) time and O(m) space, and iv) can successfully solve the problem even with, e.g., m,n≈ 106 in about 0.1 seconds. We next robustify textttARCS to noise, for which we approximately solve consensus maximization problems using ideas from robust subspace learning and interval stabbing. Thirdly, we refine the approximately found consensus set by a Riemannian subgradient descent approach over the space of unit quaternions, which we show converges globally to an varepsilon-stationary point in O(varepsilon-4) iterations, or locally to the ground-truth at a linear rate in the absence of noise. We combine these algorithms into textttARCS+, to simultaneously search for rotations and correspondences. Experiments show that textttARCS+ achieves state-of-the-art performance on large-scale datasets with more than 106 points with a 104 time-speedup over alternative methods. urlhttps://github.com/liangzu/ARCS