PaperlayerView exact revision on arXiv

Source-linked AI summary

GMOR: A Lightweight Robust Point Cloud Registration Framework via Geometric Maximum Overlapping

Zhao Zheng, Jingfan Fan, Long Shao, Hong Song, Danni Ai, Tianyu Fu, Deqiang Xiao, Yongtian Wang, Jian Yang

arXiv:2508.17427v2cs.CVcs.RO

TL;DR

Point-cloud registration methods face scalability, weighting, and staged-search challenges. GMOR combines rotation-only BnB with geometric RMQ solvers; reported results show improved RR on 3DMatch and the highest RR on 3DLoMatch, with suboptimal time consumption on the latter.

  • Problem

    Existing staged methods may treat correspondences uniformly and propagate local optima, while interval stabbing alone collapses only one degree of freedom.

    Source: §I · p. 2

  • Method

    GMOR decomposes general rigid registration into rotation-axis and rotation-angle BnB stages, using RMQ formulations to reduce search dimensions.

    Source: §I · p. 2

  • Results

    Over 2% in RR over all baselines on 3DMatch with FPFH; GMOR achieves the highest RR and suboptimal time consumption on 3DLoMatch.

    Source: 1) 3DMatch Dataset · p. 11, 2) 3DLoMatch Dataset · p. 12

  • Takeaways & Limitations

    The framework is reported to provide efficient, robust registration with polynomially bounded time and linear space complexity in the number of correspondences.

    Source: §IX · p. 16

Abstract

from arXiv · show

Point cloud registration based on correspondences computes the rigid transformation that maximizes the number of inliers constrained within the noise threshold. Current state-of-the-art (SOTA) methods employing spatial compatibility graphs or branch-and-bound (BnB) search mainly focus on registration under high outlier ratios. However, graph-based methods require at least quadratic space and time complexity for graph construction, while multi-stage BnB search methods often suffer from inaccuracy due to local optima between decomposed stages. This paper proposes a geometric maximum overlapping registration framework via rotation-only BnB search. The rigid transformation is decomposed using Chasles' theorem into a translation along rotation axis and a 2D rigid transformation. The optimal rotation axis and angle are searched via BnB, with residual parameters formulated as range maximum query (RMQ) problems. Firstly, the top-k candidate rotation axes are searched within a hemisphere parameterized by cube mapping, and the translation along each axis is estimated through interval stabbing of the correspondences projected onto that axis. Secondly, the 2D registration is relaxed to 1D rotation angle search with 2D RMQ of geometric overlapping for axis-aligned rectangles, which is solved deterministically in polynomial time using sweep line algorithm with segment tree. Experimental results on indoor 3DMatch/3DLoMatch scanning and outdoor KITTI LiDAR datasets demonstrate superior accuracy and efficiency over SOTA methods, while the time complexity is polynomial and the space complexity increases linearly with the number of points, even in the worst case.

I. INTRODUCTION

Global point-cloud registration estimates a six-degree-of-freedom transformation from correspondences, but existing approaches face scalability, weighting, and staged-search challenges. GMOR addresses these with a two-stage rotation-only BnB framework and geometric RMQ solvers.

I. INTRODUCTION

  • GMOR uses a two-stage rotation-only BnB framework for general 6-DoF registration, optimizing weighted correspondence overlap rather than uniform inlier counts.It combines rotation-axis search with 1D RMQ and rotation-angle search with 2D RMQ, reducing search dimensions while retaining polynomial time and linear space complexity.Source: §I · p. 2

A. Feature extraction and learning-based registration

  • Feature-based registration estimates transformations from correspondences, while traditional graph- or solution-space methods are reported to surpass learning approaches in accuracy and efficiency.The paper notes that learning approaches can generalize poorly to practical applications.Source: A. Feature extraction and… · p. 2

B. Iterative Random Sampling

  • RANSAC methods can perform strongly with moderate outlier ratios and sufficient correspondences, but their complexity becomes exponential at extremely high outlier ratios.Source: B. Iterative Random Sampling · p. 3

C. Spatial Compatibility Graph Matching

  • Graph methods can be accurate on sparse correspondence sets, but graph construction uses quadratic space and dense-graph clique search can be exponential.The paper also identifies possible inaccurate registration under improper rotations because SC is invariant under E(3), not SE(3).Source: C. Spatial Compatibility Graph Matching · p. 3

