The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
image pyramid was constructed consisting of five levels. 
Starting with the original image, each subsequent level was 
created by sub-sampling the previous level’s image smoothed 
by a Gaussian filter. Interest points were generated by Fòrstner 
operator (Fòrstner, 1986) at every image scale. 
Figure 3. Workflow of the hierarchical stereo matching process 
Matching started with the images of lowest resolution; results 
were then transferred to the next higher level, with more interest 
points being extracted and matched. The images, interest points 
and orientation parameters were used as input for the stereo 
matching process. At the lowest level, geographic locations of 
interest points were estimated by assuming a flat terrain. This 
enabled automatic pairing of interest points in stereo images. 
The search radius was confined to the neighborhood of the 
corresponding interest points, and matched points were selected 
based on correlation coefficient values. 
Automatic error detection is performed at each level by 
eliminating outliers based on elevation distribution of 
neighboring points. For each point, a small local DEM surface 
was constructed from the matched points and modeled as a flat 
terrain (may be improved to a plane). Then the standard 
deviation of the plane estimation, a, was calculated. If the 
residual of a point exceeded 2a, it was regarded as an error and 
eliminated. 
At subsequent levels, points from the previous level were 
matched again to achieve higher matching precision. A TIN 
(Triangulated Irregular Network) surface of parallax differences 
was generated from these matched points using the Delaunay 
triangulation method. This TIN was used to estimate the 
corresponding tie points. To improve matching performance for 
points located around the boundary of each CCD, HiRISE 
imaging geometry was fully utilized. Instead of mosaicking 
images from separate CCDs, we loosely stitched together the 
TIN surface based on the best-fitting alignment derived from 
interest point matching between adjacent CCDs. 
After matching the interest points generated from the highest- 
resolution images, 10-pixel grid points were defined to form a 
basis for further matching. To generate a 1-m-resolution DEM 
of the terrain, 3-pixel grid points were matched. For sub-meter 
level DEM, dense matching was performed for every pixel in 
the images of highest-resolution. Evenly distributed tie points 
between the stereo images were selected from the set of 
matched interest points to be used in the subsequent bundle 
adjustment. The final DEM was generated after bundle 
adjustment and elimination of matching errors. 
3.2 Matching performance evaluation 
We tested this process using a stereo pair of HiRISE images that 
cover the Columbia Hills area of the Spirit rover landing site 
(TRAJ301513 1655 and TRA_001777_1650). The 
TRA001513 image was obtained on November 22, 2006. It is 
centered at 14.6 °S latitude, 175.5°E longitude. It has 27.1 
cm/pixel resolution and 80,000 rows. The TRA 001777 image 
was taken on December 12, 2006. It has a resolution of 26.3 
cm/pixel and 40,000 rows. Its extent is entirely covered by 
TRA001513. The two images have a convergence angle of 
19.8 degrees. 
Level 
Image 
Scale 
Point 
Type 
Residuals (pixel) 
Mean 
Standard 
Deviation 
Maximum 
1 
1/16 
Interest 
0.26 
0.55 
1.41 
2 
1/8 
Interest 
0.19 
0.53 
2 
3 
1/4 
Interest 
0.13 
0.33 
1 
4 
1/2 
Interest 
0.18 
0.47 
1.41 
5 
1 
Interest 
0.19 
0.39 
1 
6 
1 
10-pixel grid 
0.06 
0.24 
1 
Table 1. Matching residuals at intermediate levels 
A quantitative evaluation of matched points was conducted for 
the hierarchical matching results. At each intermediate level, 16 
points were randomly selected throughout the entire study area. 
The automatically generated matching results were compared 
with manually matched points. Table 1 shows the results of this 
evaluation of matching accuracy. The highest mean residual 
was found at the first level. However, this mean was still less 
than 1 pixel, with maximum residual being 1.41 pixels. The 
largest error, 2 pixels, was found at the second level. Since 
interest points for levels 1 through 4 were projected onto higher 
resolution images and adjusted by re-matching, the errors from 
the previous levels were not propagated into subsequent levels. 
While the mean residuals did not necessarily decrease over the 
hierarchical process, they did remain at a reasonably low level 
providing accurate-enough estimates of parallax differences for 
use at the next level. 
At the final level, matching results of 3-pixel grid points were 
evaluated based on five test regions with different terrain types. 
Region 1 is a relatively flat area at the Spirit rover landing 
center. Region 2 is crater northeast side of Bonneville crater. 
Region 3 is the summit of Husband Hill. Region 4 is the Inner 
Basin area, located on the south side of the summit. Region 5 is 
Home Plate. 
Figure 4. Distribution of check points at five test regions 
989