A Systematic Approach for Cross-source Point Cloud Registration by Preserving Macro and Micro Structures

Xiaoshui Huang, Jian Zhang, Lixin Fan, Qiang Wu, Chun YuanIEEE TIP 2016 · DOI · OpenReview

TL;DR

This paper introduces a novel method for registering 3D point clouds from different sensor types (e.g., LiDAR, Kinect, RGB cameras), which is notoriously difficult due to variations in data density, missing information, and scale differences. The core innovation lies in preserving both the overall shape (macro structure) and local details (micro structure) of objects using a graph-based approach, leading to significantly more robust and accurate registration compared to existing methods.

What Problem Does This Paper Address?

Registering 3D point clouds – aligning multiple scans of the same scene or object into a single, coherent model – is a fundamental problem in computer vision, robotics, and graphics. While methods exist for registering point clouds from the same sensor type, the challenge escalates dramatically when dealing with cross-source point clouds. These arise from diverse sensors like LiDAR, depth cameras (Kinect), and photogrammetry (Structure from Motion using RGB cameras). The key difficulties include:

  • Varying Densities: Different sensors capture points at vastly different resolutions.
  • Missing Data: Certain sensors struggle with reflective surfaces or uniform textures, leading to gaps in the point cloud.
  • Scale and Rotation Differences: Sensors may capture objects at different distances or orientations, requiring robust scale and rotation estimation.
  • Noise and Outliers: Real-world sensor data is inherently noisy.

Existing methods often fail under these conditions, especially when dealing with large datasets or significant variations. This paper aims to bridge this gap by developing a systematic approach that can handle these complex cross-source registration challenges.

Methods

The proposed method, termed CSGM (Cross-Source Graph Matching), tackles the problem through a multi-stage pipeline:

  1. Scale Normalization: An automatic method is introduced to normalize the scale of the two point clouds, addressing a critical challenge in cross-source registration. This is done by comparing the mean distances of points in each cloud.
  2. Macro/Micro Structure Extraction: This is the core novelty. Instead of relying solely on point-to-point correspondences, the method extracts two types of structural information:
  3. Macro Structure: Represents the overall outline and global shape of the object or scene.
  4. Micro Structure: Represents local details, defined as "super voxels" (segments of the point cloud with similar geometric properties).
  5. Graph Construction: The extracted macro and micro structures are integrated into a graph. Super voxel centroids form the nodes (representing micro structures), and their spatial relationships form the edges (representing macro structure). Crucially, the ESF (Ensemble of Shape Functions) descriptor is used for nodes, providing a robust feature that captures local geometry and is less sensitive to density variations and noise than raw coordinates. Edge descriptors capture spatial and geometric relationships.
  6. Optimization (Enhanced Graph Matching): The registration problem is transformed into a graph matching problem. An improved factorized graph matching (FGM) method is proposed that incorporates a "smoothness" term. This term leverages the fact that rigid transformations (rotation and translation) should maintain relative distances between corresponding points, helping to avoid local optima and achieve a more globally consistent match.
  7. Transformation Estimation: After graph matching provides initial correspondences, 3D RANSAC is used to robustly remove outliers, followed by Iterative Closest Point (ICP) to refine the final transformation matrix and produce the aligned point clouds.

Datasets

The paper utilizes several datasets for evaluation:

  • Same-Source Datasets: Standard 3D models like "Bunny," "Lucy," and "Armadillo" from the Stanford 3D scanning repository are used to test robustness to noise, outliers, and rotation.
  • Real Cross-Source Datasets:
    • Database A: Comprises four sets of cross-source objects created using KinectFusion (dense, uniform point clouds) and VSFM (from RGB images, often sparser and with more artifacts).
  • Database B: Built using KinectFusion and its RGB camera, with a specific methodology to ensure accurate ground truth by re-projecting VSFM point clouds into the KinectFusion coordinate system. This database contains 13 datasets.
  • Synthetic Cross-Source Datasets (Database C): Synthetically generated datasets are created to specifically simulate cross-source challenges like varying density, missing data, scale differences, and noise. These are based on Stanford 3D objects.

