A PARALLEL ALGORITHM FOR LOCAL POINT DENSITY INDEX COMPUTATION OF LARGE POINT CLOUDS
A PARALLEL ALGORITHM FOR LOCAL POINT DENSITY INDEX COMPUTATION OF LARGE POINT CLOUDS
复制标题
DOI：
10.5194/isprs-annals-viii-4-w2-2021-75-2021
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
A. Vo;C. N. Lokugam Hewage;N. A. Le Khac;M. Bertolotto;D. Laefer
中科院分区：
文献类型：
--
作者：
A. Vo;C. N. Lokugam Hewage;N. A. Le Khac;M. Bertolotto;D. Laefer
摘要。点密度是决定点云数据集可用性的一个重要属性。本文介绍了一种高效、可扩展、并行的计算局部点密度指数的算法，这是一种复杂的点云密度度量。计算局部点密度指数是非常重要的，因为这种计算涉及到对潜在的大输入点云中的每个单独点都需要进行邻居搜索。大多数现有的算法和软件都不能大规模地计算点密度。因此，本文介绍的算法旨在解决在大型现代点云（如在国家或区域扫描中收集的点云）中考虑这一因素所需的计算效率和可扩展性。该算法分为两个阶段。在阶段1中，执行点级并行处理步骤，将非结构化输入点云划分为部分重叠的缓冲块。每个块周围都有一个缓冲区，这样数据分区就不会在最终结果中引入空间不连续。在阶段2中，缓冲的块被分配到不同的处理器，用于并行计算局部点密度指数。该平铺级并行处理步骤使用具有r树数据结构的传统算法执行。该算法简单、高效，特别适合处理大型点云。利用在爱尔兰都柏林部分地区获得的14亿个点数据集进行的实验表明，效率系数高达14.8/16。更具体地说，当进程（即执行器）的数量增加16倍时，计算时间减少了14.8倍。使用16个执行器和每个执行器8个内核，为14亿个点数据集计算本地点密度指数只需5分钟多一点。与没有并行所需的6小时相比，计算时间减少了近70倍。
Abstract. Point density is an important property that dictates the usability of a point cloud data set. This paper introduces an efficient, scalable, parallel algorithm for computing the local point density index, a sophisticated point cloud density metric. Computing the local point density index is non-trivial, because this computation involves a neighbour search that is required for each, individual point in the potentially large, input point cloud. Most existing algorithms and software are incapable of computing point density at scale. Therefore, the algorithm introduced in this paper aims to address both the needed computational efficiency and scalability for considering this factor in large, modern point clouds such as those collected in national or regional scans. The proposed algorithm is composed of two stages. In stage 1, a point-level, parallel processing step is performed to partition an unstructured input point cloud into partially overlapping, buffered tiles. A buffer is provided around each tile so that the data partitioning does not introduce spatial discontinuity into the final results. In stage 2, the buffered tiles are distributed to different processors for computing the local point density index in parallel. That tile-level parallel processing step is performed using a conventional algorithm with an R-tree data structure. While straight-forward, the proposed algorithm is efficient and particularly suitable for processing large point clouds. Experiments conducted using a 1.4 billion point data set acquired over part of Dublin, Ireland demonstrated an efficiency factor of up to 14.8/16. More specifically, the computational time was reduced by 14.8 times when the number of processes (i.e. executors) increased by 16 times. Computing the local point density index for the 1.4 billion point data set took just over 5 minutes with 16 executors and 8 cores per executor. The reduction in computational time was nearly 70 times compared to the 6 hours required without parallelism.