D. BnB Search in Solution Space

  • BnB offers global optimality in its searched space, but high-dimensional search is costly and staged decompositions can propagate local optima.Prior staged methods use interval stabbing to reduce search dimensions, but a local optimum in one stage can prevent later stages from finding the correct result.Source: D. BnB Search in Solution Space · p. 3

E. Practical LiDAR registration with Gravity Priors

The section situates gravity-constrained LiDAR registration as a reduced-DoF setting and formulates GMOR’s general registration objective. GMOR decomposes rigid motion and uses weighted feature-space correspondences before its two-stage search.

E. Practical LiDAR registration with Gravity Priors

  • Gravity priors constrain rotation to yaw, yielding a 2.5D problem with three translational and one rotational DoF; BEV projection can reduce registration further to 3 DoF.The latter simplifies registration to a 2D formulation by discarding the dimension along gravity.Source: E. Practical LiDAR registration with… · pp. 3–4

III. PROBLEM FORMULATION

  • GMOR maximizes the weighted sum of correspondences whose transformed points lie within noise threshold ξ, reducing to an inlier-count objective when all weights equal one.The noise threshold follows a 95% 3-DoF chi-square quantile under per-dimension Gaussian noise.Source: §III · p. 4
  • Chasles’ decomposition represents rigid motion as translation along rotation axis r plus rotation about that axis through a fixed point C.The two-stage search resolves the axis and axial translation, then rotation angle and center; weighted cross-matching supplies correspondences for filtering.Source: §III · p. 4, §IV · p. 4

IV. PREPROCESSING: WEIGHTED CROSS-MATCHING IN FEATURE SPACE

  • Feature-space preprocessing forms weighted correspondences using softmax-weighted k-nearest-neighbor search with a dustbin threshold and bidirectional matching.The correspondence weights downweight distant features, and matching is computed in both directions before combining results.Source: §IV · pp. 4–5

V. STAGE I: ROTATION AXIS SEARCH

Stage I searches for the rotation axis and axial translation by maximizing correspondence inlier weights. Cube mapping parameterizes the hemisphere, while projection bounds support the axis search.

V. STAGE I: ROTATION AXIS SEARCH

  • Stage I maximizes inlier weights over rotation axis r and translation distance d, using a 2D best-first BnB search over cube-mapped hemisphere coordinates.The search bisects the parameter space and is guided by an upper bound.Source: §V · p. 5

A. Projection onto Rotation Axis

  • For each surface element of candidate axes, projection boundaries bound each correspondence’s possible translation distance, with tighter bounds derived for whether it crosses the element.The bounds use parallel and perpendicular components of the difference vector and the maximum angle within the surface element.Source: A. Projection onto Rotation Axis · p. 6

B. Gradually Converged Interval Stabbing

Weighted interval stabbing estimates the translation distance by finding the location of maximum accumulated overlap. A gradually converged threshold narrows branch ranges and supports pruning.

B. Gradually Converged Interval Stabbing

  • The translation distance is estimated at the peak overlap of weighted intervals formed by correspondence projection boundaries.Sorting boundaries, adding each left-boundary weight and subtracting each right-boundary weight, then accumulating yields the global maximum.Source: B. Gradually Converged Interval Stabbing · p. 6, Figure 4 · p. 6
  • A branch-specific threshold between its upper bound and the global best lower bound defines an inherited translation range and prefilters correspondences.The range is bounded where accumulated weights exceed the threshold.Source: B. Gradually Converged Interval Stabbing · p. 6
  • Branches are pruned when their upper bound falls below the best lower bound, their search width is too small, or their weight-bound gap is below threshold..Source: B. Gradually Converged Interval Stabbing · p. 6

C. Post Top-k Plane Fitting

GMOR selects top-k candidate rotation axes and solves the residual planar registration by searching rotation angle while estimating its center. Geometric bounds make the center search equivalent to maximizing overlap.

C. Post Top-k Plane Fitting

  • Filtered inliers refine each candidate axis by fitting a plane; its minimal-variance direction is the refined rotation axis.The plane is estimated by eigenvalue decomposition of the inlier covariance matrix.Source: C. Post Top-k Plane Fitting · pp. 6–7

VI. STAGE II: ROTATION ANGLE SEARCH

  • For each candidate axis, projected correspondences form a 2D rigid-registration problem that GMOR reduces to a 1D rotation-angle search with a segment-tree-accelerated sweep line for the center.The residual problem has one rotational and two translational degrees of freedom.Source: §VI · p. 7

