Abstract
Current bundle adjustment solvers such as the Levenberg-Marquardt (LM) algorithm are limited by the bottleneck in solving the Reduced Camera System (RCS) whose dimension is proportional to the camera number. When the problem is scaled up, this step is neither efficient in computation nor manageable for a single compute node. In this work, we propose a stochastic bundle adjustment algorithm which seeks to decompose the RCS approximately inside the LM iterations to improve the efficiency and scalability. It first reformulates the quadratic programming problem of an LM iteration based on the clustering of the visibility graph by introducing the equality constraints across clusters. Then, we propose to relax it into a chance constrained problem and solve it through sampled convex program. The relaxation is intended to eliminate the interdependence between clusters embodied by the constraints, so that a large RCS can be decomposed into independent linear sub-problems. Numerical experiments on unordered Internet image sets and sequential SLAM image sets, as well as distributed experiments on large-scale datasets, have demonstrated the high efficiency and scalability of the proposed approach.
Introduction
In 3D reconstruction tasks like Structure-from-Motion (SfM) or Simultaneous Localization and Mapping (SLAM), Bundle Adjustment (BA) is the critical optimization step that refines camera poses and 3D point coordinates to minimize reprojection error. Standard solvers typically rely on the Levenberg-Marquardt (LM) algorithm. However, as datasets grow to include tens of thousands of images, the LM algorithm encounters a significant bottleneck: solving the Reduced Camera System (RCS). The RCS is a massive linear system that becomes computationally expensive and memory-intensive, making it difficult to solve on a single node and challenging to parallelize effectively.
Methodology: Stochastic Relaxation
The proposed Stochastic Bundle Adjustment (STBA) reimagines the optimization process by decomposing the global problem into independent, parallelizable sub-problems through a novel stochastic relaxation framework.
Point Splitting and Reformulation
STBA transforms the standard BA problem into a constrained Quadratic Programming (QP) problem. The core idea is "point splitting": physical 3D points are split into multiple "virtual points"—one for each camera that observes it. To maintain physical consistency, equality constraints are added to force these virtual points to occupy the same location.
Chance-Constrained Relaxation and Decomposition
Rather than enforcing these constraints strictly, which would keep the system globally coupled, STBA relaxes them into "chance constraints." By using a sampled convex program, the algorithm randomly selects a subset of constraints to satisfy in each iteration. When constraints are dropped, the cameras decouple into independent clusters. This transforms the dense RCS matrix into a cluster-diagonal structure, allowing each cluster to be solved independently and in parallel across multiple compute nodes.
Correction and Clustering
To ensure convergence despite the approximation errors introduced by stochastic sampling, a steepest descent correction step is added when the algorithm operates in a small trust region. Furthermore, the visibility graph is dynamically partitioned in every iteration using a randomized Louvain modularity algorithm, allowing the solver to utilize different second-order information over time.
Experimental Results
The authors evaluated STBA across several datasets, including the 1DSfM (unordered Internet images), KITTI (sequential SLAM), and a custom large-scale urban dataset featuring over 30,000 images.
Efficiency and Scalability
On standard benchmarks, STBA reached target objective thresholds over 5x faster than standard LM and Dogleg solvers. On the large-scale dataset, STBA achieved convergence rates an order of magnitude faster than state-of-the-art distributed solvers like DBACC.
As shown in the performance analysis, the per-iteration time for STBA drops significantly as more compute nodes are added. This demonstrates near-linear scalability for the RCS solution, which is the most computationally expensive part of the optimization process. Unlike previous distributed frameworks that require complex hyper-parameter tuning (e.g., ADMM), STBA offers a more "plug-and-play" approach for large-scale engineering pipelines.
Conclusion and Future Work
STBA successfully addresses the RCS bottleneck by leveraging stochasticity as a tool for scalability. While the method provides massive gains in efficiency, the authors note that clustering-based methods can experience slower convergence when very close to a stationary point. Future research may explore more sophisticated sampling strategies for chance constraints to further improve approximation quality without increasing the computational load. The code for STBA is available at https://github.com/zlthinker/STBA.
Summary updated