PaperlayerView exact revision on arXiv

Source-linked AI summary

Guaranteed Outlier Removal for Point Cloud Registration with Correspondences

Álvaro Parra Bustos, Tat-Jun Chin

arXiv:1711.10209v1cs.CV

TL;DR

Robust point cloud registration is costly because 3D keypoint correspondences contain many outliers and are often numerous. GORE preprocesses correspondences with deterministic geometric tests that remove only true outliers, preserving the global optimum while accelerating later optimization.

  • Problem

    3D keypoint mismatches create high outlier rates, making robust registration expensive because RANSAC and global methods scale poorly with contamination and data size.

  • Method

    GORE uses deterministic geometric consistency checks and bounds to reject correspondences guaranteed not to belong to the globally optimal solution.

  • Results

    Almost 90% of true outliers can be eliminated on real data, while the globally optimal solution is preserved and subsequent optimization is substantially accelerated.

  • Takeaways & Limitations

    GORE provides a deterministic preprocessing stage that reduces data and outlier ratios before approximate or globally optimal registration.

  • Takeaways & Limitations

    GORE can be ineffective for low-outlier-ratio problems and generally cannot remove all true outliers except in trivial instances.

Abstract

from arXiv · show

An established approach for 3D point cloud registration is to estimate the registration function from 3D keypoint correspondences. Typically, a robust technique is required to conduct the estimation, since there are false correspondences or outliers. Current 3D keypoint techniques are much less accurate than their 2D counterparts, thus they tend to produce extremely high outlier rates. A large number of putative correspondences must thus be extracted to ensure that sufficient good correspondences are available. Both factors (high outlier rates, large data sizes) however cause existing robust techniques to require very high computational cost. In this paper, we present a novel preprocessing method called \emph{guaranteed outlier removal} for point cloud registration. Our method reduces the input to a smaller set, in a way that any rejected correspondence is guaranteed to not exist in the globally optimal solution. The reduction is performed using purely geometric operations which are deterministic and fast. Our method significantly reduces the population of outliers, such that further optimization can be performed quickly. Further, since only true outliers are removed, the globally optimal solution is preserved. On various synthetic and real data experiments, we demonstrate the effectiveness of our preprocessing method. Demo code is available as supplementary material.

1 INTRODUCTION

3D keypoint correspondences frequently contain mismatches, making robust registration expensive when outlier rates and input sizes are large. GORE deterministically removes only correspondences excluded from the globally optimal solution, reducing the burden on subsequent optimization while preserving that solution.

  • 1 INTRODUCTION: 3D keypoint matching methods produce mismatches, so registration must estimate transformations robustly from point correspondences.The task is rigid registration between point clouds, where the transformation is a rotation or Euclidean transformation.
  • 1 INTRODUCTION: RANSAC runtime grows exponentially with outlier ratio, while real point clouds commonly exceed 95% outliers.The high contamination is linked to lower 3D matching accuracy caused by irregular density and limited point texture.
  • 1 INTRODUCTION: Global methods provide optimal solutions but become costly with large correspondence sets and high outlier contamination.Branch-and-bound runtimes increase exponentially with input size, and real correspondence sets of N = 1000 can require several hours.
  • 1.1 Our contributions: GORE reduces the input H to H′ while guaranteeing that every discarded correspondence is a true outlier, unlike RANSAC’s potentially suboptimal consensus output.The globally optimal solution is therefore preserved in H′, although GORE need not remove every true outlier.
  • 1.1 Our contributions: On real data, GORE eliminates almost 90% of true outliers and can reduce total optimization runtime by more than an order of magnitude.The reduced set can benefit both approximate methods such as RANSAC and globally optimal optimization.
  • 1.1 Our contributions: GORE is deterministic and also returns a suboptimal transformation empirically comparable in quality to RANSAC’s result.The method extends earlier 3 DoF rotational GORE to 6 DoF Euclidean registration.
  • 1.2 Related work: preprocessing for robust estimation: Except in trivial instances, GORE generally cannot remove all true outliers because doing so would solve the intractable maximum consensus problem.Its guarantee concerns only rejected correspondences; residual outliers may remain in H′.

