- 1 -
TOPOGRAPHIC OBJECT RECOGNITION THROUGH
SHAPE
Lau a Keyes and Adam Wins anley
Technical Repo
Submi ed o
O dnance Su ey, Sou hamp on
Ma ch 2001
Depa men o Compu e Science
Na ional Uni e si y o I eland, Maynoo h
Co. Kilda e
I eland
- 2 -
ABSTRACT
Au oma ic s uc u ing ( ea u e coding and objec ecogni ion) o opog aphic da a,
such as ha de i ed om ai su ey o as e scanning la ge-scale pape maps,
equi es he classi ica ion o objec s such as buildings, oads, i e s, ields and
ailways. The ecogni ion o objec s in compu e ision is la gely based on he
ma ching o desc ip ions o shapes. Fou ie desc ip o s, momen in a ian s, bounda y
chain coding and scala desc ip o s a e me hods ha ha e been widely used and ha e
been de eloped o desc ibe shape i espec i e o posi ion, o ien a ion and scale. The
applicabili y o he abo e ou me hods o opog aphic shapes is desc ibed and hei
use ulness e alua ed.
All me hods de i e desc ip o s consis ing o a small numbe o eal alues om he
objec ’s polygonal bounda y. Two la ge co po a ep esen ing da a se s om O dnance
Su ey maps o Pu beck and Plymou h we e a ailable. The e ec i eness o each
desc ip ion echnique was e alua ed by using one co pus as a aining-se o de i e
dis ibu ions o he alues o supe ised lea ning. This was hen used o eclassi y
he objec s in bo h da a se s using each indi idual desc ip o o e alua e hei
e ec i eness. No indi idual desc ip o o me hod p oduced consis en co ec
classi ica ion.
Va ious models o he usion o he classi ica ion esul s om indi idual desc ip o s
we e implemen ed. These we e used o expe imen wi h di e en combina ions o
desc ip o s in o de o imp o e esul s. O e all esul s show ha Momen In a ian s
used wi h he “min” usion ule ga e he bes pe o mance wi h he wo da a se s.
Much u he wo k emains o be done as enume a ed in he concluding sec ion.
- 3 -
TABLE OF CONTENTS
ABSTRACT
Chap e 1: INTRODUCTION
Chap e 2: SHAPE-BASED DESCRIPTION
2.1 Fou ie Desc ip o s
2.2 Momen In a ian s
2.3 Scala Desc ip o s
Chap e 3: CLASSIFICATION
3.1 Supe ised Unsupe ised Classi ica ion
3.2 Classi ica ion using Bayes Theo em
3.3 Implemen ing Bayesian Classi ica ion
Chap e 4: COMBINING CLASSIFIERS
4.1 The Fusion Model
4.2 Theo y
4.2.1 The P oduc Rule
4.2.2 Sum Rule
4.3 Classi ie Combina ion
4.3.1 Majo i y Vo e Rule
4.3.2 Min Rule
4.3.3 Max Rule
4.3.4 Median Rule
4.4 Implemen ing Da a Fusion
Chap e 5: EXPERIMENTAL RESULTS
5.1 Indi idual desc ip o s
Chap e 6: CONCLUSIONS
REFERENCES
- 4 -
Appendix 1: Resul s om Pu beck da a se
Appendix 2: Resul s om Plymou h da a se
Appendix 3: Classi ica ion code
Appendix 4: Da a Fusion code
Appendix 5: Summa y o classi ica ions by desc ip o me hod and ea u e ype
- 5 -
Chap e 1: INTRODUCTION
The In elligen and G aphical Resea ch G oup wi hin he Depa men o Compu e
Science a Na ional Uni e si y o I eland, Maynoo h (NUIM) is esea ching in o he
au oma ic ecogni ion o ea u es and objec s on opog aphic maps. The main
applica ion o his wo k is he au oma ic s uc u ing o opog aphic da a o compu e
ca og aphy and GIS sys ems. The echniques being e alua ed can be di ided in o wo
b oad ca ego ies:
• ecogni ion based on isola ed shape (desc ibed he e), and
• ecogni ion based on con ex .
In shape-based classi ica ion, he shape o each objec is desc ibed using a small
numbe o desc ip o alues ( ypically 7 o 15 eal numbe s). Recogni ion is based on
ma ching he desc ip o s o each shape o s anda d alues ep esen ing ypical shapes
and choosing he closes ma ch. Se e al ypes o desc ip o alues ha e been
de eloped (mos ly in he ield o compu e ision). Resea ch a NUIM so a has
concen a ed on ou echniques:
• scala desc ip o s (a ea, dimension, elonga ion, numbe o co ne s e c.),
• Fou ie desc ip o s,
• momen in a ian s and
• bounda y chain encoding.
These echniques a e well unde s ood when applied o images and can be no malised
o desc ibe shapes i espec i e o posi ion, scale and o ien a ion. They can also be
easily applied o ec o g aphical shapes.
Wo k ca ied ou o da e includes he objec ecogni ion and classi ica ion o buildings
and pa cels ( om es da a p o ided by he Isle o Man go e nmen ) using h ee o he
abo e men ioned echniques namely Fou ie desc ip o s, momen in a ian s and
scala desc ip o s. Resul s indica e ha no one shape echnique alone is powe ul
enough o he ask - in di e en si ua ions one echnique will pe o m be e han he
o he s and p oduce signi ican esul s (e.g. dis inguishing buildings om linea
ea u es in buil -up a eas using he momen in a ian s me hod).
In o de o es hese echniques u he , hey we e e alua ed on a co pus o
opog aphic da a p o ided by OSGB using he ea u e codes (objec ypes) used in he
la ge-scale OS GB opog aphic da abase. The mos signi ican aims we e o:
• s a is ically analyse he ange o desc ip o alues ob ained by each me hod bo h
wi hin and be ween each OS ea u e ype;
• e alua e classi ica ion pe o mance o each me hod on all polygons h ough
compa ison wi h o iginal da a;

