will fit the
e in similar
to millions
nth its non-
ally refer to
tically with
al and cycle
tting of the
use in non-
actability in
ch. It is also
of the same
the example
recognition
lata that the
)se presence
| property of
inistration A
nisable from
on the skill
. going to do
urgent with
section of an
1. Since there
ite 3D-lines,
ad displayed
Eckart Michaelsen
e The SIGMA system by [Matsuyama, 1985], with productions capturing for instance the functionality between a
house, the road and the connecting vehicle path between them. Examples working on single 2D aerial images are
given.
e Semantic networks have been proposed to represent the ‘knowledge’ about the image or scene. Additional to the
part-of hierarchy and the geometric relations for grouping then another relation called *concrete-of' may be defined
and help in formulating such things as the different appearance of the same objects in different data sources. One
example is the system MOSES [Quint, 1995] capable of combining structure from maps and aerial images of inner
city regions. This has been achieved by making use of the shell ERNEST [Kummert, 19??], which is a problem
independent semantic network interpreter using A*-search.
e The BPI system has been designed to handle comparably small production systems on huge data sets. In analogy to
semantic networks we display such a system as production-net and reported results in 2D and 3D for instance in
[Stilla & Michaelsen, 1995]. One speciality is the irrevocable accumulating control, still allowing priority ordered
queuing of the search.
e It is also possible to utilise commercial available computer vision shells like KBV with its token sets. Aseptically if
there is no need for intelligent control or associative access, an exhaustive search is desired and possible, and a nice
interactive working frame helps.
e. With rather big amounts of knowledge (production sets) and then inevitably small data sets, also multi purpose Al-
interpreters like PROLOG, OPSS5, CLIPS, e. c. have to be considered, since they allow to directly give the
productions and let the machine do the interpretation on the data.
The choice among these proposals with a given task at hand is by no means trivial. Each has its pro and cons. And
understanding any such system takes time and experience. Unfortunately there have been little publications comparing
different of these shells or approaches with common benchmarks.
4.2 Comparing Semantic Networks to Production Nets
Since in the recent past we had the opportunity to cooperate and /or compete with F. Quint working on the same data
and similar tasks with our BPI that he used for testing his MOSES, we dare to publish some words.
The most serious problem for production nets in the recent decade has been problem 1 (missing segments). After all the
approach has been syntactically inspired [Michaelsen, 1998]. Parsers will usually reject an input already, if there is any
single terminal missing in a syntactically correct pattern. Modelling becomes a laborious task, if also all tolerable kinds
of deletions have to be considered. On the other hand this rather explicit handling of problem 4 (defining proper feature
subsets for recognition) helps keeping the awareness of its existence. This might be circumvented by using rather flat
hierarchies and lots of intermediate cue clustering. The approach then more and more gains the hue of template-
matching and Hough-transforms. Of course also problem 7 (combinatorial growth of instance set) is encountered. But
the BPI-shell has been specially designed with respect to the handling of large data sets. There are for instance software
and hardware mechanisms of associatively querying the database with search regions (see Sec. 4.3 and [Lütjen,
Michaelsen & Stilla, 1998]). Also the irrevocable accumulating control scheme helps reducing search effort. Each
intermediate result is for instance stored as element instance and may be used by more than one branches of the search.
Furthermore production nets allow cycles. Thus they capture generic models like the house-row example in a fairly
straightforward syntactic way by some production of the form (house, house-row) — > (house-row).
Semantic networks with search mechanisms like ERNEST seam to suffer most from problem 7 (scaling in
computational complexity with the number of alternatives). A search tree is spanned with each node representing a
stade of search to be displayed by a partially instantiated network [Quint, 1995]. Every little change in the database like
doing a single correspondence between a line segment and a model contour, leads to a new stade. Intermediate results
(instances or modified concepts) from one stade are only accessible by the functions working on the successor. If the
same intermediate results are needed elsewhere in the tree, they have to be re-established. On the other hand semantic
nets are a pretty swift mechanism to handle complicated modelling tasks. Problems 1 and 4 (modelling the appearance
and the likelihood of deletions) loose much of their impact compared to how they appeal to the production net designer.
Still the awareness of these problems is not hidden. It may even be handled elegantly by the concrete-of-links and other
mechanisms like context provided by ERNEST. A serious problem to ERNEST are generic models with cyclic part-of
hierarchies. Cycles are explicitly prohibited in the part-of and concrete-of net.
j) compare the
of concern of
, but also the
a quantitative
Common to both approaches — but not every other published work on model based recognition — is the awareness of
problem 6 (erroneous early decisions, that prune away the correct solution). Both approaches offer means to avoid such
difficulties completely, with mathematically proven truth. Since adjusted to this end both approaches suffer seriously
from problem 7 (combinatorial growth), both approaches also offer means to relax such demands for strict correctness
xamples are gradually to the desired degree. Such opportunity to trade problems 6 and 7 against each other is very desirable.
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 581