2 THEORY OF GORE

GORE tests whether each correspondence can participate in a globally optimal consensus solution by comparing an upper bound on a constrained subproblem with a lower bound on the original problem. Correspondences failing this test are safely rejected, and the bounds also yield a suboptimal solution.

  • 2 THEORY OF GORE: The robust registration problem is reformulated into subproblems Pk that seek the best transformation agreeing with as many matches as possible while aligning match k.The subproblem quality is denoted pk, and the reformulation supports outlier identification rather than directly simplifying the original optimization.
  • 2 THEORY OF GORE: Given a lower bound l on the original solution and an upper bound p̂k on Pk, GORE tests each correspondence for safe rejection.The lower bound may come from any suboptimal solution to the original problem.
  • 2 THEORY OF GORE: If p̂k < l, correspondence (xk, yk) is a true outlier and cannot belong to the globally optimal inlier set.The test follows because inclusion in the global optimum would require pk = |I∗|, contradicting p̂k < l ≤ |I∗|.
  • 2 THEORY OF GORE: GORE computes l and p̂k for all k, using efficient bound calculations and iterative procedures that tighten the bounds during rejection testing.The algorithms are developed separately for rotational and 6 DoF rigid registration.

3 GORE FOR ROTATIONAL REGISTRATION

For rotational registration, GORE uses geometric bounds on feasible rotations to safely prune correspondences while preserving the globally optimal solution. Experiments show that this preprocessing substantially improves runtime at high outlier rates and retains accurate approximate rotations.

  • Problem formulation: GORE first develops rotational registration as the kernel for the full 6 DoF method.The rotational problem uses an angular error metric with data-dependent inlier thresholds.
  • Rotation parameterization: A candidate rotation is decomposed into a rotation B satisfying the reference-match constraint and an angle rotation A about axis Bxk.This reduces the search to a 2 DoF choice for B and a 1 DoF rotation angle.
  • Uncertainty bounds: GORE bounds each correspondence’s possible transformed position using spherical uncertainty regions induced by feasible rotations.The feasible axis region is centered at yk, while additional spherical regions bound possible locations of Bxi and Rkxi.
  • Guaranteed pruning: A correspondence is safely removed when its allowable region does not intersect the target uncertainty region, because no feasible rotation can align it.This is the geometric basis of guaranteed outlier removal.
  • Guaranteed pruning: The method converts surviving uncertainty bounds into angular intervals and compares bounds to produce a reduced correspondence set guaranteed to contain the global optimum.The interval reduction supports efficient upper-bound computation, and the output set H′ preserves the globally optimal solution.
  • Experimental evaluation: At outlier rates of at least 90%, GORE preprocessing significantly improves runtime across tested data sizes, while GORE’s approximate rotation error remains at most 0.05°.RANSAC runtime grows exponentially with outlier rate, whereas GORE grows much more slowly; preprocessing also improves RANSAC and BnB pipelines.
  • Experimental evaluation: Warm-starting BnB with a RANSAC result does not reduce runtime, whereas reducing the data amount is the dominant factor in accelerating BnB.At high outlier rates, RANSAC itself becomes a major computational burden.

4 GORE FOR EUCLIDEAN REGISTRATION

