Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection

By Heng Yang, Pasquale Antonante, V. Tzoumas, Luca Carlone. IEEE Robotics and Automation Letters, 2019

321 citations recorded by the source corpus.

Semidefinite Programming (SDP) and Sums-of-Squ- ares (SOS) relaxations have led to <italic>certifiably</italic> optimal <italic>non-minimal</italic> solvers for several robotics and computer vision problems. However, most non-minimal solvers rely on least squares formulations, and, as a result, are brittle against outliers. While a standard approach to regain robustness against outliers is to use robust cost functions, the latter typically introduce other non-convexities, preventing the use of existing non-minimal solvers. In this letter, we enable the simultaneous use of non-minimal solvers and robust estimation by providing a general-purpose approach for robust <italic>global</italic> estimation, which can be applied to any problem where a non-minimal solver is available for the outlier-free case. To this end, we leverage the Black-Rangarajan duality between robust estimation and outlier processes (which has been traditionally applied to early vision problems), and show that <italic>graduated non-convexity</italic> (<monospace>GNC</monospace>) can be used in conjunction with non-minimal solvers to compute robust solutions, without requiring an initial guess. we demonstrate the resulting <italic>robust non-minimal solvers</italic> in applications, including point cloud and mesh registration, pose graph optimization, and image-based object pose estimation (also called <italic>shape alignment</italic>). Our solvers are robust to 70–80% of outliers, outperform <monospace>RANSAC</monospace>, are more accurate than specialized <italic>local</italic> solvers, and faster than specialized <italic>global</italic> solvers. We also propose the <italic>first</italic> certifiably optimal non-minimal solver for shape alignment using SOS relaxation.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Control and Systems Engineering

View Paper: https://www.semanticscholar.org/paper/918ae14086d77f943873b5334e1bce9cb882a7ae

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

1. Yun Chang
2. Jingnan Shi
3. Luca Carlone
4. Heng Yang
5. Jonathan P. How
6. Carlos Nieto-Granda
7. Fernando Herrera Arias
8. Yulun Tian

In Computer Vision and Pattern Recognition

1. Luca Carlone
2. Yun Chang
3. Jingnan Shi
4. Carlos Nieto-Granda
5. Heng Yang
6. Jonathan P. How
7. Fernando Herrera Arias
8. Yulun Tian

In Control and Systems Engineering

1. Luca Carlone
2. Heng Yang
3. Yun Chang
4. Jonathan P. How
5. Jingnan Shi

Citations in the corpus

• Kimera-Multi: Robust, Distributed, Dense Metric-Semantic SLAM for Multi-Robot Systems (2021, methodology): “In this paper, we propose a new distributed approach for robust trajectory estimation based on GNC [15].”
• TEASER: Fast and Certifiable Point Cloud Registration (2020, methodology): “4(c)]; 2) the optimality certification algorithm 3 can certify all the correct GNC solutions and reject all incorrect GNC solutions within 200 iterations.”
• A Survey on Active Simultaneous Localization and Mapping: State of the Art and New Frontiers (2022, unknown): “, [244], [245], [246], [247], [248], [249]).”