often 
edge 
; to be 
small 
on the 
m the 
S), 
th), 
gion. 
iptive 
treak 
ing to 
orner 
ption 
edge 
The 
f the 
) the 
'cted 
) the 
o be 
6. side (left or right). 
5. . Graph-Based Feature Matching 
The fundamental idea for the matching of edge 
feature pairs is that any property of the edge features can 
be compared with the help of a match function. In this 
way the properties contribute to a measure of similarity 
of the candidate features. As no constraints have to be 
fulfilled, one or several properties that differ for 
candidate feature pairs do not prevent the algorithm from 
identifying a correct match, as long as the overall 
similarity can be proven with a high similarity value. 
5.1 The Match Function 
The comparison of candidates for matching is 
conducted with a match function which evaluates feature 
parameters (McIntosh and Mutch, 1988): 
2. (wi: vi) 
E (5.1) 
Wi 
where v; = similarity value for a parameter pair, 
w; = weight of parameter i. 
The result of the match function is a similarity value s of 
the features compared. 
The similarity values v; of the parameters are 
computed according to the nature of the specific 
parameters. Generally, the computation is conducted 
according to (after McIntosh and Mutch, 1988): 
_ min (|pj. | -| per 1) (5.2) 
max (|p|, | pr) 
i 
where pj, and pir are the instantiations of the compared 
parameters. 
For some parameters, equation (5.2) is not suitable. 
The similarity value for segment directions tr, tr is 
computed as (McIntosh and Mutch, 1988): 
vp =  - |t, - td (5.3) 
ó 
where Ij, tg are the directions of the left and right 
segment in n 
The value ó is interpreted as the maximum allowable 
difference between the directions compared. If the 
magnitude of the difference If, - tr! is larger than 6, then 
the similarity value v, will be negative. 6 is computed 
according to: 
z — 255g (5.4) 
3 = Ömax min(50, Ir, + Ig) 
where Omax is set to 80 rad 
Iz, Ig are the lengths of the left and the right 
segments. 
This means that ó is generally 80 m a value that has 
been determined empirically. ó is increased when the sum 
of the segment lengths is less than 50 pixels as directions 
of short segments agree considerably less than directions 
of longer segments. 
For the propagation step of the generation of 
hypotheses, for both the left and the right edge segments 
L and R, "parent" nodes in the edge neighbourhood 
graphs are known. This provides also the possibility to 
compare relational parameters. The similarity value of 
two relations ry, rg between parent and neighbour nodes 
is computed according to: 
  
_1/9-l61- tr} , min (dr1, drr) 3.5 
" 4 ó Rl At ener 65 
where f, = direction between related edges in the left graph, 
tyr = direction between related edges in the right graph, 
dy, = distance between related edges in the left graph, 
drr = distance between related edges in the right graph 
6 = computed value according to (5.4), 
> 
edges belonging to the same edge streak 
50 if both left and right relation are referring to 
| 100 if both left and right relation are referring to | 
C= ; , 
edges not belonging to the same edge streak | 
0 otherwise 
100, f ri, rage P 
100, if rz, rge N 
100, if (re, KrE PVTL,TRE N) 
0, ifr, e P^rge N) v(rz € N^rge P) 
50 otherwise 
| 100; iffrı, rre L 
Sd 100, if riz, rge R | 
0 otherwise 
Here P = {r|ris a relation of parallel edge segments} , 
N - (ririsarelation of perpendicular edge segments), 
L - (rlris rel. of a parent node and a left child node), 
R - [rlris rel. ofa parent node and a right child node). 
Thus, the similarity of two relations depends on the 
direction and the distance between the related segments, 
edge-streak membership and topology. 
The parameters compared by the match function are 
determined by the domain to which the matching method 
is applied; in this case the application domain is stereo 
imagery. For other domains such as matching of digitized 
maps, the parameters p and, if necessary, the parameter 
similarity functions v, could be adapted to the specific 
problems. Image geometry could also be taken into 
account as a parameter of the match function. 
5.2 The Matching Procedure 
The matching process consists of three steps: (1) the 
prediction of hypotheses, (2) the propagation of the 
predicted hypotheses based on the edge neighbourhood 
graph, and (3) the solution of conflicts between 
concurrent connected components. Ayache and Faverjon 
(1987) used a similar algorithm. 
5.2.1 The Prediction of Hypotheses 
In the prediction step a set of particularly obvious 
matches is attempted. First, sets of comparatively 
311