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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> respectively with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m\geq n$</tex> . We first propose a solver, ARCS, that i) assumes noiseless point sets in general position, ii) requires only 2 inliers, iii) uses <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(m\log m)$</tex> time and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(m)$</tex> space, and iv) can successfully solve the problem even with, e.g., <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m, n\approx 10^{6}$</tex> in about 0.1 seconds. We next robustify ARCS 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon$</tex> -stationary point in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\varepsilon^{-4})$</tex> iterations, or locally to the ground-truth at a linear rate in the absence of noise. We combine these algorithms into ARCS+, to simultaneously search for rotations and correspondences. Experiments show that ARCS+ achieves state-of-the-art performance on large-scale datasets with more than 10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">6</sup> points with a 10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> time-speedup over alternative methods. https://github.com/liangzu/ARCS