PaperlayerView exact revision on arXiv

Source-linked AI summary

TEASER: Fast and Certifiable Point Cloud Registration

Heng Yang, Jingnan Shi, Luca Carlone

arXiv:2001.07715v2cs.ROcs.CVmath.OC

TL;DR

Robust 3D registration with extreme outliers is difficult because TLS optimization is combinatorial and non-convex. The paper introduces certifiable TEASER and fast TEASER++, which decouple transformation estimation, provide optimality guarantees, and outperform existing methods in evaluation.

  • Problem

    3D registration needs methods that remain reliable with large numbers of spurious correspondences, although TLS formulations are difficult to solve globally.

  • Method

    TEASER decouples scale, rotation, and translation using invariant measurements, adaptive voting, maximum-clique pruning, and SDP relaxation; TEASER++ replaces the large SDP with GNC and certifies optimality.

  • Results

    Both algorithms dominate the state of the art and remain robust to more than 99% outliers; TEASER++ runs in milliseconds and solves correspondence-free problems.

  • Takeaways & Limitations

    Certifiable registration can detect failures before they cascade through robotics systems, while TEASER++ combines certification with practical speed.

Abstract

from arXiv · show

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.

SUPPLEMENTARY MATERIAL

The paper targets 3D registration with unknown or highly corrupted correspondences by combining a robust TLS formulation with decoupled, certifiable estimation. TEASER and TEASER++ provide global guarantees, extreme-outlier robustness, and practical speed across registration benchmarks.

  • Problem: 3D registration seeks a transformation aligning two point clouds, but unknown correspondences and high outlier rates can make standard estimators unreliable.These conditions are common in 3D keypoint detection and matching.
  • Robust formulation: The paper reformulates registration with a Truncated Least Squares cost that is insensitive to many spurious correspondences despite being combinatorial and non-convex.The formulation is designed for robust registration under extreme correspondence corruption.
  • Core framework: A graph-theoretic framework decouples scale, rotation, and translation, solves them in cascade, and prunes outliers through invariant measurements and maximum-clique inlier selection.The framework formalizes the decoupling under unknown-but-bounded noise.
  • Certifiable optimization: Adaptive voting solves scalar TLS subproblems in polynomial time, while a tight SDP relaxation provides certifiable robust rotation estimation.The scalar solver supports scale and component-wise translation estimation.
  • TEASER++: TEASER++ replaces the large SDP with graduated non-convexity and uses Douglas-Rachford Splitting to certify global optimality efficiently.This design yields a fast implementation while retaining certification.
  • Evaluation: Both algorithms dominate reported baselines and tolerate more than 99% outliers; TEASER++ runs in milliseconds and also handles correspondence-free registration.The evaluation covers standard benchmarks, object detection, and 3DMatch scan matching.

IV. ROBUST REGISTRATION WITH TRUNCATED LEAST SQUARES COST

The paper formulates robust 3D registration with a Truncated Least Squares cost under bounded inlier noise, allowing large numbers of outlier correspondences to be discarded. This formulation is harder than outlier-free least squares, but it enables robust estimation without assuming an outlier model.

  • Problem formulation: The robust registration problem estimates scale, rotation, and translation from putative 3D correspondences under unknown-but-bounded inlier noise.Inlier errors are bounded by β_i, while outlier correspondence offsets are arbitrary.
  • TLS formulation: TLS retains squared residuals below a threshold and truncates larger residuals to a constant, reducing the influence of outliers.The threshold c̄² controls how strictly potential outliers are treated.
  • Assumptions: The method assumes bounds on expected inlier errors but makes no assumptions about the generative model of outliers.The bound β_i can represent a 3-sigma bound or the maximum expected inlier error.
  • Computational challenge: Unlike the outlier-free case, TLS registration is globally challenging because truncation creates a combinatorial optimization and rotation is constrained to the non-convex set SO(3).Even TLS over a convex feasible set is NP-hard in the dimension and admits exhaustive search in O(2^N).
  • Core strategy: The paper’s key strategy is to reformulate measurements into quantities invariant to subsets of scale, rotation, and translation, enabling their estimation to be decoupled.This extends the closed-form decoupling available in the outlier-free case to registration with outliers.

