logo NCGeo

Acquisition of 3D topography. Automated 3D road and building reconstruction using airborne laser scanner data and topographic maps

Pog 74, Oude Elberink, Acquisition of 3D topography. Automated 3D road and building reconstruction using airborne laser scanner data and topographic maps

Sander Oude Elberink

Publications on Geodesy 74
Delft, 2010. 194 pagina's. ISBN: 978 90 6132 318 1.


Introduction and research goal

Our research covers the automation in acquiring three dimensional (3D) topographic objects. The research tasks focus on two specific objects: roads and buildings. These objects are of high importance in 3D city models as they are two major topographic classes in the urban environment.

Our activities are located between:

  • how topographic objects exist in reality;
  • how they are captured in the data, and
  • how they appear in a modelled/virtual world.

To accomplish an automated approach, existing 2D topographic maps are upgraded to 3D using airborne laser scanner data. 3D topography also includes multiple heights or even multiple objects on top of each other at a certain location.

The essence in the research activities on roads differs basically from those on buildings. For roads the focus is on reconstructing the edges’ height of the objects, whereas for buildings the challenge is to reconstruct the 3D polyhedral roof shape inside the building edges.

3D Road reconstruction

When examining 3D road objects, we can expect that multiple road objects cross at a certain location. An automated method for 3D modelling of complex highway interchanges is presented. Laser data and 2D topographic map data are combined in an innovative 3D reconstruction procedure. Complex situations demand for knowledge to guide the automatic reconstruction. This knowledge is used in the fusion procedure to constrain the topological and geometrical properties of the reconstructed 3D model. Laser data has been segmented and filtered before it is fused with map data. In the surface-growing algorithm combining map and laser points, the laser data is assigned to the corresponding road element. Elevations of map points are determined by least squares plane fitting through a selection of neighbouring laser points. Although results are shown using two specific data sources, the algorithm is designed to be capable of dealing with any polygon-based topographic map and any aerial laser scanner data set.

Quality analysis is essential for developing a reliable reconstruction process and for a proper use of 3D data. The quality of 3D reconstructed roads strongly depends on accuracy and type of input data and the reconstruction processing steps. We predict the precision of reconstructed map elevations by propagating errors in the input data through the processing steps. Besides this quality prediction, we test the reconstructed model against independent reference data. Differences between these two datasets are explained by the predicted uncertainty in the model. Map point heights can be reconstructed with an average precision of 10 to 15 cm, depending on the laser point configuration.

3D Building reconstruction

The building reconstruction task contains three main goals:

  • to select laser points belonging to building roofs,
  • to detect the roof structure of that building, and
  • to reconstruct the outlines of the roof.

We present a building reconstruction approach, which is based on a target graph matching algorithm as intermediate step to relate laser data with building models. Establishing this relation is important for adding building knowledge to the data. Our targets are topological representations of the most common roof structures which are stored in a database. Laser data is segmented into planar patches. The segments that are selected in the segment-in-polygon algorithm are considered initial roof segments. Topological relations between segments, in terms of intersection lines and height jumps, are represented in a building roof graph. These relations are labelled according to their geometry and that of the segments (e.g. same/opposite normal direction, convex/concave, tilted/horizontal). This graph is matched with the graphs from the target database. Matching results describe which target objects appear topologically in the data.

Our target based graph matching algorithm supports the first two goals. The matching algorithm performs a filtering task: data features that topologically correspond with common roof structures are considered to be part of the roof structure of that building. These data features will be transferred to our automated building reconstruction, where the outlines of the roof faces have to be reconstructed. Segments and intersection lines that do not fit to an existing target roof topology will be removed from the further automated reconstruction approach. The reconstruction algorithm covers the third main goal of our building reconstruction task.

For the geometric reconstruction, we present two approaches that vary in the amount of information they take from the data.

The first, more data driven approach starts with laser data features that have been matched with target models. In general, the matched intersection lines represent the interior of the roof structure, so the task is to find an appropriate solution for the remaining roof edges, e.g. eaves and gutters. Map data is used for selection of roof segments and is taken as location for walls. Therefore we need to split up map polygons in order to build walls that distinguish various height levels, e.g. at step edge locations.

The second, more model driven approach reconstructs parameterised building models. This approach relies more on geometric assumptions, such as roof symmetry, but the models can be refined if the data deviates significantly from the model. The target information includes the details on how these deviations are determined and on the thresholds to decide what is significant or not.

We present results of 3D reconstructed models, including several quality checks. These quality measures describe the completeness of the match results plus the correctness of assumptions to the roof outline. About 20% of the buildings are affected by segments that did not completely match with the target graphs. In a few of these cases, this is correct because the segment is not representing a roof face. However, in about 40% of these cases, a neighbouring segment that would complete a target match is missing. Adapting processing parameters, such as minimum segment size, may improve the result but it may also disturb other topological relations. Setting the parameters is therefore an important task for the operator. Specially, parameters that define the segmentation algorithm are crucial as the segment is the key data feature in our building reconstruction algorithm.

