ibul 2004
(6)
(7)
(8)
ly useful
tion and
on least
ations 1s
transfor-
ix form:
(9)
tten as
(10)
is calcu-
(11)
del so far
automati-
s required
ng it with
d into the
ng, an in-
segments
used. At
itio of the
tched ac-
culated to
Its present
ctangle is
. data seg-
rnaltively,
lis way, à
which we
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
5.2 Search
The model derived during initialization is now searched
for in the whole edge image or a user-defined subsection
thereof. It can be freely rotated or translated, but the aspect
ratio is kept constant, and only a limited amount of scaling
is allowed, as we will see later.
An edge image can consist of several hundred edges, so
pruning of the interpretation tree is inevitable. The an-
gle and distance constraint defined earlier are used for
that. The distance constraint also rules out solutions which
would require scaling of the model beyond the bounds of
the constraint, which accounts for the limited amount of
scaling.
Because there are usually many edges in the facade of a
building and the number of edges determines the depth of
the tree, careful application of constraints is necessary to
avoid search explosion. It is possible to divide the search
space and search several small trees instead of one big one.
For this, the edge image is tiled after initialization. Tiles
are twice as big as the initialized model, and tiling takes
place in a way that tiles overlap halfway so every correct
solution is contained in at least one complete tile, although
it can also be contained partially in several other tiles.
Effectively, tiling means enforcing the distance constraint
in a way that two data segments can't be part of the same
match if their distance is more than twice the size of the
model. For the search inside the individual tiles, the dis-
tance constraint can now be relaxed without causing a
search explosion because the number of edges inside a tile
is usually small by comparison to the total number of edges
in a building facade.
It is also possible to filter edges after initialization and be-
fore further search. An angle criterion can be used because
after the first fit it is known which angles edges have to be
suitable candidates for more matches.
Another way to reduce complexity during search and also
eliminate finding the same solution several times is to
delete data edges from the search space after matching
them successfully. If a real edge consists of several seg-
mented edges, more than one match could be found which
essentially represents the same building structure. In fact,
only one solution is of interest, so the rest can be safely
omitted. Apart from this, due to the rotational symmetry of
models, a solution is found multiple times, once for each
orientation of the model. If data edges are deleted after
finding the first solution, this can’t happen anymore.
6 EXPERIMENTAL RESULTS
6.1 Tests
We testet our procedure on various single laser scans of
buildings. This section presents the results for the Opera
House in Hannover. First, the range image is calculated
and line extraction is applied. The edge image is shown in
1083
figure 4. A section of the edge image showing a single win-
dow was selected and used for initialization of a rectangle
(figure 5).
Figure 4: Edge image.
A small frame is defined by the user for an initial estimate
of one window. A generic rectangle is fitted and stretched
according to the window's proportions (see figure 5). No
constraints are used.
Figure 5: Initialized model.
After successful initialization, multiple occurrences of this
window are found by matching the rectangle to the edges
inside a user-defined bigger frame, which can contain the
whole façade or a particularly interesting part thereof (see
figure 6). Full automation for this step is aimed for, so far
the user also needs to define deviations for the constraints
so a meaningful fit is achieved.
In figure 6, 1t can be seen that windows of similar size and
shape as the initial window are successfully found. Some
of the windows are found multiple times. This is due to
the fact that there are many small edges for each window
and the initial rectangle can be successfully fitted into sev-
eral different subsets of them. To remedy this problem, one
could apply a more complex window model, or otherwise
use a filtering postprocessing step which eliminates over-
lapping matches. No meaningful matches are found in the
central part of the building.
Figure 6: Correspondences found.