A. Rotation Center Determined by Angle

  • For a given angle, each correspondence constrains the rotation center to a noise-bounded region, making center estimation equivalent to maximizing geometric overlap.The center range is determined by the angle interval and correspondence geometry.Source: A. Rotation Center Determined by Angle · pp. 7–8

B. Maximum Overlapping via Sweep Line Algorithm

The method solves the center-search overlap problem as a weighted rectangle-overlap query. A sweep line and discretized segment endpoints support maximum-overlap updates.

B. Maximum Overlapping via Sweep Line Algorithm

  • At each angle interval, axis-aligned rectangles represent correspondence constraints, and their maximum weighted overlap is computed as a Klee’s rectangle problem.The method uses a sweep line with a segment tree.Source: B. Maximum Overlapping via Sweep Line… · p. 8

1) Segments discretization:

  • Each rectangle contributes vertical segments at its left and right edges, weighted by w and −w, respectively.The segment endpoints are sorted by y-coordinate and discretized by their sorted indices.Source: 1) Segments discretization · p. 8
  • The discretized segments are sorted by x-coordinate so the sweep line can traverse them from left to right.Source: 1) Segments discretization · p. 8

2) Segment tree with lazy propagation:

A segment tree maintains maximum weighted overlap during the sweep, enabling efficient rotation-center queries. The method also handles near-zero rotation and refines the final transformation with weighted SVD and IRLS.

2) Segment tree with lazy propagation:

  • Lazy propagation defers child-node updates, reducing each segment update to O(log N), while the root provides the current maximum overlap in O(1).The tree maintains the maximum weighted overlap as the sweep line advances.Source: 2) Segment tree with lazy propagation · p. 9

C. Degeneration Induced by Translation-only Problem

  • Near zero rotation, GMOR approximates rotation by identity and the arc by a straight line, then uses the translation-only overlap as an initial lower bound.The approximation uses bounding boxes based on the thresholds in the registration objective.Source: C. Degeneration Induced by… · p. 9

D. Post-Refinement with IRLS

  • After the two-stage search, weighted SVD on inliers refines the transformation using IRLS with Tukey’s biweight kernel.The robust-weight scale is c = 4.685 × MAD.Source: D. Post-Refinement with IRLS · p. 10

E. Subproblem of 4-DoF Registration

GMOR provides alternative decompositions for the known-axis 4-DoF subproblem and has polynomial-time search complexity. On 3DMatch with FPFH, it exceeds all baselines in recall while requiring less computation than MAC and SC2-PCR++.

E. Subproblem of 4-DoF Registration

  • For known-axis 4-DoF registration, 1+3 estimates axial translation first, while 3+1 solves the planar transformation first; the latter is expected to be more robust to high outlier ratios or noisy correspondences.The 1+3 strategy is sensitive to outlier distributions along the axis.Source: E. Subproblem of 4-DoF Registration · p. 10

VII. SPACE AND TIME COMPLEXITY

  • The total search time ranges from O(k log(1/ϵ) N log N) to O(1/ϵ^2 N log N), with worst-case space O(N + 1/ϵ^2).Source: §VII · p. 10

1) Datasets and Metrics:

  • Evaluation uses indoor 3DMatch and 3DLoMatch, outdoor KITTI, and synthetic data; registration recall counts pairs below both rotation- and translation-error thresholds.The reported average RE and TE are for successful pairs.Source: 1) Datasets and Metrics · pp. 10–11

A. Indoor 3DMatch and 3DLoMatch Evaluation

1) 3DMatch Dataset:

  • With FCGF on 3DMatch, GMOR has suboptimal RR but the lowest RE and TE, with significantly reduced computation time versus SC2-PCR++ on identical hardware.TEASER++ takes over two hours and runs out of memory in some cases when processing FCGF correspondences.Source: 1) 3DMatch Dataset · p. 11

2) 3DLoMatch Dataset:

GMOR performs strongly across indoor and outdoor registration tests, including low-overlap 3DLoMatch and KITTI LiDAR. Ablations and 4-DoF evaluation show how search settings and decomposition choices affect its results.

2) 3DLoMatch Dataset:

  • GMOR achieves the highest recall rate (RR) on 3DLoMatch with FPFH and the suboptimal time consumption, registering pairs in 0.65 s.With Predator descriptors, its RR is also suboptimal and time consumption is 0.51 s.Source: 2) 3DLoMatch Dataset · pp. 12–13, Table II · p. 12

