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