Analysis of Large-Scale Unstructured Urban Range Scan Data

Master's Thesis


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.


Attribute NameValues
  • etd-12112009-111336

Author Alexandri Gregor Zavodny
Advisor Patrick J. Flynn
Contributor Scott Emrich, Committee Member
Contributor Kevin W. Bowyer, Committee Member
Contributor Patrick J. Flynn, Committee Chair
Degree Level Master's Thesis
Degree Discipline Computer Science and Engineering
Degree Name MSCSE
Defense Date
  • 2009-12-01

Submission Date 2009-12-11
  • United States of America

  • range scan data

  • object extraction

  • University of Notre Dame

  • English

Record Visibility Public
Content License
  • All rights reserved

Departments and Units


Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.