Well-Composed Cell Complexes

Well-Composed Cell Complexes Rocio Gonzalez-Diaz, Ma ia-Jose Jimenez, and Belen Med ano Applied Ma h Depa men , Uni e si y o Se ille, A . Reina Me cedes, s/n, Se ille, Spain { ogodi,maji o,belenmg}@us.es Abs ac . Well-composed 3D digi al images, which a e 3D bina y dig- i al images whose bounda y su ace is made up by 2D mani olds, enjoy impo an opological and geome ic p ope ies ha u n ou o be ad- an ageous o some applica ions. In his pape , we p esen a me hod o ans o m he cubical complex associa ed o a 3D bina y digi al im- age (which is no gene ally a well-composed image) in o a cell complex ha is homo opy equi alen o he i s one and whose bounda y su - ace is composed by 2D mani olds. This way, he new ep esen a ion o he digi al image can bene i om he applica ion o algo i hms ha a e de eloped o e su aces embedded in R3. Keywo ds: Well-composed digi al images, cubical complex, cell com- plex, homo opy equi alence. 1 In oduc ion We a e mainly in e es ed in s udying opological ea u es o 3D digi al images. Mo e conc e ely, ou ul ima e pu pose is ha o ex ac ing cohomological in- o ma ion o a 3D model ha could be used in cha ac e iza ion o ecogni ion asks (see [5,6,4,7] as ela ed wo ks). Fo his aim, i would be use ul o com- pu e fi s geome ically ele an ep esen a i e cycles o homology gene a o s o dimension 1 in he su ace o he model, since his could simpli y cohomological compu a ions. Many applica ions such as opology epai , su ace pa ame e iza- ion and ea u e ecogni ion benefi om compu ing loops on su aces ha w ap a ound hei ‘handles’ and ‘ unnels’ (defined by Dey e al. in [2]). In he pape [3], he e is an algo i hm o compu e opologically co ec loops ha a e also geome ically ele an in ha sense. A efinemen o he algo i hm is gi en in [1]. Howe e , all he compu a ions a e ca ied ou o e a connec ed closed su ace in R3. Since we a e in e es ed in applying hese esul s o 3D bina y digi al images, we ocus in he so-called well-composed images. A 3D bina y digi al image is said o be well-composed i and only i he squa e aces sha ed by o eg ound and backg ound oxels o he image o m a 2D mani old. Well-composed images enjoy impo an opological and geome ic p ope ies: he e is only one ype o connec ed componen in any well-composed image, and hence, se e al algo i hms used in compu e ision, compu e g aphics and image p ocessing a e simple ; hinning algo i hms can be simplified and na u ally made pa allel i he inpu I. Debled-Rennesson e al. (Eds.): DGCI 2011, LNCS 6607, pp. 153–162, 2011. c Sp inge -Ve lag Be lin Heidelbe g 2011 154 R. Gonzalez-Diaz, M.-J. Jimenez, and B. Med ano image is well-composed [10,13]; some algo i hms o compu ing su ace cu a u e o ex ac ing adap i e iangula ed su aces [8], assume ha he inpu image is well-composed. Since 2D and 3D images a e o en no well-composed images, he e a e se e al me hods ( epai ing algo i hms) o u ning 3D bina y digi al images ha a e no well-composed in o well-composed ones (see [12,15]), bu hese me hods do no gua an ee he opological equi alence be ween he o igi- nal objec and i s co esponding well-composed image. In ac , he pu pose can e en be o simpli y as much as possible he opology in he sense o emo ing li le opological a i ac s om he image. Howe e we a e conce ned wi h he ac o p ese ing he opology o he inpu image ha ing in mind cases in which sub le de ails can be impo an . 2 3D Digi al Images and Cubical Complexes Conside Z3as he se o poin s wi h in ege coo dina es in 3D space R3.A3D bina y digi al image I=(Z3,26,6,B)(o I=(Z3,B) o sho ), whe e B⊂Z3 is he o eg ound and Bc=Z3 B he backg ound, is ep esen ed by he se o uni cubes ( oxels) cen e ed a he poin s o B oge he wi h all hei aces. This iden ifica ion o oxels wi h 3D cubes in R3leads, in a na u al way, o he combina o ial s uc u e o cubical complexes, whose geome ic building blocks (cells) a e poin s, edges, squa es and cubes (see [9]). Mo e conc e ely, gi en a oxelcen e eda apoin o Z3o coo dina es (i, j, k), he cells associa ed o his oxel conside ed as a 3D cube a e deno ed as ollows (see Fig.1): –The eigh e ices (0-cells): (i±1 2,j±1 2,k±1 2) –The wel e edges (1-cells): (i, j ±1 2,k±1 2), (i±1 2,j,k±1 2), (i±1 2,j±1 2,k). –The six squa e aces (2-cells): (i, j, k ±1 2), (i, j ±1 2,k), (i±1 2,j,k). –Thecube(3-cell):(i, j, k). By conside ing he (26,6)- ela ionship we can gua an ee ha he opology o he cubical complex associa ed o he image eflec s he opology o he objec . A cubical complex is, in ac , a special case o cell complex, which is a mo e gene al opological s uc u e by which a space is decomposed in o basic elemen s (cells) o diffe en dimensions ha a e glued oge he by hei bounda ies. Gi en a cell complex K,ap ope ace o σ∈Kis a ace o σwhose dimension is s ic ly less han he one o σ.A ace o σisap ope aceo σo maximal dimension. A maximal cell o Kis a cell o Kwhich is no a p ope ace o any o he cell o K. The dimension o Kis he maximal dimension o he maximal cell o K. A ace ha is inciden only o one cell is called a bounda y ace .The union o all he bounda y ace s is he bounda y o he cell complex which is deno ed by ∂K. The cubical complex Q(I) ep esen ing a 3D bina y digi al image Isa isfies ha he maximal cells a e cubes and he elemen s o he bounda y o Q(I), ∂Q(I), a e all he squa e aces o Q(I) which a e sha ed by a oxel o Band a oxel o Bc oge he wi h all hei aces. Well-Composed Cell Complexes 155 Fig. 1. No a ion o he e ices {pi},edges{ai}and squa e aces {ci}associa ed o he oxel (i, j, k) Gi en a cell complex K, define Kqas he se o q-cells o K. Define he mo phism kq:Kq×Kq−1→Z2gi en by kq(c, c):=1i cis a ace o cand kq(c, c) := 0 in o he case (we do no ake in o accoun o ien a ion). Then, we can codi y a cell complex as a pai (K, k)whe eK=qKqis he se o cells o Kand k=⊕qkqdefines he ela ion be ween each cell and i s ace s. The mo phism kis called he incidence numbe (see [14]). Fo example, since any cubical complex Qis a pa icula case o cell complex, i can be codified as a pai (Q, kQ): Le Q0be he se o e ices, Q1 he se o edges, Q2 he se o squa e aces and Q3 he se o cubes o Q. Define he mo phism kQ q:Qq×Qq−1→Z2gi en by kQ q(c, c):=1i cis a ace o cand kQ q(c, c) := 0 in o he case. Taking in o accoun he no a ion gi en o he cells o Qas poin s in R3, define kQ q(c, c) := 1 i he Euclidean dis ance be ween c and cis 1 2and kQ q(c, c) := 0 in o he case. 3 Well-Composed Cell Complexes A3Dbina y digi al image I=(Z3,B)iswell-composed [10] i he bounda y o he cubical complex associa ed, ∂Q(I), is a 2Dmani old, i.e. i each poin in 156 R. Gonzalez-Diaz, M.-J. Jimenez, and B. Med ano ∂Q(I) has a neighbo hood homeomo phic o R2. This defini ion implies a simple co espondence be ween a 3Dbina y digi al image and he bounda y su ace o he associa ed cubical complex. Thus, one can use well-known p ope ies o con- inuous bounda y su aces o de e mine and analyze p ope ies o hese digi al images. Since he bounda y o he cubical complex associa ed o I=(Z3,B)coincides wi h he one o Ic=(Z3,Bc), a 3Dbina y digi al image Iis well-composed iff Icis also well-composed. 3D bina y digi al images a e o en no well-composed images. Ne e heless, he e a e se e al me hods o u ning 3D bina y digi al images ha a e no well-composed in o well-composed ones (see [12,15]). The p oblem is ha , in gene al, hese echniques do no gua an ee he opological equi alence be ween he o iginal objec and i s co esponding well-composed image, since hey can modi y he o iginal image by mo ing some oxels om Bc o B. In his sec ion, we a e in e es ed in ob aining a homo opy-equi alen cell com- plex o he cubical complex associa ed o a 3D bina y digi al image whose geo- me ic ealiza ion could enjoy he ad an ages o well-composed images. Specifi- cally, we p esen a me hod o ans o m he cubical complex Qassocia ed o a 3D bina y digi al image which is no gene ally a well-composed image in o a cell complex (K, k). This cell complex (K, k) sa isfies ha i is homo opy equi alen o Qand i s bounda y su ace, ∂K, is composed by 2D mani olds. The ollowing p oposi ion shows he cha ac e iza ion o well-composed images in e ms o simple local condi ions on cubes in he cubical complex associa ed, as one can obse e in Fig. 2. P oposi ion 1. [11] A 3Dbina y digi al image I=(Z3,B)is well-composed iff he configu a ions o cubes C1, C2 and C3 (modulo eflec ions and o a ions) do no occu in Q(I): C1 Fou cubes sha e an edge (a, b, c)and exac ly wo o hem which do no sha e a ace a e con ained in Q(I)and he o he wo a e no con ained in Q(I). Tha is, i Wdeno es he se o he ou cubes sha ing he edge (a, b, c), he e a e exac ly wo cubes o W, deno ed by w1and w2, ha a e cubes o Q(I) and whose squa ed Euclidean dis ance is 2. C2 Eigh cubes sha e a e ex (a, b, c)and exac ly wo o hem which a e co ne - adjacen a e con ained in Q(I)while he o he six a e no . Tha is, i S deno es he se o he eigh cubes sha ing he e ex (a, b, c), he e a e exac ly wo cubes o S, deno ed by s1and s2, ha a e cubes o Q(I)and whose squa ed Euclidean dis ance is 3. C3 Eigh cubes sha e a co ne poin and exac ly wo o hem which a e co ne - adjacen a e con ained in Q(Ic)while he o he six a e no . Tha is, i T deno es he se o he eigh cubes sha ing he e ex (a, b, c).Then, he ea e exac ly wo cubes o T, deno ed by 1and 2, ha a e no cubes o Q(I)and whose squa ed Euclidean dis ance is 3. Gi en a cubical complex Qassocia ed o a 3D bina y digi al image, we say ha an edge (a, b, c)o Qis a c i ical edge i (a, b, c) is an edge sha ed by ou Well-Composed Cell Complexes 157 Fig. 2. Con igu a ions C1, C2 and C3 (modulo e lec ions and o a ions). These con- igu a ions canno occu in Q(I). cubes ha cons i u e he C1-configu a ion. We say ha a e ex (a, b, c)o Q is a c i ical e ex i i is ei he a e ex sha ed by eigh cubes ha cons i- u e he C2-configu a ion o a e ex sha ed by eigh cubes ha cons i u e he C3-configu a ion o a e ex sha ed by eigh cubes such ha one o se e al c i i- cal edges a e inciden o i . Summing up, one can obse e in Fig. 3 all he c i ical configu a ions ha a e possible by he combina ion o he men ioned c i ical el- emen s wi hin a se o eigh cubes sha ing a e ex. No ice ha configu a ions C(2,0), C(2,1), C(3,0) and C(3,1) a e complemen a y o configu a ions C(6,2), C(6,1), C(5,1) and C(5,2), espec i ely; as well as configu a ions C(4,1), C(4,2) and C(4,3) a e sel -complemen a y. Now, gi en a cubical complex Qassocia ed o a 3D bina y digi al image, we p esen a me hod o gene a e a new cell complex by some basic ope a ions on he inpu cubical complex o epai all he c i ical edges and c i ical e ices ha appea in Q. The me hod consis s o h ee s eps: (1) all he c i ical edges and c i ical e ices ha appea in Qa e labeled and pu in o ei he he se E o c i ical edges o he se Vo c i ical e ices; (2) apply Algo i hm 1 o he cubical complex Q o epai all he edges o Eand (3) apply Algo i hm 2 o he cell complex ou pu by he p e ious algo i hm o epai all he e ices o V. Algo i hm 1. Repai he c i ical edges in E. Inpu : The cubical complex (Q, kQ)associa ed o a 3D bina y digi al image. Ini ialize K i:={(a, b, c, 0):such ha (a, b, c)∈Qi}and k i((a, b, c, 0),(a,b ,c ,0)) := kQ i((a, b, c),(a,b ,c )), o any (a, b, c),(a,b ,c )∈Qiand o 0≤i≤3. –Fo each c i ical edge (a, b, c)∈E, do: •Duplica e he edge: K 1:= K 1 {(a, b, c, 0)}∪{(a, b, c, 1),(a, b, c, 2)}. •Addanew2-cell: K 2:= K 2∪{(a, b, c, 1,2)}. •Deno e by w11 and w12 he wo squa e aces o w1sha ing he edge (a, b, c).Deno ebyw21 he one o he squa e aces o w2sha ing he edge (a, b, c)such ha he squa ed Euclidean dis ance be ween w11 and w21 is 1 2.Deno ebyw22 he o he squa e ace o w2sha ing he edge (a, b, c)(see Fig. 4). 158 R. Gonzalez-Diaz, M.-J. Jimenez, and B. Med ano Fig. 3. All he c i ical con igu a ions wi hin a se o eigh cubes sha ing one e ex (modulo e lec ions and o a ions) •Define k 1((a, b, c, j), ):=k 1((a, b, c, 0), ) o j=1,2and o any e ex ∈K 0. •Define k 2( ,(a, b, c, j)) := 1 i =wij , o i=1,2,o =(a, b, c, 1,2), o j=1,2. •Define k 2((a, b, c, 1,2),e):=0i e=(a, b, c, j) o j=1,2, ha is, he only ace s o he new 2-cell (a, b, c, 1,2) a e he edges (a, b, c, 1) and (a, b, c, 2). •Define k 3(w, (a, b, c, 1,2)) := 1 i w=wi o i=1,2and 0in o he case. Ou pu : The cell complex (K,k). Algo i hm 2. Repai he c i ical e ices in V. Inpu : The cell complex (K,k)ob ained a e applying Algo i hm 1. Ini ialize Ki:= K iand ki:= k i o 0≤i≤3. –Fo each c i ical e ex (a, b, c)∈Vwi h he configu a ion C(2,1), do: •Duplica e he e ex: K0:= K0 {(a, b, c, 0)}∪{(a, b, c, 1),(a, b, c, 2)}. •Add wo new edges: K1:= K1∪{(a, b, c, 1,2),(a, b, c, 2,1))}. •Addanew2-cell:K2:= K2∪{(a, b, c, 1,2,1)}. Well-Composed Cell Complexes 159 Fig. 4. No a ions o he cells a ound a c i ical edge (a, b, c) •Take wo squa e aces o s1sha ing he e ex (a, b, c)and deno e hem by s11 and s12. Take he squa e ace o s2sha ing he e ex (a, b, c) whose squa ed Euclidean dis ance o s11 is 2;deno ei bys22.Deno eby s21 he o he squa e ace o s2sha ing he e ex (a, b, c)whose squa ed Euclidean dis ance o s12 is 2(see Fig. 5). •Define k1(e, (a, b, c, 1)) := 1 i ei he e=(a, b, c, 1,2) o e=(a, b, c, 2,1), o eis a ace edge o s1sha ed by s11 and s12 o eis any o he o he wo edges o s2such ha k 1(e, (a, b, c, 0)) = 1 and ha a e no sha ed by s21 and s22 a he same ime, and 0o he wise. •Define k1(e, (a, b, c, 2)) := 1 i ei he e=(a, b, c, 1,2) o e=(a, b, c, 2,1), o eis a ace edge o s2sha ed by s21 and s22 o eis any o he o he wo edges o s1such ha k 1(e, (a, b, c, 0)) = 1 and ha a e no sha ed by s11 and s12 a he same ime, and 0o he wise. •Define k2( ,(a, b, c, 1,2)):=1 i =s12 o =s22 o =(a, b, c, 1,2,1), and 0o he wise. •Define k2( ,(a, b, c, 2,1)):=1 i =s21 o =s11 o =(a, b, c, 1,2,1), and 0o he wise. •Define k3(w, (a, b, c, 1,2,1)) := 1 i w=si o i=1,2and 0o he wise. –Fo each c i ical e ex (a, b, c)∈Vwi h any configu a ion o Fig. 3 apa om C(2,1), do: •Label he backg ound connec ed componen s o he configu a ion o eigh 3-cells a ound he c i ical e ex wi h labels 1,2,3and 4, espec i ely (no ice ha he numbe o connec ed componen s may a y om 2 o 4). Le L={1,2,...,l}be he se o labels assigned. •Label all he edges inciden o (a, b, c) ha belong o he bounda y o K, wi h he co esponding label o he backg ound componen ha sha es such an edge. •Subs i u e he c i ical e ex by a se o e ices, one o each label co e- sponding o a backg ound connec ed componen : K0:= K0 {(a, b, c, 0)}∪ {(a, b, c, 1),...,(a, b, c, l)}. 160 R. Gonzalez-Diaz, M.-J. Jimenez, and B. Med ano Fig. 5. No a ions o he cells a ound a c i ical e ex (a, b, c) wi h he con igu a ion C(2,1) •Add new edges: K1:= K1∪{(a, b, c, i, j),i,j∈L, i < j}. •I l≥3, add new 2-cells K2:= K2∪{(a, b, c, i, j, k), i,j,k ∈L, i < j < k}. •I l=4, add a new 3-cell K3:= K3∪{(a, b, c, 1,2,3,4)}. •Define k1(e, (a, b, c, i)) := 1 i ei he k 1(e, (a, b, c, 0)) = 1 and eis an edge wi h label io e=(a, b, c, i, j), o any jo e=(a, b, c, j, i), o any j, and 0o he wise. •Define k2( ,(a, b, c, i, j)) := 1 i ei he is a 2-cell wi h wo ace edges labeled as iand jo =(a, b, c, i, j, k)o =(a, b, c, i, k, j)o = (a, b, c, k, i, j),and0o he wise. •Define k3(w, (a, b, c, i, j, k)) := 1 i ei he wis a 3-cell wi h h ee ace edges labeled as i,jand k,o w=(a, b, c, 1,2,3,4),and0o he wise. Ou pu : The cell complex (K, k). P oposi ion 2. The cell complex (K, k)and he cubical complex Qa e homo- opy equi alen . Mo eo e , he bounda y su ace ∂K, o he cell complex (K, k), is composed by 2D mani olds, ha is, each poin o ∂K has a neighbo hood home- omo phic o R2. Example 1. Conside he 3Dbina y digi al image I=(Z3,B)wi hB={(1,1,0), (0,0,1),(0,2,1),(0,1,2)}.Le Q he cubical complex associa ed o he image. This cubical complex has 4 oxeles (3-cells), 24 squa e aces (2-cells), 45 edges (1-cells) and 26 e ices (0-cells). The conflic i e cells o Ka e: –The edges a1=(0,1 2,3 2)anda2=(0,3 2,3 2); –The e ices 1=( 1 2,1 2,1 2)and 2=( 1 2,3 2,1 2). Applying he p e ious me hod o his cubical complex, he ob ained well- composed cell complex Kha e ou 3-cells, wen y eigh 2-cells (21 squa e aces, 2 pen agons and 1 hexagon), 51 edges and 28 e ices (see Fig. 7). Well-Composed Cell Complexes 161 Fig. 6. No a ions o he cells a ound a c i ical e ex (a, b, c), wi h he con igu a ions C(6,1)( i s ow)andC(4,1) (second one) Fig. 7. Example o a cubical complex and well-composed complex 4 Conclusion and Fu u e Wo k We ha e p esen ed a me hod o ob aining a well-composed cell complex om he cubical complex associa ed o a 3D bina y digi al image. We a e con inced ha his new ep esen a ion will sa is y e y nice p ope ies: fi s , he new cell complex will allow o compu e he homology o he image by compu ing he