TEASER: Fast and Certifiable Point Cloud Registration

By Heng Yang, Jingnan Shi, Luca Carlone. IEEE Transactions on robotics, 2020

917 citations recorded by the source corpus.

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 show that 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 $\text{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++.

Subfields: Aerospace Engineering, Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/71451f07b98cb2fe76148e692e9a8bb6c2fb3c6a

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. Luca Carlone
  2. Yun Chang
  3. Antoni Rosinol
  4. Nathan Hughes
  5. Jingnan Shi
  6. Rana Abbas
  7. Jian Zhang
  8. Juyong Zhang

In Computer Graphics and Computer-Aided Design

  1. Yuxin Yao
  2. Juyong Zhang
  3. Bailin Deng
  4. Marcus Abate
  5. Shiguo Lian
  6. Yun Chang
  7. Luca Carlone
  8. Nathan Hughes

In Computer Vision and Pattern Recognition

  1. Luca Carlone
  2. Yun Chang
  3. Antoni Rosinol
  4. Nathan Hughes
  5. Juyong Zhang
  6. Yuxin Yao
  7. Bailin Deng
  8. Jingnan Shi

Citations in the corpus