TT rr BDBEZ 
identified; roads of characteristic shape can be strong, 
easily recognized features, as can also be fences 
between paddocks of differing vegetation, particularly 
the corners. 
The early details of our patch-based approach have 
been published elsewhere (Abbasi and Freeman, 
1994a,b). In this paper, the basic method will be 
outlined, and then our efforts to proceed from matched 
patches to actual points in the images will be described, 
along with tests with SPOT images and close-range 
images. 
2. PATCH-BASED MATCHING 
2.1 Patch extraction 
An advantage of patch-based matching is the simplicity 
of definition of the feature and its computer 
implementation. To find a uniform patch, we search in 
the image for an area of uniform colour or gray value 
that is larger than some minimum size, and expand the 
area to include neighbouring pixels of the same colour. 
The minimum size was chosen arbitrarily as a 3x3 pixel 
window, this size being large enough to be visible by eye 
in a typical SPOT image, but small enough to not miss 
small patches. The notion of "uniform colour" had to be 
adjusted to accommodate the variation in colour 
typically found in areas visually perceived as uniform. 
Extensive testing established that a grayscale tolerance 
of +2 was most effective. Even with this tolerance, 
there are areas of bright colour that we perceive as 
uniform but which exceeds this level of variation. 
Perhaps a logarithmic variation of the tolerance with 
gray level is needed to account for this. We have not 
tested this yet. 
In implementation, a patch is stored as a series of 
scanlines, with a start and end pixel address for each 
line; concave patches may require more than one start 
and end for the one line. Associated with a patch will 
be its bounding area, the minimum and maximum X 
and Y coordinates. The area can be quickly derived by 
summing the differences between the start and end for 
each scanline. Drawing the boundary of a patch is more 
difficult with this storage scheme, as the start for a 
particular scanline must be matched with its 
corresponding one in the next scanline. When there is 
no corresponding point in the next scanline, a 
horizontal line is needed. 
2.2 Patch matching criteria 
With each image having a set of patches found by the 
above procedure, the next task is to find how the 
patches match. A deliberate decision was made to 
ignore gray value or colour in this comparison. This 
was based on the observation that in images of natural 
scenes, water bodies often appear as quite different 
colours when viewed from different directions. This is 
understandable when the physics of light interaction 
with the water bodies is considered. Whereas most 
other objects in natural scenes exhibit Lambertian 
reflection, typical of matt surfaces, where the amount of 
light reflected by the surface is constant for all viewing 
directions, water bodies (and also many metallic roofs) 
exhibit specular reflection, where the reflected light is 
much brighter in some viewing directions than in 
others. Because water bodies are features that our 
method is seeking to locate, it was important that patch 
matching not exclude them by requiring uniformity of 
colour intensity. Other workers have handled colour 
differently, catering for overall differences in intensity 
level, possibly caused by differing levels of atmospheric 
pollution or different responses of the photo-detectors in 
the two views, and seeking to allow for this variation 
while requiring the relative colours in the two images 
be the same. 
The characteristic of a patch that is of greatest 
assistance in performing the match is size. The patches 
are sorted by size, and the largest patches are 
considered first in seeking a match. There are usually 
very many small patches, and few large ones. By 
working first with the large patches, we anticipate that 
we will be concentrating on the easy patches before 
considering the more difficult ones, and find successful 
matches most rapidly. 
Of course, the patches may not necessarily be the same 
size in the two images, owing to the two different 
viewing directions. We need to allow for the different 
geometry of the two views when comparing area or any 
other attribute of two patches. In the testing we have 
performed, we have used the geometry of two SPOT 
images, one an overhead view and the other at the 
maximum oblique angle, as the basis for comparing 
shapes. A scanline in nadir viewing covers 60km and in 
the oblique view 80km, so in comparing patch 
attributes, we have adopted the similarity test: 
2 4 
3 3 
where P, and P, are an attribute of two patches being 
compared, one from each image. 
PjsP,e$P, 
This test could be greatly improved if we know the two 
viewing directions and we know in advance the extent 
to which the distance from the scene to the view points 
varies across the images. 
We explored a variety of criteria for comparing patches 
(Abbasi, 1995), and concluded that several criteria were 
needed to effectively distinguish similar patches: 
e area of the patch 
e width of bounding rectangle 
* height of bounding rectangle 
* perimeter of the patch 
* linearity of the patch 
® concavity of the patch 
The last two were developed from an analysis of chain 
codes for representing and comparing patches. Chain 
codes (Freeman, 1961) are usually a sequence of digits 
based on traversing the boundary of an area in a 
clockwise direction, with each digit representing the 
102 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B2. Vienna 1996 
dire: 
Alth 
time 
diffi 
The 
num 
start 
valu 
secoi 
digit 
(Abb 
Ach 
a set 
whei 
diffe: 
whei 
repri 
thes: 
will | 
shap 
digit 
(G, i 
The | 
segm 
with 
The | 
extei 
assu 
clock