A. Translation Invariant Measurements (TIMs)

Translation Invariant Measurements remove translation by differencing point pairs, while Translation and Rotation Invariant Measurements additionally remove rotation through pairwise norms. These invariants enable cascaded estimation of scale, rotation, and translation.

  • TIMs: Subtracting two correspondence equations cancels translation and produces TIMs whose measurements depend on scale and rotation.For pair (i,j), the relative vectors are ā_ij = a_j − a_i and b̄_ij = b_j − b_i.
  • TIMs: TIM noise is bounded by δ_ij = β_i + β_j when the two participating correspondences have bounded errors.The pairwise outlier term is zero when both correspondences are inliers and arbitrary otherwise.
  • Graph construction: A graph with arbitrary edges generates TIMs through its incidence matrix, connecting invariant measurements to graph topology.A complete graph can generate up to N(N − 1)/2 pairwise measurements.
  • TRIMs: Taking the norm of each TIM vector removes rotation, yielding TRIMs whose generative model depends only on the unknown positive scale.The normalized measurement s_ij = ∥b̄_ij∥/∥ā_ij∥ has noise bound α_ij = δ_ij/∥ā_ij∥.
  • Cascaded estimation: The invariants support a cascade that estimates scale from TRIMs, rotation from TIMs, and translation from the original correspondences.Scale and component-wise translation use scalar TLS estimation, while rotation uses robust rotation estimation.

D. Boosting Performance: Max Clique Inlier Selection (MCIS)

The graph-theoretic formulation enables additional outlier pruning after scale estimation. Inlier TIM edges form a clique, so maximal-clique search can isolate a set containing all inliers before the remaining estimation stages.

  • Graph pruning: After scale estimation, edges whose TRIM residuals exceed the TLS threshold are removed to form a pruned graph.The pruning rule discards edge (i,j) when |s_ij − ŝ| > c̄ α_ij.
  • Max Clique Inlier Selection: Inlier TIM edges form a clique in the pruned graph, and at least one maximal clique contains all inliers.This is the maximal clique inlier selection guarantee.
  • Max Clique Inlier Selection: Maximal-clique search can therefore prune outliers before the rotation and translation estimates are computed.The graph is sparse under high outlier rates, supporting practical clique computation despite worst-case exponential complexity.
  • TEASER pipeline: The TEASER pipeline takes point correspondences and noise bounds, computes TIMs and TRIMs, estimates scale, rotation, and translation, then returns the three transformation components.Algorithm 1 specifies outputs ŝ, R̂, and t̂.
  • Adaptive Voting: Scalar TLS estimation for scale and each translation component can be solved exactly in polynomial time using adaptive voting.Adaptive voting enumerates intervals with constant consensus sets and returns the lowest-cost solution.

VIII. ROBUST ROTATION ESTIMATION:

Robust rotation estimation is transformed from a non-convex TLS problem into a QCQP and then relaxed to an SDP. Binary cloning handles inlier/outlier decisions, while the SDP provides global solutions or certificates in practical problems.

  • Problem: The robust rotation problem is globally difficult because TLS is non-convex and the rotation domain SO(3) is non-convex.The paper nevertheless reports polynomial-time global solutions in virtually all practical problems using a tight SDP relaxation.
  • Certification: The SDP relaxation convexifies the QCQP and supports both globally optimal rotation estimation and a posteriori certification of a proposed rotation.The fast certifier tests whether a rotation guess is optimal without requiring the full large relaxation to be solved by a conventional SDP solver.
  • QCQP reformulation: A quaternion formulation and binary cloning reformulate robust rotation estimation as a QCQP.Binary cloning introduces one quaternion clone per measurement, with sign choices representing inliers and outliers.
  • TLS encoding: Binary variables encode whether each measurement is treated as an inlier or an outlier, exposing the TLS non-convexity in a form suitable for relaxation.The TLS cost’s binary structure enables binary cloning and subsequent semidefinite relaxation.
  • QCQP formulation: The QCQP uses a stacked vector of the global quaternion and per-measurement clones, with a known symmetric matrix determined by TIM measurements.The resulting QCQP is equivalent to the binary-cloning formulation in its optimal rotation q.

