GISdevelopment.net ---> AARS ---> ACRS 1989 ---> Mapping from Space

Relative DEM Production from SPOT Stereo without GCP

ASkihito Akutsu, Ryutaro Tateishi
Remote Sensing & Image Research Center, Chiba University
1-33 Yayoi-cho, Chiba 260 Japan


Abstract
The authors propose a practical method to produce relative DEM (digital elevation model) from SPOT level 1A stereo pair ore triplet images without using GCP (ground control points). Proposed method consists of 1) stereo matching by correlation, 2) calculation of an intersecting point of viewing lines by using satellite geometric data and 3) interpolation of random data to grid data. Proposed stereo matching technique is based on selection of target points by preprocessing of edge detection, search along approximate epipolar line and multi window matching. RMS of relative error of produced DEM with a grids of 25 meter was found to be less than 25 meter compared with a topographic map with a scale of 1:2:500. This relative error includes error by interpolation and errors by mismatched points. Therefore it is expected to improve the relative accuracy more after removing these errors.

Introductiuon
Since SPOT/HRV stereo data were provided, there were many papers on DEM production using SPOT digital data. These papers mainly consisted of two parts: (i) matching technique and (ii) generation of digital elevation model. The matching technique has generally been done by template correlation method. Recently the least-square matching method has presented by Forstner (1982) [1]. Rosenhoilm, D. (1988) [2] reported the application of least-square method to SPOT stereo image data. But the least-square method is effective only when accurate matching which in a pixel is necessary. Concerning with the matching technique using the correlation method, many investigations were done. Hattori, S. et al (1986) {3} reported the multi-step correlation method known as coarse-to-fine technique. In general, DEM was generated by obtaining parallaxes. To obtain parallaxes from satellite stereo images, image data should be rectified into epipolar aligned format. Otto, G.P. (1988) [4]showed that SPOT data could not be rectified into an exact "epipolar aligned" format without a DEM. Tateishi, R. et al (1988) [5] reported another method to obtain three dimensional coordinates of matched points by the calculation of an intersecting point of viewing lines which are derived from satellite geometric data and coordinate of matched point.

This paper proposes a practical method to produce relative DEM from SPOT level. 1A stereo pair or triplet images in the area where GCP are not available. The matching method is based on correlation technique. To calculate the matching points efficiently, the target points on one image are selected by edge detection and search area on the other image is determined by approximate epipolar line and maximum slope gradient. To eliminate mismatching, multiwindow matching (11 by 11, 15 by 15 and 29 by 29 pixels window matrices) is applied in the paper. Elevation of matched point is derived by the above method by Tateishi {%}. The grid elevation data are calculated from random DEM data using weighted mean interpolation. RMS of relative error of produced DEM is calculated by comparing with a topographic map with a scale of 1:2,500.

Spot Image
The Stereo Triplet Images Covered Mt. Fuji in Japan was used in this study. The parameters of three images are as follows:

    'Left image' 'Center image' 'right image'
Spectral mode : Panchromatic Panchromatic Panchromatic
Senaor : HRVI HRVI Panchromatic
Observation Data : March 17 1986 March 7 1986 March 8 1986
Viewing angle : 15.4 degree 4.3 degree 23.8 degree
    East East West
Processing level : 1A 1A 1A
Path-row : 329-279 329-279 329-279

The test area is Turu City near Mt. Fuji which includes 256 by 400 pixels. (Figure 5.)

Matching
  1. Selection of target point

    The purpose of relative DEM production in this study is to know terrain relief roughly even though the area has no GCP. For this purpose it is necessary to know relative position of ridges and valleys. Those points on ridges and valleys are extracted by edge detection. The matching target points is

    Selected at intervals of more than 3 pixels in x direction, and at intervals of 5 pixels in y direction.

    Edge sampling procedure:- Sobel operator was used for edge detection in this study. Target points are selected from the points, which have the maximum value of Sobel intensity and also have 35 or more sobel intensity (s) is calculated from 3 by 3 pixels as follows:


    Sobel Intensity difference is defined as the difference of maximum and minimum of Sobel intensity, which are calculated along x direction and y direction in local area of the image.

  2. Restriction of search area

    For a target certain point in a image, window in the other image is moved in the search area to extract the best fit point. Search area should be as small as possible for efficient computer processing. Y direction of search area can be restricted by approximate epipolar line and x direction can be also restricted by maximum slop gradient. Dark blue parallelogram with the size of 4 pixels by 14 pixels in Figure 5 shows the search area determined by the following method.

    Approximate epipolar line:- The gradient of approximate epipolar line is defined as the following equation (see in figure 1) :


    The gradient is calculated by using a set of corresponding points in one line. This calculation is based on least-square method. The calculated gradient is used in the matching on the next line. Initial gradient is derived from the following equation (see in Figure 2):


    In this study, initial gradient of right image was 0.065 for a pair of right and center images, and the one of left image for a pair of left and center images were -0.015. Gradient is computed in every matching line until the difference between calculated gradient of two consecutive matching lines becomes smaller than 0.005. An approximate epipolar line is shown as light blue band in Figure 5.


    Figure.1 Approximage epipolar line of stereo pair image.


    Figure.2 Calculation of initial value of gradiaent of approximate epipolar line.

    Maximum slope gradient:- Figure 3 shows search range along an approximate epipolar line. The point A' has been already matched to the point A. the point B is the next target point. When the maximum slope gradient O and a satellite geometric data are given, the point B should be projected between the point B' and the point C'. We assumed in this study that the maximum slope gradient is 45o. The restriction of search area in x direction is shown as light blue rectangle in Figure 5.


    Figure 3. Research range along approximate epipolar line.

  3. Matching Procedures

    Before the matching processing, one pair of corresponding points should be given. Matching processing is based on correlation method with search area restriction. The sizes of three matrix windows for computing correlation coefficient are 11 by 11, 15 by 15 and 29 by 29 pixels. The whole three correlation coefficients are not always calculated. Three matrics are considered to have hierarchical structure. The correlation coefficient is calculated in order from high hierarchy to low hierarchy. If the matched point is judged as poorly matched point, the correlation coefficient is calculated again in second hierarchy. The judgment of matching is based on a correlation coefficient and a distance between matched point which has correlation coefficient. 1.0 and distance 0.0 is judged as the best matched point. In the case of correlation coefficient is poor but distance has smaller value, the matching point is judged as matched point. If distance has large value but correlation coefficient is better, the matching point is also judged as matched point. In this study, the high hierarchy was 15 by 15 matrix and low was 29 by 29 matrix. These matrices were experimentally selected by assuming that small matrix was effective with large distortion and large matrix was effective with poor features in local area.15 by 15 matrix was regard as standard in matching process. These matrices were set by considering process speed. In triplet matching process, tripplet matching is performed as a combination of two stereo pair matching (a pair of Center and Right image, and a pair of Center and Left image). Common target points in the Center image are used for two stereo pairs.
