Box Operations.
e feature based
age matching is
\n informed tree
photogrammet-
ta acquisition of
e segmentation,
all these means
ny a priori infor-
plications of the
utomated digital
the correspond-
ation level. The
ning of two rela-
n this paper the
in the structural
topological and
Jetermination of
g tasks can be
ation.
inally developed
jrammetry there
ling to solve the
patch and the
)sselman/Haala,
an benefit from
tic relative and
riangulation, the
slevation model,
; image analysis
would be further
about the struc-
cquisition of the
al approach for
an a project to
m for the auto-
ie, in which the
ed as a major
| be reported. A
ural matching is
ssible matching
iple of the maxi-
the mutual prob-
iutual probability
sarch method is
rder to keep the
search time acceptable for the photogrammetric applica-
tions, a series of strategies have been worked out and
integrated into the search method. These are the sub-
structure theory, the unit ordering, the best minimum
matching, the geometric constraints, the adaptive correc-
tion, pyramid structures and so on. For the data acquisition
of the structural descriptions the methods for the image
preprocessing, edge detection, line extraction, image seg-
mentation, feature point extraction, direction-invariant
correlation and topology extraction are also developed.
With all these means together the fully automatic recogni-
tion of the corresponding image objects is realized without
to know any a priori information and without to have any
relation assumptions about the digital images.
In following sections the developed method for the struc-
tural matching is introduced. Some application examples
about the fully automatic relative orientation of any stereo
image pairs and the automated digital aerotriangulation
are then illustrated. They show with the application of the
structural matching method the digital photogrammetry
has reached its highest automation level. The "black box"
philosophy for photogrammetric operations, which has
been predicted by some photogrammetric experts [e.g.
Achermann, 1991], is further realized in this contribution.
2. AN APPROACH FOR STRUCTURAL MATCHING
2.1 Structural Description
The structural matching establishes a correspondence
between two structural descriptions. A structural descrip-
tion of a digital image includes the radiometric, geometrical
and topological information of the image. This information
can be divided into features and relations as the Figure 1
Fig. 1:
called primitives. Each kind of primitives and relations can
be described by several attributes. E.g. a point primitive p;
can be described by:
p; = {coordinates = (x,y), gray = g, gradient = t} (1)
and a relation r; between two lines can be described by:
r= {lines 1,1 cross = yes, angle = 0} (2)
The goal of the structural matching is to find out a corre-
spondence or homomorphism (i.e. the best matching) from
the primitives and relations of one structural description to
the primitives and relations of second structural descrip-
tion. The available primitives and relations of a digital
image are enormous. Two digital images are usually only
partly overlapped, so the right matching of the two descrip-
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
tions is only a part correspondence of all primitives and
relations. One primitive (or relation) of the first description
may be matched with one or several or no primitive (or
relation) of the second description. Therefore there may be
many possible matches between two structural descrip-
tions. So the search time for the best matching can be very
long. In order to solve the structural matching problem
quickly and correctly, the topics like evaluation function,
search method, correctness check and the efficient extrac-
tion of the structural description etc. must be researched
and resolved.
2.2 Evaluation Function
Suppose we match two digital images and use DL for the
structural description of the first image and DH for the
structural description of the second image. According to
the maximum likelihood estimation the best matching of
the two descriptions h, should have the maximal condi-
tional probability among all possible matches h,, h2, … iy:
h, = max P (I/ DL, DR) (3)
i
Using Bayes-Formula P(h,/DL, DR) is equal to:
P (DL, DR/h) P (I) (4)
P(h/DL, DR) = P (DL, DR)
It can be known from the equation (4) that maximizing
P(h/DL,DR) is equal to maximizing P(DL, DR/h;) . SO
the mutual probability P (DL, DR/h; can be taken as an
evaluation index for the goodness of a possible matching.
Since:
P(DL,DR/h) = XP (DL, DR,/h) P(DL, DR/DL; DR; hy (5)
Lj :
where the subscripts i and j represent the primitives of the
descriptions, the. mutual probability P(DL,DR/h;) is also
quite simple to calculate in practice.
2.3 Search Method
The tree search methods are often used to find out the
solution in many artificial intelligence problems [Nilson,
1982]. A search tree for the structural matching can be
root
DL, level /
DL; level i
DL, && 8 a Bu ES BE PS gg level m
m
Fig. 2: a search tree
schematically demonstrated in Figure 2. Each level of the
tree represents a primitive or a relation (both called an
unit) of the first description. Each node represents a possi-
ble matching of two units. The nodes in the last level are
also called tree leaves. Each path from the root to a leaf is
a possible matching. The tree search methods can be
divided into two types: blind search methods and informed
search methods. The blind search methods treat all the
tree nodes equally, so they usually take a long time to find
the solution. The informed search methods use some
919
