This paper introduces XM (conveX bundle adjustMent), a novel, scalable, and initialization-free solver for global bundle adjustment (BA), a core problem in 3D reconstruction. Traditional BA is highly non-convex and struggles with large-scale datasets and the need for good initializations. The authors propose a Scaled Bundle Adjustment (SBA) formulation that leverages learned monocular depth to lift 2D keypoint measurements to 3D, incorporating a scaling parameter to correct noisy depth predictions.
To solve the resulting non-convex SBA problem, XM designs an empirically tight convex Semidefinite Programming (SDP) relaxation. This SDP is then solved efficiently at extreme scales by exploiting its low-rank structure through Burer-Monteiro factorization and a custom C++/CUDA-based trust-region Riemannian optimizer. This GPU-accelerated implementation demonstrates up to 100 times speedup over state-of-the-art CPU methods and achieves certifiable global optimality. Integrated into a full Structure from Motion (SfM) pipeline, XM-SfM is shown to be significantly faster, more scalable, and initialization-free compared to existing pipelines like COLMAP and GLOMAP, while maintaining comparable reconstruction quality across diverse real-world and synthetic datasets.
Summarizing "Building Rome with Convex Optimization"
Introduction to Bundle Adjustment (BA): BA is fundamental to Structure from Motion (SfM) and Simultaneous Localization and Mapping (SLAM), estimating camera poses and 3D landmarks from 2D image keypoints.
Challenges of Classical BA: The problem is highly non-convex due to the camera projection function and large scale (hundreds to tens of thousands of cameras), often requiring good initializations and getting stuck in local minima, making incremental SfM pipelines (e.g., COLMAP) slow.
The core idea is to lift 2D keypoints to approximate 3D points using learned depth from monocular depth prediction models (e.g., UNIDEPTH).
A per-frame scaling parameter (si) is introduced to correct for imperfect depth predictions, leading to the Scaled Bundle Adjustment (SBA) formulation which removes the non-convex reprojection function.
Contributions of the Paper (XM):
Convex SDP Relaxation: An empirically tight convex Semidefinite Programming (SDP) relaxation is designed for the SBA problem, allowing for certifiable global optimality.
Scalable Solver (XM): The convex SDP is solved at extreme scales using Burer-Monteiro (BM) factorization, exploiting the low-rankness of optimal solutions. This is coupled with a C++/CUDA-based trust-region Riemannian optimizer (dubbed XM), achieving up to 100x speedup over CPU-based alternatives.
Initialization-Free Global Optimality: The "Riemannian Staircase" Algorithm 1 ensures global convergence by starting at a low rank (r=3), performing local optimization, checking for dual optimality certificates, and increasing rank if stuck in a local minimum.
Full SfM Pipeline (XM-SfM): The authors built a complete SfM pipeline using XM as its optimization engine, integrating techniques for feature matching, view graph creation, and outlier-robust filtering.
XM-SfM Pipeline Steps: Involves feature extraction and matching (from COLMAP), view graph creation (from GLOMAP), depth estimation (e.g., UNIDEPTH), two-view estimation and outlier filtering, the XM solver (sometimes run twice, XM2, for better outlier removal), and a final CERES refinement step (warm-started by XM's solution for the original BA problem).
Experimental Results:
BAL Dataset: XM solver is 100 times faster than MANOPT, scales to over 10,000 camera frames, and achieves certifiable global optimality for most cases. CERES fails without good initialization.
Replica Dataset: XM-SfM (with ground truth depth) is 100 to 1000 times faster than COLMAP and GLOMAP, solving 2000-frame datasets in about 10 seconds while maintaining high accuracy (1% median translation error).
Mip-Nerf and Zip-Nerf Datasets: With learned depth and CERES refinement, XM-SfM is 10 to 100 times faster than baselines, showing comparable accuracy and no noticeable impact on downstream 3D Gaussian Splatting tasks. The BM factorization effectively escapes local minima by increasing rank.
IMC, TUM, and C3VD Datasets: XM demonstrates consistent efficiency and scalability across diverse and challenging real-world datasets (e.g., large photo collections, medical data), achieving comparable accuracy to GLOMAP while being significantly faster.
Limitations and Future Work:
XM can be sensitive to noise and outliers; further refinement of filtering is needed.
The current GPU solver uses dense matrix operations; future work includes supporting sparse matrix-vector multiplications for SLAM applications.
Further CUDA acceleration for preprocessing steps like filtering and matrix construction.
Reliance on well-trained depth prediction models, which can be challenging in data-scarce domains.