In order to improve our matching algorithm, the likelihood of relations between segments could be included in the attribute list of edges in the roof topology graph. At the moment only information on the geometric appearance of the intersection line is given as attribute value to the corresponding graph edge. Future work includes defining likelihood functions for graph edges and analysing the effect of likelihood attributes.


  • Part I: Introduction to acquisition of 3D topography  1
  • Part II: 3D Roads  25
  • Part III: 3D Buildings  65
  • Part IV: Conclusions and recommendations  153
  • List of publications  159
  • Bibliography  160
  • Summary  165
  • Samenvatting  168
  • ITC Dissertation List  172
  • Curriculum Vitae  173


Introductie en doel van het onderzoek

Het promotieonderzoek behandelt de geautomatiseerde inwinning van drie dimensionale (3D) topografische objecten. We richten ons daarbij op de 3D reconstructie van wegen en gebouwen. Deze objecten zijn belangrijke elementen in digitale 3D modellen.

De onderzoeksactiviteiten verbinden drie versies van topografische objecten met elkaar:

  • hoe de objecten er in werkelijkheid uitzien;
  • hoe ze gerepresenteerd worden in de data, en
  • hoe ze gemodelleerd moeten worden in een 3D model.

Om een geautomatiseerde inwinning mogelijk te maken, is uitgegaan van bestaande 2D topografische bestanden. Deze worden geconverteerd naar 3D door laseraltimetriegegevens toe te voegen. In 3D modellen kunnen meerdere hoogtes op dezelfde locatie voorkomen en er kunnen zelfs meerdere objecten boven elkaar liggen.

Het onderliggende principe om van 2D wegen naar 3D wegen te komen, is wezenlijk anders dan het principe om 3D gebouwen uit 2D gebouwen te verkrijgen. Dat komt omdat voor wegen het doel is om de zijkanten van de weg in 3D vast te leggen, en de weg zelf als een (getrianguleerd) vlak te beschouwen tussen de 3D zijkanten. Voor 3D gebouwen is het juist van belang te kijken naar wat de 3D vorm is van dakdelen binnen de omlijning (muren) van het gebouw.

3D wegen

Kijkend naar de aansprekende 3D situaties voor wegobjecten, dan komen we al snel uit bij viaducten en complexere knooppunten. Op die locaties bevinden zich meerdere wegdelen boven elkaar. Ons onderzoek richt zich op deze situaties. Om een goede combinatie van laseraltimetriegegevens en 2D topografie mogelijk te maken, is gekeken naar algemene kennis over hoe de weg in werkelijkheid verloopt. Deze kennis is geïntegreerd in onze automatische reconstructiemethode. Een voorbeeld van deze kennis is dat een weg een glad, niet abrupt, hoogteverloop kent. Daarom zijn kleine objecten uit de laser data gefilterd (bijvoorbeeld data op auto’s en verkeersmeubilair) om zo alleen de laser data van de wegvlak over te houden. Aan de hand van deze punten kan beredeneerd worden hoe de weg lokaal verloopt. Deze gefilterde data wordt samengevoegd met 2D topografische objecten op basis van de horizontale en de verticale positie. Dit laatste is noodzakelijk om een goede samenvoeging te krijgen op de plekken waar wegen elkaar kruizen. Laserdata op het bovenliggende wegvlak, dient immers niet samengevoegd te worden met het onderliggende wegvlak. De hoogte van de zijkanten van de weg wordt verkregen door een mathematisch vlak te berekenen door de laserpunten in de buurt van die zijkant. De hoogte van het vlak op de positie van de zijkant van de weg wordt vastgelegd als 3D positie.

Een goede kwaliteitsbeschrijving is belangrijk, zowel tijdens de opbouw van het algoritme als tijdens het gebruik van de 3D data. De kwaliteit van de berekende 3D posities is afhankelijk van de input data en de verwerkingsstappen. We berekenen de precisie van de gereconstrueerde hoogtes door middel van de foutenvoortplanting van de precisie van de input data. Dit wordt de geschatte precisie genoemd. Naast deze schatting, zijn de hoogtes ook getoetst aan de hand van referentiemetingen. Verschillen tussen de referentiemetingen en de gereconstrueerde hoogtes kunnen worden verklaard aan de hand van de geschatte precisie van ons model. Afhankelijk van de configuratie van de laser punten ligt de gemiddelde precisie van de gereconstrueerde hoogte van de zijkanten van de weg tussen de 10 en 15 centimeter.

3D gebouwen

De 3D gebouwreconstructie bestaat uit drie hoofdtaken:

  • selecteren van laser data die op dakvlakken liggen,
  • detecteren van dakvormen van elk gebouw, en
  • reconstrueren van de dakomlijning.

