Application of Numerical Linear Algebra techniques to the Bundle Adjustment problem

Abstract

With the increase in number and size of the problems in the computer vision domain, a lot of research has focused on speeding up the algorithms in these domains. Most of these algorithms require the solution of a linear system at some point. This thesis explores the application of numerical linear algebra(NLA) techniques for increasing the efficiently of algorithms related to the bundle adjustment[62] problem. Since, the dimensions of the linear systems associated with these problems is large, iterative methods such as conjugate gradients(CG) and generalized minimal residual(GMRES), are used. However, the efficiency of these methods depends on the condition number(defined as the ratio of the largest eigenvalue to the smallest eigenvalue) of the coefficient matrix. In general, the matrices associated with these problems are very badly conditioned. This motivates the use of preconditioning matrices, or preconditioners, which are close to the original matrix in some sense, and simplifies the solution of the linear systems. In this thesis, some novel preconditioners are developed and their effects on the efficiency of the algorithms are presented.Two NLA techniques, namely the domain decomposition method and the multigrid method, are used to develop preconditioners for the bundle adjustment problem. This is the first time these techniques have been applied to this problem. Another method is explored in this thesis that is based on deflation of unfavourable eigenvectors. These preconditioners are integrated with popular solvers like SSBA1 and Ceres[2] and their improvements are demonstrated experimentally