This paper presents a matching algorithm for automatic DTM generation from SPOT images that provides dense, accurate and reliable results and attacks the problem of radiometric differences between the images. The proposed algorithm is based on a modified v

SPOT stereo matching for DTM generation

Page 6

generally smoothly changing (average slope 7 ). The 1225 DTM was derived from 252000 height values, has an accuracy of 4.1 m and a height range of 1500 m. Although it is not the most extreme case that can be encountered in Switzerland, the terrain is in most parts steep (average slope 18 ). Forests cover ca. 20% of map sheet 1224 and 35 - 40% of map sheet 1225. In the latter there are also lakes covering ca. 4% of the area. Some clouds were present. The radiometric differences were larger in map sheet 1224 which included agricultural areas. In a previous test published in Baltsavias and Stallmann, 1992b the accuracy potential of the algorithm was tested by using good approximations that were derived from the reference DTMs. For matching, the following 5 different versions were compared: Version 1: patch size 17 x 17, no geometric constraints, conformal transformation Version 2: patch size 17 x 17, constraints, conformal transformation Version 3: patch size 17 x 17, constraints, shifts only Version 4: patch size 17 x 17, constraints, conformal transformation, grey level images Version 5: patch size 9 x 9, constraints, shifts only All versions used gradient magnitude images with the exemption of version 4 that used grey level images. The aim was to compare constraints vs. no constraints, grey level vs. gradient magnitude images, conformal vs. shift transformation, and shifts with different patch sizes. The case of af ne transformation was excluded a priori because in many cases it is not stable since the selected points lie at edges and thus two scales and one shear are often not determinable. Table 1 shows the difference between the 34000 - 38000 matched points and the reference DTM, whereby the cleaned data refer to the matching results after automatic blunder detection.

Table 1

Differences of estimated heights (cleaned data) to heights bilinearly interpolated in the reference DTM (in meters) 1224 max. absolute 31.0 33.8 38.7 40.9 41.7 RMSE 7.2 8.5 9.5 9.6 10.2 mean+1.8+2.7+2.9+3.3+2.7%≥ 40 m 0.0 0.0 0.0 0.0 0.0 max. absolute 42.9 44.8 47.6 48.0 52.7 RMSE 8.9 9.4 11.2 10.0 10.7 1225 mean+1.1+1.5+1.1+2.3+1.5%≥ 40 m 0.0 0.1 0.2 0.1 0.2

In the here presented test, the same points were matched but their approximations were derived by a hierarchical approach using image pyramids. 6 pyramid levels, including

the original image were used. They were created with a decimation factor of 2 and a 3x3 Gaussian low-pass lter. Due to the non- ltering of the borders of the pyramid levels and a border for half the patch size to be used in matching, some border points could not be matched and were excluded a priori. The same points were matched in all pyramid levels. From the ve versions of the old test, version 5 was dropped and a new version 6 was used. It is similar to version 2 but instead of a conformal transformation, only two shifts and one rotation were used, since the scale was not expected to be always well-determinable as the points were lying along edges. Table 2 shows these results for the 0th pyramid level. Unsuccessfully matched points are those that needed more than 20 iterations.

Version 1 2 3 4 5

This paper presents a matching algorithm for automatic DTM generation from SPOT images that provides dense, accurate and reliable results and attacks the problem of radiometric differences between the images. The proposed algorithm is based on a modified v

SPOT stereo matching for DTM generation

Page 7

Table 2 Version

Matching versions 1224 Successfully matched points 85.0% 92.8% 97.6% 86.1% 96.0% Iterations per point 5.8 4.1 3.3 4.7 3.7 1225 Successfully matched points 89.1% 94.4% 97.4% 89.7% 96.8% Iterations per point 5.2 4.1 3.6 4.3 3.9

1 2 3 4 6

