Figure 7: Search tree for the incorrect image description
of landmarks and images. In this paper we focussed on the
recognition of a landmark in the image. We did not discuss
the exact measurement of the landmark’s coordinates. Once a
landmark has been located approximately, other methods can be
used for the coordinate measurement (e.g. a robust least squares
adjustment [Sester and Förstner 1989]). For the recognition of a
landmark inaccurate models and a simple geometric transforma-
tion (affine transformation) are sufficient. A precise measurement
would require accurate 3-dimensional landmark models and a full
model of the perspective transformation.
The relational image descriptions we used were extracted from
colour images and colour infra-red images. The colour informa-
tion was of crucial importance for the feature extraction. With-
out the use of colour (or multi-spectral) images, a reliable extrac-
tion of road and rivers is hardly possible.
In order to determine the exterior orientation of an image, it is
necessary to measure three landmarks at least. The landmarks
we used all contained a minimum number of five points. If the
terrain coordinates of those points would be known, one could
calculate a spatial resection after the measurement of only one
landmark. Of course, the accuracy of this resection would be bad,
because the points of the landmark lie closely together. How-
ever, the transformation parameters can be used to constrain the
search space for the recognition of the landmarks that remain
to be measured. The relational matching algorithm does not re-
quire approximate values, but, if approximate values are available
(e.g. for scale rotation or position of the landmark), they are very
useful for reducing the search space.
Such approximate values can be easily integrated into the eval-
uation of the mappings with the mutual information. The more
accurate these values are, the higher the conditional probabilities
will be. E.g., if the image scale factor is known to be near S, one
knows that the length of a line in the landmark should be about
S times the length of the corresponding line in the image de-
scription. This helps to discriminate between correct and wrong
correspondences. The conditional probabilities (and also the mu-
tual information) of the correct correspondences will be high and
the conditional probabilities of the wrong correspondences will
be low. The calculation or empirical acquisition of the probabil-
ities does require quite some effort before one can start with the
matching. But this only has to be done once. In all six examples
we used the same probability tables. Once the probabilities have
been determined, the maximum likelihood mapping between two
descriptions can be found by maximizing the mutual information.
Unfortunately, the search time needed to find a match is hard
to predict. In the first place it depends on the number of image
and model features that have to be matched. Two other fac-
tors also have a strong impact on the search time: the quality
of the image description and the uniqueness of the landmark at-
975
tributes. Differences between the geometry or topology of the
image and landmark description lead to a substantial increase of
the search space. These differences are usually caused by errors
in the segmentation of the image. A good image segmentation
is therefore very important. In the previous section the example
parcel2 showed a relatively high search time. This was caused
by the fact that the image contained many features and relations
between features with similar attribute values. This increases the
search effort that has to be made in order to find the correct map-
ping. One therefore should use such landmarks that have unique
attribute values. This limits the number of mappings that have
to be evaluated and therefore limits the search time.
LITERATURE
Ackermann, F. and P. Krzystek [1991]: MATCH-T: Automatic
Mensuration of Digital Elevation Models. Presented paper
to the 3rd Technical Seminar of the Sociedad Espanola de
Cartografia Fotogrametria y Teledeteccion, April, 12 1991.
Arcelli, C. and G. Sanniti di Baja [1985]: A Width-Independent
Fast Thinning Algorithm. IEEE Transactions on Pattern
Analysis and Machine Intelligence, vol. 7, no. 4, 1985.
Frey, H. [1990]: Die Verarbeitung von Farbbildern nach Hel-
ligkeit, Sättigung und Buntton. In: Mustererkennung 1990,
Informatik Fachberichte, no. 254, Aaalen, September 1990,
Springer Verlag, pp. 324-331.
Haralick, R.M. and G.L. Elliott [1980]: Increasing Tree Search
Efficiency for Constraint Satisfaction Problems. Artificial
Intelligence, vol. 14, pp. 263-313, 1980.
Nilsson, N.S. [1982]: Principles of Artificial Intelligence.
Springer-Verlag, Berlin Heidelberg New York, 1982.
Pearl, J. [1984]: Heuristics: Intelligent Search Strategies for
Computer Problem Solving. Addison-Wesley, Reading, MA,
1984.
Schenk, T., J-C Li and C. Toth [1991]: Towards an Autonomous
System for Orienting Digital Stereopairs. Photogrammetric
Engineering & Remote Sensing, vol. 57, pp. 1057-1064,
1991.
Sester, M. and W. Fórstner [1989]: Object Location based on
Uncertain Models. In: Mustererkennung 1989, Informatik
Fachberichte, vol. 219, Hamburg, October 1989, Springer
Verlag, pp. 457-464.
Shannon, C.E. and W. Weaver [1949]: The Mathematical The-
ory of Communication. University of Ilinois Press, 1949.
Shapiro, L.G. and R.M. Haralick [1981]: Structural Description
and Inexact Matching. IEEE Transactions on Pattern Anal-
ysis and Machine Intelligence, vol. 3, pp. 504-519, 1981.
Tsingas, V. [1991]: Automatische Aerotriangulation. In: Pro-
ceedings of the 43th Photogrammetric Week, Series of the
Institute of Photogrammetry, Stuttgart University, vol. 15,
Stuttgart, September 1991, pp. 253-268.
Vosselman, G. [1992]: A Probabilistic Measure for Comparing
Relational Descriptions. In: Proc. Int. Workshop on Ro-
bust Computer Vision - Quality of Vision Algorithms, Bonn,
March 1992, Wichmann Verlag, pp. 151-169.
