Strong separating (k, k)−surfaces on Z3

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