A PARALLEL ALGORITHM for LOCAL POINT DENSITY INDEX COMPUTATION of LARGE POINT CLOUDS

A. V. Vo, C. N. Lokugam Hewage, N. A. Le Khac, M. Bertolotto, D. Laefer

Research output: Contribution to journalConference articlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)75-82
Number of pages8
JournalISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Volume8
Issue number4/W2-2021
DOIs
StatePublished - Oct 7 2021
Event16th 3D GeoInfo Conference, 3D GeoInfo 2021 - New York City, United States
Duration: Oct 11 2021Oct 14 2021

Keywords

  • Apache Spark
  • Density
  • Distributed
  • LiDAR
  • Local Point Density Index
  • Parallel
  • Point cloud

ASJC Scopus subject areas

  • Instrumentation
  • Environmental Science (miscellaneous)
  • Earth and Planetary Sciences (miscellaneous)

Fingerprint

Dive into the research topics of 'A PARALLEL ALGORITHM for LOCAL POINT DENSITY INDEX COMPUTATION of LARGE POINT CLOUDS'. Together they form a unique fingerprint.

Cite this