💻 computer science

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

This paper proposes GMOR, a lightweight and robust point cloud registration framework that achieves superior accuracy and efficiency by decomposing rigid transformation via Chasles' theorem and solving the resulting rotation and translation subproblems through a deterministic branch-and-bound search combined with range maximum query techniques, thereby overcoming the high complexity of graph-based methods and the local optima issues of multi-stage approaches.

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

Published 2026-02-02

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have two massive, messy piles of Lego bricks. Each pile represents a 3D scan of a room or a street, but they are scattered, rotated, and mixed with thousands of fake bricks (outliers) that don't belong. Your goal is to figure out exactly how to rotate and slide one pile so it perfectly matches the other. This is called Point Cloud Registration.

The paper introduces a new method called GMOR (Geometric Maximum Overlapping) to solve this puzzle faster and more accurately than current top-tier methods. Here is how it works, broken down into simple concepts:

The Problem: The "Needle in a Haystack"

Current methods try to find the right match by building a giant map of how every single brick relates to every other brick.

The Graph Problem: Imagine trying to draw a line connecting every Lego brick to every other brick to see which ones fit. If you have 10,000 bricks, that's 100 million lines to draw. This takes up too much computer memory and time, like trying to fill a swimming pool with a teaspoon.
The "Local Trap" Problem: Other methods try to solve the puzzle in steps (first find the angle, then the slide). But if they get stuck in a "local trap"—thinking a slightly wrong angle is the best one—they can't recover, and the final picture ends up blurry.

The Solution: GMOR's Two-Step Dance

GMOR avoids the giant map and the local traps by using a clever two-step strategy based on a mathematical rule called Chasles' Theorem. Think of this theorem as realizing that any complex movement of a rigid object (like a spinning top) can be broken down into just two simple moves:

Spinning around a specific stick (the rotation axis).
Sliding along that same stick.

GMOR solves the puzzle in two stages:

Stage 1: Finding the "Magic Stick" (Rotation Axis)

Instead of guessing the direction of the spin blindly, GMOR looks for the best "stick" (axis) to spin around.

The Analogy: Imagine the world is a globe. GMOR projects this globe onto the faces of a cube (like unfolding a die). It then searches these cube faces to find the best direction.
The Trick: Once it picks a direction, it doesn't check every single brick. Instead, it projects all the bricks onto that imaginary stick. It then uses a technique called Interval Stabbing.
- Visual: Imagine the bricks are shadows cast on a wall. GMOR slides a ruler up and down the wall to find the spot where the most shadows overlap. That spot tells it exactly how far to slide the pile. It does this quickly by sorting the shadows, rather than checking them one by one.

Stage 2: Finding the "Spin Angle" (Rotation Angle)

Now that GMOR knows the direction of the stick and how far to slide, it just needs to figure out how much to spin.

The Analogy: Imagine you are looking at the shadows of the bricks from the side of the stick. The problem becomes a 2D puzzle: "How do I rotate these flat shapes so they overlap the most?"
The Trick: GMOR turns this into a "Rectangle Overlap" problem. It draws a box around where each brick could be if it were a match. It then uses a Sweep Line Algorithm (imagine a laser scanner moving across a screen) to find the spot where the most boxes overlap.
- This is solved using a Segment Tree, which is like a highly organized filing cabinet that lets the computer instantly find the "busiest" spot without checking every single file.

Why is GMOR Special?

It's Lightweight: Unlike the "Graph" methods that try to connect every brick to every other brick (which crashes computers with too many bricks), GMOR's memory usage grows slowly and predictably, like adding one more shelf to a bookcase rather than building a new library.
It Avoids Traps: By keeping the search focused on the "stick" first and then the "spin," it avoids getting stuck in local traps that confuse other methods.
It's Fast: It uses smart math tricks (like the sweep line) to solve the overlap problem in polynomial time. This means even if you double the number of bricks, the time it takes doesn't explode; it just goes up a little bit.

The Results

The authors tested GMOR on:

Indoor Scans: Rooms with furniture (3DMatch/3DLoMatch).
Outdoor Scans: Streets and cars (KITTI LiDAR).
Synthetic Data: Computer-generated noise and chaos.

In these tests, GMOR was consistently more accurate (finding the right match more often) and faster than the current best methods. It handled high levels of "noise" (fake bricks) better than its competitors and didn't run out of memory, even with huge datasets.

In short: GMOR is a smart, efficient way to align 3D scans. Instead of trying to map every connection between millions of points, it breaks the problem down into finding a spin axis and a slide distance, using clever geometry to find the perfect overlap quickly and without crashing the computer.

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

