Siddhant Katyan, received his MS in Computer Science and Engineering (CSE). His research work was supervised by Dr. Pawan Kumar. Here’s a summary of Siddhant Katyan’s MS thesis, Fast Optimization Solvers for Bundle Adjustment as explained by him:
Recently, a lot of the standard algorithms in machine learning and computer vision need to be re-designed for handling large scale problems. In this thesis, we explore one such fundamental algorithm, which is inherent in almost every multi-view reconstruction system pipeline in computer vision. Recently, bundle adjustment has been the key component in Structure-from-Motion (SfM) problem. Bundle adjustment (BA) jointly optimizes the camera parameters and feature points parameters according to an objective function of reprojection errors. This joint optimization of camera parameters and feature points parameters 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. Some widely used methods like Cholesky Decomposition and Preconditioned Conjugate Gradients, to solve these normal equations still face some challenges in robustness, accuracy, and efficiency. In this thesis, we propose a deflated algebraic two-grid method has been used as a preconditioner for Generalized Minimal Residual Method (GMRES), for solving these normal equations arising in the Bundle Adjustment process. We show that the proposed method is several times faster than iterative schur and jacobi schur which are considered as state-of-the-art methods to solve the Bundle Adjustment problem. We verify the competence of our algorithm by benchmarking it against the state-of-the-art methods on publicly available Bundle Adjustment in the Large (BAL) dataset. To the best of our knowledge, this is the first time a deflation based solver has been investigated for such problems. Our experiments suggest that or most of the BAL datasets, the proposed solver is better than state-of-the-art solvers present in popular ceres solver, in some cases, it is upto five times faster than the best. Given that the bundle adjustment problem often leads to very ill conditioned problems with condition number of the order of 1020, we establish that explicit deflation is essential in achieving efficient solvers. In particular, we observed that deflating couple of largest eigenvectors instead of smallest ones is beneficial, because there are very large eigenvectors of the order of 1015, and they tend to slow down the convergence of Krylov subspace type methods. In future, we will try to explore more along these lines, and try to estimate the convergence rate guarantees.