Each valley segment is traced in turn by searching

for logical extensions of the segment in a

direction consistent with the current direction of

the segment. The tracing stops when there are no

more pixels to add to the segment, or when the

segment encounters a pixel labelled as part of

another valley. In this case, the pixel which has

been encountered is labelled as a node. All node

locations are stored in a file for the matching

process.

In the examples presented here, there were 367

nodes and 945 valley segments detected in the SAR

mask and 2813 nodes and 4731 valley segments

detected in the DEM mask.

POINT PATTERN MATCHING

The goal of this step is to identify a subset of

nodes from each of the masks which correspond to

the same location on the ground. The method is

loosely based on the relaxation algorithm proposed

by Ranade and Rosenfeld (1980).

Given a hypothetical transformation between the

two masks, we may examine all combinations of

point pairs (hereafter a 'point pair' implies one

node taken from each image) and determine whether

or not the pair 'supports' the hypothesis. The

support is calculated by a figure of merit defined

by:

4>(x) = (1 +(^ L ) 2 )' 1

where x is the Euclidean distance between the test

point pair after applying the transformation. It

can be seen that as x increases, the figure of

merit decreases. The parameter a is included to

allow for an error tolerance in the match.

The algorithm used here operates as follows. Every

possible combination of point pairs is tested as

a hypothetical match with each match defining a

hypothetical linear translation between images. An

MxN 'support matrix' can thus be defined, where M

and N are the number of points in each mask to be

matched. The support for each hypothesis is

calculated by searching all remaining combinations

of point pairs to find an optimum set of pairs,

ie. the pairs with the least separation after

applying the hypothetical translation. The figure

of merit is calculated for each pair in the

optimum set and summed.

The support matrix is then thresholded at a fixed

percentage of the maximum support value in the

matrix. The point pairs which give a support value

below the threshold are discarded and the calcula

tion of the support matrix is repeated using the

subset of points which remain after thresholding.

The process is iterated until a consistent set of

point pairs remains, all of which give support

values above the threshold.

Since the calculation of the support matrix takes

on the order of 0(M 2 N 2 ), the number of points used

must be minimized. This is accomplished automati

cally by thinning the initial set of points by

retaining only those nodes which are connected to

long valley segments (since these are most likely

to be included in both masks) and by deleting

points which are close to one another in the same

mask using valley length information stored at the

linking and labelling step. Points from each mask

are also eliminated at each iteration, and there

fore the calculation takes less time as it

progresses.

The resulting set of point pairs may then be used

to define an affine transformation model. The

original lists of nodes are searched to find

additional point pairs which match within the

error tolerance based on this new transformation

model.

The success of the point pattern matching

algorithm depends on having a sufficient number of

points in each mask which actually correspond. The

low resolution DEM must be sampled at the same

resolution as the SAR image resolution to give a

similar level of detail in the valley network.

Given this condition, the method is robust with

respect to the choice of the processing

parameters, a and the support threshold.

Figure 3 shows the DEM valley mask overlaid on the

SAR mask, resampled using the affine transforma

tion model which results from the match. In this

example, the initial thinning parameters were a

minimum valley length of 5 pixels in the SAR mask

and 15 pixels in the DEM mask, and a minimum node

separation of 5 pixels, leaving approximately 150

nodes from each mask to be used as input to the

matching process. A consistent set of 8 point

pairs were successfully matched at the end of the

iterative process, using a=3 pixels and a

threshold of 65%. An additional 51 point pairs

were added using the affine transformation model,

resulting in an RMS error of approximately 1 pixel

(50m) in both the pixel and line directions.

CONCLUSIONS

A feature-based image matching algorithm for

ground control point acquisition has been

presented. In the application shown here, valley

masks extracted by two different methods have been

successfully matched. The algorithm can easily be

adapted for other applications where a spatial

point pattern of image features may be extracted

from two images. The only requirements are for the

two images to be roughly similar in scaling and

rotation, and have a similar level of detail in

the features extracted.

REFERENCES

Guindon, B., 1989. Development of a Shape-from-

Shading Technique for the Extraction of

Topographic Models from Individual Spaceborne SAR

Images. Proceedings of the 1989 International

Geoscience and Remote Sensing Symposium. 597-602.

Guindon, B. and H.Maruyama, 1986. Automated

Matching of Real and Simulated SAR Imagery as a

tool for Ground Control Point Acquisition. Can.

J. Remote Sensing. 12:149-158.

Qian, J., R.W.Ehrich and J.B.Campbell, 1990.

DNESYS - An Expert system for Automatic Extraction

of Drainage Networks from Digital Elevation Data.

IEEE Trans. Geoscience and Remote Sensing. 28:29-

45.

Ranade, S. and A.Rosenfeld, 1980. Point Pattern

Matching by Relaxation. Pattern Recognition.

12:269-275.

812