Experiment Results
To show the performance of our algorithms, we tested three algorithms on 6000x6000 SPOT panchromatic images. For the quantitative accuracy assessment, we calculated RMS error by comparing the resulting DEMs with DTED which was produced by the USGS.

• Simple correlation algorithm (SPMatch)
• Adaptive least square correlation algorithm (ALSM)
• Our matching algorithm (EpiMatch)

In the simple correlation approach, the similarity between two patches was calculated using the zero mean normalized cross correlation. The adaptive least square correlation algorithm was proposed by Gruen [Gruen, 1985, Otto, 1989]. The region growing approach was used for all methods where the initial estimation is acquired from the result of its parent.

The 6000x6000 SPOT panchromatic images used as object and search image are shown in Figure 4 and 5. The results are summarized in the table 1 and the DEMs are shown in the Figure 6, 7, 8 and 9. As shown in Table 1, simple correlation algorithm takes long times however the coverage was good. But due to the blunder propagation (See Figure 7, white blobs (peaks) are errors), the accuracy of the DEMs is low. On the other hand, the accuracy of height calculated by adaptive least square correlation algorithms was high, but its coverage is substantially low (Figure 8). As shown in Table 1, RMS error of our method is 29.74m. Also, execution time was minimum of any other method at reasonable DEM coverage,

Figure 4. Object SPOT Image



Figure 5. Search SPOT Image


Table. 1 Experiment Results – Boryung, Korea

	SPMatch 3x3	TKMatch	EpiMatch
Execution Time	1h 26m 39.71s	22m 52.18s	11m 20.89s
Coverage	750125	126686	715262
Accuracy	88.04m	31.02m	29.74m

Figure 6. Truth DEM (DTED)



Figure 7. SPMatch DEM



Figure 8. ALSM DEM



Figure 9. EpiMatch DEM

In our results, any post-processing was not applied. However, if we post-process the DEMs (automatic), we can minimize the accuracy up to 20.5m. The accuracy of our algorithms is more superior to that of the PCI^Ò Software which have the accuracy of the 44.7m on the same stereo scene and the same GCPs in our experiments.

Conclusion
The extraction of the DEM from the satellite images has many advantages. But the characteristics of the satellite images make it difficult to extract the DEM. The reason is the difficulty of the stereo matching.

In this paper, we proposed the stereo matching algorithm based on the geometry of the satellite. Through the careful consideration of the satellite geometry, we could achieve high accuracy and minimize execution time in the process of the DEM extraction.

Acknowledgement
The work presented here is supported by Ministry of Science and Technology of the Government of Korea (Contract No. NN22820)

References

• Kim, T., 1999a, "A Study on the Epipolarity of Linear Pushbroom Images", Photogr. Eng. Remote Sens., (submitted).
• A. Orun and K. Natarajan, 1994, "A modified bundle adjustment software for spot imagery and photography : Tradeoff," Photogr. Eng. Remote Sens., vol. 60, pp. 1431-1437.
• Kim, T., Park W. K. and Lee, H. Y., 1998, "For better automation in DEM generati on from satellite images: Fuzzy logic approach for the determination of match quality," Proc. of ISPRS, (Ohio, USA).
• Kim, T., Shin, D., 1999b, " Development of a Robust Algorithm for Transformation of a 3D Object Point onto a 2D Image Point for Linear Pushbroom Imagery," Photogr. Eng. Remote Sens., (submitted).
• M. Lemmens, 1988, "A survey on stereo matching techniques," Proc. of ISPRS, vol. 27, pp. 11-23.
• Gruen, 1985, "Adaptive least squares correlation: A powerful image matching technique," South African J. Photogr., Remote Sens. & Cartogr., vol 14, pp. 175-187.
• G. Otto and T. Chau, 1989, "A region growing algorithm for matching of terrain image," Image and Vision Comp., vol. 7, pp. 83-94.