CS Paper Radar

On Maximum Clique and Maximum Consensus Formulations in Point Cloud Registration

Abolfazl Babanazari, Kaveh Fathian

cs.RO cs.CV ·submitted 2026-10-19 20:47 UTC · v1
theory

Abstract

Maximum clique and maximum consensus are widely used formulations for robust point cloud registration in robotics. Maximum consensus seeks one transformation that aligns as many matches as possible, while maximum clique selects matches through pairwise distance tests. Maximum clique is often used as a substitute for or an approximation to maximum consensus, with empirical evidence suggesting a close relationship. However, how closely the two formulations agree is not fully understood. We study this relationship theoretically. We show that a maximum clique can have arbitrarily large alignment error and be arbitrarily larger than the maximum consensus set at any fixed positive tolerance, and derive geometric conditions that bound this error. When rotation is fixed, we derive sharp error bounds and tests that exactly characterize maximum consensus for the translation subproblem. Finally, we study group-$k$ consistency, which tests groups of $k$ matches, and determine the smallest group sizes that guarantee alignment error bounds independent of point cloud scale and geometry. These are $d+1$ for rotations and translations and $d+2$ when reflections are allowed, in dimensions $d\ge 2$. Interactive examples and proof verification using the Lean theorem prover are available at https://ariarobotics.github.io/mc-vs-mc-registration/.

Comment
8 pages, 7 figures. Interactive examples and Lean proof verification: https://ariarobotics.github.io/mc-vs-mc-registration/

Closest papers

Nearest neighbours by meaning across the whole index.

Unsigned Distance Maps on 2D Point Cloud Registration

cs.RO ·2026-09-22 ·Ricardo B. Sousa, Giorgio Grisetti, Héber Miguel Sobreira, Carlos André Silva, António Paulo Moreira
publishedbenchmarkcode/data similarity 0.63
Abstract · 8 pages, 0 figures, 4 tables. Accepted to the 9th Iberian Robotics Conference (ROBOT2026), November 18-20, 2026, Barcelona, Spain. Source co…

2D point cloud registration arises in laser odometry and Simultaneous Localization and Mapping (SLAM) for mobile robots. Iterative Closest Point (ICP) is one of the most widely used approaches. Still, its iterative procedure recomputes correspondences via nearest-neighbor search at every iteration, whereas correspondence-free alternatives focus on scan-to-map alignment. This paper proposes a 2D point cloud registration approach based on unsigned distance maps, precomputing the Euclidean distance to the nearest reference point, along with its spatial derivatives, over a discrete grid, replacing the per-iteration search with O(1) lookups. Moreover, point-to-point and point-to-plane error formulations are derived on the SE(2) manifold and solved via Gauss-Newton optimization. On a synthetic benchmark and the real-world IILABS 3D dataset, the precomputed point-to-point variant outperforms its analytical counterparts, achieving competitive laser-odometry drift compared to point-to-plane formulations, as the precomputed gradient regularizes correspondences in the presence of sensor noise.

0.39

Spectral Consistency-Guided Multiview Point Cloud Registration for Low-Overlap Scenes

cs.CV ·2026-09-11 ·Tianyu Li, Yanghong Lin, Shudong Zhou, Kui Yang, Jingru Zhang +2 more
code/data similarity 0.62
Abstract

Multiview point cloud registration is particularly challenging in low-overlap scenes, where reliable correspondences are limited and incorrect pairwise transformations can affect global pose estimation. In addition, registering all scan pairs is computationally expensive because many pairs provide weak geometric information. To address these problems, we propose GMPCR, a non-learning-based spectral consistency-guided framework for efficient and robust multiview point cloud registration. GMPCR builds a refined second-order compatibility structure from initial correspondences and uses its dominant spectral response to evaluate both correspondence reliability and scan-pair confidence. This allows unreliable correspondences to be filtered and informative scan pairs to be selected before relative transformation estimation, leading to a sparse pose graph and reduced pairwise registration cost. For each retained scan pair, maximal-clique-based hypothesis generation is used to estimate reliable relative transformations. The resulting pose graph is further refined by an adaptive history-aware synchronization scheme, in which the effect of residual history is adjusted according to changes in the global rotation residual. A recovery mechanism also allows down-weighted edges to regain confidence when their global consistency improves. Experiments on 3DMatch, 3DLoMatch, ScanNet, and ETH demonstrate the effectiveness of GMPCR. It achieves registration recalls of 97.2% and 89.6% on 3DMatch and 3DLoMatch, respectively, while maintaining competitive performance on ScanNet and ETH. The results show that GMPCR provides a favorable balance among registration accuracy, robustness to low overlap, and computational efficiency. The code is publicly available at https://github.com/swccj/gmpcr.

