TY - JOUR
T1 - A PARALLEL ALGORITHM for LOCAL POINT DENSITY INDEX COMPUTATION of LARGE POINT CLOUDS
AU - Vo, A. V.
AU - Lokugam Hewage, C. N.
AU - Le Khac, N. A.
AU - Bertolotto, M.
AU - Laefer, D.
N1 - Funding Information:
This publication has emanated from research supported in part by a grant from Science Foundation Ireland under Grant number SFI - 17US3450. For the purpose of Open Access, the au- thor has applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission. Further funding for this project was provided by the National Science Foundation as part of the project “UrbanARK: Assessment, Risk Management, & Knowledge for Coastal Flood Risk Management in Urban Areas” NSF Award 1826134, jointly funded with Science Foundation Ireland and Northern Ireland Trust (Grant USI 137). The clusters used for the testing were provided by NYU High Performance Computing Center and University of Genoa. The authors thanks the NYU HPC staff and Mr Federico Dassereto for the excellent technical support. The aerial LiDAR data of Dublin were acquired with funding from the European Research Council [ERC-2012-StG-307836] and additional funding from Science Foundation Ireland [12/ERC/I2534].
Publisher Copyright:
© 2021 A. V. Vo et al.
PY - 2021/10/7
Y1 - 2021/10/7
N2 - 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.
AB - 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.
KW - Apache Spark
KW - Density
KW - Distributed
KW - LiDAR
KW - Local Point Density Index
KW - Parallel
KW - Point cloud
UR - http://www.scopus.com/inward/record.url?scp=85118735508&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85118735508&partnerID=8YFLogxK
U2 - 10.5194/isprs-annals-VIII-4-W2-2021-75-2021
DO - 10.5194/isprs-annals-VIII-4-W2-2021-75-2021
M3 - Conference article
AN - SCOPUS:85118735508
SN - 2194-9042
VL - 8
SP - 75
EP - 82
JO - ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
JF - ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
IS - 4/W2-2021
T2 - 16th 3D GeoInfo Conference, 3D GeoInfo 2021
Y2 - 11 October 2021 through 14 October 2021
ER -