Onze gebouwreconstructie is gebaseerd op een zogenaamde 'target graph matching' algoritme. Dat betekent dat we kenmerken die in de laserdata gevonden kunnen worden, gerelateerd (gematched) worden met gebouwmodellen (targets) uit een database. Deze relatie is belangrijk om kennis over gebouwen toe te voegen aan de corresponderende laserdata. De targets zijn topologische beschrijvingen van de meest voorkomende dakvormen, die worden vastgelegd in een graaf. Elke graaf bestaat uit knopen (dakvlakken) en lijnen. Elke lijn beschrijft een relatie (bijvoorbeeld snijlijn) tussen twee dakvlakken. De laserdata wordt gesegmenteerd. Ieder segment bestaat uit laserpunten die in een bepaald 3D vlak liggen. De segmenten die zich (grotendeels) binnen een gebouwpolygoon bevinden worden geselecteerd als voorlopig daksegment. De daksegmenten vormen samen met de snijlijnen en hoogtesprongen tussen twee naburige segmenten, een graaf van dakvlakken. Deze graaf bestaat dus uit knopen (de segmenten) en lijnen (de relatie tussen twee segmenten). De lijnen zijn gelabeld aan de hand van de geometrie van de relatie tussen twee segmenten en van de segmenten zelf. Bijvoorbeeld krijgen alle horizontale snijlijnen tussen daksegmenten met tegengestelde richting hetzelfde label. Deze graaf wordt gematchd met de topologische beschrijvingen van de meest voorkomende dakvormen, ofwel de targetgraaf. Het resultaat van het matchingalgoritme beschrijft welke dakvormen voorkomen en welke data daaraan gerelateerd is.

De matching is van belang voor de uitvoering van de eerste twee hoofdtaken. Ten eerste worden segmenten die niet tot een bepaald dakmodel horen, eruit gefilterd. De overgebleven segmenten hebben allen een bepaalde relatie met een bestaand dakmodel. Deze segmenten gaan naar de automatische dakreconstructiemodule, waar de omlijning van elk daksegment bepaald wordt. Dit wordt de geometrische reconstructie van de omlijning van gebouwdaken genoemd. De geometrische reconstructie is het derde deel van de gebouwreconstructie en hebben we op twee manieren bepaald.

De eerste, meer datagestuurde aanpak combineert alle segmenten en snijlijnen die gematched zijn met één of meerdere targetmodellen. Over het algemeen representeren de snijlijnen tussen twee daken de interne structuur van het dak (bijvoorbeeld de noklijn), dus de taak is om de buitenkant van het dak (bijvoorbeeld de goot) te reconstrueren. De gebouwpolygonen uit de 2D topografische kaart worden gebruikt voor de locatie van de muren van het gebouw. De polygonen worden gesplitst als er een hoogtesprong binnen het gebouw optreedt om op die locatie een muur neer te kunnen zetten.

De tweede, meer modelgestuurde aanpak gaat uit van een geparameteriseerd model van de target die gematched zijn met de data. Deze aanpak is meer gebaseerd op geometrische aannames, zoals de aanname dat een dak symmetrisch is, maar kan worden aangepast als de data daar aanleiding toe geeft. Het targetmodel bevat informatie over de wijze waarop omgegaan moet worden met verschillen tussen data en een gereconstrueerd model.

In dit proefschrift beschrijven wij het opbouwproces en de resultaten van 3D gebouwreconstructies. Deze modellen worden ook voorzien een kwaliteitsbeschrijving. Deze beschrijven de volledigheid van het matchingsproces en de kwaliteit van de aannames over de omlijning van de daken. Ongeveer 20% van de gebouwen bezit een segment dat niet gerelateerd kan worden aan een targetmodel. We noemen deze segmenten onderdeel van een niet volledige match. In enkele van deze gevallen is dat een goed teken, omdat dat segment daadwerkelijk geen deel uitmaakt van een dakvorm. Echter, in ongeveer 40% van deze gevallen is een gebrek aan een ander segment, de oorzaak van de niet volledige match. Aanpassen van de verwerkingsparameters, bijvoorbeeld de segmentatieparameters, zouden de resultaten kunnen verbeteren, maar kan voor andere situaties de resultaten verslechteren. Daarom is het van belang om de goede verwerkingsparameters vast te stellen. Vooral de segmentatieparameters zijn belangrijk omdat elk segment behandeld wordt als dakvlak en daarom als belangrijk element fungeert in de gehele gebouwreconstructie.

Een mogelijkheid om ons matchingalgoritme te verbeteren is het toevoegen van waarschijnlijkheden aan de elementen in het target model. Op dit moment wordt alleen de geometrische informatie van een snijlijn vastgelegd als label van de bijbehorende lijn in een graaf. Toekomstig onderzoek bevat het vaststellen van waarschijnlijkheden van snijlijnen en het analyseren van het effect van deze waarschijnlijkheden op het matchingsresultaat en op het uiteindelijke 3D gebouwmodel.

Ga naar boven
JSN Boot template designed by JoomlaShine.com