B. Semidefinite Relaxation

The paper relaxes the non-convex TLS rotation problem into an SDP whose rank-1 solutions certify global optimality. TEASER++ avoids the expensive SDP by combining GNC rotation estimation with Douglas-Rachford-based certification.

  • SDP formulation: The TLS rotation problem is formulated as a non-convex QCQP and relaxed into a convex SDP by dropping the rank-1 constraint and adding redundant constraints.The redundant constraints enforce symmetry in off-diagonal 4×4 blocks and tighten the relaxation.
  • Global optimality: If the SDP solution has rank 1, its cost matches the QCQP optimum and its rank-1 decomposition yields the unique global rotation minimizer up to quaternion sign.The two quaternion signs represent the same rotation.
  • Computational trade-off: The SDP is empirically tight under noise and extreme outlier rates exceeding 95%, but solving it for K = 100 takes about 1200 seconds with MOSEK.The quaternion-based relaxation also outperforms a comparable rotation-matrix relaxation in accuracy and robustness.
  • TEASER++: TEASER++ uses GNC for fast TLS rotation estimation and certifies the candidate a posteriori with Douglas-Rachford Splitting.The certifier computes a suboptimality bound even when the candidate or relaxation is not globally optimal.

IX. PERFORMANCE GUARANTEES

This section gives certifiable recovery conditions for TEASER in noiseless and noisy settings with outliers. The guarantees weaken with noise and depend on geometric, consensus, and certification assumptions.

  • Noiseless inliers and random outliers: In the noiseless random-outlier case, TEASER can recover the ground-truth transformation from 3 noiseless non-collinear inliers and arbitrarily many generic outliers.The recovery result is probabilistic and assumes zero residuals in each subproblem plus a valid rotation certificate.
  • Noiseless inliers and adversarial outliers: With adversarial outliers, exact recovery requires at least 3 more inliers than outliers, no three inliers collinear, zero subproblem residuals, and a valid rotation certificate.When inliers do not exceed outliers, TEASER instead seeks a transformation consistent with the largest inlier set.
  • Theoretical contribution: The paper presents the first exact recovery results for registration with outliers.These results are stated in Theorems 15–16.

B. Approximate Recovery with Outliers and Noisy Inliers

The experiments evaluate module-level robustness and the practical TEASER++ implementation under noisy and outlier-corrupted registration. They show strong performance in the tested regimes while retaining computational and modeling boundaries.

  • Scope of guarantees: The theoretical noisy-registration bounds require bounded inlier noise and geometric and consensus separation assumptions, so they do not cover unrestricted noisy configurations.The paper notes that tighter bounds are more expensive to compute.
  • TEASER++ implementation: TEASER++ replaces the large SDP with GNC rotation estimation and uses a scalable certifier, enabling millisecond execution on practical problem instances.Scale estimation and maximum-clique pruning first reduce the outlier burden presented to GNC.
  • Scale estimation: The TLS scale solver remains robust against 80% outliers, whereas Consensus Maximization failed twice in that regime.Scale error is measured as |ŝ−s°|.
  • Rotation estimation: The GNC rotation heuristic performs well below 80% outliers and then begins failing, while the two relaxations have similar performance and the quaternion relaxation is slightly more accurate at high outlier rates.The quaternion relaxation is reported to be tighter than the earlier rotation-matrix relaxation.
  • Translation estimation: Component-wise translation estimation using both Consensus Maximization and TLS is robust against 80% outliers.The translation error is the 2-norm distance between estimated and ground-truth translations.

B. Benchmarking on Standard Datasets

