PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Heng Yang, Luca Carlone

arXiv:1903.08588v2cs.ROcs.CV

TL;DR

Point-cloud registration becomes difficult when correspondences contain extreme outliers, while existing methods do not jointly meet the stated goals of global solving, polynomial runtime, and guarantees. TEASER uses a TLS formulation and decouples scale, rotation, and translation, solving the subproblems with polynomial-time methods. It tolerates up to 99% outliers and compares favorably with several established approaches.

  • Problem

    Registration with extreme outlier correspondences is challenging, and the reviewed approaches do not simultaneously provide global solving, polynomial time, and formal performance guarantees.

    Source: §I · p. 1

  • Method

    TEASER uses a TLS cost and decouples scale, rotation, and translation, applying adaptive voting to scale and component-wise translation and an SDP relaxation to rotation.

    Source: §I · pp. 1–2

  • Results

    99% outliers: TEASER tolerates this rate and returns highly accurate solutions, outperforming RANSAC and robust local optimization and favorably comparing with Branch-and-Bound methods.

    Source: §I · p. 2, §VII · p. 8

  • Takeaways & Limitations

    TEASER is presented as a polynomial-time outlier-robust registration algorithm with computable performance guarantees.

    Source: §I · p. 2

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper targets 3D point-cloud alignment when putative correspondences contain extreme outliers, where existing approaches do not jointly meet the stated goals of global solving, polynomial time, and performance guarantees. It proposes TLS-based TEASER, decouples transformation estimation, and reports strong outlier tolerance and benchmark comparisons.

I. INTRODUCTION

  • 99% outliers: TEASER returns highly accurate registrations, outperforming RANSAC and robust local optimization and favorably comparing with Branch-and-Bound methods while running in polynomial time.The figure illustrates registration with 80% outlier correspondences and reports robustness up to 99%.Source: Figure 1 · p. 1, §I · p. 2
  • The paper targets global registration without an initial guess, extreme outlier tolerance, polynomial runtime, and formal guarantees—goals the reviewed literature does not meet simultaneously.The introduction contrasts methods robust to moderate outlier rates but lacking optimality guarantees with globally optimal Branch-and-Bound methods that have exponential worst-case time.Source: §I · p. 1
  • The approach uses a TLS cost to reduce sensitivity to spurious correspondences, then decouples scale, rotation, and translation for cascade estimation.Scalar TLS scale and component-wise translation can be solved exactly in polynomial time by adaptive voting; rotation uses an SDP relaxation, with per-instance performance bounds.Source: §I · pp. 1–2

A. Correspondence-based Methods

  • Correspondence-based methods match 3D keypoints before robust estimation, but spurious matches are common and existing methods have distinct robustness or complexity limits.The cited discussion notes that 95% spurious correspondences are common; FGR tends to fail above 80%, while GORE does not estimate scale and has exponential worst-case complexity.Source: A. Correspondence-based Methods · p. 2

B. Simultaneous Pose and Correspondence Methods

  • Simultaneous Pose and Correspondence methods alternate correspondence finding and transformation estimation; local variants need a good initial guess, while global approaches can have exponential runtime.The cited global approaches include Branch-and-Bound and mixed-integer formulations.Source: B. Simultaneous Pose and… · p. 2

III. ROBUST REGISTRATION WITH TRUNCATED LEAST SQUARES COST

  • The TLS registration formulation assumes unknown but bounded measurement noise and minimizes residuals below a threshold while large-residual measurements contribute a constant cost.The threshold can be adjusted to be stricter or more lenient toward potential outliers.Source: §III · p. 3

IV. DECOUPLING SCALE, ROTATION, AND TRANSLATION ESTIMATION

TEASER decouples registration by constructing measurements invariant to subsets of scale, rotation, and translation. Pairwise differences remove translation, while normalized pairwise distances yield measurements that depend only on scale.

A. Translation Invariant Measurements (TIM)

  • Pairwise point differences cancel translation, producing Translation Invariant Measurements (TIMs) that still depend on scale and rotation.Their noise is bounded by the sum of the two points’ noise bounds; pairs involving outliers may contain arbitrary errors.Source: A. Translation Invariant Measurements… · p. 3
  • An arbitrary graph’s incidence matrix can generate TIMs, allowing the measurement graph to be chosen rather than requiring every point pair.All-pairs TIMs number at most N(N−1)/2, and the paper notes that downsampling may reduce computation.Source: A. Translation Invariant Measurements… · p. 3

B. Translation and Rotation Invariant Measurements (TRIM)

  • Taking TIM norms removes rotation dependence, and dividing by the source-pair distance produces scalar Translation and Rotation Invariant Measurements (TRIMs) of scale.The resulting measurements have bounded noise and may contain arbitrary outlier values.Source: B. Translation and Rotation Invariant… · pp. 3–4