0.31

Distributed Geometric Optimization and Control of Rigid Differential-Drive Formations from Relative-Position Measurements

eess.SY cs.ROmath.OC ·2026-11-04 ·Thanacha Choopojcharoen, Erman Selim, Ramisha Anjum, Baris Fidan
similarity 0.58
Abstract · 11 pages, 6 figures

Distance based formation control fixes the shape of a robot team but leaves its position and orientation unconstrained. We regulate all three for differential drive robots that have only one absolute position anchor, absolute headings, body frame relative position measurements, and communication with their neighbors. We derive a two layer estimation control scheme directly from optimization. The first half of the result is a set of graph-proximal estimators that reconstruct the centroid, the anchor vector, and the centered coordinates. Exact proximal updates reach consensus in finitely many steps, and a finite number of primal dual iterations leaves a bounded reconstruction error. The controller combines proximal centroid and orientation steps with distance gradient shape regulation, and a finite rotation removes the orientation drift caused by the shape step. A discrete Lyapunov analysis gives local exponential convergence once the estimators have converged. We validate the method in ROS 2 Gazebo and in experiments with five physical robots.

0.36

PESTO: Formally Correct Registration of LiDAR Point Clouds with Limited Overlap

eess.SY cs.RO ·2026-09-16 ·Valen Yamamoto, Matteo Marchi, Paulo Tabuada
published similarity 0.58
Abstract · 8 pages. Accepted at the 65th IEEE Conference on Decision and Control (CDC), 2026. This version includes appendices with proofs omitted from…

In this paper we tackle the problem of aligning LiDAR point clouds also known as the point cloud registration problem. We propose a new algorithm, PESTO, that exploits tetrahedra as "universal features" for LiDAR data, i.e., features that are agnostic to the environment where the LiDAR sensors are deployed. We show empirically that PESTO is competitive with existing solutions for aligning LiDAR point clouds, especially in environments with occlusions. Moreover, we establish PESTO's formal correctness by proving worst-case bounds on the alignment error.

0.47

PARTE: Plane-Assisted Robust Transformation Estimation for Point Cloud Registration

cs.RO cs.CV ·2026-09-21 ·Abolfazl Babanazari, Carson Cramer, Tyler Summers, Carlos Nieto, Kaveh Fathian
code/data similarity 0.58
Abstract · 16 pages, 14 figures, 11 tables. Code: https://ariarobotics.github.io/parte/. Updated project website URL

Global point-cloud registration remains challenging when limited overlap, repetitive geometry, and sensor noise produce correspondence sets dominated by outliers. Planar regions are particularly difficult for conventional point descriptors and are therefore often suppressed or discarded before matching. We present PARTE (Plane-Assisted Robust Transformation Estimation), a global registration method that instead treats planar structure as complementary registration evidence. PARTE extracts planar patches and represents them using our novel Plane Context Histogram (PCH), a descriptor that encodes the geometry surrounding each patch, while a two-level matching procedure identifies reliable plane correspondences. Candidate point and plane correspondences are combined in a confidence-weighted compatibility graph for joint outlier rejection, followed by rigid transformation estimation. When no usable plane correspondences are available, PARTE naturally reduces to point-only registration. We evaluate PARTE on 8,097 registration pairs across six indoor and outdoor benchmarks spanning dense RGB-D and sparse LiDAR measurements. Evaluations show PARTE achieves the highest overall success rate against 13 standard and state-of-the-art methods while maintaining low runtime. An open-source C++ implementation with Python bindings is provided at https://ariarobotics.github.io/parte/.

0.50

Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry

cs.CV cs.CGcs.LGcs.RO+1 ·2026-10-07 ·Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome
theory similarity 0.56
Abstract · 67 pages, 20 figures. Includes full proofs and experimental appendices

