International Archives of Photogrammetry and Remote Sensing, Vol. 32, Part 7-4-3 W6, Valladolid, Spain, 3-4 June, 1999 
42 
Figure 7. Flow-chart summarising patch matching procedure. 
The cost function used by Morgado and Dowman (1997) is: 
T = ^\a l - a 2 \+\p i -p 2 \ + \r l - r 2 \+\c l -c 2 \+... 
where T is the value of the cost function, a/ is the area of patch 
i, Pi is the perimeter length, and rj and q are the length and 
width of the bounding rectangle. 
A specific problem associated with this function is that it was 
found that the area component influenced the results more than 
the other attributes. To get around this problem, the value of the 
area component was halved to reduce its influence. However, 
since areas and lengths are being compared, it seems more 
reasonable to take the square root of the area component, so that 
all the components being compared have the same 
dimensionality. Furthermore, with the above function, larger 
patches will always produce a larger value than smaller patches. 
Therefore, to ensure this is not the case, the differences in 
components have been normalised with respect to patch size. 
Thus, the cost function used in this study is expressed by the 
equation: 
l 
a \ ~ a 2 
2 
+ 
Pi -Pi 
+ 
r i ~ r 2 
+ 
C i C 1 
«1 +a 2 
Pl+ Pi 
r i +r i 
Cj + c 2 
are shown in Table 2. It is apparent from this table that by using 
a combination of the cost function, the patch separation and the 
overlap, correct matches can be identified. Although the cost 
function is not by itself reliable, there is a clear bimodal 
distribution of the patch separations and the overlap. Using this 
method, correct matches can be identified and these are shown 
in Figure 8. 
In order to determine the best method of segmentation, the tests 
were repeated for all methods of patch extraction using the 
Istres images and another pair. The results do not allow any 
conclusions about the best method, only that there are large 
variations with image and method. For both these images it is 
interesting that the number of correct matches from all 
combinations varied from 0 to 5 out of total matches varying 
from 39 to 366. 
The correct matches were successfully used to register the 
SPOT and SAR images together. 
SAR patch 
index 
SPOT patch 
index 
Cost 
function 
Patch 
separation 
(pixels) 
Percentage 
overlap 
(x 100) 
2 
5204 
0.463 
112.429 
0.194 
3 
0,484 
0.353 
0.885 
7 
13897 
0.270 
225.892 
0.331 
9 
3417 
0.550 
253.794 
0.312 
10 
2901 ¡1 
0.277 
4.651 
0.899 
12 
3754 
0.229 
6.835 
0.944 
13 
18389 
0.265 
267.599 
0.199 
18 
26749 
0.240 
514.928 
0.372 
21 
13746 
0.662 
209.264 
0.668 
22 
21272 
0.394 
275.525 
0.366 
24 
8585 
0.259 
378.102 
0.401 
28 
18558 
0.306 
166.298 
0.493 
30 
21476 
0.327 
198.795 
0.526 
32 
11307 
0.313 
59.894 
0.561 
33 
25114 
0.129 
242.566 
0.561 
37 
21579 
0.137 
303.653 
0.652 
39 
20029 
0.286 
395.225 
0.573 
43 
16449 
0.549 
43.834 
0.307 
45 
15793 
0.287 
3.995 
0.887 
56 
1339 
0.414 
330.546 
0.230 
60 
11922 
0.416 
382.007 
0.629 
61 
16119 
0.474 
123.264 
0.596 
71 
17966 
0.215 
347.164 
0.514 
73 
13154 
0.714 
222.182 
0.290 
75 
6637 
0.276 
384.673 
0.482 
76 
16520 
0.186 
386.544 
0.351 
77 
4572 
0.382 
418.060 
0.471 
Table 2. Matching results with correct matches highlighted. 
5. EDGE MATCHING 
Every patch in image 2 is matched with each patch in image 1 
and the matches with the lowest cost function are retained. 
There will be false and multiple matches and these are reduced 
by eliminating matches with large differences in centroid 
values. A further technique used to improve matching is to 
repeat the operation with image 2 as the master and image 1 as 
the slave. To compare shape is a further check. Patches are 
compared by counting the number of pixels in common when 
centroids are made coincident. Those with large overlap are 
considered to be the best matches. The results of these processes 
The polygon matching provides directly the centroid co 
ordinates of conjugate polygons and these can be used to carry 
out a transformation between the two images. This 
transformation can be improved by matching the detail of the 
edges around the polygons. The basic method of edge matching 
using dynamic programming is described by Newton et al. 
(1994). This previous work used the edges of the polygons as 
extracted by the segmentation. In the new method, edges are 
extracted from the raw data in the region of the polygon 
boundary and then matched using dynamic programming as 
before. In this way, it is ensured that reliable edges are extracted