Vo-Norvana: Versatile Framework for Efficient Segmentation of Large Point Cloud Data Sets

Dense three-dimensional (3D) point clouds collected from rapidly evolving data acquisition techniques such as light detection and ranging (lidar) and structure from motion (SfM) multiview stereo (MVS) photogrammetry contain detailed geometric information of a scene suitable for a wide variety of applications. Among the many processes within a typical point cloud processing workflow, segmentation is often a crucial step to group points with similar attributes to support more advanced modeling and analysis. Segmenting large point cloud data sets (i.e., hundreds of millions to billions of points) can be extremely time consuming and tedious with current tools, which primarily rely on significant manual effort. While many automated methods have been proposed, the practicality, scalability, and versatility of these approaches remain a bottleneck stifling processing of large data sets. To overcome these challenges, this paper introduces a novel, generalized segmentation framework called Vo-Norvana, which incorporates a new voxelization technique, a normal variation analysis considering the positioning uncertainty of the point cloud, and a custom region growing process for clustering. The proposed framework was tested with several large-volume data sets collected in diverse scene types using several data acquisition platforms including terrestrial lidar, mobile lidar, airborne lidar, and drone-based SfM-MVS photogrammetry. In evaluating the accuracy of models generated from Vo-Norvana against manual segmentation, the average error of the position, orientation, and dimensions are 2.7 mm, 0.083 degrees, and 0.9 mm, respectively. Over 0.2 million points per second and 36 thousand voxels per second can be achieved when segmenting an airborne lidar data set containing over 639 million points to about 1 million segments.