For 6 DoF Euclidean registration, GORE derives an upper bound for each correspondence through a two-step geometric procedure, then compares it with a lower bound to safely reject outliers. The algorithm preserves remaining correspondences and a current transformation estimate while substantially reducing the data considered for exact optimization.

  • The Euclidean-registration subproblem uses a rigid transformation T_k=(R_k,t_k) constrained by correspondence residuals no greater than ξ.
  • q_k is used as an upper bound for the subproblem value p_k because Theorem 3 establishes q_k ≥ p_k.q_k is the maximum objective value of the rotational registration problem Q^rig_k.
  • GORE first converts Q^rig_k to an angular-error rotational problem and applies Algorithm 1 to prune correspondences, leaving H′_k.This is the first step of the two-step procedure for computing the upper bound.
  • If the upper bound ˆp_k is below the current lower bound l, correspondence (x_k,y_k) is rejected as an outlier; otherwise, BnB exactly solves Q^rig_k on the reduced set.The second step is applied only when the initial rejection test is unsuccessful.
  • Algorithm 2 iterates through correspondences, updates the lower bound and transformation estimate from consensus sets, and returns the retained set H′ and transformation ˜T.The algorithm initializes H, H′, O, V, and l, then removes correspondences failing the upper-bound test.
  • Algorithm 2 has exponential worst-case time complexity because BnB may be required, but pruning usually makes its working subset much smaller than the original input.The paper states that the algorithm is efficient in practice and demonstrates high efficiency on large inputs.

5 RESULTS FOR RIGID REGISTRATION

GORE was evaluated on synthetic, real, and RGB-D rigid-registration problems with extremely high outlier rates. It reduced correspondence sets quickly while preserving accurate or globally optimal registration and substantially accelerating downstream solvers.

  • Qualitative evaluation: For N = 500 real-data instances containing >90% outliers, GORE terminated within 5 seconds except vaihingen-b at 11 seconds and retained <15% of the input.The approximate transformation produced by GORE gave satisfactory registrations.
  • Quantitative benchmarking: GORE reduced all real-data problem instances to H′ within 30 seconds, and to H′ < 70 for most instances.The resulting reduction in data size and outlier rate greatly reduced the time to obtain local or global solutions.
  • Quantitative benchmarking: GORE+BnB typically required half the runtime of BnB alone while remaining globally optimal after reducing the median BnB problem size to 50.GORE+RANSAC runtimes were two orders of magnitude smaller than RANSAC alone.
  • RGB-D evaluation: For RGB-D data with more than 95% outliers, GORE produced H′ <10% of the original points and satisfactory approximate transformations.It terminated within 7 seconds for stitching and under 0.5 seconds for localization.
  • Failure case: GORE can be ineffective at low outlier ratios: with η = 0.23, it removed only two outliers and BnB ran faster without preprocessing.This failure case occurred on two consecutive views of bunny.

6 CONCLUSIONS

The paper presents GORE as a deterministic geometric preprocessor for robust Euclidean point cloud registration. Experiments show that reducing data and outliers accelerates both local and global registration while preserving globally optimal solutions.

  • Conclusion: GORE guarantees that every removed correspondence is absent from the globally optimal solution.The method uses simple geometric operations and is deterministic and efficient.
  • Conclusion: Reducing the amount of data and outliers with GORE greatly speeds up both local and global registration.

A.1 Derivation of (18) in the main text

This derivation establishes the rotation-distance relation needed for condition (3). It uses a rotation minimizing motion between the relevant points and the triangle inequality on rotation distances.

  • Rotation-distance relation: The rotation B is related to the estimated rotation ˆB through a correction rotation C, yielding d∠(B, ˆB) = d∠(C).C minimizes motion between yk and u in Sϵk(yk).
  • Rotation-distance relation: Because C has rotation axis orthogonal to yk and angle ϵk, the derivation connects the rotation distance to the angular uncertainty ϵk.
  • Rotation-distance relation: The displayed relation is equivalently expressed in the form given by equation (18) in the main text.

A.3 Derivation of (23) in the main text

