Two-Grid Preconditioned Solver for Bundle Adjustment

Abstract

We present the design and implementation of Two-Grid Preconditioned Bundle Adjustment (TPBA), a robust and efficient technique for solving the non-linear least squares problem that arises in bundle adjustment. Bundle adjustment (BA) methods for multi-view reconstruction formulate the BA problem as a non-linear least squares problem which is solved by some variant of the traditional Levenberg-Marquardt (LM) algorithm. Most of the computation in LM goes into repeatedly solving the normal equations that arise as a result of linearizing the objective function. To solve these system of equations we use the Generalized Minimal Residual (GMRES) method, which is preconditioned using a deflated algebraic two-grid method. To the best of our knowledge this is the first time that a deflated algebraic two-grid preconditioner has been used along with GMRES, for solving a problem in the computer vision domain. We show that the proposed method is several times faster than the direct method and block Jacobi preconditioned GMRES.