# TEASER: Fast and Certifiable Point Cloud Registration

arXiv: https://arxiv.org/abs/2001.07715 · HTML: https://mlsanity.com/paper/2001.07715/

## Key facts

- Cited by 274 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2020.

## Built on by (most cited first, 30 of 274)

- [BundleSDF: Neural 6-DoF Tracking and 3D Reconstruction of Unknown Objects](https://mlsanity.com/paper/2303.14158/) (2023)
- [Kimera: from SLAM to Spatial Perception with 3D Dynamic Scene Graphs](https://mlsanity.com/paper/2101.06894/) (2021)
- [PointDSC: Robust Point Cloud Registration using Deep Spatial Consistency](https://mlsanity.com/paper/2103.05465/) (2021)
- [BundleTrack: 6D Pose Tracking for Novel Objects without Instance or Category-Level 3D Models](https://mlsanity.com/paper/2108.00516/) (2021)
- [A comprehensive survey on point cloud registration](https://mlsanity.com/paper/2103.02690/) (2021)
- [3D Registration with Maximal Cliques](https://mlsanity.com/paper/2305.10854/) (2023)
- [GeoTransformer: Fast and Robust Point Cloud Registration with Geometric Transformer](https://mlsanity.com/paper/2308.03768/) (2023)
- [You Only Hypothesize Once: Point Cloud Registration with Rotation-equivariant Descriptors](https://mlsanity.com/paper/2109.00182/) (2021)
- [LCDNet: Deep Loop Closure Detection and Point Cloud Registration for LiDAR SLAM](https://mlsanity.com/paper/2103.05056/) (2021)
- [SC^2-PCR: A Second Order Spatial Compatibility for Efficient and Robust Point Cloud Registration](https://mlsanity.com/paper/2203.14453/) (2022)
- [BOP Challenge 2023 on Detection, Segmentation and Pose Estimation of Seen and Unseen Rigid Objects](https://mlsanity.com/paper/2403.09799/) (2024)
- [Category-Level 6D Object Pose Estimation in the Wild: A Semi-Supervised Learning Approach and A New Dataset](https://mlsanity.com/paper/2206.15436/) (2022)
- [Motion Inspired Unsupervised Perception and Prediction in Autonomous Driving](https://mlsanity.com/paper/2210.08061/) (2022)
- [HouseCat6D -- A Large-Scale Multi-Modal Category Level 6D Object Perception Dataset with Household Objects in Realistic Scenarios](https://mlsanity.com/paper/2212.10428/) (2022)
- [nerf2nerf: Pairwise Registration of Neural Radiance Fields](https://mlsanity.com/paper/2211.01600/) (2022)
- [CT-ICP: Real-time Elastic LiDAR Odometry with Loop Closure](https://mlsanity.com/paper/2109.12979/) (2021)
- [Accurate Point Cloud Registration with Robust Optimal Transport](https://mlsanity.com/paper/2111.00648/) (2021)
- [RegFormer: An Efficient Projection-Aware Transformer Network for Large-Scale Point Cloud Registration](https://mlsanity.com/paper/2303.12384/) (2023)
- [ICP-Flow: LiDAR Scene Flow Estimation with ICP](https://mlsanity.com/paper/2402.17351/) (2024)
- [Object Pose Estimation with Statistical Guarantees: Conformal Keypoint Detection and Geometric Uncertainty Propagation](https://mlsanity.com/paper/2303.12246/) (2023)
- [SE(3) Diffusion Model-based Point Cloud Registration for Robust 6D Object Pose Estimation](https://mlsanity.com/paper/2310.17359/) (2023)
- [GenFlow: Generalizable Recurrent Flow for 6D Pose Refinement of Novel Objects](https://mlsanity.com/paper/2403.11510/) (2024)
- [Robust Outlier Rejection for 3D Registration with Variational Bayes](https://mlsanity.com/paper/2304.01514/) (2023)
- [What Is The Best 3D Scene Representation for Robotics? From Geometric to Foundation Models](https://mlsanity.com/paper/2512.03422/) (2025)
- [SAGE: SLAM with Appearance and Geometry Prior for Endoscopy](https://mlsanity.com/paper/2202.09487/) (2022)
- [MULLS: Versatile LiDAR SLAM via Multi-metric Linear Least Square](https://mlsanity.com/paper/2102.03771/) (2021)
- [Self-supervised Geometric Perception](https://mlsanity.com/paper/2103.03114/) (2021)
- [R-PointHop: A Green, Accurate, and Unsupervised Point Cloud Registration Method](https://mlsanity.com/paper/2103.08129/) (2021)
- [DiffusionNOCS: Managing Symmetry and Uncertainty in Sim2Real Multi-Modal Category-level Pose Estimation](https://mlsanity.com/paper/2402.12647/) (2024)
- [ReAgent: Point Cloud Registration using Imitation and Reinforcement Learning](https://mlsanity.com/paper/2103.15231/) (2021)

## Abstract (arXiv)

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.