Two-Grid Preconditioned Solver for Bundle Adjustment

Siddhant Katyan, Shrutimoy Das, Pawan KumarWACV 2020

TL;DR

This paper introduces a novel "deflated two-grid" preconditioning technique for the GMRES iterative solver, specifically designed to accelerate bundle adjustment (BA) in computer vision. By explicitly removing the influence of large eigenvalues from the problem's Hessian, their method achieves significant speedups over existing direct and iterative solvers, making large-scale 3D reconstruction more efficient.

What Problem Does This Paper Address?

Structure-from-Motion (SfM) pipelines, which reconstruct 3D scenes from multiple images, heavily rely on bundle adjustment (BA) as a core optimization step. BA aims to simultaneously refine camera poses and 3D point locations to minimize reprojection errors. The computational bottleneck in BA lies in solving a large, non-linear least-squares problem, typically tackled using iterative methods like Levenberg-Marquardt (LM). Each LM iteration requires solving a system of linear "normal equations," which can be computationally expensive, especially for large-scale datasets with many cameras and points. While iterative solvers like GMRES are memory-efficient, they require effective preconditioning to achieve fast convergence. Existing preconditioning methods often struggle with the specific structure of the BA Hessian, leading to slow convergence or requiring substantial memory.

Methods

The paper proposes a Two-Grid Preconditioned GMRES (TPBA) solver. The core innovation is a deflated algebraic two-grid preconditioner. Traditional two-grid methods use a coarse grid correction to dampen low-frequency errors and a smoother for high-frequency errors. This new approach modifies the coarse grid correction by using a deflation technique.

Here's a breakdown:

  • GMRES Solver: The paper uses the restarted Generalized Minimal Residual (GMRES) method as the iterative solver for the linear systems arising in LM.
  • Deflated Two-Grid Preconditioner:
    • Smoother: A standard Jacobi smoother is used to dampen high-frequency components of the error.
  • Coarse Grid Correction (Deflation): Instead of a traditional coarse grid correction, they employ a deflation preconditioner. This method explicitly removes the influence of eigenvectors corresponding to the largest eigenvalues of the Hessian. This is achieved by constructing a coarse grid matrix using these eigenvectors.
  • Multiplicative Combination: The overall preconditioner is a multiplicative combination of the Jacobi smoother and the deflation component, aiming to leverage the strengths of both.
  • Hessian Structure Exploitation: The method leverages the block-sparse structure of the BA Hessian (as described in Section 2.2) to construct the preconditioner efficiently.

Datasets

The experiments were conducted on the BAL dataset (Bundle Adjustment in the Large) released by Agarwal et al. [1]. The authors selected ten specific datasets from BAL, ranging in size from 7K to 700K points, due to memory constraints on regular PCs for some larger BAL datasets.

Key Insights and Ideas

  • Deflating Large Eigenvalues is Key: Unlike traditional deflation methods that target small eigenvalues, this work shows that deflating the largest eigenvalues of the BA Hessian is crucial for accelerating convergence. These large eigenvalues contribute significantly to the ill-conditioning of the problem.
  • Synergy of Deflation and Smoothing: The combination of explicitly deflating large eigenvalues (removing dominant error components) and using a Jacobi smoother (dampening remaining high-frequency errors) proves to be highly effective.
  • Scalability Advantage: The proposed method requires significantly less memory than direct solvers as the problem size increases, making it suitable for large-scale SfM.
  • Robustness: The method demonstrates robust performance across various datasets and cost functions, achieving comparable or better reprojection errors than other methods.

Key Results

  • Speedup: The proposed Two-Grid Preconditioned GMRES (TPBA) solver is several times faster than direct methods (LDL factorization) and block Jacobi preconditioned GMRES. For larger problems, it converges two to three times faster than direct and block Jacobi methods.
  • Memory Efficiency: TPBA requires memory on the same order as the Jacobi method and uses only 54% of the memory required by direct methods for larger problems.
  • Performance Comparison: Table 3 shows that for most datasets, TPBA achieves the fastest time per iteration, often significantly outperforming direct solve and block Jacobi. For example, on dataset F-1936, TPBA takes 60.9 seconds per iteration compared to 129.4 seconds for direct solve and 114.7 seconds for block Jacobi.
  • Comparable Accuracy: The method achieves comparable or better mean reprojection errors, indicating that the speedup does not come at the cost of accuracy.

Limitations and Future Work

  • Limitations:
    • The paper notes that traditional multigrid methods (like AGMG) designed for scientific computing often fail on BA problems because the Hessian is neither diagonally dominant nor an M-matrix. This highlights a limitation of applying off-the-shelf multigrid solvers.
  • While the paper shows TPBA is faster than direct methods even for smaller problems, it acknowledges that direct methods are fastest for the smallest problems.
  • Future Work:
    • Explore more sophisticated deflation techniques.
  • Conduct extensive comparisons with other methods for solving bundle adjustment problems.

Summary updated

BibTeX
@inproceedings{katyan2020two,
  author = {Siddhant Katyan and Shrutimoy Das and Pawan Kumar},
  title = {{Two-Grid Preconditioned Solver for Bundle Adjustment}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2020},
}
Figure