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 pages. ISBN: 978 90 6132 318 1. € 13.00
Summary
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:
1. how topographic objects exist in reality;
2. how they are captured in the data, and
3. 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:
1. to select laser points belonging to building roofs,
2. to detect the roof structure of that building, and
3. 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.
Contents
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
Samenvatting
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:
1. hoe de objecten er in werkelijkheid uitzien;
2. hoe ze gerepresenteerd worden in de data, en
3. 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:
1. selecteren van laser data die op dakvlakken liggen,
2. detecteren van dakvormen van elk gebouw, en
3. 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.