This paper describes a method for extracting roads from a large scale unstructured 3D point cloud of an urban environment consisting of many superimposed scans taken at different times. Given a road map and a point cloud, our system automatically separates road surfaces from the rest of the point cloud. Starting with an approximate map of the road network given in the form of 2D intersection locations connected by polylines, we first produce a 3D representation of the map by optimizing Cardinal splines to minimize the distances to points of the cloud under continuity constraints. We then divide the road network into independent patches, making it feasible to process a large point cloud with a small in-memory working set. For each patch, we fit a 2D active contour to an attractor function with peaks at small vertical discontinuities to predict the locations of curbs. Finally, we output a set of labeled points, where points lying within the active contour are tagged as ``road'' and the others are not. During experiments with a LIDAR point set containing almost a billion points spread over six square kilometers of a city center, our method provides 86% correctness and 94% completeness.

@article{Boyko:2011:ERF,
   author = "Aleksey Boyko and Thomas Funkhouser",
   title = "Extracting roads from dense point clouds in large scale urban
      environment",
   journal = "ISPRS Journal of Photogrammetry and Remote Sensing",
   year = "2011",
   month = oct
}