Cup P oduc s on Polyhed al App oxima ions
o 3D Digi al Images
Rocio Gonzalez-Diaz1, Ja ie Lama 2, and Ronald Umble3
1Dep . o Applied Ma h (I), School o Compu e Enginee ing, Uni e si y o Se ille,
Campus Reina Me cedes, C.P. 41012, Se ille, Spain
[email p o ec ed]
2Pa e n Recogni ion Depa men , Ad anced Technologies Applica ion Cen e ,
7 h A enue #21812 218 and 222, Siboney, Playa, C.P. 12200, Ha ana Ci y, Cuba
[email p o ec ed]
3Depa men o Ma hema ics, Mille s ille Uni e si y o Pennsyl ania,
P.O. Box 1002 Mille s ille, PA 17551-0302, Pennsyl ania, USA
[email p o ec ed]
Abs ac . Le Ibe a 3D digi al image, and le Q(I) be he associa ed
cubical complex. In his pape we show how o simpli y he combina-
o ial s uc u e o Q(I) and ob ain a homeomo phic cellula complex
P(I) wi h ewe cells. We in oduce o mulas o a diagonal app oxima-
ion on a gene al polygon and use i o compu e cup p oduc s on he
cohomology H∗(P(I)). The cup p oduc encodes impo an geome ical
in o ma ion no cap u ed by he cohomology g oups. Consequen ly, he
ing s uc u e o H∗(P(I)) is a ine opological in a ian . The algo i hm
p oposed he e can be applied o compu e cup p oduc s on any polyhed al
app oxima ion o an objec embedded in 3-space.
Keywo ds: Cellula complex, cohomology, cup p oduc , diagonal
app oxima ion, digi al image, polyhed on.
1 In oduc ion
Th oughou his pape , coefficien s lie in he field Z2.Le Xbe a cellula com-
plex embedded in 3-dimensional space and cons uc ed by gluing 3-dimensional
polyhed a oge he along common aces (see [4]). A a mos basic le el, he con-
nec ed componen s, homo opy classes o non-con ac ible loops, and bounda ies
o unnels in Xgene a e he cellula cohomology H∗(X). A he nex le el, ce -
ain ela ionships among he gene a o s a e encoded by he cup p oduc , which
endows H∗(X) wi h a g aded commu a i e ing s uc u e. Indeed, he disc imi-
na ing in o ma ion encoded by he cup p oduc imp o es ou capabili y o dis-
inguish be ween 3D images. Fo example, H∗(S1∨S1∨S2)andH∗(S1×S1)
a e isomo phic as ec o spaces bu no as ings since cup p oduc s anish in
he wedge bu no in he p oduc . Thus S1∨S1∨S2and S1×S1ha e qui e
diffe en opological p ope ies.
To da e, he cup p oduc has seen limi ed applica ion o p oblems in 3D image
p ocessing. In [10,11], Gonzalez-Diaz and Real used hei 14-adjacency algo i hm
J.K. Agga wal e al. (Eds.): IWCIA 2011, LNCS 6636, pp. 107–119, 2011.
c
Sp inge -Ve lag Be lin Heidelbe g 2011
108 R. Gonzalez-Diaz, J. Lama , and R. Umble
Fig. 1. Le : A digi al image I=(Z3,26,6,B); he se Bconsis s o 8 uni cubes
( oxels). Righ : The quad angles o ∂Q(I).
and he s anda d o mula ion in [17] o compu e cup p oduc s on he simplicial
complex K(I) associa ed wi h a gi en digi al image I. Mo e ecen ly, Gonzalez-
Diaz, Jimenez and Med ano in oduced a me hod o compu ing cup p oduc s
on cubical app oxima ions Q(I). Thei cup p oduc s a e compu ed di ec ly om
he cubical complex, and no addi ional subdi isions a e necessa y [8,9]. Fo a
geome ical in e p e a ion o cohomology in he con ex o digi al images, we
e e he eade o [5,6,15].
In [14], K a a z compu ed cup p oduc s on a gene al 2-dimensional polygon
in e ms o a combina o ial diagonal app oxima ion, which assumes a pa icula
o de ing o he e ices. In his pape , we in oduce a mo e gene al o mula o
compu ing cup p oduc s, which is independen o he o de ing o e ices and
compu a ionally effec i e.
A p oblem ha equen ly a ises in 3D image p ocessing is o efficien ly en-
code he bounda y su ace o a gi en digi al objec as a se o oxels. The mos
popula app oach o his p oblem uses a iangula ion. While iangles a e com-
bina o ially simple, and isualiza ion o iangula ed su aces is suppo ed by
exis ing ha dwa e and so wa e, he numbe o iangles equi ed is o en la ge
and he compu a ional analysis co espondingly slow. I is desi able, he e o e,
o seek mo e compu a ionally economical combina o ial app oxima ions. Adja-
cen coplana iangles in a iangula ion, o example, can be me ged in o mo e
gene al polygons and become aces o mo e gene al bu combina o ially simple
polyhed a. The payoff om combina o ial simplici y is imp o ed compu a ional
efficiency.
App oxima ing 3D objec s wi h polyhed al complexes is a well-s udied p ob-
lem in he field o Compu a ional Geome y ( o example, see [1,2,3]). An al-
go i hm o cons uc ing polyhed al app oxima ions in ce ain special cases was
gi en by Ko ale sky and Schulz in [13,19]. Thei algo i hm gene a es he con ex
hull o a gi en objec hen modifies he con ex hull by ecu si ely gene a ing
con ex hulls o ei he subse s o he gi en oxel se o subse s o he backg ound
oxels. The esul o his me hod is a polyhed on ha sepa a es objec oxels
om backg ound oxels.
The compu a ional me hods in oduced in his pape can be effec i ely ap-
plied o any polyhed al app oxima ion o a 3D objec . Indeed, one maximizes
compu a ional efficiency by app oxima ing a gi en 3D objec wi h a polyhed al
Cup P oduc s on Polyhed al App oxima ions o 3D Digi al Images 109
Fig. 2. Le : Quad angles in he bounda y o cubes cand σsha ing a squa e σ(in
bold). Righ : Quad angles in ∂(c):=∂(c+σ), he bounda y o he cell ca e emo -
ing σ.
complex con aining a minimal numbe o cells. To he ex en ha his is ou
long- e m objec i e, we ake a fi s s ep in his di ec ion he e.
The pape is o ganized as ollows: In Sec ion 2 we in oduce a simplifica ion
p ocedu e, which p oduces a cellula complex P(I) homeomo phic o Q(I)wi h
significan ly ewe cells. In Sec ion 3 we define a diagonal app oxima ion on a
gene al polygon and use i o compu e he cohomology ing o P(I). Conclusions
and some ideas o u u e wo k a e discussed in Sec ion 4.
2 3D Digi al Pic u es and Cellula Complexes
Le Ibe a 3D digi al image and le Q(I) be an associa ed cubical complex. In
his sec ion we in oduce a simplifica ion p ocedu e, which p oduces a cellula
complex P(I) homeomo phic o Q(I) wi h significan ly ewe cells.
In ui i ely, a cellula decomposi ion o a 3D space Xembedded in R3is a
ep esen a ion o Xas a fini e union o e ices (0-cells), edges (1-cells), polygons
(2-cells), and polyhed a (3-cells), which ha e been glued oge he in such a way
ha he non-emp y in e sec ion o wo cells is a cell. A k-cell is also e e ed o
as a k- ace.Acellula complex is a 3D space Xembedded in R3 oge he wi h
a cellula decomposi ion. Fo a p ecise defini ion o a cellula complex, which is
mo e sub le han one migh expec , see [4].
Acubical complex Qis a cellula complex whose 2-cells a e squa es (o quad-
angles) and whose 3-cells a e cubes. No e ha i a cube is in Q, i s bounding
quad angles a e in Q; i a quad angle is in Q, i s bounding edges a e in Q;and
i an edge is in Q, i s endpoin s a e in Q.
Conside a 3D bina y digi al pic u e I=(Z3,26,6,B), whe e Z3is he un-
de lying g id and B( he o eg ound) is a fini e se o poin s o he g id fixing
he 26-adjacency o he poin s o Band he 6-adjacency o he poin s o Z3 B
( he backg ound). The cells o Q(I) a e uni cubes cen e ed a he poin s o B
wi h aces pa allel o he coo dina e planes (called he oxels o I), oge he wi h
hei quad angles, edges, and e ices.
Le Kbe a cellula complex. An i-cell σ∈Kis a ace o a cell σ∈Ki σis
an (i+ 1)-cell and σis a ace o σ.Amaximal cell o Kis no a ace o any cell
o K. The bounda y o K, deno ed by ∂K, is he subcomplex o Kconsis ing o
all cells ha a e ace s o exac ly one (maximal) cell, and hei aces. No e ha
110 R. Gonzalez-Diaz, J. Lama , and R. Umble
Fig. 3. C i ical con igu a ions (i), (ii) and (iii) (modulo e lec ions and o a ions)
he maximal cells o ∂Q(I) a e all he quad angles o Q(I)sha edbya oxelo
Band a oxel o Z3 B(see Figu e 1).
Following he exposi ion in [8,9], gi en a digi al image Iand i s associa ed
cubical complex Q(I), we apply a ace- educ ion echnique o educe he num-
be o cells in Q(I) ∂Q(I) and ob ain a cellula complex K(I) homeomo phic
o Q(I) whose maximal cells a e he quad angles o ∂Q(I)(seeFigu e2and
Algo i hm 1). Then, ∂K(I)=∂Q(I).
Inpu : A cubical complex Q(I)associa ed o a 3D digi al image I.
Ini ially, K(I):=Q(I).
While he e exis s a cell σ∈Q(I) ∂Q(I)do
I σis a ace o exac ly wo cells c, σ ∈Q(I)do
emo e σand σ om he cu en K(I);
ede ine cas c∪σ.
I σis a ace o exac ly one cell σ∈Q(I)do
emo e σand σ om he cu en K(I).
Ou pu : he cellula complex K(I).
Algo i hm 1. Face-Reduc ion P ocess
Nex , we p e o m a simplifica ion p ocess in ∂K(I) o p oduce a cellula
complex P(I) homeomo phic o K(I) such ha he maximal cells o ∂P(I)a e
polygons. Bu fi s , we need a defini ion.
De ini ion 1. A e ex ∈∂K(I)is c i ical i one o he ollowing si ua ions
occu s:
(i) is a ace o some edge esha ed by ou cubes, exac ly wo o which in e sec
along eand lie in Q(I)(see cubes w1and w2in Figu e 3).
(ii) is sha ed by eigh cubes, exac ly wo o which a e a e co ne -adjacen and
con ained in Q(I)(see cubes s1and s2in Figu e 3).
(iii) is sha ed by eigh cubes, exac ly wo o which a e co ne -adjacen and no
con ained in Q(I)(cubes 1and 2in Figu e 3).
Cup P oduc s on Polyhed al App oxima ions o 3D Digi al Images 111
Fig. 4. (a) N ←{q1,q2,q3,q4},(b) ace so p←{e1,e2,e3,e4,e5,e6,e7,e8}
I is a well-known ac ha a non-c i ical e ex o ∂K(I) lies in a neighbo hood
o ∂K(I) homeomo phic o R2(see [16]).
Algo i hm 2 p ocesses he non-c i ical e ices o ∂K(I) o ob ain he cellula
complex P(I). Ini ially, P(I)=K(I). Fo a e ex ∈∂P(I), le N be he se o
2-cells q∈P(I)inciden o he e ex .I N defines a egion R homeomo phic
o a disc, hen N is eplaced by a new 2-cell pin P(I), which is he union o he
cells o N .Theedgeso ∂P(I)inciden o and he e ex a e emo ed om
P(I) (see Figu e 4). Obse e ha he maximal cells o he final cellula complex
∂P(I) a e polygons and ∂P(I) has ewe cells han ∂K(I). We can se some
e mina ing condi ions. Fo example: (1) e mina e when he numbe o edges
o he polygons in ∂P(I) each some specified maximum; o (2) e mina e a e
me ging he se N o coplana 2-cells o ∂P(I) ( his p ese es he geome y bu
emo es ewe cells). An example o he diffe ences ha a ise om hese diffe en
e mina ing condi ions is demons a ed in Example 1.
Obse e ha Algo i hm 2 uses he o de ing on he se o non-c i ical e ices
V⊂∂K(I) o selec he nex non-c i ical e ex. To he bes o ou knowl-
edge, his is he fi s algo i hm o appea ha p oduces a cellula complex wi h
polygonal maximal cells by emo ing non-c i ical e ices.
Example 1. Le μI be a μMRI o a abecula bone o size: 85 ×85 ×10 oxels
(see Figu e 5 in which μI is gi en by a sequence o 10 2D digi al images o size
Inpu : The ou pu o Algo i hm 1: he cellula complex K(I).
Ini ially, P(I):=K(I);
V:= o de ed se o non-c i ical e ices o ∂K(I).
While ∃ ∈Vsuch ha R is homeomo phic o a disc do
emo e om P(I)and V;
emo e he edges inciden o om P(I);
emo e he 2-cells o N om P(I);
add a new 2-cell p o P(I)which is he union o he cells o N .
Ou pu : The cellula complex P(I).
Algo i hm 2. Algo i hm o ob ain he cellula complex P(I)

112 R. Gonzalez-Diaz, J. Lama , and R. Umble
Fig. 5. AμMRI o a abecula bone
85 ×85). The numbe o quad angles in ∂Q(μI) is 20956 (see Figu e 6). A e
applying Algo i hm 1 o ob ain he cellula complex K(μI), we apply Algo i hm
2 oK(μI) wi h he e mina ing condi ion 1 ( he numbe o he edges o he
polygons in ∂P(μI) is smalle o equal o 10). Then, he numbe o polygons o
∂P(μI) is 1567 (see Figu e 7.a). I we only conside he se o coplana polygons
N , hen he numbe o polygons o ∂P(μI) a e applying Algo i hm 2 is 9321
(see Figu e 7.b).
3 Compu ing he Cohomology Ring o P(I)
T adi ionally, one compu es cup p oduc s in simplicial o cubical complex using
he s anda d o mulas in [17,20]). In his sec ion, we gi e a p ocedu e o compu -
ing cup p oduc s on P(I) ( he ou pu o Algo i hm 2), which a oids iangula ion
by defining explici o mulas o diagonal app oxima ions on polygons.
We begin wi h a e iew o some s anda d defini ions om Algeb aic Topology
( o de ails see [17]). Gi en a g aded se S={Sq}q, heq-chains o S,whicha e
fini e o mal sums o elemen s o Sq, define an addi i e abelian g oup s uc u e
on Sq. These g oups, called q-chain g oups, a e deno ed by Cq(S). The collec-
ion o all chain g oups associa ed wi h Sis deno ed by C∗(S)={Cq(S)}q
Fig. 6. The cubical complex ∂Q(μI)
Cup P oduc s on Polyhed al App oxima ions o 3D Digi al Images 113
andis e e ed oas hechain g oup o S.Achain complex (C∗(S),∂)is
a chain g oup C∗(S) oge he wi h a squa e ze o homomo phism ∂={∂q:
Cq(S)→Cq−1(S)}q,called he bounda y ope a o . Fo example, conside a i-
angle  i,
j,
kwi h e ices i<
j<
k. The bounda y o he iangle is he
o mal sum o i s edges, ha is, ∂2( i,
j,
k)= i,
j+ j,
k+ i,
k.
No e ha any chain g oup C∗(S) oge he wi h he ze o bounda y map ∂≡0
is a chain complex.
The chain complex associa ed wi h P(I) ( he ou pu o Algo i hm 2) is he
collec ion (C∗(P(I)),∂)={Cq(P(I)),∂
q}qwhe e:
•each Cq(P(I)) is he chain g oup gene a ed by he q-cells o P(I),
• he bounda y ∂q:Cq(P(I)) →Cq−1(P(I)) e alua ed on a q-cell o P(I)is
he o mal sum o i s ace s, and
• he bounda y o a gene al q-chain is defined by linea ly ex ending ∂.
Gi enachaincomplex(C∗(S),∂), a q-chain σ∈Cq(S) is called a q-cycle i
∂q(σ)=0.I σ=∂q+1(μ) o some(q+1)-chainμ hen σis called a q-bounda y.
Re e ing o he iangle  i,
j,
kabo e, σ= i,
j+ j,
k+ i,
kis bo h
a 1-cycle and a 1-bounda y since ∂1(σ)=0andσ=∂2( i,
j,
k).
Two q-cycles aand aa e homologous i he e exis s a q-bounda y bsuch
ha a=a+b. Deno e he g oups o q-cycles and q-bounda ies by Zq(S)and
Bq(S), espec i ely. All q-bounda ies a e q-cycles (Bq(S)⊆Zq(S)). Define he
q h homology g oup o be he quo ien g oup Hq(S)=Zq(S)/Bq(S), o all q.
Each elemen o Hq(S)isaclass[a]=a+Bq(S)andais a ep esen a i e q-cycle.
The homology o Sis he collec ion o all he homology g oups associa ed wi h
S, i.e., H∗(S)={Hq(S)}q.
Le (C∗(S),∂)and(C∗(S),∂) be chain complexes. A homomo phism =
{ q:Cq(S)→Cq(S)}qsuch ha q∂q=∂
q q o all qis a chain map. No e
ha he iden i y idC∗(S)={idCq(S):Cq(S)→Cq(S)}qis a chain map.
Le ={ q:Cq(S)→Cq(S)}qand g={gq:Cq(S)→Cq(S)}qbe
chain maps. A chain homo opy om o gis a homomo phism φ={φq:
Cq(S)→Cq+1(S)}qsuch ha φq−1∂q+∂
q+1φq= q+gq o all q. Achain
con ac ion o (C∗(S),∂) o (C∗(S),∂) is a iple ( ={ q:Cq(S)→Cq(S)}q,
g={gq:Cq(S)→Cq(S)}q,φ={φq:Cq(S)→Cq +1(S)}q) such ha
(i) and ga e chain maps;
(ii) φis a chain homo opy om idC∗(S) o g ={gq q:Cq(S)→Cq(S)}q;
(iii) g ={ qgq:Cq(S)→Cq(S)}q=idC∗(S).
Cochain g oups a e he linea duals o chain g oups. Gi en a chain complex
(C∗(S),∂), a q-cochain c∈Hom(Cq(S),Z/2). I we index he q-cells in a cellula
complex om 1 o nq, hei co esponding duals gene a e C∗(S). Thus a cochain
c∈C∗(S)isaZ2-linea combina ion o he nqelemen s in he dual basis, and
as such can be hough o as a bi s ing o leng h nq.
The se Cq(S)o allq-cochains is a g oup, and he di ec sum o all cochain
g oups associa ed wi h Sis he g aded g oup C∗(S)={Cq(S)}q.Thecobounda y
ope a o δ={δq:Cq(S)→Cq+1(S)}qis defined on a q-cochain cby δq(c)=
c∂q+1.No e ha δ◦δ= 0. The associa ed cochain complex is he pai (C∗(S),δ).
114 R. Gonzalez-Diaz, J. Lama , and R. Umble
Fig. 7. (a) The cellula complex ∂P(μI) o 10 edges as uppe bound on p∈∂P(μI).
(b) The cellula complex ∂P(μI) p ese ing geome y.
Aq-cochain cis a q-cocycle i δq(c)=0.Aq-cochain bis a q-cobounda y i
he e exis s a (q−1)-cochain csuch ha b=δq−1(c). Two q-cocycles cand ca e
cohomologous i he e exis s a q-cobounda y bsuch ha c=c+b(see Figu e
8). We deno e he subg oup o q-cocycles by Zq(S), and he subg oup o q-
cobounda ies by Bq(S). The q h cohomology g oup is defined o be he quo ien
Hq(S)=Zq(S)/Bq(S). Each elemen o Hq(S)isaclass[c]=c+Bq(S).
The elemen cis a ep esen a i e q-cocycle o he cohomology class [c]. The
cohomology o Sis he g aded Z/2- ec o space H∗(S)={Hq(S)}q.
Since P(I) ( he ou pu o Algo i hm 2) is embedded in R3,homology and
cohomology o P(I) a e isomo phic and o sion ee.
An AT-model [10,11] o a chain complex (C∗(S),∂), deno ed by ((S, ∂),H,
,g,φ), consis s o a chain complex (C∗(H),∂≡0) oge he wi h a chain con-
ac ion ( ,g,φ)o (C∗(S),∂) o(C∗(H),∂). The ollowing p ope ies hold:
•I σ∈Hq, hen gq(σ)∈Cq(S) is a ep esen a i e cycle o a class o
Hq(C(S)).
•The cochain ∂σ :Cq(S)→Z/2 defined by
∂σ (μ):=1,i σappea s in he exp ession o (μ),
0,o he wise;
is a ep esen a i e cocycle o a class o Hq(S).
•The map Hq→Hq(S)gi enbyσ→ [g(σ)] linea ly ex ends o an isomo -
phism Cq(H)∼
=Hq(S).
•The map Hq→Hq(S)gi enbyσ→ [∂σ ] linea ly ex ends o an isomo -
phism Cq(H)∼
=Hq(S).
Example 2. Conside he cellula complex ∂P(μI) shown in Figu e 7.b ob ained
a e applying Algo i hm 2 o a μMRI o a abecula bone o size 85 ×85 ×10
Cup P oduc s on Polyhed al App oxima ions o 3D Digi al Images 115
0-cochain { 1}
1-cochain {e1,e
4}
1-cobounda y δ{ 1}={e3,e
4}
1-cocycle c={e1,e
2}
1-cocycle d={e1,e
2,e
3,e
4}
homologous cocycles cand d;sinced=c+δ{ 1}
Fig. 8. Example o cochain, cocycle and cobounda y
oxels. Table 1 shows he esul s o he homology compu a ion, i.e, he numbe
o connec ed componen s, holes and ca i ies ob ained a e compu ing an AT-
model o ∂P(μI). Rep esen a i e 1-cycles a e shown in Figu e 9.
Table 1. Resul s o he homology g oups compu a ion o he cellula complex ∂P(μI)
shown in Figu e 7.b. (see Figu e 9).
Cellula Complex H0H1H2
∂P(μI)526
An AT-model o (C∗(S),∂) always exis s and can be compu ed in O(m3), whe e
mis he numbe o elemen s o S(see [10,11]).
Gi enanAT-model((P(I),∂),H, ,g,φ) o P(I) ( he ou pu o Algo i hm
2), we ha e ha
C∗(H)∼
=H∗(P(I)) ∼
=H∗(P(I)) ∼
=Hom(H∗(P(I)),Z/2) ∼
=C∗(H).
Le α∈Hn. Conside he dual elemen a y n-cocycle in Cn(H),
α∗:Cn(H)→Z/2 such ha o μ∈Hn,α
∗(μ):=1i μ=α,
0o he wise.
P oposi ion 1. Gi en an o de ing { 1<··· <
n}o he e ices o P(I),
each polygon p∈P(I)can be exp essed as an o de ed lis o e ices { i1<
···<
ik}⊆{ 1<···<
n}wi h edges
ej:=  ij,
ij+1 ,i j<k,
 ik,
i1,i j=k.
The ollowing wo heo ems o mula e a diagonal app oxima ion ∇on a polygon
and he cup p oduc on H∗(P(I)) in e ms o ∇. All non- i ial cup p oduc s
in H∗(P(I)) a e p oduc s o 1-cocycles o dimensional easons.
Theo em 1. Conside a polygon p= 1,...,
nwi h edges ei= i,
i+1,
i<n,anden= n,
1. Then a diagonal app oxima ion on pis gi en by
∇(p):=1<i<n, i< i+1 (e1+···+ei−1)⊗ei
+1<i<n, i> i+1 (ei+1)+···+en)⊗ei.