These results were analysed for automatic detection of blunders. The criteria that have been used for quality analysis are: standard deviation of unit weight from the least square matching, correlation coef cient between the template and the patch, number of iterations, x-shift (i.e. change from the approximate values), standard deviation of x-shift, y-shift, standard deviation of y-shift, and the size of the used shaping parameters. After matching, the median ( M ) and the standard deviation of the mean absolute difference from the median ( s(MAD) ) were computed for each criterion. The median and the s(MAD) were used instead of the average and the standard deviation because they are robust against blunders. For each criterion, the threshold for the rejection of a point was de ned as M+ N s(MAD). N was selected to be 3 for all criteria with the exemption of the number of iterations, the two shifts and the scale which should be left to vary more (N= 4 ). A point was rejected (i) when one of its criterion did not ful l the aforementioned threshold (relative threshold derived from the image statistics), or (ii) one of its criteria did not ful l a very loosely set threshold, e.g. for the correlation coef cient 0.2 (absolute threshold, valid for all images). The same N and absolute thresholds were used for all versions. This blunder detection scheme was successfully applied in the old test. In the current test some problems occurred. The number of the remaining points in the 0th level was signi cant decreased when the blunder detection test was applied after each pyramid level. Thus, we decided to apply the test only to the results of the 0th level. However, wrong points in the upper pyramid levels were diverging from their correct position as matching sequentially proceeded down the image pyramid. These points were typically

tted to a side-minimum and thus were not detected by the blunder detection test. Since they were far away from their correct position, their height was gross erroneous, sometimes by several hundred meters. In this case the problem to be solved is to exclude blunders, from arbitrarily, and partly not densely, distributed points. To achieve this we developed an algorithm that uses robust statistics of the heights (based again on median and s(MAD)) within 3 neighbourhoods centred at each point to be examined, whereby a minimum number of points within each neighbourhood is required to ensure a safe estimation of the statistics. The size of the neighbourhood and the minimum number of neighbours, which is proportional to the former, are decreased when the height gradient magnitude increases, i.e. the terrain becomes steeper. Points that do no t to their neighbourhood are either replaced by their neighbourhood median or rejected. The aim of this adaptive local nonlinear ltering was to reject the blunders, without smoothing the terrain, and propagating the blunders as is the case with low-pass ltering. Points with very few neighbours are rejected, although they may be critical for a complete surface description and correct DTM interpolation. Although the algorithm needs further development and testing, it performs well, particularly when the point density is suf cient. Table 3 gives information on the amount of rejected points.

This paper presents a matching algorithm for automatic DTM generation from SPOT images that provides dense, accurate and reliable results and attacks the problem of radiometric differences between the images. The proposed algorithm is based on a modified v

SPOT stereo matching for DTM generation

Page 8

Table 3 Version

Points rejected by the two automatic blunder detection methods 1224 Percentage over all points Method I Method II 7.1% 5.9% 4.3% 6.8% 4.9% Remaining good points 9835 12171 13876 10394 13077 1225 Percentage over all points Method I 19.9% 16.9% 14.1% 18.0% 16.8% Method II 3.7% 3.2% 3.4% 2.6% 3.4% Remaining good points 13410 15183 16359 14103 15645

1 2 3 4 6

21.2% 16.7% 13.4% 19.4% 15.8%

As it can be seen from Table 2 and Table 3, the amount of successfully matched points decreases and the percentage of detected blunders increases when (i) no geometric constraints are used (version 1), and (ii) grey level images are used (version 4). From the remaining versions, the one using shifts results in more successful points because it is more stable (robust) than versions 2 and 6 which use a scale/rotation and a rotation respectively and because less criteria are used for the rst blunder detection method. Constrained matching needs less iterations per point than the unconstrained version, especially when only shifts are used (see Table 2). The above results are valid for both map sheets in spite of the different terrain form and land usage. For the accuracy analysis two comparisons were made: The matched points are bilinearly interpolated in the reference DTM grid and the differences between the interpolated heights and the heights as estimated by matching are computed (Table 6 - Table 6). A new DTM was derived from the matched points and compared to

