Creating the medial axis transform for billions of lidar points using a memory efficient method

Abstract

Using Light Detection And Radar (LiDAR) large parts of the earth's geography can be captured an represented as a 3D pointcloud. The whole elevation dataset of the Netherlands (AHN2) is currently available and captured using this technique, it contains around 640 billion points. These massive dataset in its current form is well suited for visualisation and certain forms of analysis, as the 3D points are the outer boundary of objects. However, the Medial Axis Transform (MAT) is another way to represent these objects. As it represents the inner/outer skeleton of the objects some features become more easily detectable and it could be used as a tool in point cloud analysis. The MAT can be created from pointclouds using various methods, however the shrinking ball algorithm is used as it is relative simple to implement, more storage efficient and easier to parallellize compared to other methods. Yet the computation of it for a massive dataset such as the AHN2/3 is troublesome as it does not fit inside the main memory of the computer. This thesis focusses on how to scale the MAT so it can be computed for massive datasets using a main memory efficient approach. Two methods (i.e. tiling and streaming based algorithms) are proposed. They both subdivide the pointcloud dataset in to manageable subsets, so that the MAT can be computed on these smaller sets. However, the tiling approach relies heavily on temporal storage on the external memory (harddisk) by creating smaller tiles. whilst the streaming approach tries to manage it within the Main memory by scanning the input dataset multiple times and storing tiles in the main memory. This thesis concludes that using both methods it is possible to compute the MAT of a dataset which is larger than the main memory. The tiling approach seems suited as the temporal storage of the external memory is about the same size as the output data, further more the main memory usage can be regulated easily as the amount of tiles which will be processed at the same time can be chosen. The streaming approach shows potential to be efficient as well in computing the MAT. However, because streaming computations loads the input data sequentially and processes it using a limited memory buffer, outputting data and freeing memory space is needed. In this thesis a first step in finding a way to achieve that is made, however it is not functioning that well. As such the data outputting can not be as rapid as it should be when using streaming algorithms.