various 
parison 
Image 
>tween 
ined as 
1999), 
can be 
| 10-20 
erted to 
]ly, the 
ne Earth 
image 
h other. 
al. This 
>s since 
patches 
pipolar 
line). If 
4,). The 
Wonkyu Park 
where (X,, Y5) is the image coordinate of the center of a patch, (dx, dy) is the distance between the element in a patch 
and the center of a patch. The rotation of a right patch can be expressed similarly. 
23 Stereo matching strategy 
Matching starts from determining patch shapes and orientations described previous sections. For a given left patch, a 
right patch is defined at a point within a local support region and these two patches are compared each other to calculate 
asimilarity value. The point having the highest similarity value is selected as a corresponding point for a given left 
point. We have employed a zero-mean normalized cross correlation for the similarity measure (Lee et al., 2000). 
For completeness of DEMS, it is required to match points well-distributed over stereo pairs. For this, a region growing 
approach is employed. Matching starts from initial seed points selected by a user or generated automatically from 
GCPs. These points are considered as match candidates and matching applies to one of them. When matched, its four 
neighbor points are considered as match candidates. Matching continues for other match candidates until there are no 
match candidates left. Through this region growing, it is possible to match entire scenes. 
In summary, we now describe the stereo matching strategy based on epipolarity and scene geometry (Lee er al., 2000) 
Set up camera model of a left and right image using GCPs. 
Select initial seed points. 
Select a match candidate and find its epipolar curves in a left and right image. 
Estimate a local support region and patch shapes based on epipolar curve and scene geometry 
Find a maximum correlation point by calculating similarity values with respect to all points in a local support 
region in a right image. 
If a correspondence point is found, select its neighbor points as match candidate points. 
7. Forsuch neighbor points, calculate image coordinates of corresponding right points. 
8. Repeat Step 3 - 7 until there are no match candidate points left. 
CA op p c 
e 
3 OPTIMAL INTERPOLATION 
31 Interpolation schemes commonly used 
Many interpolation schemes for elevation data have been studied (Desmet, 1997, Carlson and Foley, 1991). Most of 
these schemes, however, do not deal with real elevation data but use a test data set with less than 100 elements. To 
determine the optimal interpolation scheme for satellite images, five interpolation schemes commonly used are 
evaluated using real elevation data from automatic stereo matching. 
Five interpolation methods are listed below (Kim ef al., 1999). 
€ Gaussian: elevation on a grid is calculated from the statistical properties of a terrain (x,)2X 6H (xj), where a 
weight function is given by exp[-(x;-x,)'/o"]. 
® Minimum curvature: the minimum curvature interpolation minimizes the curvature of a surface that is formed by 
interpolated elevations. 
© Kriging: elevation on a grid is calculated from the statistical properties of a terrain (x,)-X &-H(x;), where optimal 
weights for interpolating the elevation at x, are determined from variogram describing the spatial variation of 
terrain. 
* Multiquadric: elevation on a grid is calculated from the statistical properties of a terrain (x,)=X;-H(x;), except 
that a basis function is given as Q;(x,y) = sqrt((x-x; Y'Hy-yi) +R), 
® Modified Shepard: elevation on a grid is calculated from quadratic basis functions and inverse-distance weights are 
used. 
To test the interpolation method on the real elevation data from automatic stereo matching result, two regions are 
selected: one is smooth region and the other is rough. The parameters for each interpolation schemes are determined so 
that they perform best with input data. The accuracy is assessed by comparing DEMs from each schemes with truth 
DTED produced by NIMA, USA. The results are summarized in table 1. 
Kriging and Gaussian interpolation scheme performed best. The errorof Kriging was 37.8m and 44.4m, and that of 
Gaussian is 36.5m and 44.5m for two regions, respectively. Additional comparison shows that Gaussian interpolation 
scheme is superior. Since Kriging is exact interpolation, errors in stereo matching results appear unfiltered in the 
interpolation output. These errors, however, are smoothed out in Gaussian interpolation scheme (See figure 3). 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 707