Across standard, object-detection, and scan-matching evaluations, TEASER and TEASER++ remain accurate and robust under extreme outlier rates while TEASER++ substantially reduces runtime. The methods also support correspondence-free registration, though performance is bounded by insufficient or non-unique inlier structure.

  • Standard benchmarks: TEASER, TEASER++, and GORE remain robust against up to 99% outliers, while TEASER and TEASER++ produce lower estimation errors than GORE.Under known scale, TEASER and TEASER++ outperform several baselines as outlier rates increase.
  • Standard benchmarks: TEASER++ consistently runs in less than 30ms for the unknown-scale Bunny benchmark.At 90% outliers, RANSAC1min performs better but typically requires more than 10^5 iterations, which is not practical for real-time use.
  • Correspondence-free registration: In correspondence-free registration, TEASER++ succeeds across overlap levels without an initial guess and starts failing below 10% overlap.Its runtime is dominated by maximum-clique computation and scale estimation, yet it is orders of magnitude faster than Go-ICP below 40% overlap.
  • Object pose estimation: TEASER computes highly accurate object poses from fewer than 10% inlier correspondences, typically below 5%, on a real RGB-D dataset.TEASER filters noisy FPFH matches into inlier correspondences before estimating the pose.
  • Scan matching: TEASER++ outperforms RANSAC in 3DMatch scan matching, while its certified variant rejects unreliable registrations for safer loop-closure use.The certified procedure has higher average runtime, but certification can identify incorrect estimates that would otherwise compromise maps.
  • Limitations: TEASER++ cannot solve cases with no inliers or too few inliers for a unique registration, and scene symmetries can yield incorrect but certified solutions.Symmetries may produce alternative registrations with errors around 90° or 180°.

A. Manifesto of Certifiable Perception

The paper argues that robust perception should certify solution quality or declare failure, because robust estimation is generally intractable and heuristic methods can return arbitrarily poor estimates. It contrasts Truncated Least Squares with Consensus Maximization, showing that they can select different inliers and have different robustness properties.

  • Why certification matters: Polynomial-time exact or near-optimal robust estimation is generally impossible for worst-case instances.The paper therefore targets algorithms that perform well on typical instances while detecting difficult cases.
  • Certifiable perception: Certifiable algorithms provide a quality certificate or declare failure when certification is unavailable.The certificate may establish optimality, bound sub-optimality, or bound distance from the optimal solution.
  • Why certification matters: TEASER is described as a certifiable algorithm for registration and rotation search, extending certification to outlier-robust estimation in robotics and vision.Its soundness means it does not certify incorrect solutions, although it may declare failure.
  • TLS versus Consensus Maximization: Consensus Maximization minimizes the number of outliers, whereas TLS minimizes truncated residual cost and may choose a different inlier set.TLS can discard measurements that would otherwise enlarge consensus when they induce substantial estimation bias.
  • TLS versus Consensus Maximization: In the scalar example, Consensus Maximization selects all three measurements at sMC = 1.5, while TLS selects measurements {1, 2} at ŝ = 0.The example uses s1 = s2 = 0, s3 = 3, and c̄ = 2.
  • TLS versus Consensus Maximization: The paper reports that Consensus Maximization often has a lower breakdown point than TLS because TLS penalizes inlier residuals and depends on their distribution.The two formulations are expected to behave similarly when the inlier set is large, but not in general.

H. Proof of Proposition 9: Binary Cloning

The binary-cloning proof reparameterizes binary signs multiplying a quaternion as additional quaternions, then establishes equivalent QCQP and SDP formulations. Dropping the rank constraint yields a convex SDP whose rank-one solutions recover global minimizers.

  • Binary cloning: Binary cloning replaces each sign-variable product θkq with a new quaternion qk = θkq.Because θk = q^Tqk, the mixed-integer formulation can be rewritten using q and the cloned quaternions.
  • QCQP reformulation: The cloned-quaternion formulation is equivalent to a QCQP with quadratic objectives and unit-norm consistency constraints.The proof shows equivalence of both objective functions and feasible sets.
  • QCQP reformulation: Stacking the quaternions into x and lifting to Z = xx^T converts the QCQP into a rank-constrained SDP.The lifted formulation preserves the objective and constraints when the rank-one condition is retained.
  • SDP relaxation: The SDP relaxation is obtained by adding redundant constraints and dropping the rank constraint from the lifted formulation.The resulting dual SDP is derived through standard Lagrangian duality and matches the relaxation with redundant constraints.
  • Global optimality: If the relaxed optimum has rank one, its decomposition is feasible for the rank-constrained problem and is a global minimizer of the original QCQP.This establishes the link between rank-one SDP solutions and global optimality.

