Analysis of Large-Scale Unstructured Urban Range Scan Data

Efficient 3D scanning technology has led to acquisition of very large datasets for application areas as diverse as terrain and urban modeling, but relatively few techniques exist to automatically extract meaningful regions from this data, and the largest datasets examined in the literature rarely exceed millions of points in size. In this thesis, we present an efficient algorithm for identification of locally planar regions in large-scale GPS-registered scan data containing hundreds of millions of points. We define hard, statistical measures of accuracy and examine the performance of our algorithm on two real-world datasets with vastly varying characteristics. We examine the usefulness of a number of extensions to the algorithm, and confirm our assumptions regarding the accuracy of the parallel nature of our approach. Simulating a high-performance distributed computing platform, we are able to process scan data of approximately 100 million points in under 20 minutes, and a much larger dataset of over three billion points in under 14 hours.