ymatic 
n and 
te that 
ls see 
pair of 
imum. 
(4) 
a and 
e. We 
do not 
r they 
ited as 
C, and 
further 
ym the 
pes of 
(5) 
in the 
to (2). 
tation 
ore to 
decide 
/ local 
eason, 
es of a 
ped in 
ability 
  
Chunsun Zhang 
The line structure in image is described as a graph, where the nodes of the graph represent straight lines, and the links 
between lines the relations. To find a correspondence, both individual lines and the graphs should be matched. We 
represent the straight lines in the left image as a set L, L={li}, i=1, 2, ... n, the straight lines in the right image as a set R, 
R={rj}, j=1,2,... m. The mapping from the left description to the right one is represented as T. Assuming the right type 
of mapping T, we seek the probability that line li matches rj, i.e. the matching problem becomes the computation of P( li 
— rj| Tj. Using Bayes formula, we can write: 
P(lzugT) 
PfiznITi)- PIT] (6) 
and applying the total probability theorem, 
S ENS S n Pih ru len T) 
P{h= n IT}= rieR  r-ieRrixxe RH meR (7) 
NN S Pfhs ru du n TI 
rmeR reR meR 
We assume that the relationship between (li, rj) and (In = rx) is independent of the relations of other pairs, and that (li. rj) 
does not by itself provide any information on (ln — rx) (Christmas et al, 1995). Factorizing the numerator and 
denominator in (7) we obtain: 
X P{h= mJQ(h=m) 
h=1 
where 
n m 
Oth=rn}h= Il 3 PT nj; bo, f) Wi = roba m te JP fom fu) (9) 
hel hei j=1 
The solution of the problem of line matching defined in (6) can be obtained by combining (8) and (9) in an iterative 
scheme (see Rosenfeld et al., 1976; Hummel and Zucker, 1983; Christmas et al., 1995). The previously computed 
similarity scores are taken here as the initial probabilities P?(/ = 7} for a possible match pair li and rj. The constructed 
match pool greatly speeds up the probability relaxation process because only the lines in the match pool are involved. 
PT (ril r)ll rl r«)is called compatibility function. Indeed, the compatibility function plays an important 
role in the process of structural matching. In our implementation, the evaluation is derived from the geometrical relation 
measurement between (li. In) and (rj = rk). Three relations constitute the relational description between li and In (Fig. 5). 
They are the angle between li and ln, the distance between li and ln centers and the angle between line li and the line 
joining the center points of li and In. 
Structural matching is conducted bidirectionally from left to right and from right to left. The next step is a combined 2D 
and 3D grouping of straight segments. Thereby, information in one space helps bridging gaps and combining segments 
in the other space. Thus, small gaps are bridged, edges broken in multiple straight segments are combined, matched 
segments of different length are extended. 
  
Figure 5. Three neighbouring line relations. 
The final 3D position is computed from the original edge pixels and not the fitted straight lines. This is done for each 
pixel in the overlap length of the corresponding edges. A 3D straight line is then fitted. This approach can also handle 
the problem case when a road edge goes up and downhill but appears straight in 2D. This processing is very useful as 
we suppose to reconstruct roads using straight lines in both 2D and 3D spaces. The developed method for 3D straight 
line fit recursively subdivides a segment at the points with a certain deviation from a line connecting its endpoints, this 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 1013