International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
  
  
Figure 4: The first two images of Fig. 3 in epipolar geom- 
etry. 
columnwise from left to right, i.e. by moving along the 
scan line. Each column with known costs represents the 
set of all partial solutions up to that point. The next col- 
umn will be filled in such that the best possible solution 
found so far is extended. Pointers to the preceding solution 
are stored in the matrix so that one can trace back to re- 
cover the complete path of position/disparity pairs for the 
final solution (Fig. 8). 
For each cell (4, 7), its costs Cj ; are defined by 
Cj mm Ci,j-1 + Ci; (4) 
where P; ; is the set of allowed predecessor rows of (3, j) 
and C; are the costs to include (7, 7) into the solution. 
I.e. the best solution found so far among all valid prede- 
cessors will be extended by the current position. 
The costs C . have been set to 
4:3 
à as m 
e = 1 = Tj,j+i (5) 
where rj j4; is the cross correlation coefficient between 
both image locations (z is the disparity, i.e. an offset to 
the one-dimensional position 7). 
2.4.2 Constraints Three constraints have been applied 
to guide the matching process such that recovered depth at 
the borderline of the polygon matches the borders and that 
in the interior a smooth surface will be generated. 
(a) Start and end cell In a general setup, one would have 
all cells of the first column as start cells. After cost propa- 
gation through to the last column every row is a valid end 
cell with known total costs. The one with the least costs 
would be chosen and backtracking reveals the correspond- 
ing start cell. 
Here, the disparities at both ends can be computed from the 
known polygons. This allows to give only one start cell on 
which all intermediate solutions will be based. The end cell 
will no longer be chosen based on its costs, but according 
to the disparity at the other end. At first glance, it seems 
counterintuitive not to choose the globally optimal solu- 
tion, but it is reasonable because the path that links pre- 
defined start and end cell still is the optimal path between 
these two. 
Disparity 
di,» Cui 
di, Ci 
d; C ij-1 pz Ci 
di, € riii 
di.» Cri 
j-l Xi Position 
Figure 8: Path through the cost matrix. The lower left tri- 
angle is missing because of the given start cell and the or- 
dering constraint. 
(b) Ordering constraint The most important constraint 
to get a feasible path is the ordering constraint (Koch, 
1997). It is obvious that the order of object points given 
in one image can not be reversed in the other image be- 
cause in this case the view would be blocked. This limits 
the change of disparity between neighbouring pixels to no 
more than £1. Thus we define the set of valid predecessors 
as 
sam dds dS Sd (6) 
  
(c) Neighbouring scan lines One of the problems with 
a scan line oriented approach is how to deal with neigh- 
bouring scan lines. If they are processed completely un- 
related, it happens in borderline cases that a wrong path 
is chosen and large jumps in disparity occur between con- 
secutive lines. A penalty Cj had been introduced to keep 
disparity values on one line close to those of the preceding 
line which extends the previous definition of CP; 
0 ) 
CX rd im eT) a Ÿ C; (7) 
p ommno (8) 
where 7g referes to the disparity of the current line and 2-1 
to that already found for the preceding line. c is a small 
constant factor to affect the influence between neighbour- 
ing lines. Since there exists a closed polygon of initial val- 
ues, there are always reference disparities available. 
2.5 Creation of the Depth Map 
After guided correlation, there exists a disparity map for 
each combination of input images. For the three input im- 
ages shown in Fig. 3, three disparity maps are calculated. 
First, each of them is converted to a depth map by triangu- 
lation using the recovered camera parameters. 
Additionally, the 3D coordinates can be reduced to 2.5D 
(two spatial dimensions plus depth) by subtraction of the 
given surface plane of the wire frame model. This results 
  
   
        
   
    
   
  
  
   
   
   
   
   
   
   
   
   
    
  
  
  
    
  
   
  
   
   
    
    
    
  
   
   
    
     
  
   
  
   
  
  
  
  
  
   
Inte 
— 
Fi 
ius 
of 
on 
De 
lay 
thi 
de 
an 
de 
2. 
Si 
on 
CO 
SO 
ul; 
an