distinctive edge segments are extracted from the edge
neighbourhood graphs using a selection function that
weights the segment parameters.
The selection function derives a measure of
distinctiveness d for each edge segment. The averages of
the weight function values of the user-defined parameters
are computed:
n
2, wápi)
22 (5.6)
n
where pi = argument of parameter i,
wi() 2 weight function for parameters pi,
n- number of parameters evaluated.
A weight function w; is given in digitized form as a set of
x-values defining a standard function curve.
All possible combinations of significant edge
segments (s;zL, sjg) from the left and right edge
neighbourhood graphs are compared using the match
function (5.1). The set of mutually best matches M is
considered for further processing. "Mutually best" means
that both the assignment of the best matching right
segment to the left segment as well as the assignment of
the best matching left segment to the right segment result
in the same pair of edge segments. When the similarity
measure m(S;L, Sir) is greater than a user-defined
threshold, the match is accepted as an initial match of a
hypothesis.
852.2 The Propagation Algorithm
In the propagation step, connected components are
generated by searching the edge neighbourhood graphs
for further potential matches, starting with the initial
hypothetic matches. The neighbouring edges of the initial
match (pr, pg) are compared in all combinations. Two
classes for the acceptance of a match found are defined as
follows:
I. matches which
A. are elements of the set of mutually best matches
M or matches where one segment s; is matched to a
segment s; which is matched to a segment 5;
belonging to the edge streak to which s; also
belongs,
and
B. have a match function value greater than a
threshold 11:
m(SL, SR) > 11
The matches are regarded as valid matches of a
connected component.
II. matches which fulfill condition À as before and
B. have a match function value greater than a
threshold #2, and less than the threshold ?;:
t1» m(sL, Sg) » t2
These matches are not considered being members of
the set of connected components, but they are used
for further propagation of matches in order to find
more matches of class I.
The propagation strategy is based on a breadth-first
search in a tree. The search starts by comparing
312
neighbours of the segments of an initial hypothetical
match. Thus, the initial match is the root node of a tree.
Its child nodes are the matches of classes I and II among
the neighbours of the initial segments. As a breadth-first
search is conducted in the graph, the first generation
child nodes are established in direct sequence. Then, the
second generation child nodes are searched by comparing
all neighbours of a first generation match. This means
that the breadth-first tree degenerates to a linear list with
generation indices.
In every generation, all matches of classes I and II
become further "tree" nodes of the next generation, if
they are not already part of the tree as a node of an
earlier or of the same generation. The propagation is
ended as soon as no further tree nodes can be generated,
or if there are more than three generations of class II
nodes in sequence.
Fig. 5.1 shows two neighbourhood graphs to be
matched, Fig. 5.2 gives an example for the generation of
the propagation tree, and Table 5.1 shows the class I and
class II matches established during the propagation.
4 : D
eT 1 > eT AUN
= | À AE Came NÉ
= 1 - - ^
~ >” ee \ ^
N \ i ^
2 eo 3 x BI „727 E V
7 - UV
left image right
image
1
Fig. 5.1. Two edge neighbourhood graphs.
The most distinctive edges are 3 and E. An initial
match of a hypothesis could be the match (3, E).
class II
nodes
© class I
nodes
Fig. 5.2. The propagation tree.
Even though the edge segments 2 and B do not seem to
match very well (see difference in direction), match
(7,K) was found.
dens : class I matches class II matches Seed
GE) | (6,0) (1,8) (5,F) (4D: (2,B)
(2,B) (7,K)
(S,F) (6,1)
(6,6)
Tab. 5.1. Matches from hypothesis propagation.
Match (6, G) was overwritten by match (6, I).
During the build-up of the propagation tree, the
potential matches of class I are considered to belong to a
connected component. Ambiguous assignments are solved
at th
matc
with
prop
hype
com
a co
gene
befo
shov
for
com
matc
pror
matc
gene
Afte
matc