Pyramid Semantic Graph-based Global Point Cloud Registration with Low Overlap

Zhijian Qiao, Zehuan Yu, Huan Yin, Shaojie Shen

TL;DR: Pagor is a novel framework for global point cloud registration that excels in low-overlap scenarios. By constructing a pyramid of semantic consistency graphs and using a cascaded optimization strategy, it robustly identifies data associations and achieves state-of-the-art success rates.

Abstract

Global point cloud registration is essential in many robotics tasks like loop closing and relocalization. Unfortunately, the registration often suffers from the low overlap between point clouds, a frequent occurrence in practical applications due to occlusion and viewpoint change. In this paper, we propose a graph-theoretic framework to address the problem of global point cloud registration with low overlap. To this end, we construct a consistency graph to facilitate robust data association and employ graduated non-convexity (GNC) for reliable pose estimation, following the state-of-the-art (SoTA) methods. Unlike previous approaches, we use semantic cues to scale down the dense point clouds, thus reducing the problem size. Moreover, we address the ambiguity arising from the consistency threshold by constructing a pyramid graph with multi-level consistency thresholds. Then we propose a cascaded gradient ascend method to solve the resulting densest clique problem and obtain multiple pose candidates for every consistency threshold. Finally, fast geometric verification is employed to select the optimal estimation from multiple pose candidates. Our experiments, conducted on a self-collected indoor dataset and the public KITTI dataset, demonstrate that our method achieves the highest success rate despite the low overlap of point clouds and low semantic quality. We have open-sourced our code at https://github.com/HKUST-Aerial-Robotics/Pagor.

1. Introduction

Global point cloud registration—aligning two 3D scans without a prior pose estimate—is a cornerstone of robotic mapping and localization. However, real-world conditions often involve low overlap between scans due to occlusions or large viewpoint changes.

Traditional graph-theoretic methods attempt to find a "maximum clique" of consistent matches, typically relying on a single, manually tuned consistency threshold. If the threshold is too tight, true matches are discarded; if it's too loose, the graph becomes cluttered with outliers, causing the algorithm to fail. This "threshold ambiguity" makes global registration fragile in challenging, low-overlap scenarios.

Illustration of threshold ambiguity: a lower threshold (0.04) leads to an incorrect clique, while a higher threshold (0.08) identifies the correct data association.

2. The Pagor Framework

To address these challenges, we introduce Pagor, a novel framework that integrates high-level semantic landmarks with low-level geometric cues using a "distrust and verify" strategy.

2.1 Pyramid Semantic Graph

Instead of selecting a single threshold, Pagor builds a pyramid of consistency graphs using multiple thresholds ($\epsilon_1, \dots, \epsilon_k$). This multi-level approach ensures that at least one level likely captures the correct set of inliers, effectively bypassing the sensitivity of single-threshold methods.

2.2 Cascaded Gradient Ascend

Solving for the densest clique across multiple graphs can be computationally expensive. We propose a cascaded approach where the solution from a sparser graph (with a tighter threshold) serves as the initial guess for the next, denser graph. This strategy significantly accelerates the optimization process.

2.3 Robust Pose Estimation and Verification

For each graph level, a pose candidate is generated using Graduated Non-Convexity (GNC), a robust solver capable of handling high outlier ratios. Finally, the system performs a geometric "sanity check" by projecting the original dense metric points using each pose candidate. The candidate that yields the best alignment of the dense points is selected as the final result.

The Pagor pipeline: from semantic landmarks to a pyramid of graphs, resulting in multiple pose candidates verified using dense metric points.

3. Experimental Evaluation

We evaluated Pagor on two distinct benchmarks: a self-collected indoor dataset and the public KITTI dataset.

  • Self-collected Indoor Dataset: Five sequences captured with a Velodyne VLP-16 in a university building, requiring registration against a sparse 2D floor plan.
  • KITTI Dataset (Hard): A subset of the public KITTI dataset filtered for "hard" loop-closing pairs with 10-15 meters of translation, resulting in very low overlap.

3.1 Key Results

Pagor consistently outperformed state-of-the-art (SoTA) methods:

  • Indoor Success Rate: Pagor achieved a success rate of 86.4% on the S1 sequence, significantly higher than the semantic version of TEASER++ (80.5%) and RANSAC (27.8%).
  • Outdoor (KITTI Hard): On the most challenging low-overlap pairs, Pagor reached a 90.38% success rate, whereas the previous SoTA, Segregator, achieved 79.70%.
  • Efficiency: The cascaded gradient ascend method was nearly 3x faster than solving each layer of the pyramid independently.

4. Conclusion

Pagor demonstrates that treating the consistency threshold as a multi-level search space makes global registration significantly more resilient to sensor noise and semantic mislabeling. By combining semantic pruning with geometric verification, the framework achieves robust performance in low-overlap scenarios where traditional methods fail. Future work will focus on integrating Pagor into real-time localization frameworks and large-scale map merging.

Summary updated

BibTeX
@inproceedings{qiao2023pyramid,
  author = {Zhijian Qiao and Zehuan Yu and Huan Yin and Shaojie Shen},
  title = {{Pyramid Semantic Graph-based Global Point Cloud Registration with Low Overlap}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2023},
  doi = {10.1109/iros55552.2023.10341394},
}
Figure