Structural Matching and Its Applications for Photogrammetric Automation
Dr. Younian Wang
Institute for Photogrammetry and Engineering Surveys
University of Hannover, Germany
ISPRS Commission Ill, WG 2
KEY WORDS: Vision, Orientation, Correlation, Triangulation, Automation, Image Matching Algorithms, Black Box Operations.
ABSTRACT:
The technology for stereo image matching has been extended from the area based correlation via the feature based
matching to the structure based matching. In this paper a newly developed method for the structural image matching is
introduced. An evaluation function based on the mutual probability of a possible matching is deduced. An informed tree
search method is applied to search the best matching. In order to keep the search time acceptable for the photogrammet-
ric applications, a series of strategies are worked out and integrated into the search method. For the data acquisition of
the structural description the methods for the image preprocessing, edge detection, line extraction, image segmentation,
feature point extraction, direction-invariant correlation and topology extraction are also mentioned. With all these means
together the fully automatic recognition of the corresponding image objects is realized without to know any a priori infor-
mation and without to have any relation assumptions about the digital images. Some examples for the applications of the
structural matching in the fully automatic relative image orientation and in the tie point recognition for the automated digital
triangulation are demonstrated. The results show that with the application of the developed methods and the correspond-
ing program system for the structural matching the digital photogrammetry has reached its highest automation level. The
"black box" philosophy for digital photogrammetric operations is further realized in this contribution.
1. INTRODUCTION
Image matching is a basic issue in computer vision and in
digital photogrammetry. The methods for image matching
can be divided into three classes, i.e. signal based match-
ing, feature based matching and structure based matching
[Lemmens, 1988].
The signal based matching is also called area based
matching. It refers to determine the correspondence
between two image areas according the similarity of their
gray values. The cross correlation and the least square
correlation are the well-known methods for signal based
matching. These methods need a very good initial position
and direction of the two areas.
The feature based matching determines the correspon-
dence between two image features. In photogrammetry
the feature point matching is often applied in the last few
years [z.B. Li, 1988; Schenk, 1990; Greenfeld et. al., 1991;
Tang/Heipke, 1993]. The initial values for feature based
matching need no more so accurate as for signal based
matching. But some a priori information e.g. the approxi-
mate orientation parameters, the image overlaps etc. is
still necessary to know. So it is not suitable for the fully
automatic recognition of the corresponding image objects.
The structure based matching is usually called structural
matching or relational matching. The structural matching
establishes a correspondence or homomorphism from the
primitives of one structural description to the primitives of a
second structural description [Haralick/Shapiro, 1993,
p594]. A structural description is defined by a set of primi-
tives and their interrelationship. E.g. the structural descrip-
tion of a digital image consists of the image features and
the relations among the features. The term relational
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
matching refers sometimes only the matching of two rela-
tions [Haralick/Shapiro, 1993]. Therefore in this paper the
term structural matching is used. Because in the structural
matching not only image features but the topological and
geometrical relations are also used for determination of
the correspondence, the image matching tasks can be
fully automated without any a priori information.
The concept for structural matching is originally developed
by experts in computer vision. In photogrammetry there
was a first research using structural matching to solve the
matching problem between the image patch and the
description model of a control point [Vosselman/Haala,
1992]. But many photogrammetric tasks can benefit from
the structural matching, e.g. the automatic relative and
absolute orientation, the automated aerotriangulation, the
automatic data acquisition for the digital elevation model,
the object localization and recognition, the image analysis
and understanding, and so on. So it should be further
investigated. The problems to be solved about the struc-
tural matching are mainly the efficient acquisition of the
structural descriptions and the operational approach for
the matching of the structural descriptions.
Since a few years we have undertaken a project to
develop a digital photogrammetric system for the auto-
matic reconstruction of the object surface, in which the
structural matching has been investigated as a major
issue. In this paper the achievements will be reported. A
newly developed approach for the structural matching is
introduced. An evaluation function for a possible matching
has been deduced according to the principle of the maxi-
mum likelihood estimation. It is based on the mutual prob-
ability of a matching. In the practice the mutual probability
is easy to calculate. An informed tree search method is
applied to search the best matching. In order to keep the
918
inte
stri
ma
tior
of
pre
cor
Wil
tior
to
rel:
In
tur
ab:
are
stri
ha:
phi
be:
Ac
2.1
Th
be
tio
an
ca
sh
an