The derivation bounds the possible location of a point rotated about an uncertain axis, then extends the bound to uncertainty in the point itself. The appendix uses spherical geometry centered on yk to support these bounds.

  • Rotation-axis uncertainty: For a unit-norm point p rotated by Aθ,u with uncertain axis u ∈ Sϵk(yk), the derivation bounds the possible locations of Aθ,up.The axis-angle representation and the angular radius ϵk of Sϵk(yk) provide the bound.
  • Point uncertainty: The point-location bound is extended to an uncertain point p drawn from Sϵk(ˆBxi).The extension uses the triangle inequality together with the earlier bound.
  • Geometric interpretation: Figure A1 determines γi from a right triangle whose cathetus is half the longest segment in Sϵi(yi) and whose hypotenuse is the radius of circ(yi, yk).
  • Geometric interpretation: The diagram stereographically projects the sphere to a plane using yk as the North Pole; circles and spherical regions retain their shapes, but projection is only for presentation.
  • Geometric interpretation: If ˆBxi is close to yk, the North Pole may lie in Lk(xi), in which case Θi is set to [−π, π].

A.4.2 Non-degenerate cases

The method determines bounding intervals for αi and βi using geometric constraints on spherical regions. Since exact solutions are difficult, valid intervals are obtained through linear sine approximations, with explicit handling of degeneracies and wrap-around cases.

  • Interval computation: The resulting interval is assembled from the bounds obtained for αi and βi, with the mirrored Case 2 handled by reversing the directions.The construction follows geometric considerations for the relevant spherical regions.
  • Geometric construction: αi and βi define the largest rotations for which the spherical region still touches its respective bounding meridian.αi corresponds to φ(yi) − γi, while βi corresponds to φ(yi) + γi.
  • Geometric construction: The analysis restricts αi and βi to [0, π/2], while pole-containing regions and non-intersection cases represent degeneracies.When a spherical region contains a pole, it cannot be bounded by two meridians.
  • Interval computation: For typical ϵk ≪ π, the second sine function is nearly linear over βi ∈ [0, π/2], supporting the approximation-based solution.If ϵk > 21.7° or the approximations do not intersect, the method sets Θi = [−π, π] and wraps intervals extending beyond π.
  • Interval computation: Because exact solution of the equations is non-trivial, lower- and upper-bounding linear approximations replace the sine functions to produce a valid bounding interval Θi.The same technique is used for αi and βi; Fig. A3 illustrates solving for βi.

A.5 Proof of Theorem 3 in the main text

The proof establishes that the feasible domain of the original rigid-registration problem is contained in that of its relaxed formulation. It does so by showing that every transformation satisfying the original constraints also satisfies the relaxed constraints via the triangle inequality.

  • Proof strategy: The proof aims to show that the feasible domain of P^rig_k is a subset of the feasible domain of Q^rig_k.This establishes qk ≥ pk for the corresponding optimal values.
  • Proof strategy: It suffices to verify that every constraint of P^rig_k remains satisfied under Q^rig_k for every rigid transformation Tk.The transformation is written as Tk = (Rk, tk) with consensus set Ik.
  • Proof conclusion: Applying the triangle inequality shows that the constraints in Q^rig_k are also satisfied.Thus any transformation feasible for P^rig_k is feasible for Q^rig_k.

B ADDITIONAL EXPERIMENTAL RESULTS

Additional material reports per-object registration results, qualitative visualizations across four datasets, and RGB-D instance results. It also provides supplementary Matlab demo and implementation information.

  • Qualitative results: Qualitative results cover Stanford, Mian, mining, and remote sensing datasets, including inputs, correspondences remaining after GORE, and registrations from its approximate solution.The remote-sensing visualization uses N = 500 correspondences and distinguishes true inliers and outliers by green and red lines.
  • Quantitative results: Table 1 reports individual results for every object in 6 DoF Euclidean registration, while Table 2 reports results for each RGB-D instance.Results that do not terminate within the time limit are marked with ‘-’.
  • Implementation: The supplementary demo and implementation require Matlab with point cloud support, and users are instructed to read the readme first.The material is provided as a downloadable Matlab demo and implementation.
Loading 1711.10209v1…