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