Source-linked AI summary
3D Registration with Maximal Cliques
Xiyu Zhang, Jiaqi Yang, Shikun Zhang, Yanning Zhang
TL;DR
3D point cloud registration must estimate an aligning pose despite correspondence outliers, limited overlap, noise, and difficult cross-dataset generalization. MAC loosens maximum-clique constraints to mine local consensus, generate SVD pose hypotheses, and select the best registration. Combined with GeoTransformer, it reaches 95.7% / 78.9% recall on 3DMatch / 3DLoMatch.
Problem
PCR seeks a 6-DoF pose from feature correspondences, but outliers, limited overlap, noise, and weak cross-dataset generalization make accurate registration challenging.
Method
MAC constructs a compatibility graph, searches and node-selects maximal cliques as consensus sets, computes SVD transformation hypotheses, and evaluates the best hypothesis.
Results
MAC achieves state-of-the-art performance across U3M, 3DMatch, 3DLoMatch, and KITTI, while GeoTransformer with MAC reaches 95.7% / 78.9% registration recall on 3DMatch / 3DLoMatch.
Takeaways & Limitations
MAC can outperform several deep-learned methods without training data and can boost multiple deep-learned registration frameworks.
Takeaways & Limitations
MAC produces accurate hypotheses but may fail to find them, motivating future hypothesis evaluation using semantic information.
Abstract
from arXiv · showhide
As a fundamental problem in computer vision, 3D point cloud registration (PCR) aims to seek the optimal pose to align a point cloud pair. In this paper, we present a 3D registration method with maximal cliques (MAC). The key insight is to loosen the previous maximum clique constraint, and mine more local consensus information in a graph for accurate pose hypotheses generation: 1) A compatibility graph is constructed to render the affinity relationship between initial correspondences. 2) We search for maximal cliques in the graph, each of which represents a consensus set. We perform node-guided clique selection then, where each node corresponds to the maximal clique with the greatest graph weight. 3) Transformation hypotheses are computed for the selected cliques by the SVD algorithm and the best hypothesis is used to perform registration. Extensive experiments on U3M, 3DMatch, 3DLoMatch and KITTI demonstrate that MAC effectively increases registration accuracy, outperforms various state-of-the-art methods and boosts the performance of deep-learned methods. MAC combined with deep-learned methods achieves state-of-the-art registration recall of 95.7% / 78.9% on 3DMatch / 3DLoMatch.
1. Introduction
3D point cloud registration estimates a 6-DoF pose from correspondences, but outliers, limited overlap, noise, and cross-dataset generalization challenge accurate alignment. MAC loosens the maximum-clique constraint to exploit local consensus and generate accurate hypotheses.
- PCR estimates a six-degree-of-freedom pose transformation that aligns two 3D scans of the same object or scene.
- Feature-matching correspondences often contain outliers because of detector and descriptor limitations, limited overlap, and data noise.
- RANSAC-based methods become vulnerable as outlier rates increase, while branch-and-bound methods have high computational complexity for large, highly contaminated correspondence sets.
- Deep-learned methods require substantial training data and may generalize poorly across datasets, leaving accurate registration under heavy outliers and cross-dataset conditions challenging.
- MAC models correspondences as a compatibility graph, searches maximal cliques, selects node-guided cliques, computes SVD hypotheses, and evaluates the best hypothesis for registration.
- 95.7% / 78.9% registration recall is achieved by MAC combined with GeoTransformer on 3DMatch / 3DLoMatch.
2. Related Work
Prior PCR methods include sampling- or search-based geometric approaches and data-intensive deep-learning approaches. MAC is presented as a training-free module that can outperform several deep-learned methods and boost existing frameworks.
- RANSAC and its variants iteratively sample correspondences and remain dominant approaches for estimating 6-DoF poses from correspondence sets.
- RANSAC-based methods can be time-consuming and noise-sensitive, motivating more efficient and robust hypothesis evaluation metrics.
- Branch-and-bound methods seek globally optimal solutions but address registration through computationally intensive search of the 6D parameter space.
- Deep-learned PCR methods improve keypoints, descriptors, correspondence classification, or end-to-end registration using neural networks.
- MAC requires no training data, achieves stronger performance than several deep-learned methods, and can serve as a drop-on module in deep-learning frameworks.
3. MAC
MAC constructs compatibility graphs from feature correspondences, mines and selects maximal cliques as consistent sets, then estimates and evaluates pose hypotheses. Its graph and selection design retains local compatibility information while controlling hypothesis count.
- 3.1. Problem Formulation: MAC begins by extracting local features and forming an initial correspondence set between the two point clouds.
- 3.2. Graph Construction: The compatibility graph represents correspondences as nodes and connects geometrically compatible pairs, with FOG and SOG providing graph-construction alternatives.
- 3.2. Graph Construction: 43?
- 3.3. Search Maximal Cliques: Maximal cliques capture local consensus sets, whereas the maximum clique imposes a tighter constraint focused on global consensus.
- 3.3. Search Maximal Cliques: Node-guided selection retains the greatest-weight maximal clique for each node, removes duplicates, and produces no more selected cliques than graph nodes.
- 3.4. Hypothesis Generation and Evaluation: Each selected clique yields a 6-DoF pose hypothesis through SVD, after which MAE, MSE, or inlier count evaluates hypotheses and the best one performs registration.
4. Experiments
Experiments across object-scale, indoor, and outdoor datasets show that MAC achieves strong registration performance, improves deep-learned methods, and benefits from maximal-clique and node-guided design choices.
- Experimental setup: 496 U3M point-cloud pairs were evaluated with RMSE thresholds from 0.5 pr to 5 pr, using a 0.5 pr step.The comparison included RANSAC-based, geometric-only, and other registration methods.
- U3M results: MAC performs best on U3M and significantly outperforms tested RANSAC-fashion estimators, including SAC-COT, OSAC, SAC-IA, and RANSAC.MAC also achieves the best U3M registration performance under MAE evaluation.
- Indoor results: MAC outperforms compared methods on both 3DMatch and 3DLoMatch regardless of descriptor, including deep-learned methods without data training.It also achieves the best RE and TE metrics on these indoor datasets.
- Deep-learning integration: 95.7% / 78.9% registration recall is achieved by MAC with GeoTransformer on 3DMatch / 3DLoMatch.MAC dramatically improves registration recall under all tested deep-learned methods, and SpinNet, Predator, and CoFiNet after boosting exceed GeoTransformer.
- Outdoor results: MAC presents the best registration recall on KITTI and has lower TE than the state-of-the-art geometric-only method SC2-PCR.The experiments across object, indoor, and outdoor datasets consistently verify good generalization ability.
- Ablation analysis: 9.8% and 5.55% higher recall is obtained by maximal rather than maximum cliques with FPFH and FCGF on 3DMatch.On 3DLoMatch, the corresponding improvements are 8.03% and 10.45%; maximal cliques combine local and global graph information.
- Hypothesis quality: 98.46% / 91.24% registration recall is achieved by MAC-1 on 3DMatch / 3DLoMatch under the performance-upper-bound analysis.The result indicates correct hypotheses can be produced for most pairs, including low-overlap pairs, while evaluation remains a limiting factor.
- Efficiency: MAC completes registration in tens of milliseconds below 1000 correspondences and takes about 0.29 seconds with 2500 correspondences on CPU.At 5000 correspondences, MAC’s registration time rises substantially.
5. Conclusion
MAC uses maximal cliques to generate precise pose hypotheses for point cloud registration, achieves state-of-the-art performance, and can boost deep-learned methods. Its limitation is that accurate hypotheses may still be missed.
- MAC generates precise pose hypotheses using the maximal clique constraint and achieves state-of-the-art performance on all tested datasets.
- MAC can adapt to deep-learned methods to boost their performance.
- MAC may fail to find accurate hypotheses despite producing accurate hypotheses when it does find them.
A. Comparison of FOG and SOG
SOG derives a sparser, more robust graph from FOG by incorporating common compatibility among matched pairs, helping clique search under high outlier rates.
- SOG considers commonly compatible matches globally rather than only geometric consistency, making it more robust under high outlier rates.
- SOG is sparser than FOG, which benefits faster clique search.
- FOG edge weights are transformed into corresponding second-order weights to construct SOG.
- Edges lacking remaining nodes connected to both endpoints receive zero SOG weight and are removed, naturally dividing the graph into subgraphs containing several cliques.
B. Additional Experiments
Additional experiments evaluate MAC on ETH and analyze its efficiency, memory use, and robustness when descriptor-generated correspondences contain few inliers.
- Results on ETH: ETH evaluation uses FPFH, FCGF, and Spinnet correspondences with 5000 sampled points or correspondences, counting success when RE ≤15° and TE ≤30 cm.
- Results on ETH: MAC remains effective with very low descriptor-generated inlier rates, raising registration recall by 24.2% with FPFH and 18.51% with FCGF over RANSAC.
- Experimental analysis: The additional experiments report dataset information, ETH inlier ratios, registration-recall boosting, and average time and memory comparisons in Tables 9–13.
- Results on ETH: MAC combined with Spinnet achieves 94.67% registration recall on ETH.
C. Visualizations
The paper provides process visualizations for MAC and qualitative registration comparisons on 3DLoMatch and KITTI, including registration-error examples.
- Additional registration results are shown in Figures 5–8.
- Figure 5 visualizes the MAC registration process on 3DMatch.
- On 3DLoMatch, red and green indicate failed and successful registration, respectively, in the qualitative comparison.
- Reported visualization examples include registration errors of RE=1.40° and TE=9.98 cm, RE=0.43° and TE=6.24 cm, and RE=3.93° and TE=181.39 cm.
- Figure 7 presents a qualitative comparison on KITTI.
RANSAC MAC
Figure 8 presents a qualitative comparison on ETH.
- The figure compares registration results qualitatively on the ETH dataset.