Procrustes-Wasserstein alignment jointly estimates a matching and rotation without supplied correspondences, but alternating minimization can stop at suboptimal solutions. Rubix solves the equally weighted planar problem globally under squared Euclidean loss. Each matching $σ$ of two centered $n$-point sets defines a complex correlation $z_σ=\sum_i\bar x_i y_{σ(i)}$. Their convex hull is the permutation polygon: supporting vertices give optimal matchings at fixed rotations, and the farthest vertex gives the global alignment. We prove the sharp bound of $n(n-1)$ vertices for $n\ge2$, answering Rote's rotation-assignment open problem. In exact arithmetic, assignment queries recover the polygon in $\mathcal O(n^5)$ operations. Assignment-based bounds extend the approach to three-dimensional rotations and partial matching at a supplied translation through branch-and-bound. On timed MPEG-7 shape pairs, Rubix attains every numerical reference value in 12 ms on average, 50 times faster than a rotation grid at the same accuracy. Its distances improve gravity-aligned matching of real 3D scans, shape retrieval and noisy crystal classification over alternating minimization.

0.25

Context without Commitment: Robust Dense Correspondence under Non-Rigid Deformation

cs.CV ·2026-09-29 ·Yuzhen He, Sara Homscheid
code/data similarity 0.55
Abstract

Non-rigid point-cloud registration aims to find the corresponding target point for each point on a deforming source surface. Point-level matching keeps the full target cloud available, but correspondence becomes ambiguous when different regions have similar local geometry. Regional or coarse-to-fine methods provide broader spatial context, but an incorrect regional match can exclude the correct correspondence before dense matching. We propose CoCo-Reg, which uses regional patches to enrich dense point features without allowing patch predictions to restrict the final point-level search. CoCo-Reg constructs farthest-point-sampled patches, exchanges geometric information within and between source and target, supervises patch similarity using identity-corrected point overlap, and projects the resulting regional information back to dense point features. The final registration stage still scores the full target cloud before global point-level candidate selection. On 726 held-out ModelNet10 objects across nine deformation levels, two established learning-based baselines obtain mean correspondence errors of 0.1993 and 0.1921, whereas CoCo-Reg obtains 0.0547. Relative to its point-level baseline, this is a 72.6\% reduction. CoCo-Reg achieves lower correspondence error on 92.3\% of paired test objects and reduces the mean fraction of points with error above 0.1 from 47.3\% to 17.3\%. Chamfer distance and HD95 decrease in the same direction, and CoCo-Reg remains lower across all tested deformation levels. These results support using regional context for dense non-rigid correspondence without imposing a hard patch-level restriction on the final search. Because evaluation uses one checkpoint per method, the reported gains characterize the complete systems rather than the isolated causal contribution of an individual component. Code will be made publicly available.

0.19

Attracting Rotations Obstruct Almost-Global Consensus on Spheres over Strongly Connected Graphs

eess.SY math.OC ·2026-10-20 ·Galina Sidorenko, Johan Thunberg
similarity 0.55
Abstract · 21 pages including appendices, 2 figures

We study discrete-time consensus on the Euclidean unit sphere, where weighted combinations of neighboring states are normalized to unit length. For symmetric weights on connected undirected graphs and ambient dimension $d\ge3$, earlier results establish instability of non-consensus fixed points under suitable weight conditions. For directed graphs on the unit circle, earlier results show that fixed points other than consensus and antipodal configurations occur only for a measure-zero set of weights. We show that these conclusions do not extend directly to general strongly connected directed graphs in higher dimensions. First, we construct full-rank non-consensus fixed points whose tangent eigenvalues all equal one, showing that strict linear instability need not hold. In a separate construction, for every $d\ge3$, we present a sparse strongly connected graph admitting full-rank fixed points on an open set of its permitted weights. Our main result establishes robust counterexamples to almost-global consensus: attracting rotating motions exist for $d=2$ with every $n\ge3$ and for $d=3$ with every $n\ge6$. These motions are locally asymptotically stable modulo common rotations and have asymptotic phase. They persist on open sets of strictly positive weight matrices. For each such matrix, an open set of initial configurations approaches neither consensus nor any fixed configuration. Thus the absence of full-rank non-consensus fixed points does not ensure almost-global convergence to consensus.

0.26