Eckart Michaelsen
less than 4 for each roof, because a roof is formed off a pair of rectangles and nearly all four pairings will fit the
model. In the worst case — and praxis is not too far away from that — some 4 alternatives for each house in similar
positions and parameter settings mean 16 house pairs, 64 triples e. c. In a scene like Fig. 2 this will lead to millions
or billions of alternatives that have to be evaluated and compared. Grouping tends to be exponential with its non-
locality. Just keep in mind, that it is not even trivial to pick out and unify those alternatives, that actually refer to
the same features in the same model roles but put together in a different search sequence. Mathematically with
respect to computational complexity two main types of such grouping are to be distinguished - cyclical and cycle
free part-of hierarchies. The former is NP and the latter P (see [Michaelsen, 1998] for a syntactic setting of the
problem). This does not mean, that cycle free hierarchies pose no problem in computational effort, because in non-
trivial cases the algebraic degree of the bounding polynome will be rather high, and there will be intractability in
the presence of large data sets. So everybody makes some decision or pruning at some stage of the search. It is also
possible to identify very close alternatives as not competing but as co-operative hints for the presence of the same
object. Then these should be clustered into a mean representative instead of viewed as competitors. In the example
we decided to do this on the ‘house level’. But we do not know if that will be wise for all data.
3. Discriminate Power of geometric Relations: We already sketched this problem in Sec. 2.1. If a recognition
method based of geometric modelling and thus a geometric relation between features is applied to data that the
designer has not jet seen, it may fail because the relations may suddenly also hold for many objects whose presence
we already stated under problem 2.
9. Capturing functionality by Geometry: For many Applications the function of an object is the desired property of
interest for its classification e.g. a building may be used for housing people or storing things or administration A
vehicle may be used for military or civil purposes. It is questionable how such properties may be recognisable from
geometric properties such as adjacency, height and other geometric measurements.
10. Model Acquisition: Success and failure of such model-based methods is presumably more dependent on the skill
of the person who made the model than on the method or shell used in the recognition process. Who is going to do
that in a desired application? Will there be enough trained personal resources? This becomes more urgent with
scenes and models getting more complex.
Fig. 2: House Row [Stilla & Michaelsen, 1997]
In Fig. 2 some of the problems mentioned above may exemplarity become evident. Upper left we display a section of an
aerial image of a suburban region. Underneath the result of one of our feature extraction processes is shown. Since there
is a second image of the same section from another view point (with calibrated geometry) we could generate 3D-lines,
angles and structure, finally grouping the house rows and put them in functional connection with the 3D road displayed
on the right hand using the principles explained in Sec. 2.
4 COMPARING SHELLS AND SYSTEMS
It is good practice in other pattern recognition disciplines like speech or hand-written character analysis to compare the
performance of different methods, approaches and shells on the same benchmark data sets. In the field of concern of
this paper, this a laborious task, because not only the input and desired output ( ground truth) matters, but also the
models and structure used. A comparison then becomes more a qualitative discussion rather than a quantitative
competition.
4.1 Some Possible and Published Tools for Structural Model Based Recognition
Many systems have been proposed for model based structural object recognition in the last two decades. Examples are
580 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
