tical 
tree. 
nong 
-first 
ation 
,the 
aring 
eans 
with 
id II 
n, if 
f an 
n is 
ated, 
ss II 
o be 
in of 
and 
the 
| toa 
jylved 
at the end of the processing of a hypothesis. If multiple 
matches occur between different edge streaks, the match 
with the greater similarity value is preferred. 
When a match which is found during the 
propagation of a hypothesis is the initial match of another 
hypothesis, the other hypothesis is discarded. This saves 
computation time as the second hypothesis would result in 
a connected component similar or even equal to the one 
generated. 
According to the details and features described 
before, the propagation algorithm was implemented as 
shown in Figures 5.3 and 5.4. 
  
for all hypotheses ( 
treat initial match ( pL, pR) as root node; 
while tree not completely processed ( 
Match Neighbours of (pL, pR); 
for both edge neighbourhood graphs ( 
for all segments ( 
discard ambiguous matches; 
) 
) 
) 
) 
  
  
  
Fig. 5.3. Propagation algorithm. 
  
Procedure Match Neighbours of (pL, pR) ( 
compute match function values for NL x NR; 
for all left neighbours ( 
if mutually matched ( 
if ( m(sL, sR) » 11) ( 
if (sL, sR)& tree, Make Tree Node; 
Make_Match; 
check for not yet processed hypothesis; 
) else if (m(nL, nR) > 12) { 
if (sL, sR)¢ tree, Make_Tree_Node; 
} else if sL is matched to a right segment sR which is 
matched to another segment tL of the edge streak of 
SL { 
if ( M(SL, SR) > 11) { 
if (sL, sR) etree, Make Tree Node; 
Make. Match; 
check for not yet processed hypothesis; 
} else if sR is matched to a left segment sL which is 
matched to another segment qR of the edge streak of 
sR( 
if ( m(sL, sR) » t) ( 
if (SL, SR) etree, Make Tree Node; 
Make Match; 
check for not yet processed hypothesis; 
) 
) 
) 
  
  
  
Fig. 5.4. Algorithm for the procedure "Match Neighbours of". 
The procedure Match Neighbours of does the 
comparision of neighbouring nodes of an established 
match. Procedure Make Tree Node adds a node to the 
propagation tree. The procedure Make. Match adds a 
match to the edge neighbourhood graph. During the tree 
generation, several entries per edge segment can occur. 
Afterwards, the main procedure discards the ambiguous 
matches in the connected component. 
8.23 Solution of Conflicts Between Different 
Connected Components 
Which of the conflicting hypotheses is preferred is 
based on the strength of prediction of a hypothesis. The 
connected component with the largest number of matched 
segment pairs is considered to be the correct one. 
When two matches are conflicting, the match 
belonging to the stronger hypothesis is always preferred. 
Then the strength of the weaker hypothesis is reduced by 
one. During the process of solving contradictions, only 
the original strengths of prediction are compared. This 
avoids that the order in which the hypotheses are 
evaluated for ambiguous matches influences the result of 
the process. 
After the solution of conflicts between concurring 
connected components, the remaining strengths of 
prediction are compared with a user-defined threshold. 
The threshold should be set according to the image type 
and the number as well as reliability of the matches 
needed. Hypotheses weaker than the thresholding strength 
are discarded completely, as those hypotheses often are 
not based on correct matches (Ayache and Faverjon, 
1987). 
6. Pointwise Matching and Object Space 
6.1 Establishment of Point Correspondence 
Once the edge segments are matched, 
correspondence between linear groups of points is 
established. Yet it is not determined how the points on the 
edges form pairs of matching points. The task of finding 
these point pairs is non-trivial, as there are several 
influences which are resulting in a nonlinearity of the 
function that maps points from one segment curve to the 
other. These influences include perspective distortion and 
occlusion. The parameters controlling the mapping 
between two chain-coded curves are not considered 
rigorously here, but three simple cues are used to 
establish a pointwise correspondence. 
These methods assume that the segment points have 
certain distinctive characteristics which allow for the 
determination of a measure of fitting for different 
positions while the shorter curve is sliding pixel by pixel 
along the longer curve. It is always assumed that the 
transformation function from one chain-coded curve to 
the other one is linear with slope 1. This means that both 
curves are assumed to have the same scale and that chain 
code elements are assumed to be equally long. Thus, the 
assignment of matching pixels is one-to-one. 
The cues used for curve fitting are an alignment 
according to corresponding corner points, an alignment 
according to perpendicular neighbouring edge segments 
and a least squares fitting. They are applied in the order 
in which they are mentioned here. If one method is 
applied successfully, the other methods are not pursued. 
6.2 Area-Based Matching with Subpixel 
Accuracy 
The curve fitting results in a pixel by pixel 
correspondence between the curves. An area-based 
matching algorithm with subpixel accuracy is applied to 
the end points of the edge segments and to one point in 
the middle of long segments. 
The matching algorithm of Kanade and Okutomi 
(1990) was implemented. The algorithm iteratively