L. Proof of Theorem 14: Optimality Certification

The certification proof characterizes global optimality through a positive-semidefinite matrix lying in an affine subspace. Douglas-Rachford Splitting finds this intersection efficiently and still supplies a sub-optimality bound when certification fails.

  • Matrix certificate: A feasible rotation estimate is globally optimal if a matrix M satisfies the stated affine constraints, annihilates the estimate, and is positive semidefinite.The sufficient condition is expressed through M x̂ = 0 and M − Q + μ̂J belonging to the affine subspace structure.
  • Matrix certificate: Under strong duality, the same matrix-existence condition is also necessary for global optimality.Thus the certificate gives a sufficient-and-necessary characterization in the strong-duality setting.
  • Sub-optimality bounds: Any matrix in the affine subspace, even if not positive semidefinite, yields a relative sub-optimality bound through its minimum eigenvalue.The affine subspace depends on the candidate estimate.
  • Rotated certificate space: A rotated affine subspace preserves positive semidefiniteness, eigenvalues, and the relative sub-optimality bound while enabling faster projections.The transformation maps the original certificate search to an equivalent intersection problem.
  • Douglas-Rachford Splitting: Douglas-Rachford Splitting searches for the intersection of the rotated affine subspace and the PSD cone using projections onto each convex set.When the intersection is nonempty, the iterates converge and the sub-optimality bound tends to zero.

M. Closed-form Projections

The appendix derives closed-form projections used by Douglas-Rachford Splitting and then proves TEASER’s estimation contracts. Under stated conditions, TEASER recovers the ground truth exactly in noiseless settings and bounds estimation error with noisy inliers and adversarial outliers.

  • M. Closed-form Projections: Projection onto the PSD cone is computed by spectral decomposition followed by replacing negative eigenvalues with zero.This gives a closed-form projection used in the certification algorithm.
  • M. Closed-form Projections: The affine projection is constructed blockwise, including matrix, scalar, and vector components of diagonal and off-diagonal blocks.The derivation uses residual vectors from the current rotation estimate and provides a closed-form implementation.
  • 3) Exact recovery of TEASER: For noiseless inliers and random outliers, TLS matches maximum consensus in each subproblem, and maximum consensus recovers the ground truth with probability 1.Consequently, TEASER almost surely recovers ŝ = s◦, R̂ = R◦, and t̂ = t◦.
  • 2) Exact recovery of maximum consensus: With noiseless inliers and adversarial outliers, recovery requires a stronger inlier-count condition ensuring enough correspondences are shared by competing consensus sets.The proof uses at least three common noise-free correspondences to force an alternative transformation to equal the ground truth.
  • 2) Exact recovery of maximum consensus: In the adversarial regime, recovering the ground truth does not guarantee that every outlier is rejected because some outliers can be indistinguishable from inliers.The guarantee concerns transformation recovery rather than perfect outlier classification.
  • 2) Noisy recovery of maximum consensus: For noisy inliers and adversarial outliers, TEASER’s selected inliers contain the true inliers when the maximum-consensus assumptions hold.The proof then derives bounds on the resulting scale, rotation, and translation estimates.
  • 2) Noisy recovery of maximum consensus: The noisy recovery bound requires four non-coplanar inliers so the relevant minimum singular value is nonzero.Non-coplanarity makes the corresponding difference vectors linearly independent.

Q. TLS Translation Estimation: Component-wise vs. Full

