Journal
IEEE TRANSACTIONS ON ROBOTICS
Volume 37, Issue 2, Pages 314-333Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TRO.2020.3033695
Keywords
Certifiable algorithms; object pose estimation; outliers-robust estimation; point cloud alignment; robust estimation; scan matching; three-dimensional (3-D) registration; 3-D robot vision
Categories
Funding
- ARL DCIST CRA [W911NF-17-2-0181]
- Lincoln Laboratory Resilient Perception in Degraded Environments
- Google Daydream Research Program
- ONR RAIDER [N00014-18-1-2828]
Ask authors/readers for more resources
This study introduces a fast and certifiable algorithm for registering two sets of 3-D points in the presence of outlier correspondences. By using TLS cost and graph-theoretic framework, it achieves decoupling of scale, rotation, and translation estimation, demonstrating strong robustness and good performance in modeling errors.
We propose the first fast and certifiable algorithm for the registration of two sets of three-dimensional (3-D) points in the presence of large amounts of outlier correspondences. A certifiable algorithm is one that attempts to solve an intractable optimization problem (e.g., robust estimation with outliers) and provides readily checkable conditions to verify if the returned solution is optimal (e.g., if the algorithm produced the most accurate estimate in the face of outliers) or bound its suboptimality or accuracy. Toward this goal, we first reformulate the registration problem using a truncated least squares (TLS) cost that makes the estimation insensitive to a large fraction of spurious correspondences. Then, we provide a general graph-theoretic framework to decouple scale, rotation, and translation estimation, which allows solving in cascade for the three transformations. Despite the fact that each subproblem (scale, rotation, and translation estimation) is still nonconvex and combinatorial in nature, we showthat 1) TLS scale and (component-wise) translation estimation can be solved in polynomial time via an adaptive voting scheme, 2) TLS rotation estimation can be relaxed to a semidefinite program (SDP) and the relaxation is tight, even in the presence of extreme outlier rates, and 3) the graph-theoretic framework allows drastic pruning of outliers by finding the maximum clique. We name the resulting algorithm TEASER (Truncated least squares Estimation And SEmidefinite Relaxation). While solving large SDP relaxations is typically slow, we develop a second fast and certifiable algorithm, named TEASER++, that uses graduated nonconvexity to solve the rotation subproblem and leverages Douglas-Rachford Splitting to efficiently certify global optimality. For both algorithms, we provide theoretical bounds on the estimation errors, which are the first of their kind for robust registration problems. Moreover, we test their performance on standard benchmarks, object detection datasets, and the 3DMatch scan matching dataset, and show that 1) both algorithms dominate the state-of-the-art (e.g., RANSAC, branch&-bound, heuristics) and are robust to more than 99% outliers when the scale is known, 2) TEASER++ can run in milliseconds and it is currently the fastest robust registration algorithm, and 3) TEASER++ is so robust it can also solve problems without correspondences (e.g., hypothesizing all-to-all correspondences), where it largely outperforms ICP and it is more accurate than Go-ICP while being orders of magnitude faster. We release a fast open-source C++ implementation of TEASER++.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available