TEASER: Fast and Certifiable Point Cloud Registration

• URL: http://arxiv.org/abs/2001.07715v2
• Date: Sat, 17 Oct 2020 20:03:04 GMT
• Title: TEASER: Fast and Certifiable Point Cloud Registration
• Authors: Heng Yang, Jingnan Shi, Luca Carlone
• Abstract summary: First fast and robust certifiable algorithm for the registration of 3D points in the presence of large amounts of outliers. Second fast and robust certifiable translation, named TEASER++, uses graduated non-componentity to solve a large subproblem.
• Score: 30.19476775410544
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Fast and Robust Non-Rigid Registration Using Accelerated Majorization-Minimization [35.66014845211251]
  Non-rigid registration, which deforms a source shape in a non-rigid way to align with a target shape, is a classical problem in computer vision. Existing methods typically adopt the $ell_p$ type robust norm to measure the alignment error and regularize the smoothness of deformation. We propose a formulation for robust non-rigid registration based on a globally smooth robust norm for alignment and regularization.
  arXiv  Detail & Related papers  (2022-06-07T16:00:33Z)
• Practical, Fast and Robust Point Cloud Registration for 3D Scene Stitching and Object Localization [6.8858952804978335]
  3D point cloud registration is a fundamental problem in remote sensing, photogrammetry, robotics and geometric computer vision. We propose a novel, fast and highly robust solution, named VOCRA, for the point cloud registration problem with extreme outlier rates. We show that our solver VOCRA is robust against over 99% outliers and more time-efficient than the state-of-the-art competitors.
  arXiv  Detail & Related papers  (2021-11-08T01:49:04Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  We develop a doubly robust off-policy AC (DR-Off-PAC) for discounted MDP. DR-Off-PAC adopts a single timescale structure, in which both actor and critics are updated simultaneously with constant stepsize. We study the finite-time convergence rate and characterize the sample complexity for DR-Off-PAC to attain an $epsilon$-accurate optimal policy.
  arXiv  Detail & Related papers  (2021-02-23T18:56:13Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Fast and Robust Iterative Closest Point [32.42799285301607]
  Iterative Closest Point (ICP) is a fundamental technique for rigid registration between two point sets. Recent work such as Sparse ICP achieves robustness via sparsity optimization at the cost of computational speed. We show that the classical point-to-point ICP can be treated as a majorization-minimization (MM) algorithm, and propose an Anderson acceleration approach to speed up its convergence.
  arXiv  Detail & Related papers  (2020-07-15T11:32:53Z)
• One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers [32.1176248075545]
  We propose the first general and practical to design certifiable algorithms for perception in the presence of a large amount of outliers. Our dual certifiers leverage solution-of-any suboptimal optimality of any problem.
  arXiv  Detail & Related papers  (2020-06-11T19:46:42Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  We propose a formulation for robust non-rigid registration based on a globally smooth robust estimator for data fitting and regularization. We apply the majorization-minimization algorithm to the problem, which reduces each iteration to solving a simple least-squares problem with L-BFGS.
  arXiv  Detail & Related papers  (2020-04-09T01:45:05Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.