Keywords: Digital Elevation Model, Stereo Matching, Epipolarity, Region growing

Abstract
The DEM is a digital data in which each point represents latitude, longitude and height. In the various ways to extract the DEMs, the use of the satellite images has many advantages. However, because of the characteristics of the satellite, it is difficult to apply the algorithms generally used. In this paper, we propose an accurate and robust stereo matching algorithm which is crucial to the quality of the DEMs. By considering the geometry of the satellite, we estimate the shape of the windows and the local support regions, Also we minimize the blunder propagation. To show the performance of our algorithms, we compared ours with the algorithms generally found in image processing textbooks on 6000x6000 SPOT panchromatic images. Based on the results, our algorithms show a good performance in the execution time and the accuracy.

Introduction
The Digital Elevation Model (DEM) is a digital data in which each point represents latitude, longitude and height. There are various ways to produce the DEMs from many types of sources such as airborne images, satellite images, etc. The use of satellite images from the DEM generation has the following advantages. 1) A scene covers larger area. 2) The satellite images are naturally digital data so that the automation can be achieved. 3) Nowadays, many remote sensing satellites are launched and it is becoming easier to get in hand. However, even if it has advantages as stated above, generating the DEMs from the satellite images suffers from shortcomings – accuracy, coverage and time.

Extracting DEMs consists of pre-processing, camera modeling, stereo matching and interpolation. Even though each step contributes to accuracy of the DEM, stereo matching is a crucial to achieve high accuracy and larger coverage of the DEMs and to minimize the execution time. If finding conjugate pairs from stereo scenes has errors, the heights must be erroneous. Moreover, when region-growing approach is employed, errors propagate to the whole DEMs. Also, the stereo matching algorithms often used in the DEM generation using aerial photos or 2.5D image generation from still camera that are set up in well-controlled manner. Mainly because; 1) Camera type is different. The position of camera changes line by line. 2) Noise due to haze and atmospheric distortion. 3) The intensities may be different so that the correspondence may be hard to be calculated if left image was taken in different date (for SPOT, always different) and/or season.

We propose a accurate and robust stereo matching algorithm that utilizes the characteristics of the satellite camera by considering followings.

• The epipolarity of the linear push-broom type camera
• The estimation of the matching window shape (size and rotation)
• The estimation of the local support regions
• The region growing algorithms and zero-mean normalized cross correlation

Integrating the above techniques, we could increase the accuracy of the stereo matching algorithms and minimize the execution time.

Epipolarity Of The Linear Pushbroom Camera
Generally, the epipolarity relation can be established in the stereo images that can be very useful in stereo matching process. However, the epipolarity for linear push-broom type camera is different from frame grabber type camera so that the equations found in image processing textbook cannot be applied [Kim, 1999a]. We derived the epipolarity for push-broom camera based on Orun and Natarazan’s camera model and we briefly summarize it here.


Figure 1 Epipolarity of the images
As shown in Figure 1, an epipolar geometry can be explained as this: one point in object image is mapped onto a unique line in search image. Suppose a beam of light is projected from the center of the left camera(Lc) through the point(Lp) on the object image. Each points lying on this beam(Li) can be mapped into the search image as a point. In the general images or airborne images, the epipolarity is represented as a linear equation. But the epipolarity of the satellite images acquired by the linear push-broom camera is represented as a non-linear equations as shown below[ Kim, 1999a].

Where (X_s, Y_s, Z_s) is the origin of the satellite sensor coordinate system, r₁₁~r₃₃ are elements of the rotation matrix which transform the satellite sensor coordinate system to the earth centered coordinate system and f is the focal length of CCD sensor. Also to model the satellite camera, Orun and Natarazan's camera model is used[ Orun, 1994].