A Deflation Based Fast and Robust Preconditioner for Bundle Adjustment

Shrutimoy Das, Siddhant Katyan, Pawan KumarWACV 2021

TL;DR

This paper introduces a novel deflation-based preconditioner for solving the computationally intensive bundle adjustment problem in 3D reconstruction. By strategically removing components associated with the largest eigenvalues of the Hessian matrix, their method significantly accelerates convergence, achieving up to a 5x speedup over state-of-the-art solvers on large-scale datasets.

What Problem Does This Paper Address?

Bundle adjustment (BA) is a cornerstone of 3D reconstruction, essential for accurately estimating camera poses and 3D scene structure from multiple images. As the scale of reconstruction projects grows (millions of images), the computational cost of BA becomes a major bottleneck. The core of BA involves solving a large, non-linear least-squares problem, typically linearized and solved iteratively using methods like Levenberg-Marquardt (LM). Each LM iteration requires solving a large linear system, which is often ill-conditioned, leading to slow convergence. While iterative solvers like Conjugate Gradient (CG) and GMRES are memory-efficient, their performance heavily relies on the condition number of the system. Preconditioners are crucial for improving this condition number, but existing methods often struggle with the extreme ill-conditioning of BA problems or are not scalable. This paper aims to develop a fast, robust, and scalable preconditioner specifically for large-scale BA.

Methods

The authors propose a "deflation-based" preconditioner that targets the largest eigenvalues of the Hessian matrix. The intuition is that these large eigenvalues correspond to eigenvectors that significantly slow down the convergence of iterative solvers. Instead of trying to approximate the inverse of the entire Hessian, their method explicitly "deflates" or removes the influence of these problematic components.

The core of their approach involves:

  1. Identifying Eigenvectors: They compute the eigenvectors corresponding to the largest eigenvalues of the Hessian matrix.
  2. Deflation Matrix: A deflation matrix, denoted as $B_D$, is constructed using these eigenvectors. This matrix effectively projects out the components associated with these large eigenvalues.
  3. Preconditioned System: The original linear system $Ax = b$ is transformed into a preconditioned system $B_D Ax = B_D b$.
  4. Iterative Solver: This preconditioned system is then solved using an iterative solver like GMRES. The authors show that their deflation preconditioner $B_D$ is a projection matrix and satisfies $B_D A = A B_D$, which simplifies the solution process.

A key innovation is their focus on deflating the largest eigenvalues, contrasting with some prior work that focused on smallest eigenvalues. They argue that for BA problems, the largest eigenvalues are more detrimental to convergence and that computing eigenvectors for large eigenvalues is computationally cheaper.

Datasets

The experiments were conducted on a subset of problems from the BAL dataset. These problems vary in size, with the number of cameras ranging from 257 to 1776 and the number of points from 65K to 993K. The paper provides a table detailing the specific datasets used, including their prefixes (L for LadyBug, T for Trafalgar Square, D for Dubrovnik, and V for Venice) and the resulting Hessian sizes.

Key Insights and Ideas

  • Largest Eigenvalues are the Culprits: The paper strongly suggests that the largest eigenvalues of the Hessian matrix are the primary cause of slow convergence in bundle adjustment problems. Deflating these, rather than the smallest ones, is more effective.
  • Computational Advantage of Deflating Large Eigenvalues: Computing eigenvectors associated with the largest eigenvalues is significantly faster than those for the smallest eigenvalues. This makes their deflation strategy computationally viable for large-scale problems.
  • Deflation as a Projection: The proposed deflation preconditioner is mathematically shown to be a projection matrix, which simplifies its integration and analysis.
  • Scalability: The deflation approach offers a memory-efficient solution, with memory requirements proportional to the number of deflated eigenvalues, making it suitable for very large problems where traditional dense methods fail.

Key Results

  • Significant Speedup: The proposed deflation-based solver (DEF) consistently outperforms other state-of-the-art solvers on the BAL dataset. It is reported to be up to 5 times faster than the next best solver (SNC) in some cases (e.g., dataset 4).
  • Robustness: For most datasets, the DEF solver achieves faster convergence than other methods.
  • Comparison to Existing Solvers: The paper compares DEF against several established solvers available in the Ceres framework, including Sparse Normal Cholesky (SNC), Dense Iterative Schur (DS), Iterative Schur (IS), Sparse Schur (SS), and Two Grid (TG) / Modified Two Grid (MTG) methods. DEF generally shows superior performance.
  • Effective Condition Number Reduction: Theoretical analysis and experimental results suggest that deflating the largest eigenvalues effectively reduces the condition number of the preconditioned system, leading to faster convergence.

Limitations and Future Work

  • Number of Deflated Eigenvalues: The optimal number of eigenvalues to deflate ($k$) can vary from problem to problem. While deflating the top two eigenvalues was sufficient for the tested problems, further exploration of strategies for determining $k$ could be beneficial.
  • Exploration of Deflation Strategies: The authors suggest exploring "various deflation strategies to further improve the solver" in future work. This could involve different ways of constructing the deflation space or combining deflation with other preconditioning techniques.
  • Convergence Issues: For dataset 2, the LM iterations did not converge within the specified limits for the DEF solver, indicating potential limitations in extreme cases or for specific problem structures.

Summary updated

BibTeX
@inproceedings{das2021deflation,
  author = {Shrutimoy Das and Siddhant Katyan and Pawan Kumar},
  title = {{A Deflation Based Fast and Robust Preconditioner for Bundle Adjustment}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2021},
}
Figure