In addition two other pairs which had lower resolution but 
covered a large part of the area were selected. Details of 
the image pairs matched are summarised in table 1. 
2.1.2 Matcher Parameters 
All pairs were stereo-matched using one manually se- 
lected seed-point, sheet-growing on a 4-pixel grid with a 
15-pixel square patch. Constraints were: 
e Maximum number of iterations = 10 
e Maximum eigenvalue of translation part of vari- 
ance/covariance matrix = 0.02 
Maximum absolute grey level difference between 
patches = twice standard deviation of left hand im- 
age 
e Minimum r? between patches - 0.4 
These parameters and constraints are based on previous 
experiments. 
Matches were transformed to ground co-ordinates using 
Cook's block adjustment software [Muller et al. 92]. 
2.1.3 Quality Assessment 
Figure 2 shows the coverage of the half-mapsheet ob- 
tained from each pair, and the statistics resulting from 
comparison of stereo-matcher derived elevations with the 
d USGS DEM. A blunder is defined as a point with an 
absolute elevation error exceeding 31/02 + 02, where c, 
is the matcher derived estimate of the elevation accuracy 
and c; is the estimated error introduced by comparing the 
elevation with an interpolated surface. o; is computed on 
the assumption that USGS elevations have a standard- 
deviation accuracy of 0.5km, based on their contour inter- 
val of 1km. 
2.1.4 Mapsheet Preparation 
All matches obtained were combined using Kriging to 
produce a single DEM. The Kriging process requires an 
estimate of the variogram of the terrain being interpo- 
lated, which was obtained from the elevations derived 
from pair 631A58 & 639A91, which appeared to be the 
most blunder-free. This indicated a variance sill of 6km? 
at range of 1.66°; however, noise in the samples (esti- 
mated as 757m standard deviation, see Table 1) caused 
us to revise our estimate of the variance of the underlying 
terrain to 5.43kn?. The resulting DEM is shown in Fig- 
ure 1, and should be compared with the adjacent manually 
derived USGS DEM. The major features show excellent 
agreement. The stereo-matched data shows a lot more 
fine structure, some of which is noise but much of which 
is associated with geological features, notably Ma'dim Val- 
lis. 
The Kriging process also produces a quality assurance 
map, shown in Figure 2. This is an estimate of the 
standard-deviation accuracy at each DEM grid-point, and 
reflects the estimated accuracy of the data from which the 
elevation at the grid point was interpolated, and the effect 
of the variogram on interpolation over a distance. The de- 
creasing confidence caused by interpolation across holes 
is seen as regions of high estimated c, and the regions 
802 
where more accurate measurements are made possible 
by higher resolution, higher match density or better base 
to height ratio pairs causes the darker areas. 
On comparing the regions of our Kriged DEM for which 
we estimate a better than 0.5km standard-deviation er- 
ror with the USGS DEM, we obtain a mean difference of 
0.07km and a standard deviation difference of 0.84km. 
Note that we generally find Kriging to produce optimistic 
estimates of quality; results are worse because errors are 
not uncorrelated, and some blunders produce quality es- 
timates indicating high accuracy. 
2.2 Valles Marineris 
The previous section showed application of the stereo- 
matcher to "typical" Viking stereo-pairs. Here is shown 
what can be achieved with higher resolution images. 
Unfortunately, stereo coverage at such resolutions is 
only available over a small proportion of the surface of 
Mars [Muller et al. 92]. 
Figure 3 shows one such high resolution image pair 
(details in Table 3). Figure 4 shows the DEM obtained 
by colleagues at the Open University [Thornhill et al. 92] 
using UCL's matching software, and Figure 5 the corre- 
sponding extract of the USGS DEM d the differences 
are: u =-7.377km and o =1.588km. Further analysis of 
the DEM obtained may be found in [Thornhill et al. 92]. 
3 Shape-from-Shading 
Shape-from-shading is potentially useful for extract- 
ing the small-scale detail lacking in our stereo-derived 
DEMs. However the DEMs obtained must be treated 
with caution due to the errors introduced by im- 
age noise, incorrect radiometric calibration, uncertain- 
ties in the reflectance function and atmospheric effects 
[Jankowski and Squyres, 91]. 
As input we require a single radiometrically corrected 
image which is then ortho-projected using an inverse cam- 
era model and any available elevation information (a sin- 
gle representative elevation value, the USGS a DEM or 
a stereo-matcher derived DEM). Figure 6 shows image 
057A45 ortho-projected using the stereo-matched DEM 
from Figure 4. 
3.1 Algorithm 
The Frankot and Chellappa shape-from-shading algorithm 
[Frankot and Chellappa, 88] is used. Unlike most other 
published shape-from-shading algorithms, it computes a 
set of integrable gradients at each iteration, rather than 
attempting to fit a surface to a not-necessarily integrable 
array of gradient estimates as a post-processing opera- 
tion. It is also a true surface algorithm, rather than dealing 
with for example: adjacent profiles or characteristic strips. 
The algorithm consists of a user-specified number of 
iterations, each iteration includes the following steps. We 
start the algorithm with arrays of gradient estimates (x anc 
y) set to zero. 
estimates using a 3x3 
in 
the gradient 
This step has its heritage 
e Smooth 
convolution.