An Accelerated and Robust Partial Registration Algorithm for Point Clouds

Xin Wang, Xiaohuang Zhu, Shihui Ying, Chaomin ShenIEEE Access 2020 · OpenReview

Abstract

Partial registration for point clouds is essential for 3D mapping, remote sensing, and unmanned driving. However, it remains challenging due to low overlap ratios and noise. We propose a parallel coarse-to-fine partial registration method. First, a coarse trimmed method estimates the overlap area and initial transformation using fast bilateral denoising and parallel point feature histogram (PPFH) descriptor aligning. Second, an accelerated fine registration is performed via a parallel trimmed iterative closest point (PTrICP) method. Most components are GPU-accelerated for efficiency. We also extend the method to isotropic scaling registration. Experiments show our method is robust to low overlap, outliers, noise, and scaling.

Introduction

Point cloud registration aligns multiple 3D datasets into a unified coordinate system. While standard algorithms like Iterative Closest Point (ICP) are effective for nearly identical scans, they often struggle with "partial registration." This scenario is characterized by low overlap (often 20-30%), sensor noise, and the sheer computational volume of modern LiDAR data. This paper presents a workflow designed to be both robust against these challenges and highly accelerated via GPU parallelization.

Proposed Methodology

The proposed algorithm follows a parallel coarse-to-fine workflow to ensure both global robustness and local precision.

Workflow of the proposed parallel coarse-to-fine partial registration method.

Coarse Trimmed Stage

The initial stage focuses on finding a reliable starting transformation ($T^0$).

  1. Bilateral Denoising: A parallel bilateral filter smooths noise while preserving sharp geometric edges, ensuring that subsequent feature extraction is accurate.
  2. Key Point Selection: To reduce computational load, the algorithm selects "key points" based on local curvature.
  3. Parallel Point Feature Histogram (PPFH): Geometric "fingerprints" are computed for these key points. These descriptors capture the relative orientation and distance between points in a neighborhood.
Visualization of Point Feature Histogram (PFH) descriptors for different local geometries on the Stanford Bunny model.

Fine Registration Stage

Once a coarse alignment is established, the Parallel Trimmed ICP (PTrICP) method refines the result. The "trimmed" strategy is vital here; it identifies and ignores points without close matches, effectively filtering out non-overlapping regions and outliers that would otherwise pull the registration off-course.

GPU Acceleration

Efficiency is achieved by implementing the entire pipeline—including kd-tree construction, normal estimation, and descriptor matching—using CUDA and the Thrust library. This allows the algorithm to handle millions of points in a fraction of the time required by CPU-based methods.

Experimental Results

The algorithm was evaluated using standard datasets (Stanford Bunny, Dragon) and large-scale LiDAR data (Volcano St. Helens).

  • Accuracy: In scenarios with only ~25% overlap, the method achieved a Trimmed Squared Distance (TSD) error significantly lower than state-of-the-art competitors like Super4PCS (e.g., $10^{-11}$ vs $10^{-2}$).
  • Robustness: High accuracy was maintained even with 40% random outliers.
  • Speed: GPU parallelization ensured that processing time remained low even as point density increased. For instance, registering the 40k-point Bunny model takes only a few hundred milliseconds.

Conclusion

This research introduces a robust, GPU-accelerated framework for partial point cloud registration. By combining bilateral denoising, PPFH descriptors, and a trimmed ICP approach, the method overcomes the traditional hurdles of low overlap and noise. Future work will explore extending these techniques to non-rigid registration scenarios.

Summary updated

Abstract

Partial registration for point clouds plays an important role in various fields such as 3D mapping reconstruction, remote sensing, unmanned driving, and cultural heritage protection. Unfortunately, partial registration is challenging due to difficulties such as the low overlap ratio of two point clouds and the perturbation in the orderless and sparse 3D point clouds. Thus, a variety of the 3D shape context descriptors are introduced for finding the optimal matching. However, extracting geometric features and descriptors are time consuming and easily degenerated by noise. To overcome these problems, we introduce a parallel coarse-to-fine partial registration method. Our contributions can be summarized as: Firstly, a robust coarse trimmed method is proposed to estimate the coarse overlap area and the initial transformation via fast bilateral denoising and parallel point feature histogram (PPFH) descriptor aligning. Secondly, an accelerated fine registration procedure is conducted by a parallel trimmed iterative closest point (PTrICP) method. Moreover, most parts of our coarse-to-fine workflow are accelerated under the Graphics Processing Unit (GPU) parallel execution mode for efficiency. Thirdly, we extend our method from the rigid registration to the isotropic scaling registration, which improves its applicability. Experiments have demonstrated that our method is feasible and robust in various situations, including the low overlap ratio, outlier, noise and scaling.
BibTeX
@inproceedings{wang2020accelerated,
  author = {Xin Wang and Xiaohuang Zhu and Shihui Ying and Chaomin Shen},
  title = {{An Accelerated and Robust Partial Registration Algorithm for Point Clouds}},
  booktitle = {IEEE Access},
  year = {2020},
  url = {https://openreview.net/forum?id=KJn8bZK2SNk},
}
Figure