ving 
ofs) 
t is 
patch 
y of 
sity 
heric 
ors in 
on 
ges 
itches 
ally 
that 
e 
ssful 
same 
ent 
r any 
ave 
T 
and in 
ing 
o two 
tent 
oints 
tches 
a were 
hain 
hain 
ligits 
the 
direction of an edge vector, such as: 
1 
2«—m— ——0 
3 
Although chain codes have been understood for a long 
time, they have fallen into relative disuse because of 
difficulties 
1. in establishing a starting point to enable two 
shapes to be compared, and 
2. the difficulty in obtaining a similarity measure 
other than testing exact equivalence. 
The first difficulty can be surmounted by using shape 
number (Bribiesca and Guzman, 1980), where the 
starting point is chosen to minimize the numerical 
value of the chain code. We were able to overcome the 
second difficulty by analyzing frequencies of chain code 
digits and frequencies of changes in chain code digits 
(Abbasi and Freeman, 1994c; Abbasi, 1995). 
A chain code for representing a shape is represented as 
a set of digits: 
ep eo es... 0, 
where each c; is a direction digit (0-3), and the 
differences between these codes is a related set of digits: 
dy, dy dy... d,, 
where d; 2 c;-c;,;. The frequency of the digits 
representing the four cardinal directions in each of 
these codes will be independent of starting point, and 
will give a similarity measure that is useful even when 
shapes are not identical. For a particular direction 
digit k, these frequencies are defined as: 
m 1 ife;=k 
a if; #k 
"wa der 
Gi = Ef if d, # k 
F, 
The perimeter m will then be: 
m = Go + G, + G; 
(G, is always zero.) 
The linearity, L, of a shape, or the proportion of its edge 
segments that are locally collinear, can be identified 
with Go: 
DL = 
m 
The concavity, V, of a shape, or the extent to which its 
exterior is indented, can be identified with G,, 
assuming that the chain code traverses the shape in a 
clockwise direction: 
_ Gi: 
Tem 
F, will equal F,, and F, will equal F,. These are less 
useful in discriminating shape than the frequencies of 
chain code differences; nd the width and height of the 
bounding rectangle are very similar to them and are 
easier to calculate. 
2.3 Multi-Patch process, using relative geometry 
When there are many patches, we will not want to 
systematically compare all patches from one image with 
those from the other. Even when size and other criteria 
are taken into account, it should be possible to use 
information on the patches already matched to guide 
the selection from the available candidates. Some of 
these candidates will be impossible because of their 
relative geometry to those we know already to be 
matched. We call this method of accumulating relative 
geometry of patches and eliminating impossible 
candidates based on their position the multi-patch 
process. 
Basically, it works in this way: 
1. The patches for both images are held in a size 
sorted list, with the largest first. 
2. Three large patches are chosen from the first 
image. 
3. A search is conducted among the candidates for 
each of these three patches for a combination of 
candidates that form a triangle of similar size, 
shape and orientation to the patches in the first 
image. 
4. If no suitable set of candidates can be found, one 
of the patches in step 2 is replaced, and step 3 is 
repeated. If necessary, more than one of the 
three original patches from the first image may 
need to be replaced in the search process. 
5. After steps 3 and 4 have been repeated to 
establish suitable triangles, other triangles are 
formed. With the first two successfully matched 
patches, other patches are processed in turn 
from the first image, with patches of suitable 
size and shape being considered as in step 3 to 
find the one with the correct geometry. All 
patches are processed in this way using the two 
reference patches. 
In the tests we have performed using this method, we 
have compared triangles by the length and orientation 
of edges. We have arbitrarily chosen £5? for comparing 
edge orientation, and the distance criterion above for 
edge length. These criteria would be tightened if 
camera position and the nature of the scene were 
known more precisely. 
2.4 Success of patch matching 
As previously reported (Abbasi and Freeman, 1994b; 
Abbasi, 1995), the patch matching process has been 
tested on sections of SPOT images. The first tests were 
with images captured 45 months apart, on 400x400 
sections each containing a major water body. Over one 
103 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B2. Vienna 1996