issel.ac.be
ning.
ich as building lo-
great variability of
ints which have to
is successful under
‘ware environment,
rroneous 3D points
ess for urban scene
1 particular, Recon-
ative sample region
atively refined by a
.as is demonstrated
‘co correspondence
| in this paper max-
to perform the seg-
surface slope or al-
nto a user-friendly,
Lab. ReconLab was
diting environment
zation and manipu-
r more) images of
id level curve capa-
as texture mapping
detect and remove
‘interest. In the fi-
1 global parametric
a robust estimation
:ct of (possibly re-
e parameters. It is
eding segmentation
nce speed of the fit-
the resulting DTM.
:rimental results are
tions.
ACE PARTS INA
ODEL
from a DEM is the
he ground level. To
n scene is expected
to the road network
More formally, the
which the buildings
tained from an air-
Xf the urban scenery.
considered as being
surface in 3-space.
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
Typically for the ground level (or road network) is that it corre-
sponds to a connected differentiable surface part with low altitude
(when compared to other DEM points) and which extends over
the whole urban area represented in the DEM. Therefore, our
segmentation algorithm aims at grouping DEM points that are
expected to be samples from a connected differentiable surface
patch. Moreover, since the algorithm must be able to cope with
significant variations in slope and in altitude of the ground sur-
face, “connectivity”, rather than “difference in altitude”, should
be the crucial property for deciding whether neighbouring DEM
points belong to the same connected surface component or not.
This brings us to the following notions.
21 Definitions
Let r be positive real number. An r-path is a sequence of distinct
DEM points (Po, Pi,..., P.) for which each Pj is contained in
asphere with radius r centered at Pj 1 (i € (1,2,...,n]). Two
DEM points P? and Q are said to be r-connectable, if there exists
an r-path starting at P and ending at (). Furthermore, a subset
of a DEM is called r-connected, if any two DEM points in the
subset are r-connectable. And, finally, an r-connected subset of
a DEM is maximally r-connected, if it cannot be extended with
additional DEM points and still remain r-connected.
2.2 Preprocessing
The aim of the segmentation algorithm is to extract the maximally
r-connected subsets from a DEM. But some care has to be taken
when using these notions in practice. Indeed, if DEM points are
represented as triples (x, y, z) with (x, y) the coordinates of the
scene point in some geographical reference system and with z
being the altitude of that point in the scene, then, in an accu-
rate DEM of an urban area, the difference in altitude between
neighbouring DEM points will generally be much smaller than
their distance in geographical location. Before applying the seg-
mentation algorithm, the z-values of the DEM points are there-
fore multiplied with a positive constant p, in order to bring the
modus of these differences to the same order of magnitude as the
generic distances in point location. Mathematically speaking, this
means that a "sphere with radius r centered at P" in the defini-
tions above, in practice is an ellipsoid whose maximal horizontal
section is a circle with radius r and whose smallest (vertical) axis
is 2r/ p.
À second point of attention when dealing with real data is the
presence of noise. Roughly speaking, the nastiest effect of noise
in a DEM is that the altitude of a DEM point at a particular lo-
cation deviates from its true value. If not taken into account,
these arbitrary variations in altitude may cause an oversegmen-
tation of the DEM: i.e. DEM points originating from one smooth
connected surface patch may be split up in several small surface
parts which are not semantically meaningful. This problem is
commonly alleviated by smoothing the data before processing.
If one assumes that structural errors have been removed from
the DEM, then smoothing can be performed by a local averag-
ing operation. But, as connectivity is the main segmentation
criterion here, special care has to be taken that the borders of
maximally r-connected regions are well preserved. Put differ-
ently, the altitude of DEM points lying at the borders of a maxi-
mally r-connected region may not be altered significantly by the
smoothing process. Because r-connectivity boils down to be con-
tained in a sphere with radius r, inverse distance weighting within
such a sphere is adopted for smoothing. More precisely, for each
DEM point P, all points P; contained in a sphere with radius r
centered at P? are selected and their Euclidean distance d; to P
is computed. The smoothed z-value Z for P now is the weighted
average
S Q0 24
SS Un
In practice, « is usually set to 2. It is important to remark here
that in our algorithm the smoothed altitude Z does not replace
the original, unscaled z-value of the DEM point P, but is added
as a supplementary (fourth) coordinate. In this way, the origi-
nal altitude measurements remain available at any time (e.g. to
the DTM estimation algorithm to be applied later). Moreover, by
the previous definitions, DEM points belonging to different seg-
ments (i.e. points belonging to different maximally r-connected
regions) can never be r-connectable. Thus, even in the presence
of noise, points belonging to one segment cannot significantly
influence the z-values of points in another segment.
=
~
with. wu = (1 — =) ; (1)
A third, and possibly the most important, point of attention when
dealing with real data is the detection and removal of isolated
points. Isolated points may result from errors in the measuring
process (e.g. when using laser altimetry) or from errors in the
disparity estimate (e.g. when the DEM is constructed by stereo
correspondence from imagery), but they may also be due to cor-
rect measurements of points on building facades or originate from
vegetation. Isolated points may result in tiny segments; or even
worse, they may cause linkage of one surface patch to another,
thus creating an r-path connecting two different surface patches
and misleading the segmentation algorithm to create too large
segments. Figure | illustrates these effects. In accordance with
Figure 1: Left : Segmentation result without prior removal of
isolated points (2219 regions). Right : Segmentation result with
prior removal of isolated points (699 regions).
the previous definitions, an isolated point is a DEM point Q that
counts less than a threshold number n of other DEM points in a
sphere with radius r centered at Q. Isolated point removal can be
performed iteratively: First, scan the DEM for isolated points (de-
tection phase), then remove the detected isolated points (removal
phase), and repeat the process until no more isolated points are
found. Obviously, this procedure is very time consuming. But,
as our first aim is to extract (sufficient) ground level points from
the DEM to serve as input for the DTM surface estimation al-
gorithm (in contradistinction to creating an accurate and seman-
tically meaningful segmentation of the scene), there is no harm
in occasionally removing some non-isolated points as well. In
the experiments reported below, we therefore removed all points
contained in a sphere with radius r centered at the isolated points
detected in the first scan, and we did not iterate, in order to obtain
the segmentation result in real time.
2.3 The segmentation algorithm
After the preparatory steps, the actual segmentation is performed.
As mentioned before, a segment is defined here to be a maximally
r-connected subset of the DEM. Segmentation thus can easily
be performed iteratively by a region growing approach starting
from an (arbitrary) DEM point that is not assigned to a segment