The paper compares component-wise translation estimation with globally solving the full TLS translation problem, finding the approximation sufficiently close while evaluating related robust registration components across datasets and corruption levels.

  • Component-wise versus full TLS: Component-wise translation estimation is an approximation to the full TLS translation estimate.The full vector can instead be obtained through global techniques such as SDP or GNC.
  • Component-wise versus full TLS: Adaptive voting estimates translation components separately, while TLS: SDP and TLS: GNC solve the full translation vector.The SDP approach provides a global optimality certificate; GNC is efficient but provides no optimality guarantees.
  • Rotation relaxation comparison: The quaternion-based SDP relaxation remains tight under randomized unit-vector tests, whereas the rotation-matrix relaxation has a much larger relative duality gap.Both relaxations achieve similar rotation estimation errors on the Bunny dataset.
  • Benchmark results: TEASER dominates competing methods and remains insensitive to extreme outlier rates on Armadillo, Dragon, and Buddha.The comparison includes FGR, GORE, RANSAC1K, and RANSAC at increasing outlier levels.
  • TEASER++ scalability: At 10,000 correspondences, TEASER++ solves registration in around 2 seconds while outperforming GORE across tested correspondence counts.Its runtime scales with the number of correspondences but remains practical for large inputs.
  • High-noise registration: With σ = 0.1 noise and 50% outliers, TEASER still returns a registration with rotation error 3.42° and translation error 0.098m.The result is visually difficult for a human to verify despite these ground-truth errors.
  • RGB-D object pose estimation: TEASER computes highly accurate relative poses from fewer than 10% inlier correspondences, typically fewer than 5%, on selected RGB-D scenes.The figures show initial FPFH correspondences, retained TEASER inliers, and the registered object.

U. Proof of Proposition 33: Projection onto ¯L

The proof establishes an equivalent projection onto ¯L by shifting the input and projecting onto ¯H, then derives the projection block by block.

  • Equivalent projection: The projection onto ¯L is equivalent to projecting M − ¯Q + ˆµJ onto ¯H and shifting back.This is the central statement of Theorem 34.
  • Block decomposition: The Frobenius-norm objective is separated into block-wise matrix, scalar, and vector parts.The decomposition enables independent treatment of several projection components.
  • Block projection steps: Diagonal matrix blocks are projected by subtracting their mean so their sum satisfies the required constraint.The procedure first computes the mean across diagonal matrix parts and subtracts it from each block.
  • Block projection steps: Off-diagonal matrix blocks are projected to their nearest skew-symmetric matrices, while off-diagonal scalar parts are set to zero.Symmetry means only upper-triangular off-diagonal blocks need to be projected.
  • Vector projection: The coupled off-diagonal vector projection reduces to an unconstrained convex optimization with L linear stationarity equations.The resulting matrix system uses the linear map C and vectors F_l(H) and A_l.
  • Vector projection: The structured matrix A has a closed-form inverse, yielding an explicit solution for the coupled vector projection.Theorem 35 states that each column of the inverse can be computed in closed form.

V. Initial Guess for Algorithm 3

Algorithm 3 starts from a feasible matrix whose off-diagonal blocks are zero and whose diagonal components satisfy the constraints of ¯H.

  • Initial feasible point: The initial guess ¯M_0 is constructed using a matrix ∆_0 belonging to ¯H.The construction is designed to satisfy all constraints defining the feasible set.
  • Initial feasible point: All off-diagonal blocks of ∆_0 are initialized to zero.This provides the off-diagonal initialization used by Algorithm 3.
  • Initial feasible point: The diagonal scalar terms are assigned using the stated expressions involving ˆθ_k, ∥ˆξ_k∥², and ¯c².These assignments are part of the construction that preserves feasibility.

W. Tighter Bounds for Theorem 17

The paper derives tighter estimation-error bounds for scale, rotation, and translation under noisy inliers and adversarial outliers, with dependencies that propagate through the estimation cascade.

  • Tighter bounds: The section improves Theorem 17 with tighter but more complex bounds for scale, rotation, and translation estimation.The bounds are developed separately and then related across the transformation components.
  • Assumptions: The estimation contract assumes at least three distinct non-collinear inliers, bounded inlier noise, and a sufficiently smaller second-largest consensus set.It also assumes that the inliers belong to the maximum consensus set in each subproblem.
  • Scale bound: Scale-error bounds use residual quantities computed from the TLS solution and the minimum corresponding quantity over the true inliers.Unknown inlier sets require a worst-case bound over the consensus set.
  • Rotation bound: The rotation bound depends on the scale bound and is well-defined when the normalized inlier matrix has sufficient rank.The geodesic rotation error is the angular distance between the estimated and ground-truth rotations.
  • Translation bound: The translation bound depends on both the scale bound and the rotation bound.When the true inliers are unknown, the worst-case bound requires enumerating subsets of three inliers.
Loading 2001.07715v2…