Fast Updates for Least-Squares Rotational Alignment Eurographics 2021

Jiayi Eris Zhang1, Alec Jacobson1, Marc Alexa2

1University of Toronto, 2TU Berlin
Least-squares rotation fitting is a core low-level subroutine in a number of important high-level tasks in computer graphics, geometry processing, robotics and computer vision.

Abstract

Across computer graphics, vision, robotics and simulation, many applications rely on determining the 3D rotation that aligns two objects or sets of points. The standard solution is to use singular value decomposition (SVD), where the optimal rotation is recovered as the product of the singular vectors. Faster computation of only the rotation is possible using suitable parameterizations of the rotations and iterative optimization. We propose such a method based on the Cayley transformations. The resulting optimization problem allows better local quadratic approximation compared to the Taylor approximation of the exponential map. This results in both faster convergence as well as more stable approximation compared to other iterative approaches. It also maps well to AVX vectorization. We compare our implementation with a wide range of alternatives on real and synthetic data. The results demonstrate up to two orders of magnitude of speedup compared to a straightforward SVD implementation and a 1.5-6 times speedup over popular optimized code.

Downloads

Technical Paper Talk

Coming Soon

BibTeX

@article{Zhang:Fast:2021,
  title = {Fast Updates for Least-Squares Rotational Alignment},
  author = {Jiayi Eris Zhang and Alec Jacobson and Marc Alexa},
  year = {2021},
  journal = {Computer Graphics Forum},
}

Acknowledgements

This work is funded in part by the Deutsche Forschungsgemeinschaft under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ EXC-2046/1, NSERC Discovery (RGPIN2017–05235, RGPAS–2017–507938), New Frontiers of Research Fund (NFRFE–201), the Ontario Early Research Award program, the Canada Research Chairs Program, and gifts by Adobe Systems. We thank Silvia Sellán for proofreading and all the anonymous reviewers for their helpful comments and suggestions.