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.