Real-Time Efficient Relocation Algorithm Based on Depth Map for Small-Range Textureless 3D Scanning

Fengbo Zhu, Shunyi Zheng, Xiaonan Wang, Yuan He, Gui Li, Liangxiong GongSensors 2019 · DOI

TL;DR

This paper presents a novel real-time algorithm for 3D scanner relocation using depth maps, crucial for textureless objects in industrial scanning. It achieves over 90% accuracy within 200ms by efficiently calculating, storing, querying, and verifying features derived from depth data.

What Problem Does This Paper Address?

Industrial 3D scanning, especially for objects lacking distinct visual features (like molds or sculptures), faces a significant challenge: maintaining the scanner's position and orientation (pose) as it moves. When a scanner loses track of its pose, it needs to "relocate" itself within the scanned environment. This is particularly difficult for small-range scanners that capture limited depth information per frame. Existing methods often struggle with textureless surfaces, real-time performance, and accuracy. This paper tackles the problem of robust and efficient relocation for such scenarios, focusing on using only depth map information.

Methods

The proposed relocation algorithm is a four-stage pipeline:

  1. Feature Calculation: This stage focuses on extracting stable and discriminative features from the depth map. It involves:
  2. Local Reference Frame (LRF) Calculation: Using covariance decomposition of surface normals to create a local coordinate system that is invariant to rigid transformations.
  3. Feature Extreme Point Extraction: Employing a grid-based method to select feature points that are stable and have good discrimination potential, avoiding noisy or occluded areas.
  4. Feature Description: Modifying the ISS (Intrinsic Shape Signatures) descriptor to use distance as a weight for efficiency and normalizing features to reduce the impact of varying scanning distances.
  5. Feature De-Duplication: Using a hash map and non-maximum suppression to reduce redundant feature points, speeding up subsequent stages.
  6. Feature Database Construction and Query: A Local Sensitive Hash Tree (LST) is used to efficiently store and query features. LST allows for fast approximate nearest neighbor searches, crucial for handling large datasets.
  7. Corresponding Feature Verification: This stage filters out incorrect feature matches obtained from the LST query. It combines:
  8. Eigenvalue and Descriptor Verification: Using eigenvalue constraints and feature descriptor similarity to prune dissimilar matches.
  9. Pair Distance, Angle, and Direction Verification: Leveraging the LRF information to check the geometric consistency of matching pairs based on their relative positions, angles, and directions.
  10. Feature Clustering: Applying a dynamic k-means clustering approach to group consistent transformation hypotheses, helping to reject outliers.
  11. Rigid Transformation Calculation: An improved RANSAC (Random Sample Consensus) method is used to robustly estimate the transformation matrix from the clustered feature pairs. This approach is designed to mitigate issues caused by repetitive structures in the scene. The final transformation is then refined using the ICP (Iterative Closest Point) algorithm.

The pipeline also includes a Downsampling step at the beginning to reduce the computational load of subsequent stages.

Datasets

The paper evaluates its algorithm using data collected from a small-range visual scanner. The experiments were conducted on four distinct objects: "model," "small items," "ceramic horse," and "emboss." These objects vary in size, surface texture (smooth vs. rough), and feature richness. The authors do not introduce new datasets but rather use these objects to simulate real-world industrial scanning scenarios.

Key Insights and Ideas

  • Depth Maps are Sufficient for Textureless Relocation: The core insight is that even without visual texture, depth information alone can be leveraged for robust and accurate 3D scanner relocation.
  • Multi-Stage Verification is Key: Relying on a single matching criterion is insufficient. The paper demonstrates the effectiveness of a layered approach, combining eigenvalue/descriptor checks with geometric consistency (distance, angle, direction) and clustering to significantly reduce false positives.
  • LST for Efficient Querying: The use of LST for feature database construction and querying is critical for achieving real-time performance, especially as the number of features grows.
  • RANSAC for Robustness: The improved RANSAC method is vital for handling scenes with repetitive structures, which can easily lead to incorrect matches and relocation failures in simpler methods.
  • Parameter Tuning is Crucial: The paper highlights that careful selection of parameters (e.g., thresholds for eigenvalues, distances, angles) is essential for balancing accuracy and speed.

Key Results

  • Real-Time Performance: The algorithm achieves relocation times within 200 ms, even with a large number of frames and feature points. The "base + query + reloc" time is consistently below this threshold across all tested objects.
  • High Correct Relocation Rate: The proposed algorithm consistently achieves a correct relocation rate of over 90% in offline experiments and 100% for most objects in online experiments (93% for "small items").
  • RMS Error Stability: The relocation RMS error stabilizes around 5 mm, indicating a good initial value for subsequent ICP refinement.
  • Feature Point Count: The number of feature points extracted varies significantly by object, from around 63,400 for the ceramic horse to over 239,000 for small items, demonstrating the algorithm's ability to handle varying feature densities.

Limitations and Future Work

  • LST Leaf Node Limitations: The paper acknowledges that if a feature has too many similar features in the database, they might be divided into different leaf nodes in the LST, making it difficult to find the correct match.
  • Similar Regions: If many distinct regions of the scanned object are geometrically similar, the algorithm might fail to distinguish them, leading to relocation failure.
  • Feature Point Stability: While efforts were made to improve feature stability, the paper notes that some feature points can still be disturbed by occlusion or noise, impacting the correct relocation rate.
  • Future Work: The authors suggest exploring feature points with the "flattest" neighborhood (as opposed to highest curvature) to potentially improve relocation robustness, especially in the presence of noise and occlusion. They also aim to further enhance the algorithm's performance in scenarios with highly repetitive structures.

Summary updated

Abstract

As an important part of industrial 3D scanning, a relocation algorithm is used to restore the position and the pose of a 3D scanner or to perform closed-loop detection. The real time and the relocation correct ratio are prominent and difficult points in 3D scanning relocation research. By utilizing the depth map information captured by a binocular vision 3D scanner, we developed an efficient and real-time relocation algorithm to estimate the current position and pose of the sensor real-time and high-correct-rate relocation algorithm for small-range 3D texture less scanning. This algorithm mainly involves feature calculation, feature database construction and query, feature matching verification, and rigid transformation calculation; through the four parts, the initial position and pose of the sensors in the global coordinate system is obtained. In the experiments, the efficiency and the correct-rate of the proposed relocation algorithm were elaborately verified by offline and online experiments on four objects of different sizes, and a smooth and a rough surface. With more data frames and feature points, the relocation could be maintained real time within 200 ms, and a high correct rate of more than 90% could be realized. The experimental results showed that the proposed algorithm could achieve a real-time and high-correct-ratio relocation.
BibTeX
@inproceedings{zhu2019real,
  author = {Fengbo Zhu and Shunyi Zheng and Xiaonan Wang and Yuan He and Gui Li and Liangxiong Gong},
  title = {{Real-Time Efficient Relocation Algorithm Based on Depth Map for Small-Range Textureless 3D Scanning}},
  booktitle = {Sensors},
  year = {2019},
  doi = {10.3390/s19183855},
}
Figure