TEASER: Fast and Certifiable Point Cloud Registration

Abstract

We propose the first fast and certifiable algorithm for the registration of two sets of 3D points in the presence of large amounts of outlier correspondences. We first reformulate the registration problem using a Truncated Least Squares (TLS) cost that is 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 is still non-convex and combinatorial in nature, we show that (i) TLS scale and (component-wise) translation estimation can be solved in polynomial time via adaptive voting, (ii) 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 (iii) 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 non-convexity 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, object detection, and the 3DMatch benchmarks, and show that (i) both algorithms dominate the state of the art and are robust to more than 99% outliers, (ii) TEASER++ can run in milliseconds, and (iii) TEASER++ is so robust it can also solve problems without correspondences, where it largely outperforms ICP and it is more accurate than Go-ICP while being orders of magnitude faster.

arXiv commentAccepted to IEEE Transactions on Robotics (T-RO). Code: https://github.com/MIT-SPARK/TEASER-plusplus. 20 pages main text, 24 pages appendix

References in corpus (14)

• Point-Set Registration: Coherent Point Drift
• Open3D: A Modern Library for 3D Data Processing
• Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration
• Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection
• Guaranteed Outlier Removal for Point Cloud Registration with Correspondences
• SegICP: Integrated Deep Semantic Segmentation and Pose Estimation
• PRNet: Self-Supervised Learning for Partial-to-Partial Registration
• Towards Verified Artificial Intelligence
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• Did You Miss the Sign? A False Negative Alarm System for Traffic Sign Detectors
• A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints
• Fast and Globally Optimal Rigid Registration of 3D Point Sets by Transformation Decomposition
• Nonparametric Continuous Sensor Registration
• A Dynamical Perspective on Point Cloud Registration

Cited by in corpus (8)

• A comprehensive survey on point cloud registration
• LiDAR-Based Place Recognition For Autonomous Driving: A Survey
• A Benchmark for Point Clouds Registration Algorithms
• Optimal Pose and Shape Estimation for Category-level 3D Object Perception
• DeepGMR: Learning Latent Gaussian Mixture Models for Registration
• Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras
• Diverse Plausible Shape Completions from Ambiguous Depth Images
• Non-iterative One-step Solution for Point Set Registration Problem on Pose Estimation without Correspondence