C. Our Registration Algorithm: Truncated least squares Estimation And SEmidefinite Relaxation (TEASER)

TEASER estimates scale, rotation, and translation in sequence. Its scale stage uses polynomial-time TLS estimation and graph-based outlier pruning before passing the retained measurements to later stages.

C. Our Registration Algorithm: Truncated least squares Estimation And SEmidefinite Relaxation (TEASER)

  • TEASER estimates scale from TRIMs, rotation from scale-corrected TIMs, and translation from the original TLS problem.This is the algorithm’s three-stage cascade.Source: C. Our Registration Algorithm:… · p. 4

A. Robust Scale Estimation

  • At most 2K−1 non-empty consensus sets need consideration, so optimal TLS scale estimation can be computed by enumeration in polynomial time.The sets change only at measurement-interval boundaries; adaptive voting evaluates a representative center within each interval.Source: A. Robust Scale Estimation · p. 4
  • Adaptive voting sorts interval boundaries, evaluates the consensus set at each interval center, and returns the set with the smallest TLS cost.The consensus set is constant within each interval.Source: A. Robust Scale Estimation · pp. 4–5
  • After scale estimation, the method prunes graph edges using the scale-consistency threshold; inlier TIM edges form a clique, and a largest clique is passed to rotation estimation.The authors report that the pruned graph is sparse at high outlier rates and that maximal cliques can be solved quickly in practice.Source: A. Robust Scale Estimation · p. 5
  • When scale is already known, TEASER can skip scale estimation and still use maximal-clique inlier selection to reduce outliers.The paper gives equal scale between point clouds as an example of known scale.Source: A. Robust Scale Estimation · p. 5

B. Robust Rotation Estimation

Robust rotation estimation encodes the TLS inlier-or-outlier choice through binary cloning and relaxes the resulting problem to a semidefinite program. The relaxation is empirically tight even with many TIM outliers.

B. Robust Rotation Estimation

  • The rotation objective uses scale-corrected TIMs and bounded-noise measurements, while the formulation relaxes proper rotations to the orthogonal group, which also includes reflections.The TLS objective is the rotation-estimation problem being relaxed.Source: B. Robust Rotation Estimation · pp. 5–6
  • Binary cloning represents each measurement with a matrix choice that treats it either as an inlier or as an outlier in the TLS objective.An inlier clone uses the rotation fit; an outlier clone contributes the fixed truncation cost.Source: B. Robust Rotation Estimation · p. 5
  • The rotation problem is reformulated using a positive-semidefinite matrix and relaxed into a convex program solvable in polynomial time with per-instance guarantees.The formulation relaxes non-convex constraints, including the rank-3 condition.Source: B. Robust Rotation Estimation · p. 6
  • The relaxation is empirically tight, producing a rank-3 solution even when 90% of TIMs are outliers.When it is not tight, projecting the solution to a feasible one provides an upper bound on suboptimality.Source: B. Robust Rotation Estimation · p. 6

C. Robust Translation Estimation

Translation is estimated component-wise using the scalar TLS solver. The algorithm runs that solver once for each of the three translation entries and returns the resulting vector.

C. Robust Translation Estimation

  • The translation solver applies the polynomial-time scalar TLS method independently to each component of the translation vector.It computes t1, t2, and t3 separately.Source: C. Robust Translation Estimation · p. 6
  • The component-wise formulation uses the j-th vector entry to define each scalar translation estimation problem.The notation [·]j denotes a vector’s j-th entry.Source: C. Robust Translation Estimation · p. 6
  • The implementation calls the scalar estimator three times and returns the translation estimate as [t1 t2 t3].Each call estimates one entry of the vector.Source: C. Robust Translation Estimation · p. 6

VI. EXPERIMENTS AND APPLICATIONS

The experiments test TEASER’s component solvers and clique pruning, then benchmark the method on standard point-cloud datasets with known and unknown scale. The reported results show robust component estimates and favorable performance against comparison methods at high outlier rates.

A. Testing TEASER’s Subproblems

  • The TLS scale solver remains robust to 80% outliers, whereas maximum consensus fails three times at that rate.Scale error is the absolute difference between estimated and ground-truth scale.Source: A. Testing TEASER’s Subproblems · p. 7
  • The rotation solver’s stable rank stays numerically close to 3 at 90% outliers, and its rotation error remains below 2 degrees.The reported metrics are stable rank of the SDP solution and geodesic rotation error.Source: A. Testing TEASER’s Subproblems · p. 7
  • Both maximum consensus and TLS component-wise translation estimation remain robust to 80% outliers.Translation error is the 2-norm distance between estimated and ground-truth translation.Source: A. Testing TEASER’s Subproblems · p. 7
  • Maximal-clique pruning reduces the outlier ratio below 10%, facilitating rotation and translation estimation that in isolation tolerate more than 90% outliers.The procedure removes edges and nodes outside a maximal clique after pruning inconsistent measurements.Source: A. Testing TEASER’s Subproblems · p. 7