- 6 -
• in es iga e possible imp o emen in pe o mance by e alua ing s a egies o
combining me hods; and
• e alua e pe o mance o me hods in de ec ing misclassi ied ea u es in o iginal
da a.
This epo desc ibes he esul s o his exe cise. I con ains he ollowing sec ions:
1. The main asks and aims o he p ojec ;
2. A desc ip ion o he implemen a ion and in eg a ion o he so wa e
modules o indi idual me hods;
3. An e alua ion o each me hod;
4. A compa ison be ween me hods;
5. Combina ion and selec ion o me hods o op imal esul s;
6. Conclusions;
7. Sugges ions o u u e esea ch de i ed om he conclusions.
- 7 -
Chap e 2: Shape-based Classi ica ion
Topog aphic da a cap u e o la ge-scale maps ( ypically depic ed a 1:1250 and
1:2500) consis s o wo pa s: he digi isa ion o he geome y and he addi ion o
a ibu es indica ing he ea u e and/o objec ype being depic ed. Whe eas he o me
can be au oma ed using image p ocessing and simila echniques, he la e is o en a
manual ask. One possible means o au oma ion is objec ecogni ion h ough shape.
This p ojec uses shape ecogni ion echniques bo owed om he ield o compu e
ision o desc ibe a measu emen o shape o cha ac e ise and classi y ea u es on
maps. The main applica ion o his wo k is he au oma ic s uc u ing o opog aphic
da a o compu e ca og aphy and Geog aphical In o ma ion Sys ems (GIS).
Recogni ion o objec s is la gely based on he ma ching o desc ip ion o shapes wi h
a da abase o s anda d shapes. Nume ous shape desc ip ion echniques ha e been
de eloped such as, Fou ie desc ip o s, momen in a ian s and scala ea u es (a ea,
numbe o poin s, e c.). P e ious wo k has e alua ed hese echniques on opog aphic
objec s as depic ed in la ge-scale mapping. Unlike many applica ions whe e he shape
ca ego ies a e e y exac ( o example, iden i ying a pa icula ype o ai c a in a
scene), his p oblem equi es he classi ica ion o a pa icula shape in o a gene al
class o simila objec shapes, o example, building, oad o pa cel. Each echnique
p o ed pa ially success ul in dis inguishing classes o objec al hough no one
echnique p o ided a gene al solu ion o he p oblem. As pa o his epo hese
echniques a e u he e alua ed on a eal-wo ld p oblem using a co pus o
opog aphic da a p o ided by O dnance Su ey in G ea B i ain (OS GB). The da a
se consis s o he ea u es codes (objec ypes) used on he la ge-scale OS GB
opog aphic da abase.
This epo builds on p e ious wo k ca ied ou o p oduce an accu a e combined
me hodology o he classi ica ion o gene al shapes on maps. The ollowing sec ions
in oduce each o he abo e named shape ecogni ion echniques indi idually and
desc ibe how hey a e applied as gene al classi ie s o b oad classes o opog aphic
shape (buildings, ields and oad e c.). The o e all implemen a ion o he p ojec and
expe imen is ou lined and se s ou he mos signi ican aims o he epo . An
- 8 -
e alua ion and compa ison is made o he e ec i eness o each echnique in
ecognising ea u es and objec s. A da a usion echnique is hen p oposed and
e alua ed. This allows he combining o he esul s o he Fou ie desc ip o , momen
in a ian s and scala desc ip o echniques espec i ely, o gi e an o e all sco e o
each candida e objec ca ego y. The pu pose o his epo is o d aw om ou esul s
he main conclusions and see i hey a e applicable o OS.
The ecogni ion and desc ip ion o objec s plays a cen al ole in au oma ic shape
analysis o compu e ision and i is one o he mos amilia and undamen al
p oblems in pa e n ecogni ion. Common examples a e he eading o alphabe ic
cha ac e s in ex and he au oma ic iden i ica ion o ai c a . Mos applica ions using
Fou ie desc ip o s, momen in a ian s and scala desc ip o s o shape ecogni ion
deal wi h he classi ica ion o such de ini e shapes. To iden i y opog aphic objec s
each o he echniques needs o be ex ended o deal wi h gene al ca ego ies o shapes,
o example houses, pa cels and oads.
The da a used o he expe imen s desc ibed in he ollowing sec ions was ex ac ed
om ec o da a se s ep esen ing la ge-scale (1:1250) plans o he Pu beck and
Plymou h a eas in G ea B i ain (O dnance Su ey). The da a had been p e-p ocessed
o ex ac minimal closed polygons and OS ea u e codes had been applied. An
in e pola ion me hod was applied o sample he shape bounda y a a ini e numbe (N)
o equidis an poin s. These poin s a e hen s o ed in he app op ia e o ma o
p ocessing wi h each shape desc ip ion echnique. The shapes can hen be desc ibed
using a small se o desc ip o alues ( ypically 7 o 10 eal numbe s). The ecogni ion
is based on ma ching he desc ip o s o each shape o s anda d alues ep esen ing
ypical shapes and choosing he closes ma ch.
2.1 Fou ie Desc ip o s
2.1.1 Backg ound
Fou ie ans o m heo y (Gonzalez and Win z 1977) has played a majo ole in image
p ocessing o many yea s. I is a commonly used ool in all ypes o signal p ocessing
and is de ined bo h o one and wo-dimensional unc ions. In he scope o his pape ,
- 9 -
he Fou ie ans o m echnique is used o shape desc ip ion in he o m o Fou ie
desc ip o s. The Fou ie desc ip o is a widely used all-pu pose shape desc ip ion and
ecogni ion echnique (G anlund 1972, Wins anley 1998). The shape desc ip o s
gene a ed om he Fou ie coe icien s nume ically desc ibe shapes and a e
no malised o make hem independen o ansla ion, scale and o a ion. These Fou ie
desc ip o alues p oduced by he Fou ie ans o ma ion o a gi en image ep esen
he shape o he objec in he equency domain (Wallace and Win z 1980). The lowe
equency desc ip o s s o e he gene al in o ma ion o he shape and he highe
equency he smalle de ails. The e o e, he lowe equency componen s o he
Fou ie desc ip o s de ine a ough shape o he o iginal objec
2.1.2 Theo y
The Fou ie ans o m heo y can be applied in di e en ways o shape desc ip ion.
One me hod wo ks on he change in o ien a ion angle as he shape ou line is a e sed
(Zahn and Roskies 1972), bu o he pu pose o his pape he ollowing p ocedu e
was implemen ed (Wood 1986). The bounda y o he image is ea ed as lying in he
complex plane. So he ow and column co-o dina es o each poin on he bounda y
can be exp essed as a complex numbe , x + jy whe e j is sq (-1). T acing once
a ound he bounda y in he coun e -clockwise di ec ion a a cons an speed yields a
sequence o complex numbe s, ha is, a one-dimensional unc ion o e ime. In o de
o ep esen a e sal a a cons an speed i is necessa y o in e pola e equi-dis an
poin s a ound he bounda y. T a e sing he bounda y mo e han once esul s in a
pe iodic unc ion. The Fou ie ans o m o a con inuous unc ion o a a iable x is
gi en by he equa ion:
( ) ( )
∫
∞
∞−
−
=dxeu uF uxj
π
2
(1)
When dealing wi h disc e e images he Disc e e Fou ie T ans o m (DFT) is used. So
equa ion (1) ans o ms o:
( ) ( )
N
N
x
xj
eu
N
uF
π
2
1
0
1−
∑
−
=






