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