oct surfaces 
ure. Most of 
stereo pair. 
Nith surface 
continuities 
ntial. In the 
r an image 
ces, e.g. in 
> extraction. 
Jating more 
the problem 
ospondence 
> values will 
ssult of our 
mputational 
which give 
ite general 
| degree of 
1e algorithm 
nage scales 
e described 
ed methods 
ject to be 
than two 
are usually 
convergent, 
l-case con- 
by surface 
surface can 
mation, very 
face should 
bout related 
and object 
discuss the 
literature to 
lescribed in 
Image 
2. RELATED WORK 
2.1 Matching Techniques 
One possibility to characterize matching algorithms is 
given by the geometric and radiometric models they use 
for the mapping functions (figure 1). 
  
Figure 1: Object reconstruction and image matching 
with two images; taken from (Lang et al., 1995) 
Matching algorithms which work in object space 
reconstruct the object O directly by inverting the 
perspective transformations Toi and Tos after having 
found initial correspondencies between homologous 
image features. Object space matching techniques have 
the advantage that they are closer to physical reality so 
that they may be capable of handling occlusions if more 
sophisticated object models are used for the evaluation of 
the initial correspondencies. On the other hand, the 
number of parameters to be estimated in the inversion 
process is very high (Lang et al., 1995). In order to avoid 
the computational complexity of object space matching, 
the algorithms used in most photogrammetrical systems 
apply image matching techniques (Gülch, 1994), 
(Krzystek, 1995) which relate the images |; and l» by a 
mapping function Tz. In this case, the object model is 
implicitly contained in the formulation of Tz, which can 
be approximated by an affine transformation if the object 
surface can be assumed to be locally flat. If this 
assumption is hurt, Ty» becomes more complicated. This 
is the reason why image matching techniques using a flat 
terrain model give bad results in the presence of 
occlusions (Lang et al., 1995). 
From another point of view, matching algorithms can be 
characterized by the image model they use (Gülch, 
1994). Area based matching algorithms use a raster 
representation of the image, i.e. they try to find a 
mapping function between image patches by directly 
comparing the grey levels (Ackermann, 1984). Feature 
based matching techniques on the other hand first derive 
a symbolic description of the image by extracting salient 
features from the images using some feature extraction 
operator, e. g. the Fórstner operator (Fórstner, 1986), and 
then try to find corresponding features under certain 
assumptions regarding the local geometry of the object to 
be described and the mapping geometry (Krzystek, 
1995). Feature based algorithms appear to be more 
flexible with respect to surface discontinuities and 
requirements for approximate values whereas area based 
matching techniques offer a higher potential of accuracy 
(Gülch, 1994). 
Both area based and feature based methods as described 
in the works cited above rely on similar grey level 
distributions in different images. This is an assumption 
which holds true for stereo images but may be hurt for 
693 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
images taken from convergent viewing directions. The 
topology of features which can be stored in relational 
descriptions is an image property which is invariant under 
perspective transformation (Vosselman, 1995). The topo- 
logical relations between neighbouring features can be 
extracted together with the features themselves. Matching 
of relational descriptions or relational matching thus is a 
very powerful concept which might work in rather general 
cases. However, its computational complexity is very high 
because it leads to rather complex search trees 
(Vosselman, 1995). Whereas common area and feature 
based techiques have already been applied simul- 
taneously to more than two images, no multi-image 
relational matching algorithm is known (Fórstner, 1995). 
2.2 Three - Dimensional Object Representation 
Common systems for surface reconstruction from digital 
images often use 25D surface representations which is 
convenient for many applications, especially if the object 
in consideration is the earth and if the image scale is 
small (Gülch,1994). More complex objects cannot be 
described in that way. Modeling of arbitrary surfaces 
requires the surface description to be independent from 
the coordinate system. This can be achieved by 
decomposing the surface into basic geometric entities 
such as nodes, edges and triangles. The structure of the 
surface is then described by the topological relations 
between these elements; its geometry is determined by 
assigning the nodes uniquely to the measured surface 
points. Originally, only these points (and possibly, the 
surface normals in these points) are available. The 
topological relations can be found by triangulation. 
(Heitzinger, 1996) describes an incremental method for 
that purpose which is to form the basic surface 
description model for the new implementation of the 
program system SCOP. As triangulation of a given point 
set is not unique, this method aims at a triangulation 
which reproduces the surface as correctly as possible. 
Thus after inserting a node into the triangulation, the 
triangulation has to be optimized according to some 
criterion, e.g. smoothness. Triangulation should be able 
to establish constraints in order to render possible the 
consideration of break lines (Heitzinger, 1996). 
2.3 Discussion 
Having in mind requirements stated in section 1, we think 
that feature based matching in object space is best suited 
for a solution to our problem because such an algorithm 
seems to be capable of overcoming the problem of 
occlusions by introducing more complex models for the 
evaluation of correspondence hypotheses in object space. 
It also can benefit from the possibilities of bundle block 
geometry with regard to geometrical constraints and the 
usage of more than two images. As topological relations 
between neighbouring features provide valuable infor- 
mation for the generation of correspondence hypotheses, 
they should be considered by the algorithm, too. 
The method for surface representation by (Heitzinger, 
1996) appears to be well-suited for describing quite 
general surfaces. As triangulation is rather complex a 
step, it will not be done during the matching phase, but 
will be applied to the point set which is the result of 
matching. If surface discontinuities have been detected 
by the matching algorithm, this information should be 
considered in triangulation.