TEASER: Fast and Certifiable Point Cloud Registration

3 min read

TEASER registers two 3D point sets from putative correspondences when almost all of them are wrong. The cost is truncated least squares, so any correspondence with residual above a noise bound costs a constant and stops pulling. The method decouples the problem. Differences between pairs of points do not depend on translation, and their lengths do not depend on rotation either, so scale is solved first (by adaptive voting), then rotation, then translation (voting again, per component). Pairwise length checks also define a consistency graph whose maximum clique keeps only mutually compatible correspondences, which removes most outliers before the hard part. TEASER solves rotation with a tight semidefinite relaxation; TEASER++ swaps that for GNC and then certifies the GNC answer with a Douglas-Rachford dual check, so it runs in milliseconds and still says whether the answer is optimal.

Findings

  • Bunny with known scale: TEASER, TEASER++ and GORE survive 99% outliers; TEASER++ is about ten times faster than GORE and more accurate. RANSAC with a 60 s timeout reaches 98% at around iterations.
  • With unknown scale, TEASER and TEASER++ fail only at 90% outliers; FGR fails at 70%. TEASER++ stays under 30 ms.
  • The certifier accepted every correct GNC rotation and rejected every incorrect one within 200 iterations, taking 24 iterations on average to reach a sub-optimality gap below 0.1% (about 50 ms per iteration in C++).
  • 3DMatch scan matching: TEASER++ beats both RANSAC variants on every scene except Lab, with RANSAC at 1000 iterations up to 12% lower in success rate. Restricted to the poses TEASER++ certifies, the success rate beats all of them.
  • Without correspondences (all-to-all), it beats ICP and is more accurate than Go-ICP while being orders of magnitude faster.

Limits

  • The authors separate random from adversarial outliers. With random outliers and noiseless inliers, 3 inliers suffice for exact recovery. With adversarial outliers, the inliers must outnumber the outliers by at least 3 (Theorem 16), because an adversary can plant a full fake copy of the scene and no algorithm can tell which copy is real.
  • The noise bound must be known and the maximum clique step assumes inliers are mutually consistent within it.
  • The certificate covers the optimisation problem: a certified answer is the best fit to the given correspondences, which is right only if the inliers are the largest consistent set.
  • The full SDP version is slow; the fast version certifies only the rotation subproblem.

Relevance

The adversarial-outlier theorem is the perception version of the style bounds in Byzantine fault tolerance: once liars coordinate, you need an honest majority. The maximum clique step is the same idea as PCM applied to point correspondences. TEASER++ is a standard tool in outlier-robust estimation and collaborative SLAM, and certification here led to C-3PO.