S ong sepa a ing (k,k)−su aces on Z3∗
J. C. Ci ia1, E. Domínguez1, A. R. F ancés1and A. Quin e o2
1Uni e sidad de Za agoza, Dp o. In o má ica e Ing. Sis ., Za agoza, Spain.
2Uni e sidad de Se illa, Dp o. Geome ía y Topología, Se illa, Spain.
{jcci ia,noesis,a ances}@uniza .es ,[email p o ec ed]
Abs ac Fo each adjacency pai (k, k)!= (6,6),k, k∈{6,18,26}, we in oduce a new
amily Skk o su aces in he disc e e space Z3 ha s ic ly con ains se e al amilies o su -
aces p e iously de ined, and o he objec s conside ed as su aces, in he li e a u e. Ac ually,
Skk cha ac e izes he s ongly k−sepa a ing objec s o he amily o digi al su aces, de ined
by means o con inuous analogues, o he uni e sal (k, k)−spaces in oduced in [6].
Keywo ks disc e e su ace; con inuous analogue, s ong sepa a ion.
1 In oduc ion
In he g aph– heo e ical app oach o Digi al Topology, he sea ch o a de ini ion o digi al su aces
as subse s o oxels is s ill a wo k in p og ess since i was s a ed in he ea ly 1980’s. Despi e he
in e es o he applica ions in which i is in ol ed ( anging om isualiza ion o image segmen a ion
and g aphics), he e is no ye a well es ablished gene al no ion o digi al su ace ha na u ally
ex ends o highe dimensions. The ac is ha , a e he i s de ini ion o su ace, p oposed
by Mo gen hale [11] o he g id Z3wi h he usual adjacency pai s (26,6) and (6,26), each
new con ibu ion has ei he inc eased he numbe o su aces (s ong su aces [3] and simplici y
su aces [7]) o ex ended he de ini ion o o he adjacency pai s [8], bu s ill lea ing ou some
objec s conside ed as su aces o p ac ical pu poses [10].
Fo each adjacency pai (k,k)#= (6,6),k,k∈{6,18,26}, and wi hin he amewo k o Digi al
Topology in [2], we ha e ecen ly ound [6] a homogeneous (k,k)−space (R3,
kk)whose se o
digi al su aces is he la ges in ha class o digi al spaces. Mo eo e , hese se s o su aces
con ain all hose quo ed abo e. O cou se a Jo dan sepa a ion p ope y holds o hem, bu some
do no sa is y he s ong sepa a ion p ope y usually equi ed o disc e e su aces in Z3. On he
o he hand hey a e de ined by means o con inuous analogues, and hus i migh no be conside ed
as a comple ely disc e e cons uc ion.
Ou goal in his pape is wo old. Fi s ly we p o ide a comple ely disc e e cha ac e iza ion
o he digi al su aces in each (k,k)−space (R3,
kk), by ex ending Kong’s me hod [8] based on
pla es and g aphs. Then, we ind in §5 a local cha ac e iza ion o he s ong sepa a ing condi ion
o digi al su aces o (R3,
kk)which is used o de i e a genuine no ion o (k,k)−su ace.
This wo k con ains an ex ension o p e ious esul s o he (26,6)−adjacency in [4].
2 A se o (k, k)−Jo dan objec s
In his sec ion we in oduce, o each o he usual adjacency pai s (k,k)#= (6,6),k,k∈{6,18,26},
de ined on Z3, a amily o objec s ha sa is ies a Jo dan p ope y. Ac ually, hese objec s could
be conside ed as a s a ing de ini ion o a amily o (k,k)−su aces since hey a e made o small
∗This wo k has been pa ially suppo ed by p ojec MTM2007-65726 MICINN, Spain.
73
Pc
3Pb
4Pe
4P
4Pb
5Pc
6
Pc
2Pc
5Pb
6P8
Figu e 1: Some pa e ns ha may appea in a digi al objec O⊆Z3. Each pic u e ep esen s a uni cube
Co Z3, and he black do s a e he se o oxels in O∩C. The uppe ow con ains he six non-squa e pla es
ha may appea in a digi al objec . The pa e ns in he lowe ow canno appea in a (26,6)−p esu ace.
su ace pieces, called pla es, which a e adequa ely glued o each o he in he way de ined by
an assembly g aph. To in oduce hese no ions we i s ly ecall some basic de ini ions om he
g aph– heo e ical app oach o Digi al Topology.
Two dis inc oxels σ=(xσ
1,x
σ
2,x
σ
3),τ=(xτ
1,x
τ
2,x
τ
3)∈Z3a e said o be 6-, 18- o 26-adjacen
i max{|xσ
i−xτ
i|;1≤i≤3}≤1and hey di e in, a mos , one, wo o h ee o hei coo dina es,
espec i ely. Mo eo e , we say ha wo n-adjacen oxels a e s ic ly n-adjacen i hey a e no
m-adjacen o any m < n, whe e n, m ∈{6,18,26}.Auni cube o Z3is any subse Co eigh
mu ually 26-adjacen oxels. Simila ly, a uni squa e o Z3is a subse o ou mu ually 18-adjacen
oxels ha is ac ually he in e sec ion o wo dis inc uni cubes.
Fo n∈{6,18,26} he ansi i e closu e o he n-adjacency ela ion de ines an equi alence
ela ion on each subse A⊆Z3, whose classes a e called he n-componen s o A. Mo eo e , Ais
said o be n-connec ed i i has only one n-componen .
De ini ion 2.1. Le O⊆Z3be a digi al objec . A subse p⊆Ois said o be a k−pla e in O
i ei he pis a uni squa e o Z3o p=C∩Oco esponds (up o o a ions and symme ies) o
one o he pa e ns in he se Pk, whe e Cis a uni cube o Z3and P6={Pc
3,Pb
4,Pe
4,P
4,Pb
5,Pc
6},
P18 ={Pc
6}and P26 =∅; see Fig. 1. Fo any oxel σ∈Owe deno e by Pk(O,σ) he se o all
k−pla es in Ocon aining σ, while Pk(O)is he se o all k−pla es in O.
Rema ks 2.2. No ice ha he squa e pla es a e he only 26−pla es in any objec . No ice also
ha gi en a uni cube Cand a digi al objec O he se C−O#=∅is i ially 26−connec ed, i is
18−connec ed i C∩O/∈P18 and i is 6−connec ed i C∩O/∈P6∪{Pc
5,Pb
6}; see Fig. 1.
Besides he k−pla es, we conside he ollowing bipa i e g aph, e med he k−assembly g aph,
o any digi al objec O⊆Z3.
De ini ion 2.3. The nodes o he k−assembly g aph o O⊆Z3,Gk(O), a e he elemen s o
Pk(O)∪Ek(O), whe e Ek(O)is he se o all pai s o oxels σ,τ∈Osa is ying one o he wo
ollowing p ope ies:
1. σand τa e 6−adjacen ;
2. σand τa e s ic ly 18−adjacen , no oxel in Ois 6−adjacen o bo h o hem and, mo eo e ,
{σ,τ}is in he in e sec ion o wo k−pla es o O.
And wo nodes p∈Pk(O)and e∈Ek(O)de ine an edge o Gk(O)i and only i e⊆p.
The k−assembly g aph o Oa ound a oxel σ∈Ois he subg aph Gk(O,σ)o Gk(O)induced
by he se o nodes Pk(O,σ)∪Ek(O,σ), whe e Ek(O,σ)={e∈Ek(O); σ∈e}.
Rema k 2.4. Fo k∈{18,26} he se Ek(O)consis s en i ely o pai s o 6−adjacen oxels since
he squa e pla es and he Pc
6pla es canno sha e jus wo s ic ly 18−adjacen oxels.
De ini ion 2.5. A digi al objec S⊆Z3is said o be a (k,k)−p esu ace i he ollowing condi ions
hold o each oxel σ∈S:
74
τ1
τ2
τ0
(a) S
p
p
q
q
1
1
2
2
(b) G6(S)
Figu e 2: A(18,6)−p esu ace Sand i s 6−assembly g aph G6(S). Each do in (b) ep esen s one o he
eigh uni cubes shown in (a), which a e ac ually 6−pla es o S. Each squa e in (b) ep esen s a pai o
s ic ly 18−o 6−adjacen oxels in S ha , oge he wi h pla es, de ine he 6−assembly g aph o S.
1. Fo each uni cube Cσ⊆Z3con aining σ, he in e sec ion Cσ∩Sdoes no co espond
(up o o a ions and symme ies) o any pa e n in FPkk, whe e FP6,26 =FP18,26 =
FP6,18 =FP18,18 ={P8},FP26,26 =FP26,18 ={Pc
2,P8},FP18,6={Pc
5,Pb
6,P8}and FP26,6=
{Pc
2,Pc
5,Pb
6,P8}; see Fig. 1.
2. Gi en a oxel τ∈Ss ic ly 18−adjacen o σand such ha no o he oxel in Sis 6−adjacen
o bo h σand τ, le C1and C2be he wo only uni cubes o Z3con aining {σ,τ}. I k=6
hen Ci∩S∈P6(O) o a leas one index i∈{1,2}, while i k,k∈{18,26} hen {σ,τ}is
con ained in a 6−componen o S∩(C1∪C2).
3. I τ∈Sis 6−adjacen o σ hen Pk(S, σ)∩Pk(S, τ)consis s exac ly o wo pla es.
4. Pk(S, σ)#=∅and Gk(S, σ)is a cycle.
Rema k 2.6. No ice ha condi ion (2) in he de ini ion abo e is oid i k=6.
Example 2.7. Figu e 2 depic s a (18,6)−p esu ace S, made o eigh pla es, and i s 6−assembly
g aph G6(S). No ice ha he oxel τ0∈Sbelongs o exac ly wo pla es p1,p
2∈P6(O)and i is
6−adjacen o bo h τ1and τ2. Hence, he pai s o oxels qi={τ0,τi},i=1,2, belong o E6(S, τ0)
and he 6−assembly g aph o Sa ound τ0,G6(S, τ0), is he cycle de ined by he e ices p1,p
2,q
1
and q2in Fig. 2(b).
The assembly g aph endows each p esu ace wi h he combina o ial s uc u e o a su ace. Mo e
p ecisely, we will show in Th. 4.8 below ha (k,k)−p esu aces cha ac e ize he digi al su aces o
he uni e sal (k,k)−space (R3,
kk)de ined in [6] wi hin he app oach o Digi al Topology in [2]. In
pa icula , we ob ain, as a co olla y o his cha ac e iza ion and Th. 3.3, ha all (k,k)−p esu aces
a e Jo dan objec s; ha is, each k-connec ed (k,k)−p esu ace Ssepa a es i s complemen Z3−S
in o wo k−componen s.
In o de o p o ide he app op ia e con ex o Th. 4.8 we collec he basic elemen s o his
amewo k in nex sec ion.
3 Uni e sal (k, k)−spaces and digi al su aces
In his sec ion we ecall he de ini ions and main esul s om [6] needed in his pape , which we e
es ablished wi hin he amewo k o Digi al Topology in oduced in [2]. In his app oach a digi al
space is a pai (K, ), whe e Kis a polyhed al complex and is a ligh ing unc ion om which
we associa e o each digi al image an Euclidean polyhed on called i s con inuous analogue.
In his pape we will only deal wi h he uni e sal (k,k)−spaces (R3,
kk)de ined in [6]. The
complex R3is de e mined by he collec ion o uni cubes in he Euclidean space R3cen e ed a
poin s o in ege coo dina es. Each 3-cell in R3 ep esen s a oxel, and so any digi al objec is a
subse o he se cell3(R3)o 3-cells in R3. The lowe dimensional cells o R3(ac ually, d-cubes,
0≤d<3) a e used o desc ibe he a ious possible ways oxels link o each o he . No ice ha
each d−cell σ∈R3can be associa ed o i s cen e c(σ). In pa icula , i dim σ=3 hen c(σ)∈Z3
75
and so e e y digi al objec in R3can be na u ally iden i ied wi h a subse o he disc e e space
Z3. Hence o h we shall use his iden i ica ion wi hou u he commen .
Ligh ing unc ions a e maps o he o m P(cell3(R3))×R3→{0,1}, whe e P(cell3(R3)) s ands
o he amily o all subse s o cell3(R3); i.e., all digi al objec s. In o de o in oduce he ligh ing
unc ions kkwe need some mo e no a ion.
As usual, gi en wo cells α,β∈R3we w i e α≤βi αis a ace o β, and α<βi in
addi ion α#=β. Gi en a digi al objec O⊆cell3(R3) he s a o a cell αin Ois he se
s 3(α;O)={σ∈O;α≤σ}o 3-cells ( oxels) in Oha ing αas a ace. Simila ly, he ex ended
s a o αin Ois he se s ∗
3(α;O)={σ∈O;α∩σ#=∅}. Finally, he suppo o Ois he se
supp(O)o cells o R3(no necessa ily oxels) ha a e he in e sec ion o 3-cells in O; ha is,
α∈supp(O)i and only i α=∩{σ;σ∈s 3(α;O)}. To ease he w i ing, we use he ollowing
no a ion: s 3(α;R3) = s 3(α; cell3(R3)) and s ∗
3(α;R3) = s ∗
3(α; cell3(R3)).
Rema k 3.1. The iden i ica ion be ween cells in R3and hei cen e s gi es us a one– o–one
co espondence be ween 0−cells (1−cells) and uni cubes (squa es, espec i ely) o Z3. Namely,
s 3(α;R3)is a uni cube (squa e) o each 0−cell (1−cell) α∈R3. Thus, i pis pla e in a gi en
objec O, hen p= s 3(α;O) = s 3(α;R3)∩O o some cell αwi h dim α≤1, which is called he
cen e o p. Simila ly, i e={σ,τ}is a node o Gk(O)in he se Ek(O), he cell δ=σ∩τis a
2−cell o a 1−cell, depending on whe he σand τa e 6−adjacen o s ic ly 18−adjacen , which
will be also called he cen e o he node e.
Fo (k,k)#= (6,6),k,k∈{6,18,26}, he ligh ing unc ions kk a e de ined as ollows. Gi en
a digi al objec O⊆cell3(R3)and a cell δ∈R3, k,k(O,δ)=1i and only one o he ollowing
condi ions hold:
1. dim δ≥2and δ∈supp(O)
2. dim δ=0and s 3(δ;O)co esponds (up o o a ions and symme ies) o some pa e n in
he se Pk∪FPk,k(see De s. 2.1 and 2.5)
3. dim δ=1and s 3(δ;O) = s 3(δ;R3)(i.e., δis he cen e o a squa e pla e in O), o
4. dim δ=1,s 3(δ;O)={σ,τ}, wi h δ=σ∩τ, and one o he nex u he condi ions also
holds: (a) o k=6, and k#=6, k,6(O,α1)= k,6(O,α2), whe e α1,α2a e he wo e ices o
he 1-cell δ; o (b) σand τbelong o dis inc 6−componen s o s ∗
3(δ;O), o k,k∈{18,26}.
Each o hese maps and, mo e gene ally, any ligh ing unc ion may be ega ded as a “ ace
membe ship ule”, in he sense o Ko ale sky [9], ha assigns o each digi al objec O he se o
cells O={α∈R3; (O,α) = 1}. This se yields a con inuous analogue as a na u al coun e pa
o Oin o dina y opology. Namely, he con inuous analogue o Ois he polyhed on |A
O|⊆
R3 iangula ed by he subcomplex o he i s de i ed subdi ision o R3,A
O, consis ing o all
simplexes whose e ices a e cen e s c(σ)o cells σ∈ O.1
Rega ding con inuous analogues as a “con inuous in e p e a ion” o digi al images, we in oduce
digi al no ions in e ms o he co esponding con inuous ones. Fo example, we say ha an objec
O⊆cell3(R3)is connec ed i i s con inuous analogue |AO|is a connec ed polyhed on. And,
in he same way, he backg ound o O,cell3(R3)−O, is said o be co-connec ed i |AR3|−
|AO|is connec ed. Mo eo e , we call C⊆cell3(R3)a (co-)componen o O(cell3(R3)−O,
espec i ely) i i consis s o all oxels σwhose cen oids c(σ)belong o a componen o |AO|
(|AR3|−|AO|, espec i ely). Simila ly, an objec S⊆cell3(R3)is a digi al su ace in he space
(R3, )i i s con inuous analogue |AS|is a combina o ial su ace; ha is, i he link lk( ;AS)=
{A∈AS; , A < B ∈ASand /∈A}is a 1−sphe e o each e ex ∈AS. See [2] o mo e de ails
on hese no ions o connec edness de ined in a much mo e gene al con ex and o a de ini ion o
digi al mani old in a bi a y dimension.
In ce ain digi al spaces hese no ions a e closely ela ed o he usual ones de ined on Z3be
means o adjacency pai s. Mo e p ecisely, gi en an adjacency pai (k,k)we say ha (R3, )is a
(k,k)−space i he wo ollowing p ope ies hold o any digi al objec O⊆cell3(R3):
1We o en d op he “ ” om he no a ion and also w i e AR3ins ead A
cell3(R3).
76
1. Cis a componen o Oi i is a k−componen o O; and,
2. Cis a co-componen o he backg ound o Oi i is a k−componen o Z3−O.
In pa icula , i is no di icul o show ha he digi al spaces (R3,
kk)de ined abo e a e ac ually
homogeneous (k,k)−spaces, in he sense ha , in addi ion, he con inuous analogue hey p o ide
o each digi al objec is in a ian unde isome ies o he Euclidean space p ese ing Z3.
On he o he hand, in [1, 2, 5] i can be ound se e al homogeneous (k,k)−spaces whose se s o
digi al su aces con ain he amilies o (k,k)−su aces quo ed in he in oduc ion, which a e also
digi al su aces in he co esponding uni e sal (k,k)−space as a consequence o he ollowing
Theo em 3.2 (Th. 20 in [6]).Any digi al su ace Sin an a bi a y homogeneous (k,k)−space is
also a digi al su ace in he uni e sal (k,k)−space (R3,
kk).
Finally, and conce ning he Jo dan p ope y, we ha e he ollowing sepa a ion heo em o
digi al su aces in (R3,
kk)as a co olla y o a Jo dan–B ouwe Theo em o ai ly gene al digi al
spaces in [2].
Theo em 3.3. Each k−connec ed digi al su ace in (R3,
kk)sepa a es i s backg ound cell3(R3)−S
in o wo k−componen s.
4(k,k)−p esu aces a e digi al su aces in (R3,
kk)
In his sec ion we will show ha he no ions o (k,k)−p esu ace and digi al su ace a e equi alen
in he uni e sal (k,k)−space (R3,
kk) o each adjacency pai (k,k)#= (6,6),k, k∈{6,18,26}.
This way, con inuous analogues and e en he ligh ing unc ion kk a e no longe needed o de-
e mine whe he a gi en objec is a digi al su ace in he uni e sal (k,k)−space. Mo eo e ,
(k,k)−p esu aces a e Jo dan objec s as a consequence o he sepa a ion p ope y s a ed in Th. 3.3
abo e.
The cha ac e iza ion o digi al su aces as (k,k)−p esu aces elies on he c ucial ac ha ,
o any digi al objec O⊆Z3sa is ying condi ions (1) o (3) in De . 2.5, he k−assembly g aph
Gk(O)encodes he con inuous analogue AOin he uni e sal (k,k)−space. In he p oo o his
esul we will use he nex lemmas, ha s a e almos immedia e p ope ies o he ligh ing unc ion
kk in ela ion o he condi ions de ining (k,k)−p esu aces. The i s wo lemmas show ha
kk(O,δ) = 1 o any cell δ∈R3which is he cen e o a node o he k−assembly g aph o O(see
Rema k 3.1).
Lemma 4.1. Le O⊆Z3be a digi al objec sa is ying condi ion (1) in De . 2.5. The wo ollowing
p ope ies hold o a cell δ∈R3:
1. I dim δ=0 hen kk(O, δ) = 1 i δis he cen e o a k−pla e in O.
2. I dim δ=1and δis he cen e o a squa e pla e in O hen kk(O,δ) = 1 and kk(O,αi)=0
o he wo e ices α1,α2<δ. Mo eo e , i γ>δis a 2−cell hen also kk(O, γ) = 1.
Lemma 4.2. Le δe=σ∩τbe he cen e o a node e={σ,τ}o he k−assembly g aph o Oin
he se Ek(O). Then kk(O, δ) = 1.
P oo . I σis 6−adjacen o τ hen dim δe=2and he esul ollows di ec ly om he de ini ion
o kk. O he wise, dim δe=1. Then, necessa ily he e ices α1,α2<δea e he cen e s o he
wo k−pla es o Ocon aining e. Thus, by he de ini ion o he ligh ing unc ion kk(O,αi)=1,
i=1,2, and also kk(O, δe) = 1 since k=6by Rema k 2.4.
Lemma 4.3. Le O⊆Z3be a digi al objec and pak−pla e in Owi h cen e a he cell αp.A
cell γ∈R3belongs o supp(p)i and i αp<γand γ∈supp(O).
Lemma 4.4. Le O⊆Z3be a digi al objec sa is ying condi ions (1) and (2) in De . 2.5. I
β∈R3is an edge which is no he cen e o a squa e pla e in Oand kk(O, β) = 1 hen k=6
necessa ily and he wo ollowing p ope ies also hold:
77

1. The se A={α<β; k,6(O,α)=1}consis s o he wo e ices o βwhich a e ac ually
cen e s o 6−pla es in O; mo eo e , βis he cen e o a node e={σ,τ}∈E6(O)o G6(O).
2. k,6(O,γ) = 0 o any 2−cell γ>β.
Lemma 4.5. Le O⊆Z3be a digi al objec sa is ying condi ions (1) and (3) in De . 2.5. I γ∈R3
is a 2−cell such ha kk(O,γ) = 1 hen s 3(γ;O)={σ,τ}and he se A={α<γ; kk(O,α) = 1}
consis s o wo elemen s which a e cen e s o k−pla es in O. The e o e, γis he cen e o he node
{σ,τ}∈Ek(O).
Lemma 4.6. Le O⊆Z3be a digi al objec sa is ying condi ions (1), (2) and (3) in De . 2.5. I
δ1<δ2a e wo cells in R3wi h dim δi≤2and kk(O,δi) = 1,i=1,2, hen δ1is he cen e o a
k−pla e in Owhile δ2is no .
P oposi ion 4.7. Le O⊆Z3be a digi al objec sa is ying condi ions (1), (2) and (3) in De . 2.5,
and le AObe i s con inuous analogue in he uni e sal (k,k)−space (R3,
kk). Then, he e exis s
a simplicial isomo phism ϕ:Gk(O)→
!
AO=AO−{c(σ); σ∈O}, whe e he simplicial complex
!
AOis he subcomplex o AOconsis ing o all simplices A∈AOsuch ha c(σ)/∈A o any oxel
σ∈O. Mo eo e , o each σ∈O he isomo phism ϕ es ic s o an isomo phism ϕσ:Gk(O,σ)→
lk(c(σ); AO).
P oo . Acco ding o Rema k 3.1 le αn∈R3be he cen e o a node n∈Pk(O)∪Ek(O)o he
k−assembly g aph o O. Since dim αn≤2, he map n-→ ϕ(n)=c(αn)be ween he se o nodes
o Gk(O)and he e ices o he simplicial complex
!
AOis well–de ined by Lemmas 4.1 and 4.2.
Mo eo e , ϕis a bijec ion by Lemmas 4.4 and 4.5. This map na u ally ex ends also o edges.
Recall ha a k−pla e p∈Pk(O)and a pai o oxels e={σ1,σ2}∈Ek(O)de ine an edge in
Gk(O)i e⊆p. Then αp<αe=σ1∩σ2by Lemma 4.3 and hus hei images de e mine he
1−cell .c(αp),c(αe)/∈
!
AO. Finally we check ha ϕis ac ually a simplicial isomo phism; ha
is, o any edge .c(γ1),c(γ2)/∈
!
AO he nodes ϕ−1(c(γi)),i=1,2, de e mine an edge in Gk(O).
Indeed, i γ1<γ2, hen γ1is he cen e o a k−pla e p∈Pk(O)while γ2=σ1∩σ2is he cen e
o a pai o oxels e={σ1,σ2}∈Ek(O)(he e we use again Lemmas 4.4 and 4.5), and he esul
ollows since σi∈s 3(γ1;O)=p,i=1,2.
Finally, by using Lemma 4.3 i is immedia e o check ha ϕ(Pk(O, σ)∪Ek(O,σ)) = {c(α)∈
AO;α<σ} o each oxel σ∈O, and he e o e he isomo phism ϕiden i ies he g aph Gk(O,σ)
wi h lk(c(σ); AO).
Theo em 4.8. A digi al objec S⊆Z3is a (k,k)−p esu ace i and only i i is a digi al su ace
in he uni e sal (k,k)−space (R3,
kk).
P oo . Assume S⊆Z3is a (k, k)−p esu ace. I will su ice o check ha he link Lδ= lk(c(δ); AS)
is a 1-sphe e o each cell δ∈R3such ha kk(S, δ) = 1. Fo each oxel δ∈S,Lδcan be
iden i ied wi h he k−assembly g aph Gk(S, δ)a ound δ, by P op. 4.7, and hence i is a 1-sphe e
by condi ion (4) in De . 2.5. I dim δ=2 he esul is an immedia e consequence o Lemma 4.5.
Simila ly, i dim δ=1 he esul ollows om Lemma 4.4 in case δis no he cen e o a pla e, and
om Lemma 4.1(2) o he wise.
Finally, i δis a e ex hen i is he cen e o a pla e p∈Pk(S)by Lemma 4.1. By he
de ini ion o he ligh ing unc ion kk we know ha kk(S, σ∩τ) = 1 o each pai o 6−adjacen
oxels σ,τ∈pand, in pa icula , i is eadily checked ha Lδis a 1−sphe e whene e p is a Pc
6
pla e. I pis no a Pc
6pla e hen k=6. Mo eo e , i pis no a C
4pla e, σ1,σ2∈pa e s ic ly
18−adjacen and no o he oxel in pis 6−adjacen o bo h o hem, we de i e om he ac ha
c(δ)∈Lσi,i=1,2, which has been p o ed o be a 1−sphe e, ha kk(S, σ1∩σ2)=1. The e o e
Lδis also a 1−sphe e in hese cases by he de ini ion o kk. In case p={σ1,σ2,σ3,σ4}is a C
4
pla e we ha e some choices o make. As c(δ)is in he 1−sphe e Lσi,1≤i≤4, i con ains exac ly
wo o he h ee cen e s cj
i=c(σ1∩σi),1≤i#=j≤4. I c1
2,c
1
3∈Lσ1 hen c4
1/∈Lσ4and hus
c4
2,c
4
3∈Lσ4. The e o e c2
1,c
4
2∈Lσ2,c3
1,c
4
3∈Lσ3and so Lδis also a cycle.
78
Con e sely, assume Sis a digi al su ace in (R3,
kk). I will be enough o check condi ions (1)
o (3) in De . 2.5 o Ssince, unde he assump ion o hese p ope ies, we ge (4) as an immedia e
consequence o P op. 4.7.
I C∩Oco esponds o some pa e n in he se FPkk o some uni cube C, i can be eadily
checked om he de ini ion o kk ha he objec Ois no a digi al su ace. Hence condi ion (1)
holds o S. To check condi ion (2), le σ,τ∈Sbe wo s ic ly 18-adjacen oxels and assume
ha hey a e no 6-connec ed by a hi d oxel in S. Fo he edge β=.α1,α2/=σ∩τwe conside
he wo possible cases:
Case kk(S, β) = 0. I k=6 he de ini ion o kk shows ha k6(S, α) = 1 o a e ex α<β.
Then by condi ion (1), al eady p o ed, and Lemma 4.1 i ollows ha αis he cen e o a k−pla e
in P(S, σ)∩P(S, τ). On he o he hand, i k,k∈{18,26} hen σ,τa e 6−connec ed in s ∗
3(β;S),
by he de ini ion o kk, which is jus condi ion (2).
Case kk(S, β)=1. Then i can be eadily checked ha kk(S, αi)=1 o he wo e ices
α1,α2o β, since Sis a digi al su ace in (R3,
kk). The e o e he e ices αia e cen e s o
k−pla es in P(S, σ)∩P(S, τ)by Lemma 4.1. No ice ha his case is only posible i k=6.
Finally we p o e condi ion (3). Fo his le σ,τ∈Sbe wo 6−adjacen oxels and le γ=σ∩τ.
Then kk(S, γ) = 1 by de ini ion o kk. As lk(c(γ); AS)is a 1−sphe e he e exis exac ly wo
aces α1,α2<γwi h kk(S, αi)=1. I dim αi=0 hen αiis he cen e o a k−pla e by
Lemma 4.1. Simila ly, i dim αi=1 hen he de ini ion o kk yields ha s 3(αi;S) = s 3(αi;R3)
since i con ains he wo 6−adjacen oxels σand τ, and hence αiis he cen e o a squa e pla e.
The e o e P(S, σ)∩P(S, τ)con ains a leas wo k−pla es. Bu gi en he cen e αpo any pla e
p∈P(S, σ)∩P(S, τ)we know ha αp<γby Lemma 4.3 and, mo eo e , kk(S, αp)=1by
Lemma 4.1. This way αp∈{α1,α2}and P(S, σ)∩P(S, τ)consis s o exac ly wo k−pla es.
5(k,k)−su aces
As a consequence o Th. 3.3 and Th. 4.8 we ge ha each k−connec ed (k,k)−p esu ace S
sepa a es i s backg ound Z3−Sin o wo k−componen s. In addi ion o his Jo dan p ope y,
disc e e su aces a e usually equi ed o be s ongly k−sepa a ing; ha is, each oxel σ∈Sshould
be k−adjacen o bo h k−componen s o Z3−S(see [3]). Howe e , i is easy o check ha his
global p ope y ails o he oxel τ0in he (18,6)−p esu ace shown in Fig. 2(a).
Ou goal in his sec ion is o ind u he local condi ions cha ac e izing he s ong sepa a-
ion p ope y wi hin he class o (k,k)−p esu aces in o de o ob ain genuine disc e e su aces
acco ding o he ollowing
De ini ion 5.1. A(k,k)−p esu ace is said o be a (k, k)−su ace i i is a s ongly k−sepa a ing
objec .
In [4, §7] we ound he local condi ions cha ac e izing he subse o s ongly 6−sepa a ing
(26,6)−p esu aces. The same condi ions, and he p oo as well, wo ks o he case (18,6). Fo
he emaining cases we ge he ollowing.
De ini ion 5.2. Le S⊆Z3be a (k,k)−p esu ace, k∈{18,26}. A oxel σ∈Sis said o be a
k-su ace oxel i o each uni cube Cσ⊆Z3con aining σ he e exis s a oxel τ∈Cσ−Swhich
is k−adjacen o σ. No ice ha e e y oxel in a (k,26)−p esu ace Sis a 26−su ace oxel since
Scanno con ain he pa e n P8in Fig. 1.
Theo em 5.3. A(k,k)−p esu ace Sis a (k,k)−su ace i each σ∈Sis a k−su ace oxel.
P oo . Recall ha Sis a digi al su ace in he uni e sal (k,k)−space (R3,
kk)and so |AS|is
a combina o ial su ace. As a consequence o he Jo dan–B ouwe Theo em he di e ence D=
|lk(c(σ;AR3)|−|lk(c(σ;AS)|consis s o wo componen s, each con ained in a componen o R3−
|AS|. Mo eo e , hese componen s cha ac e ize he k−componen s o Z3−Ssince (R3,
kk)is a
(k,k)−space (see §3). Le δ1,δ2<σbe wo cells wi h hei cen e s c(δi)in each o he componen s
79
o D. No ice ha kk(S, δi)=0. Then, i σis k−su ace oxel, he de ini ion o kk gi es us wo
oxels τi/∈Swhich a e k−adjacen o σand such ha δi<τi,i=1,2. The e o e, c(τ1)and c(τ2)
a e in dis inc componen s o R3−|AS|and he esul ollows.
Con e sely, assume k= 18 ( he e is no hing o p o e i k= 26). I σis no a 18−su ace
oxel hen he e exis s a uni cube C, wi h cen e a a e ex α∈R3, such ha C−Sconsis s
o a single oxel τwhich is s ic ly 26−adjacen o σ. Then, we de i e om he de ini ions ha
k,18(S, δ)=1 o each ace α<δ<σ. Mo eo e , he cen e s o hese cells de e mine a cycle in
lk(c(σ); AS), and hen k,18(S, γ) = 0 o any o he ace γ<σ, in pa icula k,18(S, α) = 0. This
way {c(α)}is a componen o he di e ence Dabo e, and hence i ollows ha σis 18−adjacen
o jus one 18−componen o Z3−S.
Rema k 5.4. I is wo h poin ing ou ha he se o (k,k)−su aces s ill con ains s ic ly he se s
o simplici y and s ong su aces quo ed in he in oduc ion since each one o hem is a s ongly
sepa a ing objec [3, 7].
Re e ences
[1] R. Ayala, E. Domínguez, A.R. F ancés, and A. Quin e o. Digi al ligh ing unc ions. In
E. Ah ono i z and Ch. Fio io, edi o s, Disc e e Geome y o Compu e Image y, olume
1347 o Lec u e No es in Compu e Science, pages 137–150. Sp inge Be lin / Heidelbe g,
1997.
[2] R. Ayala, E. Domínguez, A.R. F ancés, and A. Quin e o. Weak ligh ing unc ions and s ong
26-su aces. Theo e ical Compu e Science, 283(1):29 – 66, 2002.
[3] G. Be and and R. Malgouy es. Some opological p ope ies o su aces in Z3.Jou nal o
Ma hema ical Imaging and Vision, 11:207–221, 1999.
[4] J.C. Ci ia, A. De Miguel, E. Domínguez, A.R. F ancés, and A. Quin e o. Local cha ac e iza-
ion o a maximum se o digi al (26,6)−su aces. Image and Vision Compu ing, 25(10):1685
– 1697, 2007.
[5] J.C. Ci ia, E. Domínguez, and A.R. F ancés. Sepa a ion heo ems o simplici y 26-su aces. In
Achille B aquelai e, Jacques-Oli ie Lachaud, and Anne Viala d, edi o s, Disc e e Geome y
o Compu e Image y, olume 2301 o Lec u e No es in Compu e Science, pages 153–161.
Sp inge Be lin / Heidelbe g, 2002.
[6] J.C. Ci ia, E. Domínguez, A.R. F ancés, and A. Quin e o. Uni e sal spaces o (k,k)-su aces.
In S. B lek, Ch. Reu enaue , and X. P o ençal, edi o s, 15 h Disc e e Geome y o Compu e
Image y, olume 5810 o Lec u e No es in Compu e Science, pages 385–396. Sp inge , 2009.
[7] M. Coup ie and G. Be and. Simplici y su aces: a new de ini ion o su aces in Z3.SPIE
Vision Geome y V, 3454:40–51, 1998.
[8] T.Y. Kong and A.W. Roscoe. Con inuous analogs o axioma ized digi al su aces. Compu e
Vision, G aphics, and Image P ocessing, 29(1):60 – 86, 1985.
[9] V. A. Ko ale sky. Fini e opology as applied o image analysis. Compu e Vision, G aphics,
and Image P ocessing, 46(2):141 – 161, 1989.
[10] G. Malandain, G. Be and, and N. Ayache. Topological segmen a ion o disc e e su aces.
In . Jou . o Compu e Vision, 10:183–197, 1993.
[11] D.G. Mo gen hale and A. Rosen eld. Su aces in h ee-dimensional digi al images. In o ma-
ion and Con ol, 51(3):227 – 247, 1981.
80