Estimation of the Shape of the Matching Windows
Because each satellite image have a different viewing angle and direction, the size and rotation of a region (a window for stereo matching) on one scene differ from those of a region on the other scene that represents the same region. Thus, the window patch should be set differently for each scene using the viewing angles and directions of the satellite images.

Figure 2 Window ratio estimation



Figure 3 Window rotation estimation
Let us assume the geometry shown in Figure 2. Let the incident angle of left image and the right image be "a" and "b", respectively. Then the ratio of the windows can be represented as below.
Window Ratio=cos(b)/cos(a)
In general, the incident angle can be calculated from the viewing angle that can be found in the SPOT header file by solving the equations. Based on this ratio, we can determine the size of the search window relative to that of the object window.

As explained in the section 2, the images acquired by linear push-broom type camera have the epipolarity represented by non-linear equations called the epipolar curve. However, because the curvatures of the epipolar curves are not severe in the matching window, the epipolar curve can be approximated as a linear equation. Because the rotation angles of the windows can be calculated from the epipolar lines, the matching windows can be set as shown in Figure 3 so that the areas included in the windows should be as identical as possible.

Region Growings and Estimation of the Local Support Regions
In order to extract reliable DEM, it is essential to find conjugate pairs for all images. It is time-consuming to search whole search image to find the matching points for one point on the object image. Thus an efficient strategies that restricts the search areas must be considered. In this paper, the region growing approach is employed so that the knowledge of the previously matched points can be efficiently utilized. However, this approach has the problem of the blunder propagation – the error of the parent is propagated to its child [Kim, 1998].

We can assume that the candidate points (trying to match) have similar height to that of neighboring points because the abrupt changes in height is highly unlikely in 10m on the ground. Based on this assumption, we can estimate the local support regions using the indirect method of linear push-broom imagery [Kim, 1999b]. Through the estimation of the local support regions, the search area can be reduced. Thus, the time of the whole process can be minimized.

The Zero Mean Normalized Cross Correlation
Gray level correlation is the simplest but robust method as a similarity measure.[ Lemmens, 1988]. In various method for correlation calculation - cross correlation, Gaussian and Laplacian, etc., we employed the zero mean normalized cross correlation defined as below as a similarity measures because the different gray level distributions between two scenes should be normalized somehow.

Where L_i and R_i are the elements of the window in object and search image, L_avg and R_avg are the average of the elements and the match point have the maximum correlation.

Stereo matching Algorithm based on the Geometry of the Satellite
In the previous sections, we have explained the techniques used in our algorithms. We now describe the complete stereo matching algorithm based on these techniques.

1. Set up the camera model of the satellite. The camera model is used to estimate an epipolar geometry.
2. Select an initial seed points used candidate points. In our algorithms, an initial seed points are selected by users or extracted from the ground control points automatically.
3. For each point y) (x, in object image, estimate the local support regions on search image and the shape of the window for both images.
4. Find a maximum correlation point.
5. The 4-neighbourhood points of the match points are selected as candidate points. To preserve these candidate points, queue data structure is generally used.
6. Iterate the (3) ~ (6) process until there are no candidate points.

As described above, the complete stereo matching algorithm is an iterative process. Therefore, the size of the window and the local support regions is related to the execution time.