Eckart Michaelsen
The other problems listed in Sec. 3, namely problems 2 (non-modelled objects), 3 (occlusion), 5 (projection), 8 col
(adequacy of relations), 9 (visibility of function) and 10 (laborious model acquisition) are more Or less problem ind
inherited and independent of the approach chosen. SOI
Co
4.3 Pushing Performance by Inverting Relations into Queries and Search Regions ift
onl
Most computer systems provide means for performance analysis, so that a statistic on the percentage of run time Ge
consumed by each module may be monitored. That will help identifiing administrative overhead. Also a close look on wit
the memory usage helps. À system performing model based perceptual grouping should spend most memory on of 1
attribute values of instances and pointers storing interrelations between instances. Most computational efford should be she
spend on searching groupings and checking the geometric relartions. the
We found that our system spends most time on searching partners for a given instance, that will fulfil the relations We
specified in the productions. Frequently used grouping relations are collinear for line prolongation and for roads and pro
rectilinear for composing pairs or triples for buildings. Of course very important relations are also parallelity, vicinity e. anc
c. The use of inverting techniques (like content addressable retrieval or hashing) for some such relations helps
accelerating the search for permissible group partners in the database. Just imagine, that the set of all line instances RE
being located close to a triggering object may be found in time independent of the overall size of the set of all lines.
Usually there is a trade-off to be balanced between swift processing and sparing memory [Knuth (1973)]. In structural Ad
image analysis today memory is not the problem, so that intelligent retrieval techniques help a lot. Furthermore one A,
might consider solutions including special hardware like [Kohonen (1985)]. We gained some experience in this field in Ba:
the recent decade [Lütjen, et al. (1998)].
We give again a simple but problematic example, where relation inverting is impractical: Suppose the task is given to Kn
group a pair of line objects into a single T-object in 2D image or ground plane space. So the lines should not be parallel
and one end of the second line should be close to the other (with Euklidean metrics), like it is exemplified by Fig. 3a). Ko
Fig. 3b) then shows the case, that the search queries the base for partners for the bolt drawn upper line triggering. Then
only lines with one end in the sketched search region will be able fulfil the relation. That will be quite fiew. So they can Ku
be tested sequentially for proper orientation. But if the other line of our group triggers, which is sketched by drawing it Sig
bolt in Fig. 3c), we don't have a simple local criterion for the ends of the partner line. Maybe we have to check all lines
and thus end up with quadratic complexity with respect to the image size compared to linear like in the case sketched in Ma
3b). Pre
Me
Fra
Mi
Joi:
Qu
Ka
Q) Ol
Sti]
= 50(
b) Sul
Gn
C) 22%
Fig 3: Problems in inverting the geometric relation ‘T-shaped’ Stil
He
This simple example shows, that sometimes the sequence in which things are put together matters very much when it 43-
comes to complexity assessment. For tasks with very huge data amounts some interdisciplinary fertilisation with data
banking is helpful. We
psy
5 CONCLUSIONS
w results in this paper. We gave a list of ten problems that in our
We did not present an new approach or method or ne
mind approaches, methods and results should be assessed. We
opinion are of importance. With these problems in
582 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