Calculation of Random DEM
Triplet matched points data were used for producing DEM. Random DEM is obtained from three dimensional coordinates of matched points. Three-dimensional coordinates are calculated as intersection of viewing lines. An intersection is defined as the point which has the lease square value of three distances to three viewing lines as is shown in Figure 4. A viewing line is defined by satellite position and look direction.


Figure 4. An intersection of triplet viewing lines by least square method.

Interpolation
The relative DEM with a grid of 25 meter is produced by using weighted mean interpolation. Interpolated elevation is derived from nearest four random DEM. Nearest four points are selected directionally, that is one for each direction of 90 degrees. The used weight value was the inverse of 1.5 power of the distance between random point and interpolated point in this study. This value is experimental value.

RMS of relative error
To calculate RMS of relative error, the produced DEM is compared with DEM from topographic maps with a scale of 1:2,500. That DEM is digitized with a grid of 25 by 25 meter grids, and is interpolated to a grid of 5 by 5 meters.

Results
  1. Result of matching

    The determined matching points are shown as green points in Figure 5. The total stereo and triplet matching points were about 2,000 points in our test area. It is clear that the matching calculation was efficiently performed in 15 by 15 matrix window (high hierarchy). 11 by 11 and 29 by 29 matrix was used to remove aberrant in matching processing. It was found out that these two matrices were effective in area with large distortion or poor features.

  2. Result of DEM production

    A white quadrangle in figure 5 shows the area for DEM production. The interpolated DEM image with 25 by 25 meters is shown in Figure 6 (b). This image is 63 by 75 pixels. The DEM from topographic maps of the same area is shown in figure 6(a). The histogram of DEM from map is shown in Figure 8. Elevation ranges from 380 to 980 meter.

  3. Result of RMS relative error

    Figure 7 is shown the difference between two DEMs. Overestimated elevation is appeared as red area and blue area shows underestimated elevation. The distribution of relative error approximates normal distribution. (Figure 9) RMS of relative error was 24.4 meter. RMS of relative error after removing mismatched points was approximately 20 meter.


    Figure.5 SPOT stereo triplet images


    Figure.6 DEM from topographic map and from SPOT.


    Figure.7 Difference two DEM.


    Figure.8 Histogram of elevation of DEM from topographic map.


    Figure.9 Histogram of relation error of DEM from SPOT.
Conclusion and Discussion
The authors produced relative DEM without using ground control point buys the proposed matching technique from SPOT stereo image. RMS of relative error was approximately 24 meters. This result was poorer than the result by Teteishi (5), which is less than 10 meters. The elatter is relative accuracy of correctly matched points, while the former includes the error by interpolation and mismatching. Mismatching points can be removed easily by comparing with the surrounding matched points. Large error by interpolation is caused by insufficient selection of target points. that is, target points should be selected from all ridges and valleys. There are some difficulties to extract ridgiies or valleys in shadow area. There are two solutions to reduce large error by interpolation. One solution is to add the processing to extract ridges and valleys in detail for the selection of target points. The other solution is to apply two-step matching. The proposed matching technique in this paper is considered to be the first step. In the second step, closely spaced matching points are generated in order to cover small ridges and valleys. It is expected that the result by using proposed matching technique is sufficiently improved by former solution.

Reference
  1. Forstner, W., 1982. One the Geometricprecisison of Digital Correlation. International Archives of Photogrammetry, Vol. XXIV . Comm. III, pp. 176-1189.

  2. Rosenholm, D., 1988. Multi-point matching along vertical line in SPOT images. INT. J. Remote Sensing, Vol. 9, NOS. 10 and 11, pp. 1687-1703.

  3. Hattori, S. C. Mori and O. Uchida, 1986. A Course-to-fine Correlation Algorithm Considering Occlusions. ISPRS, Proc. of the Symposium, From Analytical to Digital, Finland, pp. 317-328.

  4. Otto, G.P., 1988. Rectification of SPOT Data for Stereo Image Matching. International Archives of Photogrammetry and Remote SDensing, Vol. 27, Comm. III, pp. 635-645.

  5. Tateishi, R., Kuronuma, Y., Anzai, F. EVALUATION OF SPOT DATA FOR TOPOGRAPHIC MAPPING WITHOUT GCP. International Archives of Photogrammetry and Remote Sensing, Vol. 27, Comm. IV, pp