A Methodology for Automated Segmentation and Reconstruction of Urban 3-D Buildings from ALS Point Clouds

In this paper, a methodology which allows automated and efficient reconstruction of three-dimensional (3-D) geometric building models from an Airborne Laser Scanning (ALS) point cloud is introduced and its performance is analyzed and evaluated. The proposed method avoids abnormal and/or infinite solutions which are typically encountered in previously published methods that use the rooftop primitive adjacency matrix to solve the critical rooftop vertices. In particular, first, an improved random sample consensus (RANSAC) algorithm is proposed to segment the rooftop primitives, i.e., the planar patches that constitute rooftops, of each building or group of connected buildings. The algorithm successfully maintains topological consistency among primitives and avoids under- and over-segmentation with high efficiency. Second, a novel Voronoi-based primitive boundary extraction algorithm under constraints of outer and inner building boundaries is introduced in order to extract each primitive boundary. In this algorithm, the adjacent segmented primitive relationships among the various primitives are preserved by a subgraph of the Voronoi diagram so that the reconstructed neighbor primitives are seamlessly connected. Third, in order to refine the boundary shapes of primitives with irregular geometry, various criteria for making the boundary adjustments more effective are proposed. In this way, more regular 3-D buildings can be produced. Finally, the primitive boundary simplification criteria are formally introduced to generate compact 3-D building models. By using the simplification criteria, nonadjacency between neighbor primitives, intersection between boundaries, and self-intersections are, to a great extent, avoided. Numerous experimental results obtained using multiple data sets, including data from the cities of Toronto and Enschede as well as from the Niagara area, have shown that the proposed methodology has excellent performance and it can produce watertight 3-D po- yhedral building models.