# A Polynomial-time Solution for Robust Registration with Extreme Outlier Rates

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2019.

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

- [PointDSC: Robust Point Cloud Registration using Deep Spatial Consistency](https://mlsanity.com/paper/2103.05465/) (2021)
- [A comprehensive survey on point cloud registration](https://mlsanity.com/paper/2103.02690/) (2021)
- [Deep Hough Voting for Robust Global Registration](https://mlsanity.com/paper/2109.04310/) (2021)
- [Self-Contrastive Learning with Hard Negative Sampling for Self-supervised Point Cloud Learning](https://mlsanity.com/paper/2107.01886/) (2021)
- [Accurate Point Cloud Registration with Robust Optimal Transport](https://mlsanity.com/paper/2111.00648/) (2021)
- [SE(3) Diffusion Model-based Point Cloud Registration for Robust 6D Object Pose Estimation](https://mlsanity.com/paper/2310.17359/) (2023)
- [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)
- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [RANSIC: Fast and Highly Robust Estimation for Rotation Search and Point Cloud Registration using Invariant Compatibility](https://mlsanity.com/paper/2104.09133/) (2021)
- [Accelerating Globally Optimal Consensus Maximization in Geometric Vision](https://mlsanity.com/paper/2304.05156/) (2023)
- [MatchNorm: Learning-based Point Cloud Registration for 6D Object Pose Estimation in the Real World](https://mlsanity.com/paper/2203.15309/) (2022)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [TriVoC: Efficient Voting-based Consensus Maximization for Robust Point Cloud Registration with Extreme Outlier Ratios](https://mlsanity.com/paper/2111.00657/) (2021)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [Greedy-Based Feature Selection for Efficient LiDAR SLAM](https://mlsanity.com/paper/2103.13090/) (2021)
- [Robust Partial-to-Partial Point Cloud Registration in a Full Range](https://mlsanity.com/paper/2111.15606/) (2021)
- [BUFFER-X: Towards Zero-Shot Point Cloud Registration in Diverse Scenes](https://mlsanity.com/paper/2503.07940/) (2025)
- [Point Cloud Registration for LiDAR and Photogrammetric Data: a Critical Synthesis and Performance Analysis on Classic and Deep Learning Algorithms](https://mlsanity.com/paper/2302.07184/) (2023)
- [Dynamical Pose Estimation](https://mlsanity.com/paper/2103.06182/) (2021)
- [Monitoring of Perception Systems: Deterministic, Probabilistic, and Learning-based Fault Detection and Identification](https://mlsanity.com/paper/2205.10906/) (2022)
- [DANIEL: A Fast and Robust Consensus Maximization Method for Point Cloud Registration with High Outlier Ratios](https://mlsanity.com/paper/2110.05075/) (2021)
- [IRON: Invariant-based Highly Robust Point Cloud Registration](https://mlsanity.com/paper/2103.04357/) (2021)
- [Practical, Fast and Robust Point Cloud Registration for 3D Scene Stitching and Object Localization](https://mlsanity.com/paper/2111.04228/) (2021)
- [Category-Level Global Camera Pose Estimation with Multi-Hypothesis Point Cloud Correspondences](https://mlsanity.com/paper/2209.14419/) (2022)
- [CLIPPER: Robust Data Association without an Initial Guess](https://mlsanity.com/paper/2402.07284/) (2024)
- [Deep Loss Convexification for Learning Iterative Models](https://mlsanity.com/paper/2411.10649/) (2024)
- [PCR-99: A Practical Method for Point Cloud Registration with 99 Percent Outliers](https://mlsanity.com/paper/2402.16598/) (2024)
- [Neural Predictor-Corrector: Solving Homotopy Problems with Reinforcement Learning](https://mlsanity.com/paper/2602.03086/) (2026)
- [AutoSynth: Learning to Generate 3D Training Data for Object Point Cloud Registration](https://mlsanity.com/paper/2309.11170/) (2023)

## Abstract (arXiv)

We propose a robust approach for the registration of two sets of 3D points in the presence of a large amount of outliers. Our first contribution is to reformulate the registration problem using a Truncated Least Squares (TLS) cost that makes the estimation insensitive to a large fraction of spurious point-to-point correspondences. The second contribution is a general framework to decouple rotation, translation, and scale estimation, which allows solving in cascade for the three transformations. Since each subproblem (scale, rotation, and translation estimation) is still non-convex and combinatorial in nature, out third contribution is to show that (i) TLS scale and (component-wise) translation estimation can be solved exactly and in polynomial time via an adaptive voting scheme, (ii) TLS rotation estimation can be relaxed to a semidefinite program and the relaxation is tight in practice, even in the presence of an extreme amount of outliers. We validate the proposed algorithm, named TEASER (Truncated least squares Estimation And SEmidefinite Relaxation), in standard registration benchmarks showing that the algorithm outperforms RANSAC and robust local optimization techniques, and favorably compares with Branch-and-Bound methods, while being a polynomial-time algorithm. TEASER can tolerate up to 99% outliers and returns highly-accurate solutions.