Fast Pose Graph Optimization via Krylov-Schur and Cholesky Factorization

Gabriel Moreira, Manuel Marques, Joao Paulo Costeira; Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), 2021, pp. 1898-1906

Pose Graph Optimization (PGO) is an important problem in Computer Vision, particularly in motion estimation, whose objective consists of finding the rigid transformations that achieve the best global alignment of visual data on a common reference frame. The vast majority of PGO approaches rely on iterative techniques which refine an initial estimate until convergence is achieved. On the other hand, recent works have identified a global constraint which has cast this problem into the matrix completion domain. The success which both these formulations have had in computing accurate solutions efficiently has been overshadowed by large-scale industrial applications such as autonomous flight, self-driving cars and smart-cities, where it is necessary to fuse numerous images covering large areas but where each one of them has few pairwise observations. We propose a highly efficient algorithm to solve PGO which leverages the sparsity of the data by combining the Krylov-Schur method for spectral decomposition with Cholesky LDL factorization. Our method allows for high scalability, low computational cost and high precision, simultaneously.