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