Clustering Denoising of 2D LiDAR Scanning in Indoor Environment Based on Keyframe Extraction

Weiwei Hu, Keke Zhang, Lihuan Shao, Qinglei Lin, Yongzhu Hua, Jing QinSensors 2022 · DOI

TL;DR

This paper introduces a novel method for denoising 2D LiDAR scans in indoor SLAM systems by combining keyframe extraction with region-based clustering. By intelligently dropping redundant scans and processing only keyframes with a more efficient clustering approach, the method significantly reduces computational load and improves trajectory accuracy, making it ideal for resource-constrained mobile robots.

What Problem Does This Paper Address?

Indoor SLAM systems heavily rely on LiDAR sensors for mapping and localization. However, LiDAR data is susceptible to noise from various sources like lighting conditions and low-reflectivity objects, leading to inaccurate point clouds. Traditional denoising methods, often based on clustering, can be computationally expensive, posing a challenge for real-time performance on mobile robots with limited processing power. The paper aims to tackle this by developing a denoising technique that is both effective at removing noise and highly efficient, thus reducing the overall computational burden on the SLAM system.

Methods

The proposed method integrates keyframe extraction with a specialized clustering approach.

  • Keyframe Extraction: To reduce the number of scans that need processing, the system first extracts "keyframes." Raw LiDAR scans are converted into histograms, and their similarity is calculated using the Pearson Correlation Coefficient (PCC). A sliding window approach is used to compare the current scan against a history of recent keyframes. If the current scan is highly similar to previous keyframes, it's deemed redundant and dropped, saving significant processing time. This step is crucial for reducing the computational load on subsequent stages.
  • Region-Based Clustering: For the selected keyframes, a novel clustering method is employed. The LiDAR scan is first divided into several regions based on equal ring areas. Within each region, points are clustered using an angle difference threshold, which is computationally less intensive than traditional Euclidean distance calculations. This region-based approach effectively reduces the dimensionality of the clustering problem.
  • Cluster Merging and Filtering: Adjacent clusters are then merged if they meet specific angle and distance thresholds, ensuring that parts of the same object aren't split into separate clusters. Finally, clusters with fewer laser points than a predefined threshold are filtered out as noise.

Datasets

The primary dataset used for evaluation is the MIT Stata Center dataset. This dataset is noted for containing a large amount of 2D LiDAR data and providing real trajectory files, making it suitable for testing SLAM algorithms and trajectory accuracy.

Key Insights and Ideas

  • Keyframes as a Bottleneck Reduction: The core insight is that not all LiDAR scans contain new, valuable environmental information. By intelligently identifying and processing only "keyframes," the system can drastically reduce the amount of data that needs to be denoised, directly addressing the computational bottleneck.
  • Histogram for Efficient Similarity: Using histograms to represent LiDAR scans for similarity comparison is a clever way to reduce data dimensionality and enable faster calculations compared to direct point cloud comparisons.
  • Region-Based Clustering for Speed: Dividing the scan into regions and then clustering within these regions, coupled with using angle differences instead of Euclidean distances, significantly speeds up the clustering process. This is a key innovation for real-time performance.
  • Trade-off for Efficiency: The method demonstrates that a controlled reduction in the number of processed scans (via keyframe extraction) can lead to improved overall system performance without sacrificing trajectory accuracy, and in some cases, even improving it.

Key Results

  • Computational Speedup: The proposed method, when integrated into the Cartographer SLAM algorithm, reduced the processing time for a single frame from approximately 25.207 ms to as low as 0.233 ms for keyframes (a reduction to 0.92% of the original time). Even for non-keyframes that require processing, the time increase was minimal.
  • Scan Dropping Rate: The method successfully drops a significant portion of scans, with experiments showing nearly 50% of scans being dropped on average.
  • Trajectory Accuracy Improvement: The method demonstrated an improvement in trajectory accuracy, with an average increase of about 10% compared to the baseline Cartographer algorithm.
  • Comparison with DBSCAN: When compared to DBSCAN for denoising, the proposed method showed significantly faster processing times (0.679 ms vs. 13.658 ms per frame) and comparable or slightly better trajectory accuracy.

Limitations and Future Work

  • Long Corridor Environments: The paper acknowledges that in environments with highly similar consecutive scans (like long corridors), the keyframe extraction might drop too many scans, potentially performing poorly.
  • Corridor Detection: As a future direction, the authors suggest developing a simple corridor detection mechanism that could act as a "switch" to disable keyframe extraction in such environments.
  • Robot Speed and Window Size: A more accurate quantitative relationship between robot moving speed and the sliding window size for keyframe extraction is also proposed for future work.
  • 3D LiDAR Extension: The authors express interest in extending the region segmentation idea to process 3D LiDAR data.

Summary updated

Abstract

In the indoor laser simulation localization and mapping (SLAM) system, the signal emitted by the LiDAR sensor is easily affected by lights and objects with low reflectivity during the transmission process, resulting in more noise points in the laser scan. To solve the above problem, this paper proposes a clustering noise reduction method based on keyframe extraction. First, the dimension of a scan is reduced to a histogram, and the histogram is used to extract the keyframes. The scans that do not contain new environmental information are dropped. Secondly, the laser points in the keyframe are divided into different regions by the region segmentation method. Next, the points are separately clustered in different regions and it is attempted to merge the point sets from adjacent regions. This greatly reduces the dimension of clustering. Finally, the obtained clusters are filtered. The sets with the number of laser points lower than the threshold will be dropped as abnormal clusters. Different from the traditional clustering noise reduction method, the technique not only drops some unnecessary scans but also uses a region segmentation method to accelerate clustering. Therefore, it has better real-time performance and denoising effect. Experiments on the MIT dataset show that the method can improve the trajectory accuracy based on dropping a part of the scans and save a lot of time for the SLAM system. It is very friendly to mobile robots with limited computing resources.
BibTeX
@inproceedings{hu2022clustering,
  author = {Weiwei Hu and Keke Zhang and Lihuan Shao and Qinglei Lin and Yongzhu Hua and Jing Qin},
  title = {{Clustering Denoising of 2D LiDAR Scanning in Indoor Environment Based on Keyframe Extraction}},
  booktitle = {Sensors},
  year = {2022},
  doi = {10.3390/s23010018},
}
Figure