Building Reconstruction by Target Based Graph Matching on Incomplete Laser Data: Analysis and Limitations

Sander Oude Elberink, George VosselmanSensors 2009 · DOI

TL;DR

This paper introduces a target-based graph matching approach for automated building reconstruction from incomplete airborne laser scanner (ALS) data. It effectively identifies and reconstructs complete building structures while also flagging areas with incomplete data or model mismatches, paving the way for more robust 3D city modeling.

What Problem Does This Paper Address?

The increasing density of airborne laser scanner (ALS) data has enabled more detailed 3D city models. However, fully automating the reconstruction of complex building structures, particularly roofs, remains a significant challenge. A primary obstacle is the inherent incompleteness of ALS data, caused by factors like occlusions, non-reflecting surfaces, or missing laser pulse returns. This missing data can lead to incorrect assumptions in automated algorithms, resulting in incomplete or inaccurate reconstructions. The paper aims to address this by developing a method that can handle both complete and incomplete laser data, and importantly, can identify and analyze the reasons for reconstruction failures.

Methods

The core of the proposed method is a target-based graph matching algorithm. This approach integrates model-driven and data-driven techniques.

  1. Data Processing: ALS point clouds are first segmented into planar patches representing roof faces. These segments are then used to build a roof topology graph, where segments are nodes and their relationships (e.g., intersection lines, step edges) are labeled edges.
  2. Target Database: A database of common roof shapes, represented as target graphs, is maintained. These target graphs encode the expected topological relationships between roof faces.
  3. Graph Matching: The algorithm matches the roof topology graph derived from the ALS data against the target graphs in the database. This matching is labeled, meaning it considers the geometric attributes of the relationships (edges) between segments, not just their existence.
  4. Reconstruction & Analysis:
    • Complete Matches: Segments and their topological relations that fully correspond to a target graph are accepted and used for automated reconstruction of roof faces.
  5. Incomplete Matches: Segments and relations that do not form a complete match are flagged. These "leftover" segments are analyzed to understand the reasons for the incomplete match.

Datasets

The paper analyzes four datasets from two cities in the Netherlands. These datasets vary in building structure, ranging from upper-class buildings to normal suburban areas. No new benchmark datasets are introduced.

Key Insights and Ideas

  • Handling Incompleteness is Crucial: The paper strongly emphasizes that real-world ALS data is rarely perfect. A robust reconstruction method must be able to cope with missing data and identify where it fails.
  • Topology as the Bridge: Using topological relationships (how roof faces connect) as the primary matching criterion between data and models is a powerful way to overcome some data quality issues. It allows for matching even if precise geometric measurements are slightly off due to data gaps.
  • Analyzing Failures is as Important as Successes: By categorizing the reasons for incomplete matches (e.g., non-building segments, missing neighbors, over-segmentation, limitations in target models), the authors provide valuable insights into the limitations of current methods and potential areas for improvement.
  • Target Models are Not Always Sufficient: The analysis reveals that limitations in the target model database itself can lead to incomplete matches, highlighting the need for comprehensive and representative target libraries.

Key Results

  • The proposed target-based graph matching approach can reconstruct building roofs from ALS data, handling both complete and incomplete matches.
  • The method automatically detects segments that do not fit the reconstructed roofs, providing quality indicators.
  • Analysis of incomplete matches revealed that approximately 5% of roof segments (affecting 19% of buildings) did not form a complete match.
  • The primary reasons for incomplete matches were:
  • Absence of neighboring segments (39%)
    • Disturbance of topological relations due to over-segmentation (17%)
    • Limitations of the target models (e.g., missing roof shapes in the database) (20%)
    • Non-building segments incorrectly identified as roof segments (12%)

Limitations and Future Work

  • Limitations:
    • The current approach relies on a predefined set of target models. If a building's roof shape is not present in the database, it will not be reconstructed.
  • Over-segmentation can distort topological relations, leading to matching failures.
  • Data gaps and non-reflecting surfaces can lead to missing segments and thus incomplete matches.
  • Future Work:
    • Likelihood Functions: Incorporating likelihood estimators for the existence of topological relations between segments. This could help the algorithm make more informed decisions, especially when dealing with ambiguous data or potential model mismatches (as illustrated with the five-sided hip roof example).
  • Extending Target Database: Adding new target models to the database to cover a wider variety of roof shapes.
  • Adaptive Parameter Tuning: Developing automated iterative processes to adapt segmentation parameters locally for buildings affected by leftover segments, aiming to optimize results based on user-defined quality parameters.
  • Semi-automatic Processes: Investigating human intervention at various stages to improve results where automated assumptions fail, particularly for segmentation and topological relation verification.

Summary updated

Abstract

With the increasing point densities provided by airborne laser scanner (ALS) data the requirements on derived products also increase. One major application of ALS data is to provide input for 3D city models. Modeling of roof faces, (3D) road and terrain surfaces can partially be done in an automated manner, although many such approaches are still in a development stage. Problems in automatic building reconstruction lie in the dynamic area between assumptions and reality. Not every object in the data appears as the algorithm expects. Challenges are to detect areas that cannot be reconstructed automatically. This paper describes our contribution to the field of building reconstruction by proposing a target based graph matching approach that can handle both complete and incomplete laser data. Match results describe which target objects appear topologically in the data. Complete match results can be reconstructed in an automated manner. Quality parameters store information on how the model fits to the input data and which data has not been used. Areas where laser data only partly matches with target objects are detected automatically. Four datasets are analyzed in order to describe the quality of the automatically reconstructed roofs, and to point out the reasons why segments are left out from the automatic reconstruction. The reasons why these areas are left out include lack of data information and limitations of our initial target objects. Potential improvement to our approach is to include likelihood functions to the existence of topological relations.
BibTeX
@inproceedings{elberink2009building,
  author = {Sander Oude Elberink and George Vosselman},
  title = {{Building Reconstruction by Target Based Graph Matching on Incomplete Laser Data: Analysis and Limitations}},
  booktitle = {Sensors},
  year = {2009},
  doi = {10.3390/s90806101},
}
Figure