A five-eye camera head, shown in Figure 1 (b), handles 
the distance range of 2 to 15m using 8mm lenses. An 
example scene and its range image are shown in Figure 2. 
The stereo machine outputs a pair of intensity and depth 
images at 30 frames/sec. 
3. THEORY FOR THE STEREO MACHINE 
3.1 Multi-Baseline Stereo theory 
The stereo machine employs multi-baseline stereo theory 
(Okutomi and Kanade, 1993). Assuming that stereo 
images have been rectified, the disparity dis related to the 
distance z to the scene point by: 
Il 
"n 
NI-— 
I 
wx 
(1) 
Ulo 
where B and F are baseline and focal length, respectively. 
This equation indicates that for a particular point in the 
image, the disparity divided by the baseline length (the 
inverse depth C) is constant since there is only one dis- 
tance z for that point. If any evidence or measure of match- 
ing for the same point is represented with respect to Gi 
should consistently show a good indication only at the sin- 
gle correct value of { independent of B. 
The SAD* (Sum of Absolute Difference) over a small win- 
dow is one of the simplest and most effective measures of 
image matching. For a particular point in one image, a 
small image window is cropped around it, and it is slid 
along the epipolar lines of other images. Suppose that the 
stereo camera head has a base camera fy and n inspec- 
tion cameras (f, | k=1,..n}, forming n stereo pairs. For 
each stereo pair we compute the SAD value (SAD, 
k=1,...n) for a pixel (i,j) of fo with respect to C. 
SAD, (i,j) = AD, (st, 0) 
she Wij) 
m * [f(s +c, 8,: 9. te 05: (B: 0f GS 0| 
(s.D € W (i, j) (2) 
where AD, is the absolute difference between fo and fr, By 
is the baseline length between fy and fy, c = (C1,C2) is the 
unit vector pointing the direction of the epipolar line in f for 
the pixel (ij) of fy and W(i,j) is a small window cropped 
around the position (i,j). 
The curves SAD1 to SAD3 in Figure 3 show typical curves 
of SAD values with respect to Ç for individual stereo image 
pairs. Note that, as expected, these SAD functions have 
the same minimum position that corresponds to the true 
depth. We add up these SAD functions from all stereo 
pairs to produce the sum of SADs, which we call SSAD-in- 
inverse-distance. 
  
* Multi-baseline stereo theory originally adopted SSD (Sum 
of Squared Difference) and SSSD (Sum of SSD). Here 
SAD and SSAD are adopted for low-cost, high-speed 
machine implementation. 
n n 
SSAD(i,j,C) = SAD 0= S AD 51.0) 
= i (s.D e w (i, j) 
K= 1 K= 1] (3) 
The SSAD-in-inverse-distance has a clearer and less 
ambiguous minimum than individual SADs. Also, one 
should notice that the valley of the SSAD curve is sharper 
than SADs, meaning that we can localize the minimum 
position more precisely, thereby producing greater preci- 
sion in depth measurement. The algorithm has been suc- 
cessfully tested with indoor and outdoor scenes under a 
variety of conditions (Okutomi et al., 1992, Nakahara and 
Kanade, 1992). 
  
- > 
Figure 3: SAD and SSAD functions 
  
3.2 Geometric Rectification and Correction of Images 
The calculation of absolute difference AD, in equation (2) 
assumes inputs of rectified images. In general, however, 
since multiple stereo cameras are not perfectly aligned, 
and/or optical systems are not perfect, video rate image 
rectification and correction are required. 
Suppose we have multiple images {fy | k=0,...n} which are 
not rectified. Then the squared difference ADy(s,t,C) has 
the following expression. 
AD, (s,tC) = |f (8.10, Jp (8. t, Q) -f, (ly (G0. J9 (S. 0) | (4) 
Here I, and J, are functions of rectified coordinates (s.) 
and C, while lg and Jg are functions of only (s,t) (Figure 4). 
Either strong calibration methods (Tsai, 1987, Kimura et 
al., 1995) or weak calibration methods (Faugeras, 1992) 
enable us to obtain these functions. 
  
image f. 
  
image fo s Jo(s.t) 
t 
I(sitr-------—- 
«(S Q) 
interpolated pixel values 
Absolute Difference 
Figure 4: Calculation of Absolute Difference with 
Geometric Correction and Rectification 
  
   
  
  
  
  
  
  
  
  
  
  
3.3 Summary of the Algorithm for Hardware Imple- 
mentation 
The algorithm implemented on the stereo machine con- 
sists of three steps as shown in Figure 5. The first step IS 
412 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B5. Vienna 1996 
  
the Laplac 
images. T 
removes tl 
due to diff 
second ste 
geometric 
function. T 
localizatiot 
mine the i 
lyzing the | 
The total 
the SSAD 
where N° 
parity rang 
operations 
frames pe 
including i 
culation of 
= 6, and F 
giga-oper: 
the multi-k 
tage of th 
a result it 
ate for hai 
a 
4. AR 
Figure 6 i 
sists of 1 
(five-eye 
Laplacian 
and paral 
ization of 
The mact 
Figure 1) 
PLDs, hic 
mercially 
the syste 
video car 
cessor bc 
*The SS, 
and Jo-J 
Using the 
lute differ 
The table 
loaded w|