B. Benchmarking on Standard Datasets

  • TEASER, GORE, and RANSAC resist up to 90% outliers with known scale, while TEASER tends to be more accurate than GORE.At 90% outliers, RANSAC typically requires over 10^5 iterations; FGR resists 70%, and RANSAC (1K) starts breaking at 60%.Source: B. Benchmarking on Standard Datasets · p. 7
  • With unknown scale, TEASER and RANSAC (1K) fail only at 90% outliers, while FGR fails at 80%.RANSAC with a 60-second timeout outperforms the others at 90%, but typically needs more than 10^5 iterations.Source: B. Benchmarking on Standard Datasets · p. 7

C. Testing under Extreme Outlier Rates

Under known scale, TEASER and GORE remain robust at extreme outlier rates, and TEASER produces slightly lower estimation errors. The paper also demonstrates object localization with TEASER and summarizes its polynomial-time registration approach and implementation limitation.

C. Testing under Extreme Outlier Rates

  • Both TEASER and GORE remain robust to 99% outliers under known scale, with TEASER producing slightly lower estimation errors.The comparison uses 1,000 Bunny correspondences and covers outlier rates from 95% to 99%.Source: C. Testing under Extreme Outlier Rates · p. 7

D. Application: Object Pose Estimation and Localization

  • TEASER uses FPFH correspondences to estimate the relative pose of an object-scene pair and successfully localizes and estimates the pose of a cereal box.The figure depicts original noisy correspondences, TEASER-computed inliers, and the registered object.Source: Figure 6 · p. 8, Figure 5 · p. 8

VII. CONCLUSION

  • TEASER decouples scale, rotation, and translation; scale and component-wise translation are solved exactly by adaptive voting, while rotation uses an SDP relaxation.The conclusion describes the resulting approach as polynomial-time and reports tolerance of up to 99% outliers.Source: §VII · p. 8

VIII. PROOF OF THEOREM 1

  • Multiplying the generative model by the graph incidence matrix removes the translation term, yielding measurements invariant to translation.The proof uses that the all-ones vector lies in the incidence matrix’s null space.Source: §VIII · p. 9

X. NOVELTY OF TIMs AND TRIMs

The appendix distinguishes the paper’s graph-theoretic contribution from prior invariant-measurement uses, explains scalar TLS enumeration and its difference from consensus maximization, and supplies proofs for related formulations.

X. NOVELTY OF TIMs AND TRIMs

  • The graph-theoretic interpretation of Theorem 1 generalizes prior methods, and translation- and rotation-invariant measurements (TRIMs) are introduced as new.Earlier work used invariant measurements to filter outliers or speed up BnB; this paper uses them toward a polynomial-time robust registration solution.Source: §X · p. 9

XI. PROOF OF THEOREM 2

  • Scalar consensus sets change only at interval boundaries, so enumerating at most 2K − 1 candidate sets and evaluating their least-squares estimates yields the TLS solution in polynomial time.Each candidate estimate is chosen by the lowest TLS cost among the enumerated consensus sets.Source: §XI · p. 9

XII. COMMENTS ON TLS VS. CONSENSUS MAXIMIZATION

  • TLS and consensus maximization can differ because TLS may discard measurements that would bias its estimate, even when consensus maximization includes them as inliers.In the example, consensus includes all three measurements, while TLS chooses 0 and includes only the two measurements at 0.Source: §XII · p. 9

XIII. PROOF OF THEOREM 3

  • In the scale-selected graph, correct correspondences form a clique, which must be contained in at least one maximal clique.The proof uses this inclusion to justify maximal-clique inlier selection.Source: §XIII · p. 9

XIV. PROOF OF PROPOSITION 4

  • The proof of Proposition 4 reparameterizes each sign-weighted rotation as R_k = θ_kR to express the problem in the form of Problem (11).The reparameterized matrices satisfy constraints used to establish the equivalence.Source: §XIV · p. 10

XV. PROOF OF PROPOSITION 5

The proof rewrites the rotation-estimation problem using a matrix formulation and shows that its SDP relaxation preserves the objective while enlarging the feasible set.