3) Ablation Study on 3DMatch/3DLoMatch:

  • Increasing the number of candidate rotation axes improves RR with sublinear time growth, while the best convergence ratio varies by descriptor and dataset.For FCGF on 3DLoMatch, RR stays between 93.09% and 93.22% for ρ ∈ [0.05, 0.60]; larger ρ pre-filters more potential outliers.Source: 3) Ablation Study on 3DMatch/3DLoMatch · p. 13, Figure 10 · p. 13

B. Outdoor KITTI Evaluation

  • GMOR achieves the highest RR and fastest execution with both FPFH and FCGF descriptors on the KITTI test dataset.The evaluation uses 555 pairs from sequences 8 to 10, with the rotation axis constrained under the Atlanta World assumption.Source: B. Outdoor KITTI Evaluation · p. 13, Table III · p. 13

C. 4-DoF LiDAR Registration with Gravity Priors

  • Among the two 4-DoF decomposition strategies, 3+1 gives the highest recall and lowest transformation error, while 1+3 remains efficient but is slightly more sensitive to outliers.The comparison provides all methods with the ground-truth rotation axis.Source: C. 4-DoF LiDAR Registration with… · p. 14, Table IV · p. 14
  • For 4-DoF registration, jointly enforcing rotation and translation on the 2D plane yields accurate inlier identification and the correct transformation.The authors report that resolving the 2D rigid transformation first imposes stronger geometric constraints and reduces ambiguity for subsequent 1D translation estimation.Source: C. 4-DoF LiDAR Registration with… · p. 14, Figure 12 · p. 14

D. Performance Evaluation on Synthetic Data

Synthetic tests examine registration as correspondence counts and outlier ratios vary. GMOR maintains low memory use and robustness across these settings, with predictable time and memory growth as its intended outcome.

1) Number of correspondences:

  • At 100000 correspondences, GMOR keeps memory below 100 MB, while several comparison methods run out of memory beyond 50000 correspondences.Memory grows linearly for GMOR, TEAR, and TR-DE, but polynomially for TCF, TEASER++, MAC, and HERE.Source: 1) Number of correspondences · pp. 15–16

2) Outlier ratio:

  • Across outlier ratios from 0.1 to 0.9, GMOR maintains near-optimal time and memory efficiency while remaining robust.The experiment uses 10000 correspondences.Source: 2) Outlier ratio · p. 16
  • At extreme outlier ratios from 0.91 to 0.99, GMOR maintains constant memory and suboptimal performance, although its time advantage narrows in BnB worst-case scenarios.The authors note that TCF's time and memory advantage in this test is limited to synthetically added uniformly random outliers and Gaussian noise.Source: 2) Outlier ratio · p. 16

IX. CONCLUSION

  • The conclusion attributes GMOR's polynomial time and linear space complexity to decomposing registration into rotation-axis search with interval stabbing and rotation-angle search with a sweep-line 2D RMQ solver.The authors report efficient, robust registration with low computational overhead on real and synthetic data.Source: §IX · p. 16

APPENDIX A DERIVATION OF THE REFORMULATED TRANSFORMATION

The appendix derives a residual representation by separating translation and correspondence displacement into components parallel and perpendicular to the rotation axis. It also expresses rigid motion as a screw motion around that axis.

A. Decomposition of residual vector

B. Vector perpendicular to rotation axis

  • Rodrigues’ formula expresses rotation R using angle θ and axis r, with r× defined as the skew-symmetric matrix for cross product with r.The appendix uses the perpendicularity of r×v and (I − rr⊤)v to continue the residual derivation.Source: B. Vector perpendicular to rotation axis · pp. 16–17

C. Rotation center

The appendix fixes a representative point on the rotation axis and compares hemisphere parameterizations for rotation-axis search. Cube mapping has a recall advantage on the low-overlap 3DLoMatch benchmark.

C. Rotation center

  • Because C + αr represents the same rotation axis for any α, the derivation chooses the representative satisfying r⊤C = 0.This selects a point on the axis perpendicular to its direction.Source: C. Rotation center · p. 17

APPENDIX B COMPARISON OF SPHERE PROJECTIONS

  • Cube mapping achieves the highest recall on low-overlap 3DLoMatch, while hemisphere parameterizations have comparable recall on 3DMatch.The authors attribute the 3DLoMatch advantage to more uniform, bounded axis parameterization that avoids severe pole distortion and balances subbranch division under sparse correspondences.Source: Appendix B · pp. 17–18, Table VI · p. 17

Related papers

Loading 2508.17427v2…