Computing the Hausdorff distance between curved objets
Full text
Compu ing he Hausdo Dis ane Be ween Cu ed Ob je s
1
Helmu Al Ludmila Sha
Ins i u e o Compu e Siene, F eie Uni e si a Be lin, Takus .9, D-14195 Be lin
Key wo ds:
shap e ompa ison, Hausdo dis ane, pa ame i u es
1. In o du ion
Analysis and ompa ison o geome i shap es a e
o imp o ane in a ious applia ion a eas wi hin
ompu e siene, suh as pa e n eogni ion and
ompu e ision, bu also in o he disiplines on-
e ned wi h he o m o ob je s suh as a og a-
phy, moleula biology, mediine, o biome i sig-
nal p o essing.
The gene al si ua ion is ha we a e gi en wo
ob je s
A
,
B
mo delled as subse s o 2- o 3-
dimensional spae and we wan o know how muh
hey esemble eah o he [1℄.
Fo his pu p ose we need a simila i y measu e
dened on pai s o shapes india ing he deg ee
o esemblane o hese shapes. A equen ly used
simila i y measu e is he Hausdo dis ane, whih
is dened o a bi a y non-emp y ompa se s
A
and
B
. I assigns o eah p oin o one se he dis-
ane o i s loses p oin in he o he and akes he
maximum o all hese alues. Fo mally, we dene
he
one-sided Hausdo dis ane
om
A
o
B
as
~
Æ
H
(
A; B
) = max
a
2
A
min
b
2
B
d
(
a; b
)
;
(1)
whe e
d
(
x; y
) deno es a dis ane measu e b e ween
p oin s
x
and
y
.
He e we will assume he plana ase, i.e., ha
A; B
R
2
and ha
d
is he Eulidean dis ane.
The (bidi e ional)
Hausdo dis ane
b e ween
A
and
B
is dened as
Æ
H
(
A; B
) = max(
~
Æ
H
(
A; B
)
;
~
Æ
H
(
B ; A
)) (2)
We will only des ibe he ompu a ion o he
one-sided Hausdo dis ane om
A
o
B
, he om-
pu a ion o he bidi e ional Hausdo dis ane is
hen s aigh o wa d.
1
This esea h was supp o ed by he Eu op ean Union
unde on a No. IST-2000-26473, P o je ECG.
The aim o his pap e is o nd an algo i hm o
gene al shap es whih a e mo delled by wo se s o
n
algeb ai u es
. When we speak ab ou he Haus-
do dis ane be ween hese wo se s we a ually
mean he Hausdo dis ane b e ween he wo se s
o poin s lying on hese u es. We will es i
o u es ha a e gi en by
a ional pa ame e iza-
ions
, i.e., eah u e is ep esen ed by a pa ame-
e iza ion
:
I
!
R
2
;
(
) = (
x
(
)
; y
(
)) (3)
whe e
I
R
is a losed in e al and
x
(
)
; y
(
) a e
a ional un ions wi h no poles in
I
.
Obse e ha his deni ion inludes some im-
p o an amilies o ee- o m pa ame i u es, o
example B-splines.
Fo simplii y, we assume a e ain gene al p osi-
ion o he inpu u es. In pa iula , we assume
ha any wo u es in e se in a mos ni ely
many p oin s.
2. Basi ases
In his se ion we will in es iga e how he di-
e ed Hausdo dis ane b e ween wo single ob-
je s (u es o p oin s) an b e ompu ed.
2.1.
Poin -u e and u e-poin
The Hausdo dis ane om a p oin
p
= (
u;
)
o a u e
(
)=(
x
(
)
; y
(
))
;
2
I
is min
2
I
d
(
p;
(
)).
The Hausdo dis ane om a u e
(
) o a
p oin
p
is he maximum Eulidean dis ane om
any p oin on
o
p
.
In o de o nd hose pa ame e s
whe e he
minimum o maximum is a ained, we onside he
20 h EWCG Se ille, Spain (2004)
20 h Eu op ean Wo kshop on Compu a ional Geome y
ze o es o he de i a i e o he squa ed dis ane
d
d
[
d
2
(
p;
(
))℄, i.e., he equa ion
2
(
u
x
(
))
x
0
(
) + 2
(
y
(
))
y
0
(
) = 0 (4)
This equa ion has ons an ly many solu ions i he
deg ee o
is b ounded. We all a p oin sa is ying
his equa ion a
oo poin
o
p
on
. In addi ion o
he p oin s gi en by he solu ions o equa ion 4 he
minimum o maximum dis ane an be a ained a
he endp oin s o
(Fig. 1).
p
c( )
Q
Fig. 1. Hausdo dis ane om a u e
(
) o a p oin
p
is
he dis ane om
p
o he a hes p oin on
.
2.2.
Cu e-u e
We edue he p oblem o de e mining he Haus-
do dis ane om a u e
a
,
a
(
) = (
x
a
(
)
; y
a
(
)),
2
I
a
o a u e
b
,
b
(
s
)=(
x
b
(
s
)
; y
b
(
s
)),
s
2
I
b
o
de e mining he dis anes o ons an ly many an-
dida e p oin s on
a
o he u e
b
.
The e a e ou die en yp es o andida e
p oin s. Fi s ly, he Hausdo dis ane an be as-
sumed a one o he endpoin s o u e
a
(
ype
EA
).
Seondly, i an happ en ha he Hausdo dis-
ane is a ained b e ween an endpoin
Q
o
b
and a
p oin on
a
. The e o e, we de e mine on
a
all o o -
p oin s o he endp oin s o
b
by equa ion (4) (
ype
EB
).
Fo he hi d yp e o andida e p oin s we on-
side he
sel -bise o
(o
medial axis
) o a u e,
whih is he se o all p oin s whose minimal dis-
ane o he u e is a ained a mo e han one
p oin on he u e, . Fig. 2.
The Hausdo dis ane om
a
o
b
an b e a -
ained a an in e se ion p oin o
a
wi h he sel -
bise o o
b
. We will only gi e a sys em o equa-
ions des ibing suh a p oin he e o he pa o
he sel -bise o whe e he wo loses poin s a e
in e io p oin s o
b
, see Fig. 3.
poin −poin bisec o
poin −cu e bisec o
cu e−cu e bisec o
Fig. 2. Sel -bise o o a pa abola segmen .
a( )
Q
b(s)
R
P
Fig. 3. The Hausdo dis ane om he u e
a
(
) o he
u e
b
(
s
) is assumed a he in e se ion p oin
Q
o he
u e
a
wi h he sel -bise o o he u e
b
. The p oin
Q
has wo die en in e nal oo -p oin s
P
and
R
on
b
.
Supp ose
Q
=
a
(
) and ha
P
=
b
(
s
) and
R
=
b
(
) wi h
6
=
s
a e he p oin s on
b
loses o
Q
.
Then we ob ain he ollowing sys em o equa ions
o
; s;
and
:
(
x
a
(
)
x
b
(
s
))
2
+ (
y
a
(
)
y
b
(
s
))
2
(
x
a
(
)
x
b
(
))
2
+ (
y
a
(
)
y
b
(
))
2
= 0 (5)
(
x
a
(
)
x
b
(
s
))
x
0
b
(
s
) + (
y
a
(
)
y
b
(
s
))
y
0
b
(
s
) = 0 (6)
(
x
a
(
)
x
b
(
))
x
0
b
(
)+(
y
a
(
)
y
b
(
))
y
0
b
(
) = 0 (7)
In o de o en o e he ondi ion
6
=
s
we in o-
due a new a iable
u
and add one mo e equa ion
o he sys em:
1
u
(
s
) = 0 (8)
We add all poin s de e mined by he ni ely many
solu ions o his sys em o he andida e lis (
ype
SB
).
Fo he ou h yp e o possible andida e p oin s
we obse e ha he Hausdo dis ane an o u
b e ween wo in e io p oin s
p
2
a
and
q
2
b
wi h-
Ma h 25-26, 2004 Se ille (Spain)
ou one o hem lying on he sel -bise o o he
o he u e, see Fig. 4.
a( )
b(s)
p
q
Fig. 4. Hausdo dis ane a in e io poin s.
Sine
q
is a o o p oin on
b
o p oin
p
, he line
segmen
pq
mus b e p e p endiula o he angen
line o u e
b
a p oin
q
. In addi ion i an b e
shown ha he angen line o he u e
a
a p oin
p
mus b e pa allel o he angen line o he u e
b
a p oin
q
and, hus, also p e p endiula o he line
segmen
pq
. The emaining andida e p oin s (
ype
I
) o he Hausdo dis ane a e, he e o e, among
he solu ions o he ollowing sys em:
(
x
a
(
)
x
b
(
s
))
x
0
b
(
s
)+(
y
a
(
)
y
b
(
s
))
y
0
b
(
s
) = 0 (9)
(
x
a
(
)
x
b
(
s
))
x
0
a
(
) + (
y
a
(
)
y
b
(
s
))
y
0
a
(
) = 0 (10)
A de ailed geome i p oo o his a is omi ed
due o spae limi a ions and an b e ound in [7℄.
3. The gene al ase
As was said b e o e, he gene al p oblem we on-
side is o nd he Hausdo dis ane b e ween wo
p oin se s gi en by wo se s
A; B
o a ionally pa-
ame e ized algeb ai u es.
In o de o nd
~
Æ
(
A; B
) we spli he u es o
A
a
hei in e se ion p oin s wi h he Vo onoi diag am
o
B
. The esul ing se
A
0
o u es has he p op e y
ha eah u e lies in one Vo onoi ell o
B
, so i s
dis ane o
B
is he dis ane o one u e and an
b e de e mined using he ehniques o se ion 2.
Compu ing he omple e Vo onoi diag am o al-
geb ai u es is a e y diÆul ask in p a ie and
he e a e some op en ques ions abou he bise o
o algeb ai u es [3{5℄. In [5℄ an app oxima ion
algo i hm o Vo onoi diag ams o u es is gi en.
Ins ead, we jus ompu e he in e se ion p oin s
des ib ed. The spli ing o eah u e
a
o
A
is done
in emen ally. Supp ose ha we ha e lis o in e -
se ion p oin s o he Vo onoi diag am o a subse
o
B
wi h
a
and we wan o add a new u e
b
2
B
. We do his by sanning he u en segmen s
o
a
. Eah segmen
s
b elongs o some u e
2
B
whih has al eady b een p o essed. Fi s we de e -
mine all in e se ion p oin s o he bise o b e ween
b
and
wi h
a
and nd ou whih ones lie inside
s
.
s
is spli u he wi h hese p oin s and some p o -
ions a e labelled wi h
b
as nea es neighbo , o he s
wi h
. A e his has b een done i migh be ne-
essa y o me ge neighb o ing segmen s whih a e
b o h ma ked wi h
b
bu a e sepa a ed by a spli -
p oin om p e ious s eps.
Simila o he ase o sel -bise o s, he in e se-
ion poin s o wi h he bise o b e ween
b
and
an b e ound as solu ions o sys ems o equa ions.
We only gi e his sys em he e o he in e io " bi-
se o o wo u es
b
and
, no he ones o he
bise o be ween an endp oin o one u e and an-
o he u e o b e ween wo endpoin s. These sys-
ems, howe e ha e o b e onside ed, as well.
The sys em o he in e io " bise o uses he
p op e y ha i a p oin
a
(
) lies on he bise o
b e ween
b
and
and he o esp onding o o p oin s
a e
b
(
s
) and
(
) hen he line segmen
a
(
)
b
(
s
)
is p e p endiula o he angen e o
b
0
(
s
), and
a
(
)
(
) is p e p endiula o
0
(
).
d
(
a
(
)
; b
(
s
))
d
(
a
(
)
;
(
)) = 0 (11)
h
(
a
(
)
b
(
s
))
; b
0
(
s
)
i
= 0 (12)
h
(
a
(
)
(
))
;
0
(
)
i
= 0 (13)
The wo s ase unning ime o ou algo i hm
as s a ed is
O
(
nm
2
) i
A
onsis s o
n
and
B
o
m
u es, assuming ha he deg ees o he u es a e
b ounded. I an be easily imp o ed o
O
(
nm
log
m
)
by using a di ide-and-onque app oah o he
spli ing o he u es o
A
. I should b e wo hwhile
o u he imp o e he ombina o ial omplexi y o
he algo i hm (see also [2℄), bu ou ma jo in en
was o nd a simple algo i hm ha an be pu in o
p a ie wi h a easonable amoun o eo .
4. Implemen a ion
We implemen ed he algo i hm des ib ed in
C++ using he ompu e algeb a so wa e lib a y
SYNAPS (SYmboli Nume i APplia ionS), see
[8,6℄, o sol ing he sys ems o p olynomial equa-
ions.
20 h Eu op ean Wo kshop on Compu a ional Geome y
Fo isualiza ion pu p oses a g aphial use in-
e ae was de elop ed using he GTK lib a y. I
inludes isualiza ion o he u es, he inpu and
edi ing o he pa ame e iza ion and he in e als
i he pa ame e alues, he ompu a ion o he
Hausdo dis ane and he g aphial india ion o
he andida e p oin s onside ed o he ompu a-
ion. Figu e 5 shows he in e ae wi h an example.
Fig. 5. Resul o a Hausdo dis ane ompu a ion wi h
wo B-splines o deg ee 2. Bo h one-way dis anes and all
andida e p oin s a e shown.
Re e enes
[1℄ Helmu Al and Leonidas J. Guibas. Dis e e geome i
shap es: Ma hing, in e pola ion, and app oxima ion. In
Handbook o ompu a ional geome y
. Elsie e Siene
B.V., 1999.
[2℄ Helmu Al and O ied Shwa zkop . The Vo onoi
diag am o u ed ob je s. In
P o. 11 h ACM Compu .
Geom. Symp.
, pages 89{97, Vanou e , BC, 1995.
[3℄ Ge shon Elb e and Myung-So o Kim. Bise o u es
o plana a ional u es.
Compu e -Aided Design
,
30(14):1089{1096, 1998.
[4℄ Rida T. Fa ouki and Ra jesh Ramamu hy. Degene a e
p oin /u e and u e/u e bise o s a ising in medial
axis ompu a ions o plana domains wi h u ed
b ounda ies.
In e na . J. Compu . Geom. Appl.
, 8:599{
617, 1998.
[5℄ Rida T. Fa ouki and Ra jesh Ramamu hy. Vo onoi
diag am and medial axis algo i hm o plana domains
wi h u ed b ounda ies, I. Theo e ial ounda ions.
Jou nal o Compu a ional and Applied Ma hema is
,
102(1):119{141, Feb ua y 1999.
[6℄ G. Dos Reis, B. Mou ain, R. Rouillie , and Ph.
T ebuhe . An en i onmen o symb oli and nume i
ompu a ion. In
P o. o he In e na ional Con e ene
on Ma hema ial So wa e
, pages 239{249, 2003.
[7℄ Ludmila Sha . Compu ing he Hausdo dis ane
b e ween se s o u es. Mas e 's hesis, F eie Uni e si a
Be lin, Ge many, 2003.
[8℄ h p://www-sop.in ia. /galaad/logiiels/synaps/.