Clique-like Point Cloud Registration: A Flexible Sampling Registration Method Based on Clique-like for Low-Overlapping Point Cloud

Xinrui Huang, Xiaorong Gao, Jinlong Li, Lin Luo2024 · DOI

TL;DR

This paper introduces CL-PCR, a novel point cloud registration method that uses a "clique-like" sampling strategy to improve accuracy in scenarios with low overlap between point clouds. By flexibly forming subsets of correspondences that are mutually consistent, CL-PCR generates more reliable pose hypotheses, outperforming existing methods on challenging datasets.

What Problem Does This Paper Address?

Accurately aligning 3D point clouds from different sensors or scans is crucial for applications like 3D reconstruction and localization. However, a significant challenge arises when these point clouds have limited overlap, which is common in real-world scenarios like sparse lidar scans or when occlusions occur. Traditional registration methods, such as RANSAC and its variants, struggle with low overlap and high outlier ratios, leading to inaccurate results. Existing deep learning methods often require large datasets and may not generalize well. This paper aims to address the limitations of current methods in handling low-overlap point clouds and a high number of outliers.

Methods

The proposed CL-PCR method builds upon the SC2-PCR framework and introduces a novel "clique-like" sampling strategy. The core idea is to move away from fixed-size sampling and instead form flexible subsets of correspondences that exhibit high mutual consistency, inspired by the concept of maximal cliques.

Here's a breakdown of the key steps:

  • Graph Matrix Construction: The method first constructs a compatibility graph matrix from initial correspondences. It uses both a first-order matrix (FM) based on Euclidean distance constraints and a more robust second-order matrix (SM) that captures globally compatible relations.
  • Clique-like Construction: Instead of forming traditional cliques, CL-PCR constructs "clique-likes." This involves identifying an initial node and then populating it with other correspondences that are highly consistent, forming subsets of varying sizes. This flexible approach allows for the extraction of more local consensus information.
  • Sampling Enhancement: To further mitigate outlier penetration, two clique-like sampling enhancement strategies are proposed:
  • Default Demotion: Randomly demotes nodes from larger clique-likes to smaller ones, aiming to ensure that each structure contains probable inliers, even at the cost of sacrificing some inliers.
  • Safe Demotion: A more refined approach that demotes nodes while retaining them in their original classification, preventing the accidental removal of valid inliers.
  • Hypothesis Generation and Evaluation: Pose hypotheses are generated from these clique-like subsets using Singular Value Decomposition (SVD). The method compares instance-equal SVD with weighted SVD, finding that instance-equal SVD performs better for smaller clique-likes. Hypotheses are then evaluated using a combination of metrics, including Inlier Count (IC), Mean Average Error (MAE), and the proposed Feature and Spatial Consistency constrained Truncated Chamfer Distance (FS-TCD).

Datasets

The paper evaluates CL-PCR on three standard datasets:

  • 3DMatch: An indoor dataset with 1672 point cloud pairs.
  • 3DLoMatch: A more challenging indoor dataset with 1781 pairs, characterized by low overlap (10-30%).
  • KITTI: An outdoor dataset with 555 point cloud pairs.

The authors also conducted experiments on real-world data collected from a 3D laser scanner, which was further processed by adding cropping and noise to simulate challenging conditions.

Key Insights and Ideas

  • Flexibility in Sampling is Key: The core insight is that rigid sampling strategies (like fixed-size subsets) are detrimental in low-overlap scenarios. CL-PCR's "clique-like" approach, which allows for flexible subset sizes, is crucial for adapting to varying levels of overlap and finding reliable inlier groups.
  • Second-Order Compatibility Matters: Using the SM matrix for constructing clique-likes significantly improves registration recall compared to the FM matrix, highlighting the importance of considering global compatibility for robust inlier/outlier discrimination.
  • Instance-Equal SVD for Small Subsets: Counterintuitively, for the small clique-like subsets that are often crucial in low-overlap scenarios, instance-equal SVD (unweighted) outperforms weighted SVD. This suggests that for these small, highly consistent groups, global weighting might introduce unnecessary noise.
  • FS-TCD as a Powerful Evaluation Metric: Combining MAE with the FS-TCD metric for hypothesis selection leads to significant improvements in registration recall, especially for scenarios where simple inlier counts might be unreliable.
  • Robustness to Noise and Varying Overlap: The method demonstrates remarkable resilience to noise and maintains high performance across a wide range of overlap rates on real-world data, underscoring its practical applicability.

Key Results

  • Superior Registration Recall: CL-PCR consistently achieves state-of-the-art or near state-of-the-art registration recall (RR) on the 3DMatch and 3DLoMatch datasets, outperforming methods like MAC and SC2-PCR++. For instance, on 3DMatch with FPFH, CL-PCR achieves an RR of 88.48%, a notable improvement.
  • High Performance on Low-Overlap Data: On the challenging 3DLoMatch dataset, CL-PCR achieves an RR of 44.64% (FPFH) and 59.91% (FCGF), significantly outperforming many existing methods.
  • Excellent KITTI Results: On the KITTI dataset, CL-PCR achieves very high RRs (up to 99.64%) with low rotation and translation errors, demonstrating its versatility across indoor and outdoor environments.
  • Efficiency Gains: The optimized versions of CL-PCR (e.g., Fast-CL-PCRv1) significantly reduce computation time while maintaining high accuracy, making it more practical for real-time applications.
  • Robustness on Real Data: Experiments on real-world datasets show that CL-PCR is robust to varying overlap rates and even significant levels of added noise, with errors remaining consistently low.

Limitations and Future Work

  • Outlier Penetration: While CL-PCR is more robust than previous methods, the paper acknowledges that outlier correspondence penetration can still be an issue, particularly in extremely challenging scenarios. The proposed enhancement strategies aim to mitigate this, but it remains an area for further research.
  • Idealized Evaluation: The paper notes that while their method shows excellent performance, it hasn't yet achieved the absolute theoretical upper bound of registration recall. Future work could focus on further refining evaluation metrics or exploring new approaches to push these boundaries.
  • Computational Cost: Although optimized versions are faster, point cloud registration can still be computationally intensive. Further research into more efficient algorithms or hardware acceleration could be beneficial.
  • Descriptor Dependency: The performance of CL-PCR, like most correspondence-based methods, is dependent on the quality of the initial feature descriptors (FPFH, FCGF). Exploring how CL-PCR interacts with newer, more powerful deep learning-based descriptors could be a promising direction.

Summary updated

BibTeX
@misc{huang2024clique,
  author = {Xinrui Huang and Xiaorong Gao and Jinlong Li and Lin Luo},
  title = {{Clique-like Point Cloud Registration: A Flexible Sampling Registration Method Based on Clique-like for Low-Overlapping Point Cloud}},
  year = {2024},
  doi = {10.3390/s24175499},
}
Figure