over the stereo extent of the imagery. The second stage 
involves the calibration of the sensor and the production of a 
mathematical model of the sensor used to acquire the imagery, 
thus allowing conjugate points detected by the stereo-matcher 
to be transformed into 3-D [x,y,z] co-ordinates generated by 
the camera model onto a regular grid so that the results may be 
manipulated easily and comparisons can be made between 
different data more easily (figure 2). 
  
  
  
  
  
  
  
  
  
left Right 
image image 
out 
Stereomatcher je 
   
      
  
  
  
  
Sensor model 
  
  
  
  
Interpolator 
  
Regular 
DEM 
  
  
  
Fig. 2: Flow chart showing DEM production. 
2.1 STEREO-MATCHING. 
Earlier work on the same rig (Deacon et al, 1991) yielded 
absolute accuracy to within 0.5 mm (rms). This accuracy is 
higher than that required by either orthodontic or orthognathic 
surgeons. However, the problem being addressed here is not 
that of accuracy but of sampling density of the data. In order to 
increase the amount of data, the extent of the imagery 
successfully stereomatched needs to be greater. Area based 
stereo matching techniques such as the Adaptive Least Squares 
Correlation (ALSC) region growing methods (Gruen, 1985; 
Otto & Chau, 1989) requires an initial set of corresponding 
points (seedpoints) in the left and right images to begin stereo- 
matching. Feature based matching which extracts a few 
distinctive features (edge, line, interest etc) from the images 
with the aid of some operator is used. The selection principle 
of these interest points should fulfill five requirements. These 
are distinctness invariance, stability, seldomness and 
interpretability (Foerstner, 1986). The interest operator used is 
the Foerstner interest operator based on the error ellipse of the 
normal equation matrix N 
YG % Y GyGx 
|Xoyox Yo*, 
where Gx and Gy are the partial derivatives in X and Y 
respectively. The sums are calculated in a user specified 
window size (typically 7x7). The output of the conjugate 
points of the Foerstner operator are used to initiate the 
stereomatcher (Allison et al, 1991). These seedpoints are 
always determined from the highest resolution images. 
A coarse-to-fine matching strategy (Zemerly et al, 1992) 
consisting of four image resolution levels was used. Each 
higher level image was reduced by a factor of two begining 
with an image size of 512x480 at the bottom and one of 32x30 
at the top. Matching begins at the upper most level, with the 
     
   
co-ordinates of the seedpoints determined at level 0 having 
been reduced by the necessary factor. All the successful 
matches are then cascaded onto the lower level. The initial 
seedpoints are again reduced by the necessary factor for this 
level plus all the points inherited from the top level all used in 
this new level. This process continues until the lowest level of 
the pyramid is reached. 
Seed 
points 
Level 4 
(Reduction factor 16) 
NS 512x480 Level 
image 
  
Fig. 3: Illustration of the coarse-to-fine matching. 
The stereo-matcher is based on Gruen's adaptive least 
squares correlation algorithm, ALSC (Gruen, 1985) 
extended by Otto and Chau's region growing algorithm (Otto 
and Chau, 1989). The technique basically works as follows: 
Co-ordinates of initial pairs of approximately matching points 
in the left and right image are determined either by hand 
digitising on a workstation screen using a mouse, or by the 
use of interest operators. Each of these seed stereo-matches 
can be used to determine a disparity vector linking the image 
points. Five or six disparity values are required to allow the 
automatic sheet growing stereo matching algorithm developed 
at University College London *, to be applied to the images. 
Gruen's algorithm considers a patch of area around a 
seedpoint in the left image and finds the patch in the vicinity of 
the corresponding seedpoint in the right image such that the 
sum of the square of the differences between the grey levels in 
these patches is minimised. The patch is allowed to be 
distorted in the right image by an affine transformation ( i.e 
simple rotation, translation and scaling), and different 
illuminations are allowed for by multiplicative and additive 
constants. The location of the matching point in the right image 
is thus improved from the initial estimate provided by the 
seedpoint, to the pixel most closely corresponding in the right 
image to the seedpoint in the left. The disparity for the point is 
found by subtracting its co-ordinates in the right image from 
coordinates in the left. 
Gruen (1985), has shown that the "precision" of the match can 
be expressed as the maximum eigenvalue of the shift 
parameters in the covariance matrix. The magnitude of this 
eigenvalue is inversely proportional to how good the match is. 
Consequently a maximum eigenvalue is specified, and if the 
best match has eigenvalue above this limit then it is considered 
to have failed and the point is rejected. Otto and Chau (1989) 
use ALSC to grow a region of matched points from the initial 
seedpoints and then from subsequently matched points. It 
takes a point in the neighbourhood of a matched point in the 
left image, and uses ALSC to find a matching point in the right 
image starting at the same disparity - thus increasing the 
number of matched points by one. The region continues to 
grow in this manner until it extends it in all directions 
producing a point with eigenvalue exceeding the acceptable 
limit. 
* 3.D Image Maker won the 1990 British Computer Society 
award for Technical Innovation.