anbul 2004
ike angles
nodels for
entrate on
lines. The
pect ratio.
utline and
are often
jc models
decide on
ind extract
hed to one
ter 4.
|. A subset
1s clipped.
le appears
the same
inge value
86) is then
a table of
"the range
short seg-
. short de-
mplemen-
ge images
daption is
/ direcuon
»en sorted
ent. Pixels
(ling. For
e gradient
scted wilh
Ty region.
re clipped
by finding
dpoints of
International Archives of the Photogrammetry, Remote Sensin
the extracted lines. Then, a plane representing the build-
ing's facade is found. All 3D segments are projected into
that plane. This way, distortion of facade structures can be
eliminated.
4 CONSTRAINED SEARCH
4.1 Principle
Constrained Search is a technique for matching models to
data devised by (Grimson et al., 1990). The principle is to
build an interpretation tree that associates model features
with data features (see figure 3). In order to avoid search
explosion by testing every possible pairing of model fea-
tures and data features, constraints are used to prune the
interpretation tree. The goal is to use these constraints
to rule out inconsistent matches at an early stage of the
search. Every subnode of a pruned node will not be visited
during the search process. therefore complexity of the tree
Is reduced.
m
d, i
d; m, m, m, m, *m m; my m *
d,
Figure 3: Part of interpretation tree.
Constraints can be unary or binary. Unary constraints de-
fine consistency of pairings between one model and one
data feature, whereas binary constraints define consistency
between pairings of two model features and two data fea-
tures. Definitions for the constraints used in our system
will be given later.
Overall consistency of the match is verified by finding a
transformation that transforms the model features into data
feature space (pose estimation) and calculating the devia-
tion. If the deviation is below a set threshold, the match is
considered consistent and therefore accepted.
The depth of the tree is defined by the number of data fea-
tures, whereas the number of children of each node corre-
sponds to the number of model features. Null associations
are used to account for data features which are not associ-
ated with a model feature.
4.2 Application
In our system, model segments are associated with data
segments. We need to determine constraints which are
meaningful in the context of this task. As stated in chapter
1081
g and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
3, the structures we are looking for have certain geomet-
ric properties. These can be interpreted as constraints. In
particular, we are going to make use of orthogonality and
parallelism. These can be phrased in the form of an an-
gle constraint and a distance constraint. Because we don't
use absolute values for angles and distances in the range
image, constraints are binary and check that relations be-
tween model edges hold for relations between data edges.
As the models described earlier contain the right angles
and parallel lines that can be found when examining facade
structures, these are exactly the conditions that hold true
for the data edges which these models are matched to.
So, the following binary geometric constraints are used for
pruning the interpretation tree:
I. Angle Constraint: This constraint compares the angle
between two models segments to the angle between
two data segments. A user-defined deviation is al-
lowed. Formally it looks like this:
Oi;
be the angle between the edge normals of the data
edges i and |,
Org
be the angle between the edge normals of the model
edges p and q. Then
angle_constraint(i, j, p,q) = true
iff 6j; € 1 0 mue Oo + €4] (D
to
. Distance Constraint: This constraint compares the
distance between two model segments to the distance
between two data segments. Obviously, this con-
straint is not scale invariant. Maximum and minimum
distance between the endpoints of one edge to the line
through the other edge are calculated for both edges.
di i. di
be the smallest distance and the biggest distance be-
tween data edges, whereas
Dy: Din
be the smallest and the biggest distance between
model edges. À certain deviation is allowed.
distance_constraint(i, j, p,q) = true
=
iff druscnulci Dt Q0)
The distance constraint is of particular importance because
it provides the most effective pruning of our interpretation
tree without discarding correct solutions.
Unary constraints are not used because consistency checks
can be made only by relative comparisons between model
and data segments, not absolute comparisons. Constraints
that consider length are not used because generally the