=
- 16 -
Chap e 3: Classi ica ion
3.1 Supe ised Unsupe ised Classi ica ion
Shape desc ip ion echniques, such as hose desc ibed in chap e wo, gene ally
cha ac e ise an objec ’s shape as a se o eal numbe s. Classi ica ion o objec s based
on shape he e o e consis s o compa ing hese desc ip o s. Two gene al o ms o
classi ica ion a e possible: unsupe ised and supe ised.
Unsupe ised lea ning occu s whe e he dis ibu ion o desc ip o alues o objec s in
a da a-se is analysed. Clus e s o objec s o simila shape a e iden i ied. These a e
assumed o ep esen a class o simila objec s. In his scheme, he classes iden i ied
eme ge om he analysis o he da a-se and can depend bo h on ha analysis and he
da a-se in use.
Supe ised lea ning occu s when he classes o which objec s a e o be assigned a e
decided be o ehand. Values o desc ip o s ha cha ac e ise each objec class a e
de e mined in some way and objec s a e classi ied h ough he simila i y o hei
desc ip o s o hese cha ac e is ic alues. Supe ised lea ning he e o e equi es a way
o de e mine some no ms o he alues o a pa icula class and a way o measu e
whe he he desc ip o alues o an unclassi ied objec belong o he g oup de ined by
hose no ms.
A common me hod o de e mine he no ms o a class is o ake a sample o shapes we
know o belong o ha class and calcula e he mean o median alues o each
desc ip o . In addi ion, a measu e o he dis ibu ion o alues wi hin he sample can
be made. Classi ica ion hen consis s o compa ing he alues o i s desc ip o s wi h
ha o he mean, possibly aking in o accoun he dis ibu ion o he class.
Gi en wo se s o desc ip o s, how do we measu e hei deg ee o simila i y? I wo
shapes, A and B, p oduce a se o alues ep esen ed by a(i) and b(i) hen he dis ance
be ween hem can be gi en as c(i) = a(i) – b(i). I a(i) and b(i) a e iden ical hen c(i)

