A SOFTWARE SYSTEM FOR EFFICIENT DEM SEGMENTATION
AND DTM ESTIMATION IN COMPLEX URBAN AREAS
I. Van de Woestyne *, M. Jordan * T. Moons *, M. Cord 5
a Katholieke Universiteit Brussel, 1081 Brussels, Belgium, {/gnace.VandeWoestyne, Theo.Moons } @kubrussel.ac.be
^ ETIS, UMR CNRS 8051, 95014 Cergy-Pontoise Cedex, France, (cord, jordan (Qensea.fr
KEY WORDS: DEM/DTM, segmentation, urban, semi-automation, three-dimensional, aerial, imagery, laser scanning.
ABSTRACT:
Digital Elevation Models (DEMs) are a central information source for scene analysis, including specific tasks such as building lo-
calization and reconstruction. Whatever application is envisaged, DEM segmentation is a critical step, due to the great variability of
landscapes and above-ground structures in urban areas. Moreover, a DEM may contain erroneous isolated 3D points which have to
be identified before any interpretation process can start. Designing an automatic DEM segmentation method that is successful under
all circumstances can hardly be envisaged. To facilitate the segmentation process, a user-friendly, interactive software environment,
called ReconLab, has been developed. Its 3D viewing and editing capabilities allow to easily detect and remove erroneous 3D points
from the initial data, to efficiently smooth the DEM and perform the segmentation in real time. ReconLab's usefulness for urban scene
interpretation is demonstrated by applying it to the estimation of a Digital Terrain Model (DTM) from the DEM. In particular, Recon-
Lab is used to perform a fast, semi-automatic segmentation of the DEM and to provide a significant and representative sample region
consisting of ground points. These points are then used to initialize a parametric model for the terrain, which is iteratively refined by a
robust algorithm. The preprocessing by ReconLab reduces computation time by a factor 3, without loss of accuracy, as is demonstrated
by experiments on synthetic data and on real world DEMs obtained by airborne laser altimetry as well as by stereo correspondence
from imagery.
1 INTRODUCTION
Many building reconstruction and scene interpretation systems
use a Digital Elevation Model (DEM) — either generated from
imagery by stereo or multiview correspondence or obtained from
laser altimetry — as an essential information source. Whatever
application is envisaged — e.g. orthophoto production, build-
ing reconstruction, (3D) road mapping, scene classification (such
as building type, road type, vegetation type, etc.) — a critical
step often is the segmentation of the DEM in regions of inter-
est. Building reconstruction schemes usually use cadastre maps
or manual procedures of some sort for building region delineation
[see e.g. (Haala et al, 1997, Jibrini et al., 2000, Moons ef al.,
1998, Roux & Maitre, 1997, Vosselman & Suveg, 2001)]. Map-
ping and scene classification schemes, on the other hand, often
rely on a ground — above ground separation of the DEM points
[see e.g. (Baillard ef al., 1997, Collins ef al., 1995, Cord et al.,
2001, Paparoditis e al., 2001)]. For dense urban areas complicat-
ing factors for this separation task are the relatively low number
of ground points in comparison to above ground structures and —
for a great number of towns in Europe — significant variations in
terrain slope, in which case altitude is no longer an absolute in-
dication for ground or above ground structures. Moreover, the
identification of erroneous 3D data points in the DEM always re-
mains an important point of attention.
In this paper a semi-automatic procedure is presented to effi-
ciently extract a Digital Terrain Model (DTM) from a DEM of
urban areas with significant variations in terrain slope and alti-
tude. The line of reasoning consists of segmenting the DEM
into connected surface regions, identifying the regions with the
largest extent, verifying whether they belong to the ground level,
and robustly fitting a parametric surface model to the ground
points. Popular segmentation methods are based on watershed
types of algorithm. Such an approach, however, may yield poor
results when considerable variation in terrain slope and altitude
is present in the scene. The method presented in this paper max-
imally exploits the proximity of DEM points to perform the seg-
mentation task, thus being less sensitive to surface slope or al-
titude. The segmentation algorithm is built into a user-friendly,
multi-platform software system, called ReconLab. ReconLab was
initially designed to be a 3D modeling and editing environment
which allows easy and simultaneous visualization and manipu-
lation of 3D data in connection with (one or more) images of
the scene. The automatic altitude coloring and level curve capa-
bilities of ReconLab on the 3D data as well as texture mapping
from the images make it particularly easy to detect and remove
erroneous segment parts from the regions of interest. In the fi-
nal stage, a DTM is constructed by fitting a global parametric
surface model to the ground segments using a robust estimation
procedure which iteratively reduces the effect of (possibly re-
maining) above ground points on the surface parameters. It is
demonstrated on real world data that the preceding segmentation
of the DEM seriously improves the convergence speed of the fit-
ting algorithm, without loss of accuracy on the resulting DTM.
The different parts of the method and the experimental results are
described in more detail in the subsequent sections.
2 IDENTIFYING CONNECTED SURFACE PARTS INA
DIGITAL ELEVATION MODEL
The first step in the construction of a DTM from a DEM is the
identification of DEM points that belong to the ground level. To
a large extent the ground surface in an urban scene is expected
to be formed by DEM points corresponding to the road network
and to open spaces such as parking lots, etc.. More formally, the
terrain may be interpreted as a surface from which the buildings
protrude. A DEM then is a sampling (as obtained from an air-
borne laser scanning e.g.) of the top surfaces of the urban scenery.
Put differently, to some extent a DEM can be considered as being
a discretization of a piecewise differentiable surface in 3-space
International Arcl
eh
Typically for the
sponds to a conne:
(when compared
the whole urban
segmentation alg
expected to be sa
patch. Moreover,
significant variati
face, “connectivit
be the crucial pro
points belong to t
This brings us to |
2.1 Definitions
Let r be positive 1
DEM points (Po,
a sphere with radi
DEM points P an
an r-path starting
of a DEM is call
subset are r-conn
a DEM is maxime
additional DEM p
22 Preprocessi
The aim of the seg
r-connected subs:
when using these
represented as tri]
scene point in so
being the altitude
rate DEM of an
neighbouring DE
their distance in g
mentation algoritl
fore multiplied w
modus of these di
generic distances |
means that a “spk
tions above, in pr:
section is a circle
is 2r/ p.
À second point ©
presence of noise
in a DEM is that
cation deviates fi
these arbitrary va
tation of the DEIV
connected surface
parts which are r
commonly allevi:
If one assumes t|
the DEM, then st
ing operation. E
criterion here, sp
maximally r-coni
ently, the altitude
mally 7-connecte:
smoothing proces
tained in a sphere
such a sphere is a
DEM point P, al
centered at P are
is computed. The