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 3

where ( x, y ) the approximate pixel coordinates of the corresponding point in the second image and ( x, y ) the unknown x- and y-shift. Equation 1 is equivalent to the distance of a point ( x+ x, y+ y ) (the patch centre of the second image) from a straight line. The epipolar line is expressed by the normal equation of a straight line, where p is the distance of the line from the origin andβ is the angle between the perpendicular to the line and the x-axis. If the patch of the second image does not lie on this line, then it jumps onto the line right in the rst iteration. With our data, the epipolar lines are approximately horizontal, i.e. any error in the y-direction will be eliminated right in the rst iteration. Since the epipolar lines are horizontal, the measurement points must be selected along edges that are nearly vertical in order to ensure determinability and high accuracy. Some advantages of the geometric constraints will now be presented.

SPOT images include due their small scale a high degree of texture, i.e. edges. Measurement points lying along edges nearly vertical to the epipolar line can not be safely determined with other matching techniques, but with our approach they can as they lie at the intersection of two nearly perpendicular lines. Figure 2 illustrates such an example. Another usual problematic case is that of multiple solutions. With geometric constraints side minima can only result if they fall along the epipolar line. Figure 3 shows an example with and without geometric constraints.

Figure 2.

Matching along edges without (left) and with (right) constraints. The epipolar line is the white line in the right image. The black frame is the initial position and the white frame with the black centre cross the nal position.

Figure 3.

Multiple solution matching without (left) and with (right) constraints.

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

4. DATA PREPROCESSING AND SELECTION OF MEASUREMENT POINTS

First,thegradientmagnitudeimagesarecomputed.Toreduceweakedgesduetonoise,whichisverynoticeableinSPOTimages,allgradientswithamagnitudelessthanathresholdTaresetequaltoT.Thethresholdisselectedasafunctionofthemeanandthestandarddeviationofthegradientmagnitudeimage(inthiscaseT=mean-standarddeviation).Thesamefunc-tionshouldbeusedforbothimagestoensureequaltreatment.Thethresholdshouldnotbetoohighotherwise(a)usefultextureisdeleted,and(b)theedgesarebrokenandsigni cantdifferencesbetweenthetwoimagesoccurduetodifferentedgestrength.Thisapproacheliminatesnoisebutalsolowtexturewhichishowevernotverylikelytoleadtoaccuratematchingresults.Anex-ample is shown in Figure 4.

Asalreadymentioned,themeasurementpointsareselectedalongedgesnearlyperpendiculartotheepipolarlines.Inordernottoreducethenumberoftheselectedpointstoomuch(andthustheirdensity,whichin uencestheDTMaccuracy),pointsalongedgeswithanangleof±45 withtheperpendiculartotheepipolarlineshouldalsobeselected.Toavoidclusteringofgoodpointsathin-outwindowfornon-maximasuppressionisde ned.Toreducetheselectionofpointslyingatsmallandfaintnoisyedgesthepointsareextractedinthe rstleveloftheimagepyramid.Ourapproachistomatchthesamenumberofpointsinallpyramidlevels.Thus,aselectedpointmusthavetheaforementionedpropertiesinallpyramidlevels.Generally,theap-proachtobefollowedistodetectgoodpointsinalllevelsoftheimagepyramidofthetemplateimageandkeepthepointsthatappearinallpyramidlevels.However,theseSPOTimageshadalotoftextureandthiswasexpressedinallpyramidlevels.Bygoing up in the image pyramid, the relative number of selected points was actually increasing.

Figure 4.

Greylevelimage(left),gradientmagnitudeimage(middle),thresholdedgradientmag-nitude image (right)

Toavoidselectingpointsatregionsofradiometricdifferences,especiallyoneswithalargeareaextent(likeclouds),ingthePMFsandanaverageheightofthescene(derivedeitherfromaprioriknowledgeorfromtheaverageheightofthecontrolpointsusedintherigorousSPOTmodel),orapolynomialtransformationderivedfromthepixelcoordinatesofthecontrolpoints,thesearchimageisregisteredwiththetemplateimage.Iftheregistrationwereperfect,asim-plesubtractionofthetwoimageswouldgiveusthedifferentedges.Sincetheregistrationisnotperfect,animagepyramidiscreatedsothatatthehighestlevelthemisregistrationerroriswithinpixelrange.Thenthroughsubtraction,thedifferentedgesaredetectedbybinarisingthedifferenceimagewithanabsolutethreshold.Thisbinaryimagecaneventuallybedilatedinordertoavoidselectingpointswhosepatchwouldpartiallyfallinsideareaswithradiometricdifferences.Thesedisturbanceareasareprojectedinallpyramidlevelsandconvolvedwiththeselectedpointsinordertocleantheselectedpoints.Anexampleisshownin Figure 5. With this method small radiometric differences cannot be detected.