Globally Optimal Robust Rotation Averaging

Rotation averaging (recovering absolute orientations from pairwise relative rotations) underlies global Structure from Motion, multi-scan registration, and cryo-electron microscopy, and in all three the measurements are heavily contaminated by outliers. Robust solvers tolerate the contamination but certify nothing; certifiable relaxations certify a least-squares surrogate that outliers render meaningless. We certify the robust objective itself: maximum consensus, the NP-hard number of measurements explainable within a tolerance. Covering the rotation group $\mathrm{SO}(3)$ with cells of certified radius turns the continuous problem into two integer Markov random fields that bracket its optimum (cell-centre decoding from below, radius-inflated satisfiability from above), and a single branch and bound with an admissible node bound solves both at once. Because both ends are integers, subdivision does more than shrink the bracket: we prove it closes at a finite resolution set by the instance's own margin, for all but finitely many tolerances. The certificate is stated in the units that matter: the returned rotations explain $C$ measurements, and no rotations explain more. On synthetic graphs, the bracket closes on every instance in about a minute, and the solver is the most accurate method at every outlier rate we test and the only one still standing at $90\%$. As an outlier-classification front end with a single parameter set, it improves the state of the art in Structure from Motion, multi-scan registration, and cryo-EM orientation recovery. The source code will be made public.