International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
into the same category as those two to a single range im-
age.
In (Sester and Fórstner, 1989), the concept of fitting
generic models, described by a set of parameters, is pre-
sented. In this paper. emphasis is put on dealing with un-
certainty.
There is also an extensive repertoire of employing search
algorithms for matching problems. In (Rottensteiner,
2001), we find a classification of matching techniques
which is based on (Gülch, 1994). According to this, there
are three main branches of matching algorithms:
1. Raster based matching: Correspondences of images
or image patches are found by comparing grey levels
or function of grey levels.
N
. Feature based matching: Features are extracted from
images and mapping occurs between those features.
This means basically finding matches between the ge-
ometric description of objects found in different im-
ages.
9]
. Relational matching (Vosselman, 1992): Here. topo-
logical relations of features found in images are
matched. This is achieved by creating feature adja-
cency graphs first and then searching for matches be-
tween those graphs.
Building interpretation trees is a technique often used to
establish mappings between the items in the respective
search space. Depending on whether one wants to find
some matches or all matches between model and data pix-
els, features or graph nodes, a partial or exhaustive search
needs to be conducted.
In our case, we want to match geometric features doing an
exhaustive search to find all relevant structures in a build-
ing's facade. To achieve this, we use a constrained search
approach which is described in detail later. Several ob-
ject recognition systems were successfully implemented
using this technique. Earlier work includes (Grimson et al.,
1990), (Flynn and Jain, 1991) and (Walker, 1999), where
fuzzy rules are used to allow for uncertainty in the mea-
surement of the constraint parameters.
3 SEGMENTATION
We are looking for structures in façades, like windows,
doors and ornaments, that have the following properties:
|. They occur repeatedly and are arranged in a certain
way, for example in rows and columns or other regu-
lar fashions.
LD
. They consist of features that represent discontinuities,
i. €. edges.
3. They have the same size.
1080
4. They have identical geometric properties, like angles
and distances between edges.
Starting from these prerequisites, we construct models for
the facade structures. For the moment. we concentrate on
windows. These models consist so far of straight lines. The
simplest model is a rectangle with variable aspect ratio.
More complex models have a rectangle as the outline and
also contain interior structure like grids which are often
found in windows. Figure 1 shows those generic models
used.
L.
Figure 1: Models for windows.
To find instances of these models, we have to decide on
a suitable representation of the laser scan data and extract
straight lines. Those straight lines are then matched to one
of the models using search, as described in chapter 4.
The range image of a terrestrial laser scan is used. A subset
of the point cloud containing a building's facade is clipped.
The range image is modified so that the facade appears
parallel to the image plane, i.e. points having the same
distance from the facade are assigned the same range value
(see figure 2).
Range Image Plane
[
Projected Rays
Figure 2: Modified range image.
Burns' line extracting algorithm (Burns et al., 1986) is then
used to segment the range image. The result is a table of
straight segments representing breaks in depth of the range
image. Segments are filtered for length as very short seg-
ments are usually insignificant. We now give a short de-
scription of how Burns' algorithm works. Our implemen-
tation for the application of this algorithm on range images
is identical to the one for ordinary images, no adaption is
necessary.
For the line extraction, gradient images in x and y direction
are calculated for the range image. Pixels are then sorted
into overlapping buckets according to their gradient. Pixels
in the same bucket are grouped using region labelling. For
each region, a plane is fitted which represents the gradient
slope in that region. This plane is then intersected with
a plane representing the average gradient in every region.
This way, straight lines are obtained. The lines are clipped
by the boundaries of their support regions.
Those 2D segments can be transformed into 3D by finding
points in the point cloud corresponding to the endpoints of
Intern
the e:
Ing's
that p
elimit
4 C
4.1
Const
data €
build
with «
explo
tures
interp
to rul
searcl
durins
1s redi
d,
Consti
fine «
data fe
betwe«
tures.
will be
Overal
transfc
feature
tion. Il
consid
The de
tures,
sponds
are use
ated w;
42 A
In our
segmer
meanin
