SIM-Sync: From Certifiably Optimal Synchronization Over the 3D Similarity Group to Scene Reconstruction With Learned Depth

Xihang Yu, Heng YangIEEE RA-L 2024 · DOI

TL;DR

This paper introduces SIM-Sync, a novel algorithm for estimating camera trajectories and 3D scene structure directly from image keypoints. It bridges the gap between pose graph optimization and bundle adjustment by leveraging learned depth prediction to lift 2D keypoints into 3D, enabling certifiably optimal synchronization over the 3D similarity group. This approach achieves state-of-the-art performance on real-world datasets and demonstrates robustness to outliers.

What Problem Does This Paper Address?

Estimating camera trajectories and reconstructing 3D scenes from images is a fundamental problem in robotics and computer vision. Two popular approaches exist: Pose Graph Optimization (PGO), which synchronizes relative camera poses, and Bundle Adjustment (BA), which jointly optimizes camera poses and 3D points by minimizing reprojection errors. PGO allows for efficient global optimization but relies on pre-estimated relative poses, while BA directly uses image keypoints but is notoriously difficult to optimize globally due to its non-convex and non-polynomial objective function. This paper aims to bridge this gap by developing a method that directly uses image keypoints (like BA) but can be optimized globally and certifiably (like PGO).

Methods

The core innovation of SIM-Sync lies in its use of a pretrained depth prediction network. This network takes monocular images and outputs depth maps. By combining these predicted depths with 2D keypoint correspondences, the authors lift the 2D keypoints into 3D scaled point clouds. The key challenge here is that monocular depth prediction is inherently scale-ambiguous, meaning the absolute scale of the predicted depth is unknown.

SIM-Sync then formulates an optimization problem to synchronize both the camera poses (rotations and translations) and these unknown per-image scaling factors. This synchronization happens over the 3D similarity group (SIM(3)), which includes scaling, rotation, and translation. The problem is then reformulated into a quadratically constrained quadratic program (QCQP). Finally, a semidefinite programming (SDP) relaxation is applied to solve this QCQP problem to certifiable global optimality. The authors also introduce a scale regularization technique to prevent the estimated scales from collapsing to zero, which can be problematic in certain graph structures.

Datasets

The paper evaluates SIM-Sync on several datasets:

  • Simulated Datasets: Custom-generated datasets with circle, grid, and line graph topologies to test scale-free synchronization, scale regularization, and outlier rejection.
  • BAL Dataset: Specifically, the dubrovnik-16-22106 and ladyburg-318-41628 sequences, which are standard benchmarks for bundle adjustment.
  • TUM Dataset: The freiburg1_xyz and freiburg2_xyz sequences, commonly used for visual SLAM evaluation.

Key Insights and Ideas

  • Learned Depth as a Bridge: The most significant insight is using learned monocular depth prediction to transform 2D keypoint correspondences into 3D scaled point clouds. This elegantly bypasses the need for explicit relative pose estimation required by PGO, while providing a structure amenable to global optimization.
  • SIM(3) Synchronization: Extending synchronization from the Special Euclidean group (SE(3)) to the Similarity group (SIM(3)) is crucial for handling the scale ambiguity inherent in monocular depth estimation.
  • Certifiable Global Optimality: By reformulating the problem into a QCQP and applying SDP relaxation, SIM-Sync can provide provably optimal solutions, a significant advantage over traditional BA methods that rely on local optimization.
  • Scale Regularization is Crucial: The authors discovered that without explicit regularization, estimated scales can "contract" (tend towards zero), especially in certain graph structures. This regularization is essential for obtaining meaningful scale estimates and improving overall accuracy.

Key Results

  • Competitive Performance: SIM-Sync achieves comparable or superior accuracy to state-of-the-art methods like Ceres and ORB-SLAM3 on real-world datasets (BAL and TUM).
  • Robustness to Outliers: When combined with robust estimators like GNC and TEASER, SIM-Sync can successfully handle a high percentage of outlier correspondences (up to 70-80% with TEASER).
  • Tightness of Relaxation: The SDP relaxation used by SIM-Sync is shown to be tight (i.e., it yields the globally optimal solution) in many simulated scenarios, especially with low noise.
  • Effective Scale Regularization: The proposed scale regularization effectively prevents scale contraction and improves translation accuracy, particularly for larger numbers of poses.

Limitations and Future Work

  • Reliance on Depth Prediction: The performance of SIM-Sync is inherently tied to the quality of the pretrained depth prediction network. Errors or biases in depth prediction will directly impact the final pose and structure estimates.
  • Computational Cost: While certifiably optimal, SDP solvers can be computationally intensive, especially for very large-scale problems.
  • Future Work: The authors suggest speeding up SIM-Sync by exploiting low-rank properties of SDP solutions and using the reconstructed 3D scene to further improve depth prediction.

Summary updated

BibTeX
@article{yu2024sim,
  author = {Xihang Yu and Heng Yang},
  title = {{SIM-Sync: From Certifiably Optimal Synchronization Over the 3D Similarity Group to Scene Reconstruction With Learned Depth}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2024},
  doi = {10.1109/lra.2024.3377006},
}
Figure