Cheesemap: A High-Performance Point-Indexing Data Structure for Neighbor Search in LiDAR Data
Preprint
Abstract
Point cloud data, as the representation of three-dimensional spatial information, is a fundamental piece of information in various domains where indexing and querying these point clouds efficiently is crucial for tasks such as object recognition, autonomous navigation, and environmental modeling. In this paper, we present a comprehensive comparative analysis of various data structures combined with neighboring search methods across different types of point clouds. Additionally, we introduce a novel data structure, cheesemap, to handle 3D LiDAR point clouds. Exploring the sparsity and irregularity in the distribution of points, there are three flavors of the cheesemap: dense, sparse, and mixed. Results show that the cheesemap can outperform state-of-the-art data structures in terms of execution time per query, particularly for ALS (Aerial Laser Scanning) point clouds. Memory consumption is also minimal, especially in the sparse and mixed representations, making the cheesemap a suitable choice for applications involving three-dimensional point clouds.Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- Exploring Spatial Indexing for Accelerated Feature Retrieval in HPC2022
- Adaptive deep learning-based neighborhood search method for point cloudScientific Reports, 2022
- Non-destructive tree volume estimation through quantitative structure modelling: Comparing UAV laser scanning with terrestrial LIDARRemote Sensing of Environment, 2019
- Semantic Classification of 3D Point Clouds with Multiscale Spherical Neighborhoods2018
- SO-Net: Self-Organizing Network for Point Cloud Analysis2018
- 3D Semantic Parsing of Large-Scale Indoor Spaces2016
- Semantic point cloud interpretation based on optimal neighborhoods, relevant features and efficient classifiersISPRS Journal of Photogrammetry and Remote Sensing, 2015
- Contextual classification of lidar data and building object detection in urban areasISPRS Journal of Photogrammetry and Remote Sensing, 2014
- 3D terrestrial lidar data classification of complex natural scenes using a multi-scale dimensionality criterion: Applications in geomorphologyISPRS Journal of Photogrammetry and Remote Sensing, 2012
- Fixed-radius near neighbors searchInformation Processing Letters, 1991