the reference DTM (Table 6).

Table 6 gives an accuracy estimate of the raw results of the 0th pyramid level. Table 6 is like Table 6 but includes only the points that exist in all ve versions (12330 points for map sheet 1224 and 15766 for 1225 respectively). These tables, and particularly Table 6, permit a comparison of the matching accuracy of the ve versions. Version 2 and 6 perform similarly with the latter being slightly more accurate. Version 3 is worse, and version 1 and 4 are clearly the less accurate.

Table 4 Version

Differences of estimated heights (raw data) to reference DTM (in meters) 1224 max. absolute 1260 1917 1931 1854 1566 RMSE 75.5 62.9 68.3 63.9 65.8 mean+2.7+1.5+2.7+6.3+2.8%≥ 40 m 10.9 9.1 8.4 11.7 8.2 max. absolute 1944 1973 2074 2845 1339 RMSE 94.4 88.5 97.9 132.9 78.1 1225 mean -3.3 -0.2 0.0+16.2 -1.1%≥ 40 m 9.0 7.3 8.8 8.4 8.1

1 2 3 4 6

This paper presents a matching algorithm for automatic DTM generation from SPOT images that provides dense, accurate and reliable results and attacks the problem of radiometric differences between the images. The proposed algorithm is based on a modified v

SPOT stereo matching for DTM generation

Page 9

Table 5 Version

Differences of estimated heights of identical points of all versions (raw data) to reference DTM (in meters) 1224 max. absolute 1154 695 735 1854 731 RMSE 62.3 37.5 40.6 55.0 37.0 mean+3.3+2.9+3.4+5.3+2.9%≥ 40 m 8.0 4.7 4.3 9.0 4.2 max. absolute 1911 1933 1924 2845 1141 RMSE 74.0 56.4 54.2 131.4 48.2 1225 mean -3.8+0.1 -0.4+15.6 -0.7%≥ 40 m 6.8 4.2 5.1 6.9 4.7

1 2 3 4 6

Table 6 shows the nal results after blunder removal. The results of map sheet 1225 were initially similar to those of map sheet 1224. However, many mountainous areas remained with very few points and the errors after interpolating a DTM were large. Thus, the criteria of the second blunder detection method were relaxed, less points were rejected but this resulted in worse accuracy values for map sheet 1225 in Table 6.

Table 6 Version

Differences of estimated heights to reference DTM after 2st blunder detection method (in meters) 1224 max. absolute 76 78 428 131 82 RMSE 7.9 9.3 14.7 10.5 9.6 mean+1.6+2.5+3.0+3.0+2.5%≥ 40 m 0.3 0.3 0.7 0.6 0.5 max. absolute 225 218 401 294 198 RMSE 11.2 13.6 17.3 12.7 14.9 1225 mean -1.0 -0.4 -1.0+0.9 -0.9%≥ 40 m 1.1 1.5 2.8 1.4 2.0

1 2 3 4 6

From a comparison of Table 6 and Table 6 it is clearly visible that the two methods for blunder detection lead to an immense improvement of all accuracy indicators. Automatic quality control is indispensable and can take over the job of tedious and time-consuming manual editing. The maximum absolute error, the RMSE, and the percentage of errors over 40 m of Table 6 have been improved on the average by a factor 1.4, 2.1 and 3.2 respectively after using the rst blunder detection method. The latter results have been further improved by a factor 6.2, 3.2 and 2.5 after using the second blunder detection method. The second blunder detection is particular attractive, since it rejects 3 - 7 times less points than method I. The points rejected by method I as well as the unsuccessful points of Table 2 include many wrongly rejected goo

