TL;DR
This paper introduces an improved point cloud registration algorithm that leverages a novel double-threshold feature extraction method using normal vectors and curvature, combined with a Distance Disparity Matrix (DDM) to robustly filter incorrect correspondences. This approach significantly enhances both the efficiency and precision of registering large, complex 3D point clouds, outperforming existing methods.
What Problem Does This Paper Address?
Capturing the complete 3D geometry of objects often requires collecting point clouds from multiple viewpoints. To create a unified 3D model, these individual point clouds must be accurately aligned or "registered." This process is challenging, especially with the massive datasets generated by modern 3D scanning technologies. Traditional methods like Iterative Closest Point (ICP) can be slow, prone to local optima, and sensitive to noise. While feature-based methods offer speed improvements, they often struggle with accuracy due to insufficient or unreliable feature point extraction and matching. This paper aims to bridge this gap by developing a registration algorithm that is both fast and highly accurate, even for complex objects and challenging scanning conditions.
Methods
The proposed algorithm follows a coarse-to-fine registration strategy:
- Double Threshold Feature Extraction: This is the core novelty. Instead of relying on a single feature, the algorithm uses both the normal vector and curvature of local surface patches. By applying double thresholds to these attributes, it effectively identifies highly representative feature points while significantly reducing the total number of points. This is crucial for handling large datasets.
- Fast Point Feature Histogram (FPFH): Once feature points are extracted, FPFH descriptors are computed to represent their local geometric context. This allows for efficient initial matching of corresponding points between point clouds.
- Distance Disparity Matrix (DDM) Algorithm: To address the issue of incorrect initial correspondences (mismatches), the DDM algorithm is employed. It leverages the Euclidean invariant properties of rigid body transformations. By analyzing the distances between pairs of feature points before and after transformation, the DDM can effectively identify and eliminate outliers, leading to a more reliable set of initial correspondences.
- Sample Consensus Initial Alignment (SAC-IA): This algorithm is used for coarse registration. It takes the refined set of correspondences from the DDM step to find an initial transformation matrix, providing a good starting point for fine registration.
- Iterative Closest Point (ICP) Algorithm: Finally, the standard ICP algorithm is applied for fine registration, refining the transformation to achieve high precision.
Datasets
The authors evaluated their algorithm using several well-known 3D models:
- Bunny, Dragon, Armadillo, and Buddha models from the Stanford University 3D Scanning Repository.
- The Airplane model from the Modelnet40 Dataset.
These models were used in two experimental cases:
- Case 1: Point clouds from the same angle, simulating ideal conditions with one-to-one correspondence.
- Case 2: Point clouds collected from different angles, simulating more realistic scenarios with potential occlusion, noise, and varying densities.
Key Insights and Ideas
- Synergistic Feature Extraction: Combining normal vectors and curvature with double thresholds provides a more robust and discriminative way to select feature points compared to using either feature alone. This is key to reducing noise and improving the quality of initial matches.
- DDM for Outlier Rejection: The DDM algorithm's ability to leverage Euclidean invariants for outlier removal is a powerful technique for cleaning up initial correspondences, which is often a bottleneck in feature-based registration.
- Efficiency through Reduction: By drastically reducing the number of points early in the pipeline (feature extraction) and then further refining correspondences (DDM), the algorithm achieves significant speedups without sacrificing accuracy.
- Robustness to Density: The feature extraction method is less affected by point cloud density variations, making it more reliable than down-sampling approaches for complex surfaces.
Key Results
- Accuracy: The proposed algorithm achieved near-zero Mean Square Error (MSE) in Case 1 (same angle registration), indicating exact registration. In Case 2 (different angles), it demonstrated superior accuracy compared to ICP, and algorithms from references [27] and [28], particularly for complex surfaces.
- Efficiency: The algorithm significantly reduced registration time. For Case 2, it was considerably faster than ICP (e.g., 1/4 the time of [27] and 1/2 the time of [28]). The time complexity was less affected by point cloud density compared to down-sampling methods.
- Point Reduction: The number of final registered point clouds was reduced to approximately 0.1% of the original point clouds, highlighting the algorithm's efficiency in handling large datasets.
Limitations and Future Work
- Noise Sensitivity: While the algorithm shows improved robustness, the authors acknowledge that final corresponding point pairs cannot be guaranteed to be completely correct due to noise and interference factors, which can influence registration results.
- Complexity Dependence: The registration time is still related to the complexity of the object's surface. Highly complex surfaces with many feature points can lead to longer registration times.
- Future Work: The authors plan to:
- Perform noise processing on original point cloud data.
- Investigate new feature descriptors to further improve the accuracy of corresponding point pairs.
- Aim to make registration even more precise.
Summary updated