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.

    Source: §I · p. 2, §IV · p. 5

  • 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.

    Source: §I · p. 2, SEMIDEFINITE RELAXATION AND FAST… · p. 8, §X · p. 12

  • 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.

    Source: §I · p. 2, §XII · pp. 17–18

  • Takeaways & Limitations

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

    Source: §XII · p. 17, A. Manifesto of Certifiable Perception · p. 21

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.Source: §I · pp. 1–2, A. Correspondence-based Methods · p. 3

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.Source: §I · p. 2

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.Source: §I · p. 2

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.Source: §I · p. 2

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.Source: §I · p. 2

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.Source: §I · pp. 2–3, §II · p. 3

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.Source: §IV · p. 5

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.Source: §IV · p. 5

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.Source: §IV · p. 5

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).Source: §IV · p. 5

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.Source: §V · p. 5, §IV · p. 5

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.Source: A. Translation Invariant Measurements… · pp. 5–6
  • 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.Source: A. Translation Invariant Measurements… · p. 6

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.Source: A. Translation Invariant Measurements… · p. 6

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∥.Source: B. Translation and Rotation Invariant… · p. 6

Cascaded 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.Source: D. Boosting Performance: Max Clique… · p. 7

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.Source: D. Boosting Performance: Max Clique… · p. 7
  • 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.Source: D. Boosting Performance: Max Clique… · p. 7

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̂.Source: E. Pseudocode of TEASER · p. 7

Adaptive Voting

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.Source: SEMIDEFINITE RELAXATION AND FAST… · p. 8

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.Source: SEMIDEFINITE RELAXATION AND FAST… · p. 8

QCQP reformulation

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.Source: A. Robust Rotation Estimation as a QCQP · pp. 8–9

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.Source: A. Robust Rotation Estimation as a QCQP · p. 9

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.Source: B. Semidefinite Relaxation · pp. 9–10

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.Source: B. Semidefinite Relaxation · p. 10

Computational trade-off

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.Source: C. Fast Global Optimality Certification · pp. 10–11

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.Source: A. Exact Recovery with Outliers and… · p. 11

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.Source: A. Exact Recovery with Outliers and… · p. 11

Theoretical contribution

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.Source: B. Approximate Recovery with Outliers… · p. 12

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.Source: §X · p. 12

Scale estimation

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.Source: A. Testing TEASER’s and TEASER++’s… · p. 13

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.Source: A. Testing TEASER’s and TEASER++’s… · p. 13

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.Source: B. Benchmarking on Standard Datasets · p. 14
  • 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.Source: B. Benchmarking on Standard Datasets · p. 14

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.Source: C. Simultaneous Pose and… · pp. 14–15

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.Source: D. Application 1: Object Pose… · p. 16, §XII · p. 17

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.Source: E. Application 2: Scan Matching · p. 16

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°.Source: E. Application 2: Scan Matching · pp. 16–17

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.Source: A. Manifesto of Certifiable Perception · p. 21

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.Source: A. Manifesto of Certifiable Perception · p. 21

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.Source: A. Manifesto of Certifiable Perception · p. 21

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.Source: C. Truncated Least Squares vs.… · p. 22
  • 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.Source: C. Truncated Least Squares vs.… · p. 22
  • 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.Source: C. Truncated Least Squares vs.… · p. 22

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.Source: H. Proof of Proposition 9: Binary… · p. 23

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.Source: §I · pp. 23–25
  • 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.Source: J. Proof of Proposition 11: Matrix… · p. 25

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.Source: K. Proof of Theorem 13: SDP Relaxation… · p. 25

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.Source: K. Proof of Theorem 13: SDP Relaxation… · p. 26

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.Source: 1) Matrix Certificate for Global… · p. 26
  • 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.Source: 1) Matrix Certificate for Global… · p. 26

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.Source: 2) Sub-optimality Bound · p. 26

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.Source: 3) Douglas-Rachford Splitting and… · p. 27

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.Source: 3) Douglas-Rachford Splitting and… · p. 27

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

3) Exact recovery of TEASER

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.Source: 2) Exact recovery of maximum consensus · pp. 28–29
  • 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.Source: 2) Exact recovery of maximum consensus · p. 29

2) Noisy recovery of maximum consensus

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.Source: Q. TLS Translation Estimation:… · p. 30
  • 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.Source: Q. TLS Translation Estimation:… · p. 30

Rotation relaxation comparison

Benchmark results

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.Source: 3) TEASER++ on Problems with… · p. 31, Figure 16 · p. 33

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.Source: 2) TEASER on High Noise · p. 31, Figure 15 · p. 32

RGB-D object pose estimation

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

Block decomposition

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.Source: U. Proof of Proposition 33: Projection… · p. 38
  • 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.Source: U. Proof of Proposition 33: Projection… · p. 38

Vector projection

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.Source: §V · pp. 41–42
  • All off-diagonal blocks of ∆_0 are initialized to zero.This provides the off-diagonal initialization used by Algorithm 3.Source: §V · p. 42
  • 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.Source: §V · p. 42

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.Source: W. Tighter Bounds for Theorem 17 · p. 42

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.Source: W. Tighter Bounds for Theorem 17 · p. 42

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.Source: W. Tighter Bounds for Theorem 17 · pp. 42–43

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.Source: W. Tighter Bounds for Theorem 17 · pp. 42, 44

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.Source: W. Tighter Bounds for Theorem 17 · p. 44

Related papers

Loading 2001.07715v2…