Problem Statement
Point cloud registration aims to estimate the rigid transformation (6 degrees of freedom) between two point clouds by maximizing the number of inliers within a noise threshold. While current state-of-the-art (SOTA) methods utilizing spatial compatibility (SC) graphs or branch-and-bound (BnB) search perform well under high outlier ratios, they face significant limitations. Graph-based methods typically require quadratic space and time complexity for graph construction, limiting scalability. Conversely, multi-stage BnB search methods often suffer from inaccuracy due to local optima propagating between decomposed stages. Furthermore, existing approaches often rely on uniform inlier counting, which fails to leverage correspondence weights when confidence is non-uniform.

Methodology
The paper proposes GMOR (Geometric Maximum Overlapping Registration), a lightweight framework that decomposes the 6-DoF rigid registration problem into a two-stage rotation-only BnB search. The core of the method relies on Chasles' theorem, which decomposes rigid motion into a translation along a rotation axis and a 2D rigid transformation about that axis.

Stage I: Rotation Axis Search
- Parameterization: The rotation axis is searched on a unit hemisphere using a cube-mapping parameterization. This allows for efficient 2D BnB search.
- Optimization Objective: Instead of uniform inlier counting, the method maximizes a weighted correspondence overlap objective.
- Algorithm: For a candidate rotation axis, the translation along that axis is estimated via interval stabbing of projected correspondences. This is formulated as a 1D Range Maximum Query (RMQ) problem. The algorithm employs a "gradually converged" strategy to prefilter outliers and tighten search bounds at each branch node.
- Selection: The top- $k$ candidate rotation axes with the highest weights are selected to proceed to the next stage, mitigating the risk of local optima.
Stage II: Rotation Angle Search
- Decomposition: For each selected axis, the problem is reduced to 2D rigid registration on the plane perpendicular to the axis. This is further reduced to a 1D rotation angle search.
- Geometric Formulation: The rotation center for a given angle is determined geometrically. The noise constraints on the rotation center are approximated as axis-aligned bounding boxes.
- Algorithm: The problem of finding the optimal rotation center is reformulated as a 2D RMQ over pairwise intersecting rectangles, equivalent to Klee's rectangle problem. This is solved deterministically in $O(N \log N)$ time per iteration using a sweep line algorithm accelerated by a segment tree with lazy propagation.
Post-Processing
- The final rigid transformation is refined using Iteratively Reweighted Least Squares (IRLS) with Tukey's biweight kernel to further suppress outliers and optimize the transformation parameters.

Key Contributions

Novel Framework: A two-stage rotation-only BnB framework that optimizes a weighted correspondence overlap objective rather than simple inlier counting.
Efficient Search Strategy: Introduction of cube-mapping hemispherical parameterization for global rotation axis search, coupled with adaptive interval stabbing for translation estimation.
Deterministic Solution: A polynomial-time solution for the residual 2D rigid registration by reformulating it as a 2D RMQ (Klee's rectangle problem), solvable via sweep line and segment tree algorithms.
Complexity Guarantees: The framework achieves polynomial time complexity and linear space complexity (with respect to the number of points) even in the worst case, addressing the scalability issues of graph-based methods.

Experimental Results
The authors evaluated GMOR on indoor (3DMatch, 3DLoMatch) and outdoor (KITTI) datasets, as well as synthetic data with varying correspondence counts and outlier ratios.

Accuracy: GMOR demonstrated superior or competitive accuracy (Rotation Error and Translation Error) compared to SOTA methods like TEASER++, SC2-PCR++, MAC, and TR-DE. Notably, it achieved the highest registration recall (RR) on the 3DMatch dataset (89.46% with FPFH, 93.22% with FCGF) and KITTI dataset (100% RR).
Efficiency: The method exhibited significantly lower computation times than graph-based methods (e.g., SC2-PCR++ and MAC), often running 10x to 60x faster while maintaining higher accuracy.
Scalability: On synthetic data, GMOR maintained linear space complexity and stable memory usage (under 100 MB for 100,000 correspondences), whereas graph-based methods suffered from out-of-memory errors or exponential time growth.
Robustness: The method remained robust across extreme outlier ratios (up to 99%) and varying numbers of correspondences.

Significance and Claims
The paper claims that GMOR provides a unified interpretation of point cloud registration by casting interval stabbing and geometric overlap maximization as RMQ problems. By combining rotation-only BnB search with computational geometry solvers, the method achieves effective dimension reduction without sacrificing global optimality guarantees or incurring the high memory costs of graph-based approaches. The authors position GMOR as a solution suitable for lightweight robotics and computer vision applications where both high accuracy and low computational overhead are critical. The framework also naturally accommodates constrained settings, such as 4-DoF registration with gravity priors, as special cases.