corresponding linear feature pairs can be used to 
generate a coarse DEM. The major requirement for 
generating a coarse DEM with high reliability is then 
fulfilled. 
To explain the procedure of string matching more 
easily, we have designed a simplified example, taking the 
position of the linear features from the property list 
only and simplifying the cost function as: 
d(R,L)-1*|PSg- PS,|, we can then generate the 
distance matrix shown in Table 1. To avoid the same 
value being shown up in distance, we assume some non- 
integer values for position. 
Table 1: Distance matrix generated from cost function 
  
  
  
Distance Position in Right Image 
1.0 2.03.115.0:6.07.0:8.1510.0 12.0 
; 2.071"10:'0.0'1.73.0v%.0/5.0 6:7 8.0'10:0 
Y t 4.0 |. 3.0.-.2.0. 0,9 1.0.2.0 3.0 4.1 (6.0.8.0 
3 : 5.001540 3.0 1.9 0.0 1.0 2:0 3.1 5.0 . 7.0 
: 1| 8.0| 7.0 "6.0 4.9 3:0 2.01.0 0.1 2.0 4.0 
: " 9.0 | 8.0 7.0 5.9 4.0 3.0 2.0 0.9 1.0 3.0 
i g 10.0.1] 9.0. 8.0.6.9:5.0 4.03.0 1.9- 0.0 2.0 
h 12.0 111.0.10.0.8.9 7.0 6.0 5.0.3.9 .2.0 .0 0 
  
  
  
  
  
In this distance matrix, we first search column by 
column and then row by row for the smallest distance, 
and then put it into the smallest distance map which 
has been initiated with value -9 (Table 2). 
Table 2: Minimum distance map 
  
Position in Right Image 
1.0 2.0°3.1 5:0.6.0 7.0 8.1 10.0 12.0 
  
  
  
  
  
20/1 0 -9 9 -9 -9 -9 -9 -9 11 |C 
F t 4.0|-9 -9 09-9 -9 -9 -9 -9 -9|1 r 
: 5 50-9 -9.-9 0 1 -9 9 -9 -9 1 M 
: I 8.0]1-9 -9 -9 -9 -9 1 0 -9 -9|1 n 
9 ; 9.01-9 -9 -9 -9 -9 -9 0.9 -9 -9 |-1 ! 
i 9 10.0] -9 -9 -9 -9 -9 -9 -9 0° 95b t 
n 12.01-9 -9 -9 -9 -9 -9 -9 -9 On " 
-Ms dM, per 1 1 1 k 
Row for Marking a 
  
  
  
  
  
  
if more than one minimum distance appears in one 
row/column of the minimum distance map, it means 
that some extra feature exists (i.e., there are one-to- 
many correspondences). Therefore, we need to select 
the very smallest as the best matching feature (marked 
1 in the marking column/row and -1 on the extra 
474 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
linear feature). For example, in Table 2, for position 
2.0 in the left image, there are two candidates in the 
right image (see row 1: 1 and 0), giving -1 and +1 in 
the marking row to indicate the extra candidate and the 
best matching candidate. 
According to the marking, we can extract the 
corresponding features from each set of conjugated 
epipolar lines. As a result of this principle, the final 
matching scheme is indicated by the arrows in Table 3. 
Table 3: Marking and extraction of best matching 
feature pairs 
  
position in right image 
1.0 20 3.1 50 60 7.0 81 10.0 12.0 
-1 1 1 1 -1 -1 1 1 1 
a. 
2.0 4.0 5.0 8.0 9.0 10.0 12.0 
| 1 1 1 1 “1 1 1 
  
  
position in left image 
  
  
  
4. IMPLEMENTATION 
The cost function used in the string matching algorithm 
will involve several attributes of the linear features, but 
the corresponding weight assignment will be the critical 
parameter for correct matching. Several experiments 
need to be carried out in order to get the correct 
weighting for the various attributes. Based on our 
knowledge of the influence of these various attributes 
on the matching process, the conclusion reached was to 
assign weights to the attributes in proportion to their 
reliability and the derived magnitude which expresses 
their similarity (e.g.,|PS()-PSQJ) |,| SF(I)-SF(J) | ,etc.),s0 
regulating the influence of each attribute that in the 
result poor attributes will not overcome good attributes. 
As a result of aerial triangulation and the possibility of 
providing the system with good provisional positions of 
conjugated points, a higher weight was assigned to the 
position attribute (|PS(I)-PS(J)|) than to other 
attributes. On the other hand, attributes which are 
related to the grey level are given a smaller weight 
mainly due to a lack of reliable information about the 
scanning characteristics, terrain characteristics etc. As 
an example, the following cost function was chosen: 
If it is peak-to-peak or valley-to-valley : 
d(LJ) =1* |PS(D-PS(J) | +0.05* | SF(I)-SF(J) | (2) 
+0.05* | SB(I)-SB(J) | 0.01* | GL(I)-GL() | 
     
   
  
   
  
  
  
  
    
  
  
  
   
  
  
  
    
    
   
     
  
  
   
   
   
   
    
   
   
   
  
   
   
  
   
   
   
   
    
If it is 
d(LJ) 
The n 
chara: 
reliab 
canno 
it wo 
mode. 
featur 
ampli 
sign t 
absoh 
mean: 
which 
would 
trying 
would 
Fig. 2 
c wou 
is ver) 
situat 
Fig. 2 
Since 
(or vi 
The s 
mode 
cost | 
distan 
matri 
The r 
leadir 
only 
before 
minin 
one y 
the e 
situat 
incori