  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
https://github.com/HKUST-Aerial-Robotics/Pagor for this project.
