Accelerate Point Cloud Structuring for Deep Neural Networks via Fast Spatial-Searching Tree

Due to the disorder of points, point clouds need to be structured by sampling and neighbor query before feeding to Deep Neural Networks (DNNs). Structuring point clouds costs high computation overhead, which limits the deployment of DNNs on embedded devices such as autonomous vehicles and robots. To address this problem, we design a novel data structure, i.e., Fast Spatial-Searching Tree (FSSTree), to accelerate point cloud structuring for DNNs on embedded devices. The FSSTree is constructed based on density distribution of point clouds to achieve semantic segmentation, which can guarantee that points with similar spatial positions are stored in adjacent storage sets. Based on FSSTree, we propose a point-sparsity-aware sampling method and a leafwise k-nearest neighbor query method to reduce the computation overhead of structuring point clouds. Meanwhile, the point-sparsity-aware sampling method achieves fair sampling on both dense and sparse parts, which can overcome the nonuniform distribution of point clouds caused by occlusion, lighting and other factors. The leafwise k-nearest neighbor query method skips a large number of dissimilar points to quickly obtain the neighbor points, which can significantly reduce the search scope. We also present a layerwise self-pruning algorithm to automatically adjust the FSSTree after each layer’s operation to match the hierarchical architecture of DNNs. Finally, we conduct extensive experiments on KITTI, S3DIS and ModelNet40 datasets and three devices (including an RTX 3090 server, a Jetson AGX Xavier and an Apple M2). The experimental results demonstrate the efficiency of our approach, which can reduce the time overhead by up to 97.46% compared with the other five methods. The code is released at <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://github.com/EmbeddedAILab-UESTC/fsstree</uri>.