- 17 -
will be ze o. I hey a e di e en hen he magni udes o he coe icien s in c(i) will
gi e a easonable measu e o he di e ence. I p o es mo e con enien o ha e one
alue o ep esen his a he han he se o alues ha make up c(i). The easies way
is o ea c(i) as a ec o in a mul i-dimensional space, in which case i s leng h, which
ep esen s he dis ance be ween he planes, is gi en by he squa e oo o he sum o
he squa es o he elemen s o c(i). In his way classi ica ion can be pe o med by
choosing he class mean ha is closes o he shape o be classi ied.
Ea lie wo k on his p ojec used his dis ance measu e in classi ica ion wi h some
limi ed success (Keyes and Wins anley 1999, 2000). Howe e , his me hod akes no
accoun o he dis ibu ion o desc ip o alues o each class. The e o e i was
decided o inco po a e he in o ma ion gi en by he dis ibu ion using Bayesian
s a is ics.
3.2 Classi ica ion using Bayes Theo em
Bayesian s a is ics allows us o use he dis ibu ion o he alues o each desc ip o
o each class o objec in de e mining he p obabili y ha a pa icula objec belongs
o ha class. Gi en a pa icula alue o a desc ip o , we can calcula e he likelyhood
o ha alue occu ing in he dis ibu ion o alues o a pa icula class. Applying
Bayes heo em, we can calcula e om his he p obabili y o he objec belongs o ha
class. We can calcula e such a p obabili y o each class. We hen decide ha he
objec belongs o he class o which i ha desc ip o gi es he highes p obabili y.
The objec i e is o design classi ie s ha will classi y an objec in he mos p obable
o he classes gi en. Fo example, in he expe imen desc ibed la e in his epo , ou
classi ica ion ask has six classes, Buildings, De ined Na u al Land Co e , Mul iple
Su ace Land, Gene al Unmade Land, Made Road and Road Side, 61,...,
ω
ω
espec i ely, and an unknown ea u e ype aken om he da a-se ( o example a
building) ep esen ed by he ea u e ec o
x
. F om his he condi ional o pos e io i
p obabili ies 1,2,...,6 i ),|(
=
xP i
ω
can be o med which ep esen he p obabili y ha
he unknown ea u e ype belongs o he espec i e class i
ω
gi en ha he
- 18 -
co esponding ea u e ec o akes on he alue
x
. To calcula e he pos e io i
p obabili ies, Bayes decision heo y p inciples a e applied.
The i s s ep in ol es he calcula ion o he p io p obabili ies )( i
P
ω
o each class.
Take o example he Building class 1
ω
and De ined Na u al Land Co e (De ined
Land) class 2
ω
. Then, )( 1
ω
Pand )( 2
ω
Pdeno e he p obabili ies o a ea u e ype
belonging o ei he class 1
ω
o 2
ω
espec i ely be o e we ha e conside ed any
desc ip o alues. As we ha e a p e iously classi ied da a-se , we can es ima e his
p io i p obabili ies as:
OFea u esTo alNumbe
ildingsNumbe O Bu
P=)( 1
ω
OFea u esTo alNumbe
indLAndNumbe O De
P=)( 2
ω
Gi en hese p obabili ies )( 1
ω
Pand )( 2
ω
P he i s c i e ion o deciding whe he an
obse ed ea u e ype is o ype Building o De ined Land would simply be o ake he
class wi h he la ge p obabili y, which can be w i en as:
121 hen )( )(
ω
ω
ω
PPi
≥
221 hen )( )(
ω
ω
ω
PPi
<
Be e p obabili y esul s can gene ally be ob ained by conside ing addi ional
in o ma ion abou he ea u es such as he mean and s anda d de ia ion o each class.
Le his addi ional in o ma ion be iden i ied by he desc ip o ec o x (using ea u e
ec o o ep esen mo e han one single measu ed ea u e). Using his in o ma ion he
condi ional p obabili ies )|( xP i
ω
discussed ea lie can be o med. The classi ica ion
c i e ion can now be desc ibed as:
121 decide hen )|( )|(
ωωω
xPxPi >
and
212 decide hen )|( )|(
ωωω
xPxPi >
- 19 -
Bayes laws can be applied o hese condi ional p obabili ies o ede ine hem in e ms
o hei densi y unc ions, which a e deno ed by )|( 1
ω
x and )|( 2
ω
x . The
de i a ion o he new classi ica ion c i e ion, now in e ms o he condi ional densi y
unc ions )|( 1
ω
x and )|( 2
ω
x s a es ha
∑
=
=2
1
)()|(
)()|(
)|(
k
kk
ii
i
Px
Px
xP
ωω
ωω
ω
So equa ion abo e can be ew i en as:
hen
)()|(
)|()(
)()|(
)|()(
1
2
1
22
2
1
11
ω
ωω
ωω
ωω
ωω
∑∑
==
≥
k
kk
k
kk Px
x P
Px
x P
i
hen
)()|(
)|()(
)()|(
)|()(
2
2
1
22
2
1
11
ω
ωω
ωω
ωω
ωω
∑∑
==
<
k
kk
k
kk Px
x P
Px
x P
i
Bayes decision ule is ob ained by elimina ing he denomina o and is as ollows:
12211 hen )|()( )|()(
ωωωωω
x Px Pi ≥
22211 hen )|()( )|()(
ωωωωω
x Px Pi < ?
)|(
)|(
)(
1
2
ω
ω
x
x
xL =
)(
)(
2
1
ω
ω
P
P
T=
F om he condi ional densi y unc ions a likelihood a io )(hL and h eshold
T
can be
ob ained. Using hese unc ions he abo e c i e ion now be exp essed as:
- 20 -
1
hen )(
ω
xLT ≥
2
hen )(
ω
xLT <
which eads i 1
decide hen )(
ω
xLT ≥2
decide
ω
else .
This c i e ion can be gene alised qui e easily o si ua ions in ol ing mo e han wo
classes and mul iple dimensional ea u e spaces. So, le k be he numbe o classes
in ol ed in his p ojec which equals six and using he espec i e condi ional densi y
unc ions )|( i
x
ω
he Bayesian classi ica ion can now be w i en as ollows:
i
,1
)}()|({)()|(
ωωωωω
selec henPx MaxPx i kk
kk
ki =
=
3.3 Implemen ing Bayesian Classi ica ion
Applying Bayes Theo em o classi ica ion he e o e equi es:
• he calcula ion o p io p obabili ies o each class occu ing
• he modelling o a dis ibu ion unc ion o he likelihoods o alues occu ing o
each class
Bo h o hese we e es ima ed h ough an analysis o he classi ica ion o a da a-se
p o ided by O dnance Su ey. The dis ibu ion unc ion o each desc ip o was
app oxima ed as a no mal cu e, modelled om he means and s anda d de ia ions
calcula ed om he da a-se .
Using Bayesian classi ica ion a class can be assigned o each objec based on he
alue o one desc ip o . This is accompanied by a p obabili y es ima e ha he
classi ica ion is co ec . We a e e alua ing h ee shape desc ip ion me hods, each
con aining se e al desc ip o s (25 desc ip o s in all). I , as is likely, hese disag ee as
o he classi ica ion, we equi e a me hod o combining hem o p oduce an o e all
consensus as o he co ec classi ica ion.
- 21 -
Chap e 4: Combining Classi ie s
When se ing ou o design a shape ecogni ion sys em he ul ima e goal is o achie e
he bes possible classi ica ion pe o mance. A aining his goal in ol es he
applica ion o sui able classi ica ion schemes/ echniques o he p oblem. T adi ionally
an analysis o he esul s p oduced by each echnique became he basis o choosing
one o he classi ie s as a inal solu ion. Howe e , i has been obse ed in many
s udies ha al hough one echnique would yield he bes pe o mance, he se o
shapes miss-classi ied by he di e en classi ie s would no necessa ily o e lap. This
sugges s ha di e en classi ie echniques can o e complemen a y desc ip ions o
he shapes o be classi ied, which leads o he combining o he classi ie s o
imp o ed pe o mance.
4.1 The Fusion Model
Using and combining mul iple lea ned classi ica ion models o inc easing accu acy
and e iciency is an a ea a ac ing much in e es ecen ly. The cen al p oblem
in ol ed is how o in eg a e se e al classi ie s (o “expe s”) o p oduce a single inal
classi ica ion. Figu e 1, illus a es he decision combina ion opology used in his
epo .
Figu e 1, Decision combina ion opology used o using he esul s o h ee
shape ecogni ion me hods.
Fou ie desc ip o s
Momen in a ian s
Scala desc ip o s
Σ
da a usion algo i hm
map ea u e da a
se
classi ied
ea u e

- 22 -
The app oach aken he e o he usion o he ecogni ion echniques used ollows a
classi ie combina ion scheme de eloped by Ki le e al[1998].
4.2 Theo y
The usion o indi idual classi ie s is based on a heo e ical amewo k se ou in
Bayes heo em. Be o e usion can ake place p obabili ies mus be assigned o
calcula ed indica ing he likelihood ha a pa icula objec belongs o each a ailable
class.
Conside ing he classi ica ion p oblem, whe e Z is o be assigned o one o m possible
classes ),...,( 1m
ω
ω
,assume he e a e R classi ie s each ep esen ing he gi en pa e n
by a dis inc measu emen ec o , he measu emen ec o used by he i h classi ie
being deno ed by xi. In he measu emen space each class k
ϖ
is modelled by he
p obabili y densi y unc ion )|( ki
xp
ω
and i s p io i p obabili y o occu ence is
deno ed )( k
P
ω
. The models a e conside ed o be mu ually exclusi e which means
ha only one class can be associa ed wi h each objec . Acco ding o Bayes heo em,
gi en measu emen s i
x, ,,...1 Ri
=
he pa e n, Z, should be assigned o he class
j
ω
p o ided he a pos e io i p obabili y o he in e p e a ion is maximum, i.e.
assign j
Z
ω
→
i
),...,|(max),...,|( 11 Rk
k
Rj xxPxxP
ω
ω
=
(15)
The Bayesian decision ule (15) s a es ha in o de o use all he a ailable in o ma ion
co ec ly o each a decision, i is essen ial o compu e he p obabili ies o he a ious
hypo heses by conside ing all he measu emen s simul aneously. This is howe e a
e y expensi e compu a ion he e o e ule (15) is simpli ied and exp essed in e ms o
decision suppo compu a ions pe o med by he indi idual classi ie s, each exploi ing
only he in o ma ion con eyed by he ec o i
x. Rew i ing he a pos e io i p obabili y
),...,|( 1Rk xxP
ω
using Bayes heo em we ha e:
- 23 -
)
),...,(
)()|,...,(
),...,|(
1
1
1
R
kkR
Rk xxp
Pxxp
xxP
ω
ω
ω
=
(16)
whe e ),...,( 1R
xxp is he uncondi ional measu emen join p obabili y densi y. This
can be exp essed in e ms o he condi ional measu emen dis ibu ions as ollows:
∑
=
=m
j
jjRR Pxxpxxp
1
11 )()|,...(),...,(
ωω
(17)
The e o e, in he ollowing placing he concen a ion only on he nume a o e ms o
(16).
4.2.1 The P oduc Rule
The measu emen )|,...( 1kR
xxp
ω
ep esen s he join p obabili y dis ibu ion o he
desc ip o alues ex ac ed by he classi ie s. T ea ing he ep esen a ions used as
condi ionally s a is ically independen (as ou lined by Ki le e al ), he ollowing can
be ob ained,
∏
=
=R
i
kikR xpxxp
1
1)|()|,...,(
ωω
(18)
whe e )|( ki
xp
ω
is he measu emen model o he i h ep esen a ion. Subs i u ing
om (18) and (17) in o (16) gi es:
∑∏
∏
=
=
=m
j
R
ijij
R
ikik
Rik xpP
xpP
xxP
1
1
)|()(
)|()(
),...,|(
ωω
ωω
ω
(19)
and using (19) in (15) gi es he ollowing decision ule.
assign j
Z
ω
→
i
)|()(max)|()(
1
1
1
∏∏ =
=
=
=R
i
kik
m
k
R
i
jij xpPxpP
ωωωω
- 24 -
(20)
Pu ing his in e ms o he a pos e io i p obabili ies yielded by he espec i e
classi ie s:
assign j
Z
ω
→
i
)|()(max)|()(
1
)1(
1
1
)1( ∏∏ =
−−
=
=
−− =R
i
ikk
R
m
k
R
i
ikj
RxpPxpP
ωωωω
(21)
The decision ule in (21) quan i ies he likelihood o a hypo hesis by combining he a
pos e io i p obabili ies p oduced by he indi idual classi ie s by means o a p oduc
ule. I can be a se e e ule o combining he classi ie ou pu s as a single desc ip o
o inhibi a pa icula in e p e a ion by ou pu ing a close o ze o p obabili y o i .
4.2.2 Sum Rule
Ki le e el [1998] de eloped a scheme o he usion o indi idual classi ie s called
he sum ule which he based on he abo e heo e ical amewo k. Conside ing he
decision ule in (21) and based on he assump ion ha he a pos e io i p obabili ies
compu ed by he espec i e classi ie s will no de ia e d ama ically om he p io
p obabili ies, he pos e io i p obabili ies can hen be exp essed as:
)1)(()|( kikik PxP
δ
ω
ω
+
=
(22)
whe e ki
δ
sa is ies ki
δ
<< 1. Subs i u ing (22) o he pos e io i p obabili ies in (21)
gi es:
∏∏ ==
−− += R
i
kik
R
i
ikj
RPxPP
11
)1( )1()()|()(
δωωω
(23)
Expanding he p oduc and neglec ing any e ms o second and highe o de , we can
app oxima e he igh hand side o (23) as:
∏∑
==
+=+
R
i
R
i
kikkkik PPP
11
)()()1()(
δωωδω
(24)
- 25 -
By subs i u ing (24) and (22) in o (21) he sum decision ule is ob ained.
assign j
Z
ω
→
i
)]|()()1[(max)|()()1(
11 1ik
R
i
k
R
i
m
k
ikj xPPRxPPR
ωωωω
∑∑
== =+−=+−
(25)
The sum o he classi ie s R is ob ained o each class ωk and he likelihood class
compu ed by aking he maximum a pos e io i p obabili ies p oduced by he sum
combina ion scheme.
4.3 Classi ie Combina ion
The p oduc and sum decision ules in (21) and (25) o m he basic schemes o
classi ie combina ion. Many combina ion s a egies can be de eloped om hese
ules by no ing ha :
)|(max)|(
1
)|(min)|(
11
11ik
R
i
R
i
ikik
R
i
R
i
ik xPxP
R
xPxP
ωωωω
∑
∏==
==≤≤≤
(26)
This shows ha he p oduc and sum ules can be app oxima ed by he uppe o lowe
bounds sugges ed by (26), as app op ia e. Also he ha dening o he a pos e io i
p obabili ies )|( ik xP
ω
o p oduce bina y alued unc ions ki
∆
as









=∆
=
= )|(
1
max)
i
x|( i 1
o he wise 0
i
x
j
P
R
i
k
P
ki
ωω
(27)
esul in he combining o a decision ou come a he han jus he combining o
pos e io i p obabili ies. F om hese app oxima ions he ollowing ules can be
cons uc ed. All he combina ion schemes and hei ela ionship a e ep esen ed in
Figu e 2.
- 32 -
To e alua e each o he me hods as shape ecogni ion echniques, se e al shapes om
he map (buildings, pa cels and oads) we e used as es shapes. Fo he Fou ie
desc ip o and momen in a ian s me hods, he desc ip o alues used o desc ibe he
objec s a e compu ed om he equally spaced (x,y) poin s along he bounda y o each
o he es shapes using he o mulae de i ed in chap e 2. The scala desc ip o s a e
calcula ed om he bounda y o he objec s also, using he scala shape ecogni ion
aspec s desc ibed in chap e 2. The aspec s used a e: a ea; pe ime e leng h;
elonga ion; and numbe o poin s. Table 3 is an example o he i s 16 low-o de
Fou ie desc ip o s ob ained o a house shape, FD(0) ep esen s he i s desc ip o
alue.
0 1.0000 0.0440 0.0415 0.0461 0.0283 0.0095 0.0050
0.0153 0.0013 0.0013 0.0067 0.0048 0.0006 0.0019 0.0043
Table 3: Fou ie desc ip o alues calcula ed o a house shape.
F om inspec ion o he alues p oduced o each polygon, mos o he shape
in o ma ion is desc ibed by he i s ew desc ip o s and so only he i s 16 e ms
we e used o compa ison, emembe ing ha due o he no maliza ion p ocedu es,
FD(0) and FD(1) a e edundan . Table 4 is an example o a se o se en in a ian
momen s (IM) ob ained o a house, oad and pa cel shape (s a ing a index IM(0)).
Buildings Roads Pa cels
IM(0) 0.00021913563 0.0191903068 0.19419031
IM(1) 1.4175713e-08 0.0028776518 0.0093515524
IM(2) 3.3163274e-12 0.0000022101 0.00055687797
IM(3) 7.332081e-14 0.0000002565 1.0685037e-05
IM(4) 2.4223892e-14 0.0000001930 5.696268e-05
IM(5) -7.51903311e-18 -3.7718e-08 -6.2343667e-07
IM(6) 2.12921403e-26 -1.5393e-14 3.212549e-11
Table 4: Momen in a ian alues calcula ed o house, oad and pa cel shapes.
In his pape each o he shape desc ip ion echniques, Fou ie desc ip o s, momen
in a ian s and scala desc ip o s, we e compu ed o h ee ypes o ea u e, namely
buildings, pa cels and oads in six di e en sub-ca ego ies used in O dnance Su ey
la ge-scale da a-se s (Table 1).

- 33 -
Figu e 4, shows a plo o he mean alues o each o hese ca ego ies in h ee-
dimensional space (using he momen s in a ian s me hod in his example).
10-6
10-4
10-2
10-1 5
10-1 0
10-5
100
10-1 5
10-1 0
10-5
100
IM 0
IM 1
IM
2
+ =
buildin g
*= de in edland
<= su ace lan d
o = unm ade-lan d
= oad
x = oadside
Figu e 4: A e age momen in a ian s (IM) o six shape ca ego ies (Pu beck
da a)
A sample o he esul s p oduced by he applica ion o he Fou ie desc ip o s is
p esen ed o e alua e hei use ulness in he shape disc imina ion. These esul s
ob ained o each da a se we e plo ed using he Fou ie desc ip o s (FD(2), FD(3),
FD(4)) o obse e how well he o med sepa a e g oups. Figu e 5 (a) and (b) and
Figu e 6 (a) and (b) below show he deg ee o which hese da a se clus e in FD(2),
FD(3), FD(4) space. No e, ha due o no malisa ion he i s wo e ms ob ained in
he Fou ie desc ip o s se , FD(0) = 0 and FD(1) = 1 a e edundan .
Figu e 5 (a): Clus e ing o he polygon shapes, buildings and de ined na u al land
co e in h ee-dimensional space o he ea u es FD(2), FD(3) and FD(4), (b):
0
0.2 0.4
0.6
0.8 1
0
0.1
0.2
0.3
0.4
0
0.1
0.2
0.3
0.4
0.5
FD(2)
FD(3)
FD
(4)
De inedland
and
buildings
0
0.1
0.2
0.3
0.4
0
0.1
0.2
0.3
0.4
0
0.05
0.1
0.15
0.2
FD(2)
FD(3)
FD
(4)
Building
And
Road
- 34 -
Clus e o he polygon shapes, buildings and made- oad in h ee-dimensional
space FD(2), FD(3) and FD(4
Figu e 6 (a): Clus e ing o he polygon shapes, made- oad and oadside in h ee-
dimensional space o he ea u es FD(2), FD(3) and FD(4), (b): Clus e ing o he
polygon shapes, su ace land, unmade-land and buildings in h ee-dimensional
space FD(2), FD(3) and FD(4).
As hses plo s show, o en no wo ea u e classes a e comple ely dis inc om each
o he . This e idence he e o e indica es ha Fou ie desc ip o s a e no e y good o
use in shape desc ip ion whe e he da a se s a e o a e y gene al shape. To show his
ma hema ically he epea abili y unc ion was compu ed o each o he six map
ca ego ies. Table 5 shows hese measu emen s in FD(2) as i is he mos signi ican
desc ip o alue. The epea abili y o he measu emen s o each class is ep esen ed as
h ee imes he s anda d de ia ion and can be seen in he shaded diagonal column o
he able. The epea abili y o each class is sizeably la ge han he dis ance be ween
he mean alues o all he six classes which shows ha he classes a e no dis ince
enough o conclude any signi ican posi i e esul s.
Buildings De inedland Su aceland Unmade-land MadeRoad Roadside
No. polygons 7976 3147 3003 1251 487 458
Buildings 0.5166 0.0890 0.3590 0.1095 0.0495 0.0343
De inedland 1.1877 0.2700 0.0205 0.0395 0.0547
Su aceland 1.7972 0.2495 0.3095 0.3247
Unmade-land 1.3156 0.0600 0.0752
MadeRoad 1.1323 0.0152
Roadside 0.7112
Table 5: Compa ison o epea abili y wi hin ea u e classes and dis ance be ween
classes o he Fou ie desc ip o echnique in FD(1).
A sample o he esul s p oduced by he applica ion o he momen in a ian s
echnique was also e alua ed. The Figu e 7 shows plo s ob ained o he momen
0
0.2
0.4
0.6
0.8
0
0.1
0.2
0.3
0.4
0
0.05
0.1
0.15
0.2
Made- oad
Road side
FD(4)
0
0.5
1
1.5
2
0
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
FD(2)
FD(3)
FD
(4) Su ace Land
Unmade Land
Building
- 35 -
in a ian s echnique o a sample o each ea u e ype, each plo showing he deg ee
o which each se o objec s clus e in hei h ee-dimensional space.
10-8
10-6
10-4
10-2
10-30
10-20
10-10
100
10-20
10-15
10-10
10-5
IM0
IM1
IM
2
unmadeland
su aceland
building
10-10
10-5
100
10-30
10-20
10-10
100
10-20
10-15
10-10
10-5
IM0
IM1
IM
2
de inedland
buildings
10-5
100
10-15
10-10
10-5
100
10-20
10-15
10-10
10-5
de inedland
and
unmadeland
10-10
10-5
100
10-30
10-20
10-10
100
10-20
10-15
10-10
10-5
IM0
IM1
IM
2
MadeRoad
buildings
Figu e 7. Clus e ing o he polygon shapes, buildings and made- oads, in h ee-
dimensional space o he ea u es IM(0),IM(1) and IM(2).
Figu e 7 shows he deg ee o which he da a se s, building and de ined land co e
clus e and also in a clus e plo o he da a se s, de ined land co e and unmade-land.
In con as , i can be seen how he ea u es buildings and oads sepa a e when plo ed.
To measu e he clus e ing ob ained, he epea abili y unc ion and mean alue
measu emen s we e compu ed o each se o he sample shapes. The esul s can be
seen in able 6. Only he i s momen in a ian s measu e, IM(0) is used he e o make
i easie o ead he able as i is he mos signi ican momen esul .
Buildings De inedland Su aceland Unmade-land MadeRoad Roadside
No. polygons 7976 3147 3003 1251 487 458
Buildings 5.2005e-005 8.8572e-004 1.5488e-005 0.0034 0.0014 4.8116e-004
De inedland 0.0138 8.7023e-004 0.0025 5.5596e-004 4.0456e-004
Su aceland 3.9330e-004 0.0033 0.0014 4.6567e-004
Unmade-land 0.0231 0.0019 0.0029
MadeRoad 0.0188 9.6051e-004
Roadside 0.0048
- 36 -
Table 6: Compa ison o epea abili y wi hin ea u e classes and dis ance be ween
classes o he momen in a ian s echnique in IM(0).
Each ou pu o he momen in a ian s me hod in he shape ecogni ion o gene al
shapes on maps, show ha he e is a signi ican sepa a ion occu ing be ween mos o
he classes. Al hough o e lap does exis (also seen by he human eye) good
classi ica ion occu s. On examining Table 6 mo e closely i can be seen ha he
epea abili y o he buildings is smalle han he dis ance be ween he mean alues
o all ca ego ies excep o he su ace land da a se hough hese alues a e close.
This is also ue o he epea abili y measu e o he su ace land class whe e he
dis ance be ween he means alues is la ge excep o buildings. Compa ing he
igu es ob ained o he o he da a se s we see ha o many he epea abili y measu e
is la ge bu s ill close o he mean dis ance o mos cases.
As p esen ed abo e o he Fou ie desc ip o and momen in a ian s me hods, a
sample o he esul s p oduced by applying he scala desc ip o echnique o he da a
se is e alua ed also. Figu es 8 o 11 show he esul ing clus e g aphs and he deg ee
o which he ea u es sepa a e in he h ee-dimensional space o a ea, pe ime e and
numbe o poin s.
10
0
10
2
10
4
10
6
10
1
10
2
10
3
10
4
10
0
10
1
10
2
10
3
De ined
land
Building
AREA
PERIMETER
NO OF
POINTS
- 37 -
Figu e 8 Clus e ing o he polygons, buildings and de ined land co e , in he
h ee-dimensional space a ea, pe ime e and numbe o poin s
10
2
10
4
10
6
10
1
10
2
10
3
10
4
10
0
10
1
10
2
10
3
10
4
Figu e 9 Clus e ing o he polygons, de ined land co e and unmade-land, in he
h ee-dimensional space a ea, pe ime e and numbe o poin s
10
2
10
4
10
2
10
4
10
1
10
2
AREA
PERIMETER
NO OF POINTS
Figu e 10 Clus e ing o he polygons, buildings and made- oad, in he h ee-
dimensional space a ea, pe ime e and numbe o poin s
De ined land
and
Unmade land
Building
Made- oad
AREA
PERIMETER
NO OF
POINTS

- 38 -
10
0
10
2
10
4
10
6
10
0
10
2
10
4
10
0
10
1
10
2
10
3
10
4
Figu e 11 Clus e ing o he polygons, buildings, su ace land and unmade land, in
he h ee-dimensional space a ea, pe ime e and numbe o poin s
Figu e 8 shows he clus e plo o he da a se s de ined na u al land co e and
buildings. In Figu e 9 a clus e plo o he ea u es de ined na u al land co e and
unmade land. Figu e 10 and Figu e 11 show he deg ee o which he da a se s
buildings and made- oads clus e and he deg ee o which he da a se s buildings,
su ace land and unmade land clus e .
To analysis he esul s u he he esul s a e again ep esen ed ma hema ically, in his
case by compu ing he epea abili y unc ion and mean alue measu emen s o he
a ea, which is conside ed he mos signi ican ea u e desc ip o o he scala s. The
able o he epea abili y and mean alues is as ollows:
Buildings De inedland Su aceland Unmade-land MadeRoad Roadside
No. polygons 7976 3147 3003 1251 487 458
Buildings 962.3439 1.2793e+04 250.4747 3.8176e+04 1.0369e+03 255.5874
De inedland 1.0665e+05 1.2543e+04 2.5382e+04 1.1757e+04 1.2538e+04
Su aceland 1.7478e+03 3.7925e+04 786.3982 5.1127
Unmade-land 1.1575e+05 3.7139e+04 3.7920e+04
MadeRoad 6.7577e+03 781.2856
Roadside 1.7528e+03
Table 7: Compa ison o epea abili y wi hin ea u e classes and dis ance be ween
classes o he scala desc ip o echnique in a ea.
Buildings
Su ace land
Unmade land
NO OF
POINTS
PERIMETER AREA
- 39 -
The ou pu s ob ained o he scala desc ip o me hod o gene al shapes on maps show
ha he e is a signi ican dis inc ion be ween he majo i y o he classes. Some o e lap
exi s bu o e all classi ica ion is good. On examina ion, able 7 shows, especially o
he building ea u es, ha he epea abili y is smalle han han he dis ance be ween
he mean alues which indica es good classi ica ion pe o mance o he scala
me hod.
As shape desc ip o echniques he e idence published o da e is ha all h ee
echniques e alua ed, Fou ie desc ip o s, momen in a ian s and scala desc ip o s,
a e e y good ea u es o use when dealing wi h e y speci ic shapes such as a
pa icula ai c a o alphanume ic cha ac e . On in es iga ion o hei use ulness o
he shape desc ip ion o gene al shapes on maps, o example houses, oads, pa cels
e c. he Fou ie desc ip o s do no appea o be e y success ul. Howe e , he momen
in a ian s echnique p o ed o be signi ican ly mo e success ul in i s ask and speci ic
scala measu es a e also e y disc imina o y. This is illus a ed by he pie cha s in
Figu e 12 de i ed om he esul s summa y in Appendix 5. Each cha shows he
classi ica ion esul s on objec s belonging o each o he six ea u e ypes conside ed.
Fo example, scala desc ip o s co ec ly classi ied almos 100% o buildings.
100%
< 1%< 1%< 1%< 1%< 1%
59%
36%
3%
1%
84%
1%
15%
< 1%< 1%< 1%
< 1%
100%
< 1%< 1%< 1%< 1%
72%
< 1%
19%
8%
98%
2%
Building
De inedLan
d
Su aceLan
d
UnmadeLand
MadeRoad
RoadSide
Scala desc ip o me hod
Building De ined Na u al land Su ace Land
Gene al Unmade
Land
Made Road Road Side
- 40 -
99%
< 1%< 1%< 1%< 1%< 1%
92%
7%
1%
93%
4%
3%
100%
< 1%< 1%< 1%< 1%< 1%
98%
2%
98%
< 1%2%
Building
De inedLand
Su aceLand
UnmadeLand
MadeRoad
RoadSide
Fou ie Desc ip o me hod
Building De ined Na u al Land Su ace Land
Unmade Land Made Road Road Side
100%
< 1%< 1%< 1%< 1%< 1% < 1%
62% 16%
22%
< 1%< 1% 13%
34%
53%
< 1%< 1%< 1%
< 1%< 1%< 1%
100%
< 1%< 1%
63%
< 1%
23%
3%
6%
3%
48%
8%
26%
< 1%< 1%
18%
Building
De inedLand
Su aceLand
UnmadeLand
MadeRoad
RoadSide
Momen In a ian s me hod
Building De ined Na u al Land Su ace Land
Unmade Land Made Road Road Side
Figu e 12 Recogni ion pe o mance o desc ip o me hods by ea u e ype.
- 41 -
5.2 Fusion me hods
Six me hods o da a usion we e implemen ed: majoi y o e, max ule, min ule,
median ule, sum ule and p oduc ule). Two o hese (sum and p oduc ) had wo
e sions whe he hey included o excluded he adjus men o no malisa ion. They
we e applied o use he classi ica ion esul s gi en by he desc ip o s ob ained om
each polygon in h ee ways:
• Each desc ip o (25 in all) ea ed equally o ob ain a global esul (Table 8,
sec ion 7.3.1)
• Each desc ip o used in o i s g oup (3 g oups i.e. scala , FD and MI) o ob ain a
esul o each g oup (Table 8, sec ion 7.3.2 – 7.3.4)
• Each g oup esul used o ob ain an o e all esul (Table 8, sec ion 7.3.5).
Table 8 shows ha , wi h no able excep ions, he classi ica ion accu acy ob ained was
ai ly consis en no ma e which was used. Bes pe o me was he min ule ollowed
by he p oduc ule. Wo s pe o me by a was he no malised sum ule. This
con i ms he a gumen s in [Ki le 1998] which ques ions he heo e ical basis o he
sum ule.
7.3 Pe o mance o used desc ip o s o e all selec ed ea u es
Numbe o polygons p ocessed: 8837
7.3.1 All 25 Desc ip o s
ALL majo i y max min median sum sum adj p oduc p oduc adj
numbe 5978 5974 7047 5992 5992 186 6938 6603
pe cen 68 68 80 68 68 2 79 75
7.3.2 Scala Desc ip o s
SCALARS majo i y max min median sum sum adj p oduc p oduc adj
numbe 6195 6010 6592 6223 6185 196 6381 6552
pe cen 70 68 75 70 70 2 72 74
7.3.3 Fou ie Desc ip o s
FOURIERS majo i y max min median sum sum adj p oduc p oduc adj
numbe 5940 5958 5789 5921 5949 175 5837 5815
pe cen 67 67 66 67 67 2 66 66
7.3.4 Momen In a ian s
MOMENTS majo i y max min median sum sum adj p oduc p oduc adj
numbe 6192 6051 7122 6281 6119 6026 7004 6973
pe cen 70 68 81 71 69 68 79 79
7.3.5 Majo i y o 3 me hods
MAJORITY majo i y max min median sum sum adj p oduc p oduc adj
numbe 6102 6025 6544 6134 6076 198 6294 6419
pe cen 69 68 74 69 69 2 71 73
Table 8: Summa y o pe o mance o usion o desc ip o s on all ea u es in
Plymou h da a se showing numbe and pe cen age co ec ly classi ied.