Key Insights and Ideas

  • Structure over Points: The fundamental insight is that humans register complex scenes by focusing on overall structure (macro) and local features (micro), rather than precise point locations. This paper translates this human intuition into a computational framework.
  • ESF Descriptor for Robustness: Using the ESF descriptor for graph nodes is a key enabler for cross-source registration. It provides a discriminative feature that is invariant to local density variations and noise, unlike raw point coordinates.
  • Graph Matching with Global Constraints: Transforming registration into graph matching is not new, but the paper's enhancement with a "smoothness" term that considers global geometric constraints significantly improves robustness against local minima, which plague many optimization methods.
  • Systematic Pipeline: The paper presents a complete, end-to-end pipeline that addresses multiple cross-source challenges sequentially and cohesively, from scale normalization to final ICP refinement.

Key Results

  • Superior Cross-Source Performance: The proposed CSGM method consistently outperforms state-of-the-art methods (ICP, Go-ICP, GMMReg, JR-MPC, 4PCS, Super-4PCS, TPS-RPM, CPD) on challenging real and synthetic cross-source datasets, both qualitatively and quantitatively.
  • Robustness to Challenges: The method demonstrates significant robustness to large variations in density, missing data, scale differences, noise, and outliers, which are common failure points for other algorithms.
  • Quantitative Metrics: The paper reports quantitative evaluations using RMSE for rotation parameters and F-norm for transformation matrices, showing CSGM achieving the highest accuracy across multiple datasets. For instance, Figure 12 shows CSGM achieving the highest accuracy on Database B, and Figure 14/15 show similar results on Database C.
  • Same-Source Performance: The method also performs well on same-source datasets, demonstrating its general applicability.

Limitations and Future Work

  • Scale Normalization Limitations: While the proposed scale normalization is automatic, the paper acknowledges it doesn't completely eliminate scale differences, but it's sufficient for the subsequent graph matching stage.
  • Computational Cost: While the paper aims for efficiency, complex graph matching and optimization can still be computationally intensive for very large point clouds. The paper mentions that some methods (TPS-RPM, JR-MPC) were downsampled due to memory costs.
  • Future Work: The paper doesn't explicitly detail future work, but the success of the macro/micro structure approach and the enhanced graph matching suggests potential for extending this framework to non-rigid registration or more complex scene understanding tasks. The systematic pipeline itself could be further optimized for speed.

Summary updated

Abstract

We propose a systematic approach for registering cross-source point clouds. The compelling need for cross-source point cloud registration is motivated by the rapid development of a variety of 3D sensing techniques, but many existing registration methods face critical challenges as a result of the large variations in cross-source point clouds. This paper therefore illustrates a novel registration method which successfully aligns two cross-source point clouds in the presence of significant missing data, large variations in point density, scale difference and so on. The robustness of the method is attributed to the extraction of macro and micro structures. Our work has three main contributions: (1) a systematic pipeline to deal with cross-source point cloud registration; (2) a graph construction method to maintain macro and micro structures; (3) a new graph matching method is proposed which considers the global geometric constraint to robustly register these variable graphs. Compared to most of the related methods, the experiments show that the proposed method successfully registers in cross-source datasets, while other methods have difficulty achieving satisfactory results. The proposed method also shows great ability in same-source datasets.
BibTeX
@article{huang2016systematic,
  author = {Xiaoshui Huang and Jian Zhang and Lixin Fan and Qiang Wu and Chun Yuan},
  title = {{A Systematic Approach for Cross-source Point Cloud Registration by Preserving Macro and Micro Structures}},
  journal = {IEEE Trans. Image Process.},
  year = {2016},
  doi = {10.1109/tip.2017.2695888},
}
Figure