Pa h-Based Dis ance Func ions in
n-Dimensional Gene aliza ions o he
Face- and Body-Cen e ed Cubic G ids
Robin S and aand Benedek Nagy b
aCen e o Image Analysis, Uppsala Uni e si y,
PO Box 337, SE-75105 Uppsala, Sweden
bDepa men o Compu e Science, Facul y o In o ma ics, Uni e si y o Deb ecen,
PO Box 12, 4010, Deb ecen, Hunga y
Abs ac
Pa h-based dis ance unc ions a e de ined on n-dimensional gene aliza ions o he
ace-cen e ed cubic and body-cen e ed cubic g ids. The dis ance unc ions use bo h
weigh s and neighbo hood sequences. These dis ances sha e many p ope ies wi h
adi ional pa h-based dis ance unc ions, such as he ci y-block dis ance, bu a e
less o a ional dependen . Fo he h ee-dimensional case, we in oduce ou di e -
en e o unc ions which a e used o ind he op imal weigh s and neighbo hood
sequences ha can be used o de ine he dis ance unc ions wi h low o a ional
dependency.
1 In oduc ion
By adding a g id poin in he cen e o each cube wi h e ices on g id poin s
in a cubic g id, a body-cen e ed cubic (bcc) g id is ob ained. The ace-cen e ed
cubic ( cc) is ob ained by ins ead adding a g id poin a he cen e o each
ace o he cubes. When using non-s anda d g ids such as he cc and bcc
g ids o 3D images, less samples a e needed o ob ain he same ep esen a-
ion/ econs uc ion quali y compa ed o he cubic g id [1]. This is one eason
o he inc easing in e es in using hese g ids in, e.g., image acquisi ion [1],
image p ocessing [2–4], and isualiza ion [5,6]. See also [7].
Email add esses: [email protected] (Robin S and), [email p o ec ed]
(Benedek Nagy).
P ep in submi ed o Else ie Science 3 Feb ua y 2009
Op imal sampling in he sense o he Shannon sampling heo em is ob ained
when he ecip ocal o a dense g id is used o ep esen ing he image. In his
way, a spa se as possible g id is used o image ep esen a ion [7]. The cc g id
is he denses h ee-dimensional poin -la ice [8] and i s ecip ocal is he bcc
g id. In numbe heo y [8], he cc g id is usually deno ed D3and is a special
case o he poin -la ice Dn, he e e e ed o as he n-dimensional cc g id.
The ecip ocal o his poin -la ice is D∗
n, he e called he n-dimensional bcc
g id. The n-dimensional cc g id is he denses poin -la ice in h ee, ou , and
i e dimensions [8]. Thus, he n-dimensional cc and bcc g ids a e po en ially
impo an o high-dimensional image p ocessing. The 3-dimensional cc and
bcc g ids can, e.g., be used when econs uc ing, e.g., images om compu ed
omog aphy wi h inc eased accu acy, see [1,7]. The esul s in his pape can
be used o ind app op ia e dis ance unc ions o p ocessing such images.
Measu ing dis ances on digi al g ids is o g ea impo ance bo h in heo y and
in many applica ions. Because o i s low o a ional dependency, he Euclidean
dis ance is o en used as dis ance unc ion. E en hough he o a ional depen-
dency is highe , he e a e many easons o use dis ances de ined as minimal
cos -pa hs ins ead. In some aspec s, dis ance unc ions de ined by minimal
cos -pa hs i s he digi al geome y-app oach be e , [9]. Fo example, he se
o he poin s o he digi al plane (squa e g id) ha ing Euclidean dis ance, e.g.,
9 om a poin consis s o ou poin s a om each o he . Ins ead, digi al ci cles
using some pa h-based dis ances ( o ins ance, dis ances based on neighbo -
hood sequences) a e se s o consecu i e neighbo poin s. Ano he aspec is
ha when minimal cos -pa hs a e compu ed, a dis ance unc ion de ined as
he minimal cos pa h be ween any wo poin s is be e sui ed, see, e.g., [10],
whe e he cons ained dis ance ans o m is compu ed using he Euclidean dis-
ance. The esul ing algo i hm is complex since dis ances can be p opaga ed
only o “ isible poin s”. The compu a ional complexi y (w. . . bo h ime and
space) o his algo i hm is la ge han he co esponding algo i hm using a
pa h-based app oach which is simple, as , and easy o gene alize o highe di-
mensions [11,12]. We conclude ha pa h-based digi al dis ances a e impo an
bo h om a heo e ical poin o iew and o se e al applica ions.
Examples o pa h-based dis ances a e weigh ed dis ances, whe e weigh s de-
ine he cos (dis ance) be ween neighbo ing g id poin s [2,3,13], and dis ances
based on neighbo hood sequences, whe e he cos is ixed bu he adjacency
ela ion is allowed o a y along he pa h [4,14]. These pa h-based dis ance
unc ions a e gene aliza ions o he well-known ci y-block and chessboa d dis-
ance unc ion de ined o he squa e g id in [15]. We will abb e ia e neigh-
bo hood sequence wi h ns, dis ance based on neighbo hood sequences wi h
ns-dis ances, and weigh ed dis ances based on neighbo hood sequences wi h
weigh ed ns-dis ances o jus wns-dis ances.
Many app oaches whe e he de ia ion om he Euclidean dis ance is mini-
2
mized in o de o ind he op imal ns (ns-dis ances) o weigh s (weigh ed dis-
ances) ha e been p oposed o Z2. In mos pape s, e o unc ions minimizing
he asymp o ic maximum di e ence o a Euclidean ball and a ball ob ained
by using ns-dis ances [16–19] o weigh ed dis ances [3,13,20] a e minimized.
O he app oaches ha e also been conside ed o ns-dis ances. In [21], op imal
ns o he 2D hexagonal and iangula g ids a e ound using a compac ness
a io – he a io be ween he squa ed pe ime e and he a ea o he con ex
hull o he disks ob ained by using ns. In [22], he symme ic di e ence is used
o ns in Z2and in [23], he ollowing e o unc ions a e conside ed o ns
on he cc and he bcc g ids: absolu e e o , ela i e e o , compac ness a io,
maximal insc ibed ball, and minimal co e ing ball.
In [16], a gene al de ini ion allowing bo h weigh s and ns was p esen ed. The
ull po en ial o using bo h weigh s and ns was disco e ed in [24], whe e ns
and weigh s we e oge he used in he sense o [16], bu wi h he well-known
na u al neighbo hood s uc u e o Z2. In [24], he basic heo y o weigh ed
ns-dis ances on he squa e g id is p esen ed including a o mula o he dis-
ance be ween wo poin s, condi ions o me ici y, op imal pa ame e calcula-
ion, and an algo i hm o compu e he dis ance ans o m. In [25], some basic
heo e ical esul s o weigh ed ns-dis ances on he cc and bcc g ids we e
p esen ed. The heo y o weigh ed ns-dis ances on he cc and bcc g ids was
u he de eloped in [26] by p esen ing su icien condi ions o me ici y and
algo i hms ha can be used o compu e he dis ance ans o m and a minimal
cos -pa h be ween wo poin s. In [27] he heo y o weigh ed dis ances based
on neighbo hood sequences wi h wo neighbo hood ela ions o he gene al
case o poin -la ices is conside ed.
The asymp o ic e o using he compac ness a io was used o ind he op imal
weigh s and ns o weigh ed ns-dis ances on he cc and bcc g ids in [25]. The
basic analysis p esen ed in [25] is ex ended in [28] by conside ing he ela i e
e o , he compac ness a io, he maximal insc ibed ball, and he minimal
co e ing ball. As in, e.g., [3,13,16–18,20], he digi al ball is compa ed wi h he
Euclidean ball o ge a measu e o o a ional dependency o a digi al dis ance.
Also, we analyze he beha io when ns o ini e leng h, i.e., pe iodic ns is
used. No e ha he esul s p esen ed he e also applies o weigh ed dis ances
and ns-dis ances, since hey a e bo h special cases o he p oposed dis ance
unc ion. The dis ance unc ion p oposed he e is used o ind op imal weigh s
o he weigh ed dis ance and op imal ns o ns-dis ances. I ollows ha he
o a ional dependency o he weigh ed ns-dis ance is less han o equal o
bo h he weigh ed dis ance and he ns-dis ance.
When he pape [28] was p esen ed a he 12 h in e na ional wo kshop on
combina o ial image analysis (IWCIA 2008), he e we e se e al ques ions and
commen s abou n-dimensional gene aliza ions o he cc and bcc g ids. The e-
o e, in his pape , some esul s a e ex ended o highe dimensions.
3
This pape consis s o wo pa s. Fi s , we de ine weigh ed ns-dis ances in
he n-dimensional cc and bcc g ids by applying he heo e ical amewo k
p esen ed in [27] o hese g ids. Fo mulas o poin - o-poin dis ance and con-
di ions o me ici y a e p esen ed. We also p esen he op imal pa ame e
compu a ions o he 3D cc and bcc g ids om [28].
2 Dis ance Func ions and G ids
We will now gi e de ini ions o n-dimensional gene aliza ions o he cc and
bcc g ids. Using some p e ious esul s, we will also de ine he ns-dis ance and
he weigh ed ns-dis ance o hese g ids. Le he se N1={ 1, 2,..., M}
de ine he 1-neighbo s o he poin 0in a poin -la ice G. Le also N2=
{u1,u2,...,uN}de ine he s ic 2-neighbo s. We deno e he se o 2-neighbo s
by N1,2=N1∪N2.
A ns Bis a sequence B= (b(i))∞
i=1, whe e each b(i) deno es a neighbo hood
ela ion in G. I Bis pe iodic, i.e., i o some ixed s ic ly posi i e l∈Z+,
b(i) = b(i+l) is alid o all i∈Z+, hen we w i e B= (b(1), b(2),...,b(l)). A
pa h, deno ed P, in a g id is a sequence p0,p1,...,pno adjacen g id poin s.
A pa h is a B-pa h o leng h ni , o all i∈ {1,2,...,n},pi−1and pia e
b(i)-neighbo s. The no a ion 1- and (s ic ) 2-s eps will be used o a s ep o
a 1-neighbo and s ep o a (s ic ) 2-neighbo , espec i ely.
De ini ion 1 Gi en he ns B, he ns-dis ance d(p0,pn;B)be ween he poin s
p0and pnis he leng h o (one o ) he sho es B-pa h(s) be ween he poin s.
Le he eal numbe s αand β( he weigh s) and a pa h Po leng h n, whe e
exac ly l(l≤n) adjacen g id poin s in he pa h a e s ic 2-neighbo s, be
gi en. The leng h o he (α, β)-weigh ed B-pa h Pis (n−l)α+lβ. The B-
pa h Pbe ween he poin s p0and pnis a minimal cos (α, β)-weigh ed B-pa h
be ween he poin s p0and pni no o he (α, β)-weigh ed B-pa h be ween he
poin s is sho e han he leng h o he (α, β)-weigh ed B-pa h P.
De ini ion 2 Gi en he ns Band he weigh s α, β, he weigh ed ns-dis ance
dα,β(p0,pn;B)is he leng h o (one o ) he minimal cos (α, β)-weigh ed B-
pa h(s) be ween he poin s.
The ollowing no a ion is used:
1k
B=|{i:b(i) = 1,1≤i≤k}| and 2k
B=|{i:b(i) = 2,1≤i≤k}|.
We associa e wi h he se s N1and N1,2 he cham e masks C1={( i,1)}M
i=1
and C2=C1∪{(ui,1)}N
i=1. The ec o s in N1and N1,2a e associa ed wi h
4
weigh 1, and he cham e masks a e hus no hing bu uni weigh ed ec o s.
AG-basis wedge o any cham e mask C(Ccould be, e.g., ei he C1o C2)
is a se o nlinea ly independen ec o s i1, i1,..., in om Csuch ha
• i1, i1,..., inis a basis o Gand
•no ec o o Cexcep i1, i1,..., incan be w i en as a linea combina ion
wi h posi i e (no necesa ily in ege - alued) coe icien s o hese ec o s.
See [3] o de ails. Each wedge de ines a poly ope by he con ex hull o 0and
he poin s 0+ ij. Wi h uni weigh s, he poly ope BCo a cham e mask C,
[3], is he union o he poly opes o he wedges.
De ini ion 3 A cham e mask wi h uni weigh s is es ic ed (see [3]) i
(symme y) ( , ω)∈C=⇒(− , ω)∈C(1)
(O ganized in G-basis-wedges)∀p∈G,∃W o Csuch ha
p∈ W and Wis a G-basis-wedge.
(2)
(Con ex no malized poly ope)BC= con (BC).(3)
De ini ion 4 A g id Gis wedge-2-gene a ed by N1and N2i N1and N2a e
such ha
•C1={( i,1)}M
i=1 and C2=C1∪{(wi,1)}N
i=1 a e es ic ed Cham e masks,
• ∀i, ∃j, k :wi= j+ k, and
•each G-basis-wedge o N1is he union o some G-basis-wedges o N1,2.
In [27], he ns-dis ance and he weigh ed ns-dis ance we e p esen ed o an
a bi a y poin -la ice Gwedge-2-gene a ed by N1and N2. Le dC1be he
dis ance unc ion ob ained by using he Cham e mask C1and dC2be he
dis ance unc ion ob ained by using he Cham e mask C2. In o he wo ds, o
any poin s p,q∈G,dC1(p,q) is he leng h o he sho es pa h be ween p
and qusing only local s eps om N1and dC2(p,q) is he leng h o he sho es
pa h be ween pand qusing local s eps om N1,2. The ollowing heo ems a e
p o ed in [27].
Theo em 5 (ns-dis ance in Gwedge-2-gene a ed by N1and N2)Le G
wedge-2-gene a ed by N1and N2, he neighbo hood sequence Band he poin s
p,q∈Gbe gi en. Then
d(p,q;B) = min nkk≥max ndC2(p,q), dC1(p,q)−2k
Boo.
When he squa e g id is conside ed and dC2is he chessboa d dis ance and
dC1is he ci y-block dis ance, he ns-dis ance is less han (o equal o) he
ci y-block dis ance and g ea e han (o equal o) he chessboa d dis ance.
5
Theo em 5 says ha by eplacing pai s o 1-s eps om dC1wi h as many
2-s eps as he sequence allows, he ns-dis ance is ob ained.
Rema k 6 We will conside weigh s αand βas eal numbe s αand βsuch
ha 0< α ≤β≤2α. This is na u al since
•a2-s ep should be mo e expensi e han a 1-s ep since s ic 2-neighbo s a e
in ui i ely a a la ge dis ance han 1-neighbo s (p ojec ion p ope y) and
• wo 1-s eps should be mo e expensi e han a 2-s ep – o he wise no 2-s eps
would be used in a minimal cos -pa h.
In he ollowing heo em, he 1-s eps a e weigh ed wi h αand he 2-s eps a e
weigh ed wi h β. A o mal p oo is ound in [27].
Theo em 7 (Weigh ed ns-dis ance in Gwedge-2-gene a ed by N1and N2)
Le Gwedge-2-gene a ed by N1and N2, he ns B, he weigh s α,βsuch ha
0< α ≤β≤2α, and he poin s p,q∈Gbe gi en. Then
dα,β(p,q;B) = (2d(p,q;B)−dC1(p,q)) α+ (dC1(p,q)−d(p,q;B)) β.
We will now de ine n-dimensional gene aliza ions o he cc and bcc g ids and
apply Theo em 5 and 7 o hese g ids.
2.1 The n-dimensional cc g id
We use he ollowing de ini ion o he n-dimensional cc g id o n≥3:
Fn={p∈Zn:x1+x2+...+xn≡0 (mod 2)}
oge he wi h he s aigh - o wa d gene aliza ion o he neighbo hoods in he
h ee-dimensional g id Fused in, e.g., [4,25,26,28], o ge he na u al neigh-
bo hoods N1and N2 o Fn:
N1=n = ( 1, 2,..., n)∈Fn: max {| i|} = 1 and X| i|= 2o
N2=n = ( 1, 2,..., n)∈Fn: max {| i|} = 2 and X| i|= 2o.
The ollowing lemma gi es a su icien and necessa y condi ion o a se o
ec o s in Fn o be a basis o Fn.
Lemma 8 A se F={ 1, 2,..., n}o ec o s in Fnis a basis o Fni
de ( 1, 2,..., n) = ±2
6
The p oo o Lemma 8 is echnical and is he e o e omi ed. The lemma can
be p o ed analogously o Lemma 4.2 in [3]. To do so, we need o p o e ha
any de e minan o he ec o s 1, 2,..., no Fnis a mul iple o 2. Indeed,
gi en any ec o = (x1, x2,...,xn)∈Fn,x1=Pn
i=2 xi+ 2a o some in ege
a. Then
= 2a, x2−
n
X
i=2
xi, x3−
n
X
i=2
xi,...,xn−
n
X
i=2
xi!.
I ollows ha bo h |de ( 1, 2,..., n)|and ha |de ( 1, 2,...,w,..., n)|,
whe e w∈Fn, a e di isible by 2.
The ollowing ema k is used o ind he wedges used o de ine he weigh ed
ns-dis ance o Fn.
Rema k 9 The sys ems o equa ions
1 1 1 ···1 1 1
1 0 0 ···0 0 0
0 1 0 ···0 0 0
.
.
..
.
..
.
.....
.
..
.
.
0 0 0 ···1 0 0
0 0 0 ···0 1 −1
a1
a2
a3
.
.
.
an−1
an
=
x1
x2
x3
.
.
.
xn−1
xn
and
1 1 1 ···112
1 0 0 ···000
0 1 0 ···000
.
.
..
.
..
.
.....
.
..
.
.
0 0 0 ···100
0 0 0 ···010
b1
b2
b3
.
.
.
bn−1
bn
=
x1
x2
x3
.
.
.
xn−1
xn
.
ha e solu ions
a1=x2
a2=x3
.
.
.
an−2=xn−1
an−1=x1+xn−(x2+...+xn−1)
2
an=x1−(x2+x3+...+xn)
2and
7
b1=x2
b2=x3
.
.
.
bn−1=xn
bn=x1−(x2+x3+...+xn)
2
which a e all non-nega i e when x1≥x2≥...≥xnand x1≥x2+x3+...+xn.
The ollowing lemma says ha o ind a sho es pa h be ween 0and any poin
p= (x1, x2,...,xn)∈Fnsuch ha x1≥x2≥...≥xn≥0 and x1≤Pn
i=2 xi,
i is enough o use only 1-s eps.
Lemma 10 Fo any poin p= (x1, x2,...,xn)∈Fnsuch ha x1≥x2≥
...≥xn≥0and x1≤Pn
i=2 xi, he ollowing algo i hm e mina es in x1+x2+...+xn
2
s eps.
Ini ially, le j= 1 and qj=p.
⋆Dec ease he wo la ges coo dina e alues in qjby 1, inc ease jby
1and le he esul be qj.
Repea ⋆un il qj=0.
PROOF. Since he sum o coo dina es is e en by de ini ion, x1+x2+...+xn
2is
an in ege . I ollows om x1≤Pn
i=2 xi ha , i qi6=0, he e will always
be a leas wo coo dina es wi h posi i e alues: Assume ha his is no he
case, hen a some s ep qi= (b, 0,0,...,0), whe e b > 0. Since he coo dina e
wi h he la ges alue is dec eased in each s ep, x1=b+Pn
i=2 xi. Bu his
con adic s ha x1≤Pn
i=2 xi.2
Now we gi e a o mula ha gi es he ns-dis ance in he n-dimensional ace-
cen e ed cubic g id.
Theo em 11 (ns-dis ance in Fn)Le Fnbe wedge-2-gene a ed by N1and
N2and le he neighbo hood sequence Band he poin p= (x1, x2,...,xn)
such ha x1≥x2≥. . . ≥xn≥0be gi en. Then
d(0,p;B) = min ll≥max x1+x2+...+xn
2, x1−2l
B.
PROOF. Fi s he case x1≥x2+x3+...+xnis conside ed. Wi h he
neighbo hoods N1and N1,2, we use
8
F1=
(1,1,0,···,0,0,0)
(1,0,1,···,0,0,0)
.
.
.
(1,0,0,···,0,0,1)
(1,0,0,···,0,0,−1)
and
F2=
(1,1,0,···,0,0,0)
(1,0,1,···,0,0,0)
.
.
.
(1,0,0,···,0,0,1)
(2,0,0,···,0,0,0)
.
By Lemma 8, he se s F1and F2a e bases o Fnand by Rema k 9, any poin
psuch ha x1≥x2≥... ≥xnand x1≥x2+x3+...+xncan be w i en
as a linea combina ion o ec o s om F1and F2wi h posi i e coe icien s.
The e o e, F1and F2de ine he 1-wedge and 2-wedge o any poin psuch ha
x1≥x2≥...≥xnand x1≥x2+x3+...+xn. Rema k 9 gi es he numbe
o local s eps needed o each he poin p, i.e., dC1(0,p;B) = Pai=x1and
dC2(0,p;B) = Pbi=x1+x2+...+xn
2. Using Theo em 5, we ge he o mula in
Theo em 11.
Fo he case x1≤x2+x3+...+xn, we ha e no ound he wedges in he gene al
n-dimensional case. I is, howe e , clea ha he ns-dis ance is x1+x2+...+xn
2
independen o he neighbo hood sequence B(using only local s eps om N1)
as Lemma 10 shows.
Since x1≤x2+x3+...+xn, he pa h hqj,qj−1,...,q1iob ained om he
algo i hm in Lemma 10 is a pa h o leng h x1+x2+...+xn
2using only local s eps
om N1. Also, x1+x2+...+xn
2≥x1≥x1−2k
B o any Band k, so he o mula
in Theo em 11 is alid. 2
As one can see he e a e wo cases. In he i s case a sho es pa h is ob ained
by only 1-s eps; while in he second case (x1> x2+...+xn) 2-s eps should be
conside ed o ind he sho es pa h. Now we gi e he cos o a minimal cos
pa h when he weigh s αand βa e used.
Theo em 12 (weigh ed ns-dis ance in Fn)Le Fnbe wedge-2-gene a ed
by N1and N2and le he ns B, he weigh s α,βs. . 0< α ≤β≤2α,
9
2−γ
γα +β−βγ ,γ
γα +β−βγ ,0!and 1
α,1
α,0 o d cc and
2−γ
γα +β−βγ ,γ
γα +β−βγ ,γ
γα +β−βγ !and 1
α,1
α,1
α o dbcc.
The shape o he polyhed a ob ained o some alues o α, β, γ a e shown in
Figu e 2 and 3 o he cc and bcc g ids, espec i ely. In app oxima ions he
a io o αand βma e s.
Le APbe he su ace a ea and VP he olume o he ( egion enclosed by he)
polyhed on P. The alues o APand VPa e de e mined by he e ices o he
polyhed a.
Le B be a Euclidean ball o adius . The ollowing e o unc ions a e
conside ed
Fig. 3. Shapes o balls o dbcc
α,β(·,·;γ) o a ixed adius ,α= 1, and (le o igh )
γ= 0,0.25,0.5,0.75,1 and ( op o bo om) β= 1,1.25,1.5,1.75,2.
16
E1= max
p,q∈∂P |p|
|q|!−1 ( ela i e e o ) (7)
E2=
A3
P
V2
P
36π−1 (compac ness a io) (8)
E3= min
:B ⊂P(VP/VB )−1 (maximal insc ibed ball) (9)
E4= min
:P⊂B
(VB /VP)−1 (minimal co e ing ball) (10)
These e o unc ions a ain hei minimum alue 0 when Ais he su ace
a ea and Vis he olume o a Euclidean ball. The alues o α,β, and γ ha
minimize he e o unc ions a e compu ed nume ically. The polyhed a a e
gi en by hei e ices, gi en abo e. All e o unc ions a ain a minimum
alue wi hin he domain 0 < α ≤β≤2α, 0 ≤γ≤1, so he compu a ion is
s aigh - o wa d (when an analy ic solu ion could no be ound, he Nelde -
Mead simplex me hod was used). The e o unc ion E1ge s op imal alue
no only in a poin when weigh s a e used on he cc g id. In hese cases he
pa ame e s C1, C2and C3a e used in Table 1. C1can be any alue such ha
√2≤C1≤5/3.(11)
Mo eo e , C3can be any alue in he ange 0 ≤C3≤2(√2−1) and C2any
alue sa is ying he ollowing inequali ies (see also Figu e 7):
qC2
3+ 2 −2C3−C3
1−C3≤C2≤min
√3−C31
2√3 + 1
1−C3
,5
3
.(12)
Fo he ela i e e o on he cc g id, he op imum is ob ained on a egion as
shown in Figu e 7. The op imal alues a e ound in Table 1 and isualized by
he shape o he co esponding polyhed a in Figu e 6.
In Figu e 4 and 5, he asymp o ic beha io is shown by le ing α= 1 and
βbe cons an and o each k, 1 ≤k≤1000 using a ns Bo leng h k ha
app oxima es he op imal ac ion γ. The alues o he e o unc ions and k
a e plo ed in he igu es. The plo s in Figu e 4 and 5 show how he e o unc-
ions pe o m o ns o ini e leng hs (pe iodic ns). Neighbo hood sequences
ob ained by he ollowing ecu si e o mula a e used
b(k+ 1) =
1 i 1k
B< γk,
2 o he wise.
The alue o γis shown in Table 1. When γis no uniquely de ined, we use
cons an alues wi hin he allowed in e al. The same hing applies o β.
17
Table 1
Pe o mance o wns-, weigh ed- (w), and ns-dis ances using he e o unc ions E1−
E4de ined in he ex . The op ima o he e o unc ions a e a ained whene e is a
s ic ly posi i e eal numbe . The alues shown in bold a e ixed in he op imiza ion.
The pa ame e s C1,C2, and C3a e ela ed as is shown in inequali ies (11) and (12).
Rela i e e o , E1
cc bcc
Name α β γ E1α β γ E1
w C1 00.2247 1.1547 00.2393
ns 1 1 0.8453 0.2393 1 1 [1/3,2−√2] 0.2247
wns C2 C30.2247 [1/3,2−√2] 0.2247
Compac ness a io, E2
cc bcc
Name α β γ E2α β γ E2
w 1.5302 00.1367 1.2808 00.1815
ns 1 1 0.8453 0.2794 1 1 2−√2 0.2147
wns 1.4862 0.4868 0.1267 1.2199 0.4525 0.1578
Maximal insc ibed ball, E3
cc bcc
Name α β γ E3α β γ E3
w (5/3) 00.1578 1.2808 00.1815
ns 1 1 0.8453 0.2794 1 1 2−√2 0.2147
wns (5/3) 0.3280 0.1563 1.2199 0.4525 0.1578
Minimal co e ing ball, E4
cc bcc
Name α β γ E4α β γ E4
w √2 00.4234 1.1547 00.5708
ns 1 1 0.7408 0.4448 1 1 1/3 0.3860
wns 1.2179 0.5425 0.3272 1/3 0.3860
18
E1
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
β= 1,γ= 0.8453 β= 1.5, γ= 0
E2
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
β= 1,γ= 0.8453 β= 1.4862,γ= 0.4868
E3
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
β= 1,γ= 0.8453 β= 5/3,γ= 0.3280
E4
01.1
1.2
1.3
1.4
1.51.6
1.7
1.8
1.9
3
0 0.5 1 1.5 2 2.5 3
1
1.5
2
2.5
3
3.5
4
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
β= 1,γ= 0.7408 β= 1.2179,γ= 0.5425
Fig. 4. Op imal alues o E1–E4( e ical axis) on he cc g id o neighbo hood
sequences o leng h k(0 < k ≤1000, ho izon al axis showing log10 k) wi h α= 1.
See Table 1 o asymp o ic op ima.
19
E1
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
β= 1,γ= 0.5β= 1,γ= 0.5
E2
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
β= 1,γ= 2 −√2β= 1.2199,γ= 0.4525
E3
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
01.1
1.2
1.3
1.4
0.51.6
1.7
1.8
1.9
1
0 0.5 1 1.5 2 2.5 3
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
β= 1,γ= 2 −√2β= 1.2199,γ= 0.4525
E4
01.1
1.2
1.3
1.4
11.6
1.7
1.8
1.9
2
0 0.5 1 1.5 2 2.5 3
1
1.2
1.4
1.6
1.8
2
2.2
2.4
2.6
2.8
3
01.1
1.2
1.3
1.4
11.6
1.7
1.8
1.9
2
0 0.5 1 1.5 2 2.5 3
1
1.2
1.4
1.6
1.8
2
2.2
2.4
2.6
2.8
3
β= 1,γ= 1/3β= 1,γ= 1/3
Fig. 5. Op imal alues o E1–E4( e ical axis) on he bcc g id o neighbo hood
sequences o leng h k(0 < k ≤1000, ho izon al axis showing log10 k) wi h α= 1.
See Table 1 o asymp o ic op ima.
20
cc bcc
E1
β= 1.414 β= 1 β= 1.5β= 1.154 β= 1 β= 1
γ= 0 γ= 0.845 γ= 0.3γ= 0 γ= 0.586 γ= 0.586
E2
β= 1.530 β= 1 β= 1.486 β= 1.281 β= 1 β= 1.220
γ= 0 γ= 0.845 γ= 0.487 γ= 0 γ= 0.586 γ= 0.453
E3
β= 1.667 β= 1 β= 1.667 β= 1.281 β= 1 β= 1.220
γ= 0 γ= 0.845 γ= 0.328 γ= 0 γ= 0.586 γ= 0.453
E4
β= 1.414 β= 1 β= 1.218 β= 1.155 β= 1 β= 1
γ= 0 γ= 0.741 γ= 0.543 γ= 0 γ= 0.333 γ= 0.333
Fig. 6. Shapes o balls using α= 1 and alues o βand γ ha minimize E1–E4, see
Table 1.
21
1 1.25 1.5 1.75 2
0
0.25
0.5
0.75
1
C2
C3
Fig. 7. The domain o C2and C3in Table 1
4 Conclusions
We ha e gi en gene aliza ions o he cc and bcc g ids o any dimension.
Fo hese g ids, o mulas o he ns-dis ance and weigh ed ns-dis ance we e
p esen ed. We no e ha he weigh ed ns-dis ance in Bnbe ween 0and a poin
ponly depends on he wo coo dina es o pwi h highes absolu e alue. Fo
Fn, all coo dina es a e needed o calcula e he dis ance alues.
In 4D bcc he Euclidean dis ance o he 1-neighbo s a e he same as he 2-
neighbo s. In highe dimensions he 2-neighbo s ha e less Euclidean dis ance,
he e o e i seems o be ui ul o conside weigh s β < α o u u e esea ch.
By in oducing a numbe o e o unc ions ha all a o “ ound” balls (in
he Euclidean sense), he weigh ed ns-dis ance is analyzed o he cc and bcc
g ids. I u ns ou ha he op imal pa ame e s o he special cases o weigh ed
dis ances (γ= 0 o B= (2)) and ns-dis ances (α=β= 1) a e also ound
om his p ocedu e by keeping one o he pa ame e s ixed in he op imiza ion.
The same weigh s and neighbo hood sequences as we e de i ed o weigh ed
dis ances [2,3] and ns-dis ances [4] a e ound in his pape . Figu e 2 and 3 gi es
an o e iew o his ac – weigh ed dis ances a e shown in he le columns
(γ= 0) and ns-dis ances a e shown in he op ows (β= 1). We also no e ha ,
as expec ed, he alue o he e o unc ions o he wns dis ance unc ion a e
lowe han (o , in some cases, equal o) he weigh ed dis ance and ns-dis ance.
We use he coo dina es o he e ices o polyhed a co esponding o he
asymp o ic shape o he balls in he cc and bcc g ids. No e ha he e -
22
ices can be ound also o highe -dimensional gene aliza ions o he cc and
bcc g ids. Since he op imiza ion me hods use geome ic ea u es, such as
a ea and olume, hei ex ensions o highe dimension should be used. The
pa ame e op imiza ion in highe dimensions is le o u u e esea ch.
In he op imiza ion, we le γ ep esen he ac ion o 1:s in he ns. We no e
ha when γis ixed o 0 ( o weigh ed dis ances), his co esponds o a ns
wi h only 2:s. This can be a ained o a neighbo hood sequence o any leng h.
The e o e, in his case he op imum is no asymp o ic and hus, he e o is
alid also o sho dis ances (be ween e.g. neighbo ing g id poin s). When γ
is also subjec o op imiza ion (i.e. when he neighbo hood sequence is used o
de ine he dis ance unc ion), he e o unc ions ha e an asymp o ic beha io .
Howe e , some o he op ima o he ela i e e o (E1) a e loca ed on egions
whe e E1is cons an . Fo example, E1 o he weigh ed ns is op imal when
γ= 0, i.e. o he weigh ed dis ance, and he e o e he op imum is a ained
o any neighbo hood sequence consis ing o only 2:s. See Figu e 4 and 5 and
Figu e 7. This indica es ha his e o unc ion, which has been widely used in
he li e a u e, is no well-sui ed o inding he op imal weigh s and ns he e.
The eason ha E1is minimal on a egion (and no a poin ) is ha he e
a e wo e ices and wo su aces ha ha e poin s ha can be a minimal
dis ance (up o symme y). Thus, he e a e mo e deg ees o eedom han he
es ic ions in he op imiza ion p ocess. Fo he o he e o unc ions (E2–E4),
di e en iable unc ions a e de ined and hey ha e all a single minimum, see
Table 1.
We no e ha he e o unc ions E2(compac ness a io) and E3(maximal
insc ibed ball) gi e he same asymp o ic op imal esul o he bcc g id and
he same o ns-dis ances on he cc g id, see Table 1. Howe e , as is seen in
Figu e 4 and 5, he e o unc ions pe o m di e en ly o ini e, i.e., pe iodic,
neighbo hood sequences. This illus a es ha he di e en e o unc ions a e
di e en , e en hough hey all a e used o app oxima e he Euclidean dis ance.
Di e en applica ions equi e di e en aspec s o he “ oundness” o he balls
and di e en ypes o o a ional (in)dependency.
Analyzing he plo s in Table 1, we see ha he e o con e ges qui e as and
ha a ns o leng h (pe iod) 10 is su icien in gene al.
The applica ion in which he dis ance unc ion will be applied should be used
o selec which e o unc ion ha should be conside ed. Also, by using The-
o em 17, i is easy o ind neighbo hood sequences such ha he esul ing
dis ance unc ion is a me ic, which is p e e able in many applica ions. In u-
i i ely, he polyhed a ha bes app oxima e he Euclidean ball a e gi en by a
dis ance unc ion whe e bo h γand βa e non- i ial, see Figu e 2 and 3. F om
he “op imal shapes” in Figu e 6, we see ha his is wha , e.g., he compac -
ness a io E2 a o s. Thus, wi hou any speci ic applica ion in mind, we sugges
23
he pa ame e s B= (1,2), β= 1.4862α o he cc g id and β= 1.2199α o
he bcc g id. This gi es E2= 0.1276 o he cc g id ( he op imum is 0.12757
and he app oxima ed alue is 0.12760) and E2= 0.1591 ( he op imum is
0.1578) o he bcc g id. We conclude ha we ge a good app oxima ion o
he op imal alues also wi h a sho neighbo hood sequence.
Acknowledgemen s
A p elimina y e sion o he pape was p esen ed a he 12 h In e na ional
Wo kshop on Combina o ial Image Analysis, Bu alo, NY, USA, Ap il 2008
[28]. The au ho s hanks he audience o IWCIA 2008 o hei use ul com-
men s and ques ions. The esea ch is suppo ed by Digi al geome y wi h ap-
plica ions in image p ocessing in h ee dimensions (DIGAVIP) a Cen e o
Image Analysis, Uppsala Uni e si y.
Re e ences
[1] S. Ma ej, R. M. Lewi , E icien 3D g ids o image econs uc ion using
sphe ically-symme ic olume elemen s, IEEE T ansac ions on Nuclea Science
42 (4) (1995) 1361–1370.
[2] R. S and, G. Bo ge o s, Dis ance ans o ms o h ee-dimensional g ids wi h
non-cubic oxels, Compu e Vision and Image Unde s anding 100 (3) (2005)
294–311.
[3] C. Foua d, R. S and, G. Bo ge o s, Weigh ed dis ance ans o ms gene alized
o modules and hei compu a ion on poin la ices, Pa e n Recogni ion 40 (9)
(2007) 2453–2474.
[4] R. S and, B. Nagy, Dis ances based on neighbou hood sequences in non-
s anda d h ee-dimensional g ids, Disc e e Applied Ma hema ics 155 (4) (2007)
548–557.
[5] H. Ca , T. Theussl, T. M¨olle , Isosu aces on op imal egula samples, in:
C. D. H. G.-P. Bonneau, S. Hahmann (Ed.), P oceedings o he symposium on
Da a isualisa ion 2003, Eu og aphics Associa ion, 2003, pp. 39–48.
[6] R. S and, P. S elldinge , Topology p ese ing ma ching cubes-like algo i hms
on he ace-cen e ed cubic g id, in: P oceedings o 14 h In e na ional Con e ence
on Image Analysis and P ocessing (ICIAP 2007), Modena, I aly, 2007, pp. 781–
788.
[7] C. Hami ouche, L. Ibanez, C. Roux, Disc e e opology o A∗
nop imal sampling
g ids. in e es in image p ocessing and isualiza ion, Jou nal o Ma hema ical
Imaging and Vision 23 (3) (2005) 401–417.
24
[8] J. H. Conway, N. J. A. Sloane, Sphe e Packings, La ices and G oups,
G undleh en de Ma hema ischen Wissenscha en 290, Sp inge -Ve lag, New
Yo k, 1988.
[9] R. Kle e, A. Rosen eld, Digi al Geome y: Geome ic Me hods o Digi al
Image Analysis (The Mo gan Kau mann Se ies in Compu e G aphics), Mo gan
Kau mann, 2004.
[10] D. Coeu jolly, S. Migue , L. Tougne, 2D and 3D isibili y in disc e e geome y:
an applica ion o disc e e geodesic pa hs, Pa e n Recogni ion Le e s 25 (5)
(2004) 561–570.
[11] B. J. H. Ve we , P. W. Ve beek, S. T. Dekke , An e icien uni o m cos
algo i hm applied o dis ance ans o ms, IEEE T ansac ions on Pa e n
Analysis and Machine In elligence 11 (4) (1989) 425–429.
[12] R. S and, F. Malmbe g, S. S ensson, Minimal cos -pa h o pa h-based
dis ances, in: P oceedings o 5 h In e na ional Symposium on Image and Signal
P ocessing and Analysis (ISPA 2007), Is anbul, Tu key, 2007, pp. 379–384.
[13] G. Bo ge o s, Dis ance ans o ma ions in digi al images, Compu e Vision,
G aphics, and Image P ocessing 34 (1986) 344–371.
[14] A. Rosen eld, J. L. P al z, Dis ance unc ions on digi al pic u es, Pa e n
Recogni ion 1 (1968) 33–61.
[15] A. Rosen eld, J. L. P al z, Sequen ial ope a ions in digi al pic u e p ocessing,
Jou nal o he ACM 13 (4) (1966) 471–494.
[16] M. Yamashi a, T. Iba aki, Dis ances de ined by neighbo hood sequences,
Pa e n Recogni ion 19 (3) (1986) 237–246.
[17] P. P. Das, Bes simple oc agonal dis ances in digi al geome y, Jou nal o
App oxima ion Theo y 68 (1992) 155–174.
[18] P. P. Das, B. N. Cha e ji, Oc agonal dis ances o digi al pic u es, In o ma ion
Sciences 50 (1990) 123–150.
[19] J. Fa kas, S. Baj´ak, B. Nagy, No es on app oxima ing he Euclidean ci cle in
squa e g ids, Pu e Ma hema ics and Applica ions 17 (2006) 309–322.
[20] B. J. H. Ve we , Local dis ances o dis ance ans o ma ions in wo and h ee
dimensions, Pa e n Recogni ion Le e s 12 (11) (1991) 671–682.
[21] A. Hajdu, B. Nagy, App oxima ing he Euclidean ci cle using neighbou hood
sequences, in: P oceedings o 3 d Hunga ian Con e ence on Image P ocessing,
Domasz´ek, 2002, pp. 260–271.
[22] A. Hajdu, L. Hajdu, App oxima ing he Euclidean dis ance using non-pe iodic
neighbou hood sequences, Disc e e Ma hema ics 283 (2004) 101–111.
25
