The Wahba problem, also known as rotation search, seeks to find the best
rotation to align two sets of vector observations given putative
correspondences, and is a fundamental routine in many computer vision and
robotics applications. This work proposes the first polynomial-time certifiably
optimal approach for solving the Wahba problem when a large number of vector
observations are outliers. Our first contribution is to formulate the Wahba
problem using a Truncated Least Squares (TLS) cost that is insensitive to a
large fraction of spurious correspondences. The second contribution is to
rewrite the problem using unit quaternions and show that the TLS cost can be
framed as a Quadratically-Constrained Quadratic Program (QCQP). Since the
resulting optimization is still highly non-convex and hard to solve globally,
our third contribution is to develop a convex Semidefinite Programming (SDP)
relaxation. We show that while a naive relaxation performs poorly in general,
our relaxation is tight even in the presence of large noise and outliers. We
validate the proposed algorithm, named QUASAR (QUAternion-based Semidefinite
relAxation for Robust alignment), in both synthetic and real datasets showing
that the algorithm outperforms RANSAC, robust local optimization techniques,
global outlier-removal procedures, and Branch-and-Bound methods. QUASAR is able
to compute certifiably optimal solutions (i.e. the relaxation is exact) even in
the case when 95% of the correspondences are outliers.

本文提出了 QUASAR 算法，通过 Truncated Least Squares (TLS) 成本和使用 unit quaternions 重新表述问题，并将问题作为 Quadratically-Constrained Quadratic Program (QCQP) 来陈述，最后通过 Semidefinite Programming (SDP) 来放松，解决了 Wahba 问题，并验证了其在混合噪声数据集上的有效性。