d points. This de ciency can be easily removed and a cooperation between the different blunder detection procedures is planned. The percentage of errors greater than 40 m is generally less than 2%. Large errors occur especially in three types of areas: (a) At the mountain-ridges and cliffs. At these regions there are surface discontinuities and forests. Additionally interpolation errors occur because the density of the selected points was low at these regions and thus the terrain surface could not be modelled correctly (see Figure 6 and Figure 6 with the large triangular meshes for DTM interpolation). (b) At forest areas, because the matched points are on the tree tops and the reference DTM refers to the earth surface.

This paper presents a matching algorithm for automatic DTM generation from SPOT images that provides dense, accurate and reliable results and attacks the problem of radiometric differences between the images. The proposed algorithm is based on a modified v

SPOT stereo matching for DTM generation

Page 10

(c) On the lake surface (see top centre of Figures 6 and 7). The selected points lied on either sides of the lake, and at certain places much higher than the lake surface. Thus, the large triangles that were used for the DTM interpolation were lying much higher than the lake surface. The RMSE is in the 10 m level and compares very favourably with the 6 m RMS in Z of the 126 manually selected and matched check points. The accuracy difference includes errors due to the polynomial mapping functions (max. 1 m), the matching, the interpolation within the reference DTM and errors of the reference DTMs. A comparison of Table 6 with Table 1 (with very good approximations) shows a slight accuracy decrease of the former results while the maximum absolute errors increase. The mean difference is small, indicating absence of large systematic errors. It is generally always positive because (i) area-based matching tends to measure higher than the actual surface when the terrain is rugged, and (ii) the tops of the trees were measured in forested areas. The small negative mean difference in map sheet 1225 is due to the existence of blunders which were primarily negative. Version 1 (without constraints) is surprisingly good. This is mainly due to the fact that these results are based on fewer points due to many detected blunders (Table 3) through the blunder detection scheme. However, less points lead to a less accurate interpolated DTM especially in mountainous terrain (see Table 6). Another reason is due to the choice of points along nearly vertical edges. Thus, the precision in x-direction is good and errors in y (gliding along the edge) in uence minimally the estimated heights due to the horizontal base. Version 4 has similar accuracy as the version with gradient magnitude images (version 2). The difference is not so big again due to many detected blunders for version 4. The shift version (version 3) performed, as expected, worse than versions 2 and 6. Version 6 was expected to perform slightly better than version 2, because with the latter the scale is not always well-determinable. However, the viewing angles and the steep terrain, particularly in map sheet 1225, makes the use of a scale n

ecessary for a better geometric t of the patch to the template. In general the results of all versions (with exception of version 3 that had some undetected blunders) are quite similar. This is an indication that our blunder detection scheme worked equally well with all versions although their initial accuracies (see Table 4) differed signi cant. Our interpretation of Table 6 is that although versions 1 and 4 seem to perform very well, they lead to a less accurate DTM interpolation in rugged terrain because they have less points. The results of Table 6 are worse than those of Table 6 due to interpolation errors (ca. 270000 points were interpolated from 10000 - 16000 points). Still the results for map sheet 1224 are close to 10 m. The results for map sheet 1225 are worse due to mountainous terrain, many forests and the lake. With denser measurement points they should be close to the results of map sheet 1224. The results of versions 1 and 4 are not worse than those of the other versions for map sheet 1224 because the terrain slope is not large. For map sheet 1225, version 1 is clearly worse but version 4 is surprisingly the best. There are many accidental reasons for that behaviour. The main reason is that version 4 has more points in critical mountainous regions with low point density than all the other versions that used gradient magnitude images (compare the lower right part of Figures 6 and 7). In the latter versions these points were rejected by the rst blunder detection method because of the relatively low texture and low correlation coef cient. The parameters for the rejection thresholds were common for all versions, although some of them should differ due to the different nature of grey level and gradient magnitude images, i.e. for the latter they should be relaxed.

Table 7 Version