XV. PROOF OF PROPOSITION 5

  • The proof states that relaxation (13) has the same objective as Problem (11) and a feasible set containing Problem (11)’s feasible set.This is the stated basis for calling (13) a convex relaxation.Source: §XV · p. 10
  • Problem (11) is reparameterized with X = [I3 R R1 … RK], making each objective summand a quadratic function of X.The proof expresses the aggregate objective as a trace involving the matrix Q̄ and XᵀX.Source: §XV · pp. 10–11
  • The matrix formulation encodes orthogonality through block constraints and expresses the condition RᵀR_k = xI3 without adding extra variables.The proof also identifies the last two constraints as redundant given the others.Source: §XV · p. 11

1 RRke1) ⇐⇒

The rotation-estimation relaxation is obtained by expressing the problem with a positive-semidefinite rank-3 matrix and dropping its rank constraint. Two constraints are redundant for the original formulation but empirically improve the relaxation's quality.

1 RRke1) ⇐⇒

  • The last two constraints in (A22) are redundant for its result, but empirical evidence says they improve the convex relaxation's quality.They are retained for that empirical benefit.Source: §1 · p. 11
  • Writing the formulation with Z = X^T X gives a positive-semidefinite rank-3 matrix representation.The derivation rewrites the problem using this matrix representation before relaxing it.Source: §1 · p. 11
  • Dropping the rank constraint from the matrix formulation yields the convex relaxation (13).All other constraints in (A28) are convex.Source: §1 · p. 11

XVI. PROOF OF PROPOSITION 6

The proposition gives optimality and feasibility guarantees for TLS rotation estimation through the relaxation and a rounded estimate. A rank-3 relaxation solution recovers an optimum of the original problem, while rounding has a bounded suboptimality.

XVI. PROOF OF PROPOSITION 6

  • A rank-3 optimal relaxation solution factors into a matrix whose first block row solves the original rotation problem optimally.The relaxation solution can be factored as Z⋆ = (X⋆)^T X⋆.Source: §XVI · pp. 11–12
  • The rounded estimate is feasible for the original problem, and its suboptimality is bounded relative to the relaxation objective.The proposition states the bound but the supplied passage does not give its expression.Source: §XVI · pp. 11–12
  • The rounding projections can be computed efficiently, using SVD for O(3) and inspection for the two-element set {−R̂, +R̂}.The latter projection selects between the two candidate matrices.Source: §XVI · p. 12

XVII. ROBUST TRANSLATION ESTIMATION

After estimating scale and rotation, TEASER estimates translation component-wise, relaxing the original vector error constraint. The supplied experiments report results on synthetic datasets, high-noise registration, and object-pose scenes.

XVII. ROBUST TRANSLATION ESTIMATION

  • The translation stage estimates t after substituting the estimated scale and rotation, solving independently for t1, t2, and t3.This component-wise TLS formulation bounds each inlier measurement's admissible error by βi, relaxing the original ℓ2 constraint to an ℓ∞ constraint.Source: §XVII · p. 12

XVIII. EXPERIMENTS AND APPLICATIONS

  • The experiments set c̄² = 1 for scale, rotation, and translation estimation.Source: §XVIII · p. 12

B. TEASER on High Noise

  • With σ = 0.1, noise destroys the Bunny's geometric structure and exceeds noise typically encountered in robotics and computer vision applications.The experiments also characterize σ = 0.01 as a reasonable standard deviation for real-world applications.Source: B. TEASER on High Noise · p. 12
  • 3.42° rotation error and 0.098m translation error were obtained by TEASER with σ = 0.1 noise and 50% outliers, despite a visually unconvincing registration.The example uses a Bunny point cloud whose geometric structure is severely corrupted by the noise.Source: B. TEASER on High Noise · p. 12

A. Benchmark on Synthetic Datasets

  • Fig. A7 compares rotation and translation errors from five methods as outlier levels increase across Armadillo, Dragon, and Buddha datasets.It also illustrates putative correspondences with 50% outliers; the caption does not state which method performs best.Source: A. Benchmark on Synthetic Datasets · p. 12, Figure A7 · p. 13

C. Object Localization and Pose Estimation

  • The eight-scene results table reports mean and standard deviation of rotation and translation errors, correspondence counts, and estimated inlier ratios.The scenes include seven cereal-box scenes and one cap scene.Source: C. Object Localization and Pose… · pp. 12–13, Table A2 · p. 13
  • Cereal-box inlier correspondence ratios were all below 10% and typically below 5%, yet TEASER estimated the relative pose accurately using a handful of inliers.For the distinctive cap, FPFH produced more inliers and registration succeeded without problems.Source: C. Object Localization and Pose… · pp. 12–13
Loading 1903.08588v2…