Robust Point Cloud Registration via Geometric Overlapping Guided Rotation Search PubID: pubid: 0000–0000/00$00.00 © 2021 IEEE
Zhao Zheng, Jingfan Fan, Long Shao, Hong Song, Danni Ai, Tianyu Fu, Deqiang Xiao, Yongtian Wang, Jian Yang · 2025
Read Robust Point Cloud Registration via Geometric Overlapping Guided Rotation Search PubID: pubid: 0000–0000/00$00.00 © 2021 IEEE by Zhao Zheng, Jingfan Fan, Long Shao, Hong Song, Danni Ai, Tianyu Fu, Deqiang Xiao, Yongtian Wang, Jian Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-17427.txt.
Introduction
Zhao Zheng and co-authors present a fast, sturdy way to line up two three-dimensional point clouds. Their 2025 paper lines up the scans by finding the turn that makes the most point pairs overlap. Older graph methods need large memory, and older staged searches can settle on the wrong answer. The new method splits the full motion into a turn plus simple shifts, then searches step by step with exact bounds.
Tests use indoor room scans and outdoor road scans from a laser sensor on a car. The method beats leading rivals on both sets in accuracy and speed. Its memory use stays low, since it skips the large graphs that rivals build. Readers who work with robot sight or self-driving cars get a tool that stays reliable even when most point pairs are wrong.
Catalog record
| CREATOR | Zhao Zheng, Jingfan Fan, Long Shao, Hong Song, Danni Ai, Tianyu Fu, Deqiang Xiao, Yongtian Wang, Jian Yang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-17427
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Robust Point Cloud Registration via Geometric Overlapping Guided Rotation Search PubID: pubid: 0000–0000/00$00.00 © 2021 IEEE Zhao Zheng, Jingfan Fan, Long Shao, Hong Song, Danni Ai, Tianyu Fu, Deqiang Xiao, Yongtian Wang, Jian Yang Abstract 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 3DMatch, 3DLoMatch, and KITTI 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 Point cloud registration estimates the rigid transformation with 6 degrees of freedom (DoF) between two point clouds, which is a fundamental problem in simultaneous localization and mapping (SLAM) [ 1 , 2 , 3 ] , computer assisted surgery [ 4 , 5 , 6 ] and augmented reality [ 7 , 8 , 9 ] . Although iterative closest point (ICP) [ 10 ] and its variants [ 11 , 12 , 13 ] are widely used for fine registration with given initial alignment, they require robust initialization by employing a global registration method. Global registration methods estimate the rigid transformation between point clouds by establishing correspondences without initial guesses. Conventional correspondence-based approaches rely on handcrafted geometric primitives, such as 4-points congruent sets [ 14 , 15 ] , convex hull [ 16 , 17 ] and dense local feature descriptors [ 18 , 19 ] . While generating plausible correspondences, these methods typically produce significant outlier proportions that necessitate robust filtering. Recently, variants of RANSAC [ 20 , 21 ] , graph-based match [ 22 , 23 , 24 ] , and branch-and-bound (BnB) search [ 25 , 26 , 27 , 28 ] have demonstrated effectiveness in robust global registration against outliers. The exceptional outlier rejection capability of spatial compatibility (SC) from graph-based methods has prompted their integration into other pipelines [ 21 , 29 ] . Nevertheless, these methods face a critical trade-off: no universal approach simultaneously achieves robustness across varying outlier ratios and correspondence counts while guaranteeing polynomial time and linear space complexity. To achieve globally optimal point cloud registration with guaranteed space and time complexity, we propose a Geometric Maximum Overlapping Registration (GMOR) framework using two-stage rotation-only BnB search. The method employs Chasles’ decomposition theorem [ 30 ] to decouple the rigid transformation, as shown in Fig. 1 . The rotation axis is searched by cube mapping parameterization in the first stage and the translation along the axis is estimated by 1D range maximum query (RMQ) of overlapped correspondences projected onto the axis. This 1D RMQ adapts the interval stabbing algorithm used in previous works [ 26 , 27 , 28 , 29 , 31 ] . The second stage searches rotation angles in 1D space, where we relax rotation centers determined by angles to axis-aligned bounding boxes. Maximum inlier estimation is formulated as a 2D RMQ problem over pairwise intersecting rectangles. We reformulate this geometric maximum overlapping search as the stabbing counting query of Klee’s rectangle problems [ 32 , 33 ] , solving it efficiently via sweep line algorithm inspired by Bentley-Ottmann algorithm [ 34 ] augmented with segment tree. By combining BnB over Special Orthogonal Group ( \mathrm{SO}(3) ) with these computational geometry-based techniques, our approach achieves polynomial time complexity through dimension reduction while maintaining linear space complexity. The contributions of our work are as follows: • A novel two-stage rotation-only BnB framework using Chasles’ decomposition guarantees global convergence in polynomial time with linear space complexity, eliminating graph construction overhead. • Cube-mapped hemispherical parameterization for rotation axis search is coupled with adaptive interval stabbing of translation along the axis, progressively tightening intervals through correspondence projections to accelerate RMQ resolution. • A deterministic polynomial-time solution for 2D rigid registration is derived by reformulating as 1D rotation angle search with Klee’s rectangle counting, which utilizes sweep line algorithm with segment tree in O(N\log N) time per iteration. II Related Work II-A Feature extraction and learning-based registration A common approach for global registration is extracting the corresponding features between two point clouds to estimate the transformation between them. Rusu et al. [ 18 ] propose a Fast Point Feature Histograms (FPFH) descriptor for global registration, which is a handcrafted feature capturing the local geometry of each point invariant to scene context. Learning-based feature descriptors have been widely used for specific scenes, and 3DMatch proposed by Zeng et al. [ 35 ] is a pioneering work which provides the first benchmark dataset for learned feature representations. Choy et al. [ 36 ] propose Fully Convolutional Geometric Features (FCGF), which is trained separately on indoor/outdoor datasets and achieves higher inlier ratio. Huang et al. [ 37 ] demonstrate that using pairwise point clouds as joint input extracts richer features, proposing Predator for low-overlap cases. Qin et al. [ 38 ] further employ Transformer networks to model global geometric relationships of pairwise point clouds. Based on the correspondence matching in feature space, the rigid transformation is estimated by either RANSAC [ 39 ] or chunk-based methods [ 38 ] . Recently, end-to-end learning approaches, e.g. DGR [ 40 ] and PointDSC [ 22 ] , are progressive for solving the rigid transformation of correspondences. While effective in specific scenarios [ 41 , 42 ] , they generalize poorly to practical applications. Crucially, traditional methods [ 21 , 43 , 24 , 44 , 29 ] without learning now surpass them in accuracy and efficiency through graph or solution space exploration. Given these limitations, this section focuses on heuristic global registration techniques. II-B Iterative Random Sampling RANSAC [ 39 ] is a widely used algorithm for robust estimation with outliers, has inspired numerous variants [ 45 , 20 , 21 ] . Rusu et al. [ 18 ] leverage pairwise point distances and Fast Point Feature Histograms (FPFH) descriptor similarities to formulate SAmple Consensus Initial Alignment (SAC-IA), which suppresses outlier influence through finite iterations. Barath and Matas [ 45 ] improve sampling efficiency with Graph-Cut RANSAC (GC-RANSAC), removing outliers by graph cutting with local optimization. Unlike local sampling approaches, Li et al. [ 20 ] develop a one-point RANSAC variant using global pairwise