Certifiable Optimization, Part 3: Global Solvers for 3D Vision

GTSAM Posts

Author: Frank Dellaert

This third and final ICRA-week post zooms out to the broader global-solvers ecosystem. Part 1 focused on our chordal-sparsity work, which uses Bayes-tree structure to make SDP relaxations more scalable. Part 2 focused on David Rosen’s group’s Certifiable Factor Graph Optimization, which approaches related factor-graph problems through Burer-Monteiro-style low-rank optimization. But these are only two efforts in a broader push toward global solvers for 3D vision and robot perception, a lot of it started by Luca Carlone & collaborators over the last 10 years. At ICRA this year we were very fortunate to have a workshop keynote by Heng Yang, his former Ph.D. student and now a professor at Harvard:

So, in this Part 3, I want to draw some attention to Luca and Heng’s seminal work in this area

A short lineage

One way to see the field’s trajectory is through rotation estimation, pose-graph optimization, and registration. Our 2015 ICRA paper, Initialization Techniques for 3D SLAM, was about making hard nonconvex SLAM problems behave better by separating out the rotation-estimation structure before running local pose-graph optimization. At MIT, David Rosen pioneered SE-Sync, which showed how pose synchronization over SE(d) could be solved efficiently while certifying global optimality in the relevant noise regime. I also worked with David and Luca and others on Shonan Rotation Averaging, that connected SDP relaxation and manifold optimization to large-scale rotation averaging.

Heng and Luca then pushed certifiable registration toward extreme outlier robustness in the context of point cloud registration, with TEASER, by Heng Yang, Jingnan Shi, and Luca Carlone. This paper already has > 1100 citations, and Heng has been on a convex relaxation binge since then!

Global solvers for 3D vision

A lot of the recent developments in this area, by Heng and others, were collected in the workshop paper Global Solvers for 3D Vision: Foundations, Frontiers, and a Call to the Robotics Community. A longer-form version with Heng as a co-author is available on Arxiv here: Advances in Global Solvers for 3D Vision.

Taxonomy of global solvers for 3D vision, including branch-and-bound, convex relaxation, graduated non-convexity, comparative analysis, and applications.
Global solvers for 3D vision span branch-and-bound, convex relaxation, and graduated non-convexity, with applications from Wahba's problem to bundle adjustment. Figure adapted from the Zhao et al. survey.


If you’re interested in knowing more, that survey is a very useful entry point. The authors introduce branch-and-bound (B&B), convex relaxation (CR), and graduated non-convexity (GNC) in the context of geometric estimation problems that show up constantly in robot perception, for example absolute and relative pose estimation, 3D registration, rotation and translation averaging, and even full bundle adjustment.

Back to GTSAM

The recent QP and QCQP support in GTSAM is a preview of the modeling layer needed to lift, relax, decompose, and eventually certify factor-graph problems. We hope to bring certifiable optimization to GTSAM soon, and I hope this will allow more robotics people to join in the fun!

Further browsing

Disclosure: AI was used to help draft this post and prepare the figure.