Differences between new and reference DTM (in meters) 1224 max. absolute 135 129 414 127 118 RMSE 14.4 14.0 19.8 13.9 13.3 mean -0.1+0.5+2.3+1.7+0.8%≥ 40 m 2.6 2.2 2.6 1.9 1.8 max. absolute 591 427 442 304 406 RMSE 48.7 36.2 40.2 29.0 36.7 1225 mean -9.6 -3.9 -4.3+0.9 -4.1%≥ 40 m 12.6 10.8 11.3 9.1 11.2

1 2 3 4 6

This paper presents a matching algorithm for automatic DTM generation from SPOT images that provides dense, accurate and reliable results and attacks the problem of radiometric differences between the images. The proposed algorithm is based on a modified v

SPOT stereo matching for DTM generation

Page 11

Figure 6.

Triangulation mesh for DTM interpolation of map sheet 1225, version 2

Figure 7.

Triangulation mesh for DTM interpolation of map sheet 1225, version 4

This paper presents a matching algorithm for automatic DTM generation from SPOT images that provides dense, accurate and reliable results and attacks the problem of radiometric differences between the images. The proposed algorithm is based on a modified v

7. CONCLUSIONS

AmatchingalgorithmforSPOTimageswaspresentedthatusesaphotogrammetricsensormodeltoimposeconstraintsthatreducethesearchspacefrom2-Dto1-D.Thealgorithmseverelyreducestheproblemscausedbyradiometricdifferences,anddeterminesinonesteppixelandobjectcoordinates.Theuseofgradientmagnitudeimagesinsteadofgreylevelimagesim-provestheresults.Aconformal,arotation/shiftorashifttransformation,thelatterhoweverwithsmallerpatchsize,mayleadtosimilar results.

Problematiccaseslikemultiplesolutions,radiometricdifferencesandocclusionsarereducedandthecomputationtimede-creasesduetothe1-Dsearch.Ablunderdetectionschemeisproposedthatusescriteriaderivedmainlyfromthestatisticsoftheresults.Itleadstoanimpressiveimprovementofallaccuracyindicators.Inparticular,itreducesthepercentageoferrorslargerthan40mto0.5-2%.Ade ciencyofourtestwastherejectionoftoomanypoints,outofwhichmanywerecorrect,withobvi-ous negative in uence on the DTM interpolation.

Theaccuracyofthematchingisinthe10mrange.FortheinterpolatedDTMitclearlydependsonthedensityofmeasure-mentpointsandforsuf cientdensityitcanbeinthe10-20mrange.Regionswithlowpointdensityduetoradiometricdiffer-ences, low texture or shadows can be lled-in with manually measured points before the DTM interpolation.

8. ACKNOWLEDGEMENTS

TheauthorsexpresstheirgratitudetotheFederalOf ceofTopography,Bern,SwitzerlandforprovidingtheSPOTimagesand DTM data.

9. REFERENCES

Baltsavias,E.P.,1991.MultiphotoGeometricallyConstrainedMatching.Ph.D.Dissertation,MitteilungenNr.49,InstituteofGe-odesy and Photogrammetry, ETH Zurich, 221 p.

Baltsavias,E.P.,Stallmann,D.,1992a.MetricinformationextractionfromSPOTimagesandtheroleofpolynomialmappingfunc-tions. In: Proc. of 17th ISPRS Congress, 2 - 14 August, Washington D. C., USA, Vol. 29, Part B4, pp. 358-364.

Baltsavias,E.P.,Stallmann,D.,1992b.AdvancementinmatchingofSPOTimagesbyintegrationofsensorgeometryandtreatmentofradiometricdifferences.In:Proc.of17thISPRSCongress,2-14August,WashingtonD.C.,USA,Vol.29,PartB4,pp.916-924.

Kratky, V., 1989a. On-line aspects of stereophotogrammetric processing of SPOT images. PERS, Vol. 55, No. 3, pp. 311 - 316.Kratky,V.,1989b.RigorousphotogrammetricprocessingofSPOTimagesatCCMCanada.ISPRSJournalofPhotogrammetryandRemote Sensing, Vol. 44, pp. 53 - 71.