Abstract
This paper proposes a fast method for measuring the partial Similarity between 3D Model and 3D point Cloud (SimMC). It is crucial to measure SimMC for many point cloud-related applications such as 3D object retrieval and inverse procedural modelling. In our proposed method, the surface area of model and the Distance from Model to point Cloud (DistMC) are exploited as measurements to calculate SimMC. Here, DistMC is defined as the weighted distance of the distances between points sampled from model and point cloud. Similarly, Distance from point Cloud to Model (DistCM) is defined as the average distance of the distances between points in point cloud and model. In order to reduce huge computational burdens brought by calculation of DistCM in some traditional methods, we define SimMC as the ratio of weighted surface area of model to DistMC. Compared to those traditional SimMC measuring methods that are only able to measure global similarity, our method is capable of measuring partial similarity by employing distance-weighted strategy. Moreover, our method is able to be faster than other partial similarity assessment methods. We demonstrate the superiority of our method both on synthetic data and laser scanning data.
Introduction
In the field of 3D scanning, researchers often face a "needle in a haystack" challenge. Laser scanners produce point clouds—massive, unstructured collections of millions of points that are frequently noisy and incomplete due to occlusions. Automatically identifying a specific 3D model within these scans requires measuring the Similarity between 3D Model and 3D point Cloud (SimMC). Traditional global similarity measures, such as the standard Hausdorff distance, often fail in these contexts because they expect a complete match between objects rather than identifying a specific component within a larger, cluttered scene.
Methodology: Reciprocal Weighted Mean Error (RWME)
To address the computational bottlenecks of traditional methods, this paper introduces the Reciprocal Weighted Mean Error (RWME) metric. Standard approaches typically calculate bidirectional distances (model-to-cloud and cloud-to-model), but processing every point in a massive scan is computationally expensive. RWME optimizes this by focusing on the model-to-cloud distance and applying a distance-weighted strategy:
- Distance-Weighted Strategy: Higher weights are assigned to parts of the 3D model that are close to the point cloud, effectively ignoring parts of the model that have no corresponding points in the scan.
- RWME Variants: The method includes Smoothly-RWME, which uses exponential decay for weighting, and Piecewise-RWME, which uses a binary threshold to zero out weights for distant model components.
- Efficiency: By defining similarity as the ratio of the weighted surface area to the weighted distance, the method avoids the heavy computational load of bidirectional checks and utilizes the FLANN (Fast Library for Approximate Nearest Neighbors) algorithm for high-speed point searching.
Experimental Evaluation
The proposed method was evaluated using both synthetic and real-world datasets. Synthetic tests utilized three target models and query point clouds sampled to simulate varying levels of incompleteness. The RWME metric successfully identified partial similarities, correctly ranking clouds based on their completeness relative to the full model.
Real-world testing was conducted on a mobile laser scanning point cloud of a building ($C_4$) containing 190,677 points.
Key results include:
- High Speed: On the building scan, the similarity calculation took only 1.84 seconds when the model was sampled at 83k points. Even with a massive sampling of 8.3 million points, the process finished in approximately 178 seconds.
- Stability: The method remained stable across different levels of point cloud voxelization, allowing for a flexible trade-off between accuracy and processing speed.
Conclusion and Future Work
The RWME method provides a high-speed solution for measuring partial similarity, making it particularly suitable for Inverse Procedural Modeling (IPM) where speed is paramount. Future research will explore dynamic parameter tuning for complex environments and extending the method to handle non-rigid deformations and unaligned orientations.
Summary updated