In eg al Ope a o s o Compu ing Homology
Gene a o s a Any Dimension
Rocio Gonzalez-Diaz, Ma ia Jose Jimenez, Belen Med ano,
Helena Molina-Ab il, and Ped o Real
Applied Ma h Depa men , Uni e si y o Se ille, Spain
{ ogodi,maji o,belenmg,hab il, eal}@us.es
h p://alojamien os.us.es/g ocoma
Abs ac . S a ing om an nD geome ical objec , a cellula subdi-
ision o such an objec p o ides an algeb aic coun e pa om which
homology in o ma ion can be compu ed. In his pape , we de elop a p o-
cess o d as ically educe he amoun o da a ha ep esen he o iginal
objec , wi h he pu pose o a subsequen homology compu a ion. The
echnique applied is based on he cons uc ion o a sequence o elemen-
a y chain homo opies (in eg al ope a o s) which algeb aically connec
he ini ial objec wi h a simplified one wi h he same homological in o -
ma ion han he o me .
Keywo ds: in ege homology gene a o s, chain homo opies.
1 In oduc ion
Algeb aic Topology p o ides a g ea a ie y o ools ha ha e po en ial ap-
plica ions o many fields such as Disc e e Geome y, Da a Analysis, Compu e
G aphics o nD Digi al Image P ocessing. Some o hese applica ions ely on
he explici compu a ion o opological ea u es. Fo ins ance, s a ing om an
n-dimensional geome ic o combina o ial objec (mainly, n=3,4,...), one can
compu e associa ed opological in a ian s, such as Be i numbe s (which ep e-
sen he numbe o connec ed componen s, holes o ca i ies), Eule cha ac e is ic,
as well as o he ad anced ea u es, such as homology g oups. The in o ma ion
p o ided by he la e includes he o me , so homology p o ides a s onge
cha ac e iza ion o he opology.
When he g ound ing is a field, he algeb aic opological model gi en in [5,6]
(inspi ed in he inc emen al echnique o Delfinado-Edelsb unne [3]) is a use ul
ool o compu ing homology and ep esen a i e cycles o homology gene a o s.
Wo king in he in ege domain, a chain homo opy e sion o he Smi h No mal
Fo m (SNF) me hod o compu e homology [13,4,14] is gi en in [7,8].
In his pape , in o de o educe he numbe o gene a o s o he ini ial chain
complex C, we define e y simple and elemen a y ope a o s, which gi e place
Pa ially suppo ed by Jun a de Andalucia (FQM-296 and TIC-02268) and Spanish
Minis y o Science and Educa ion (MTM-2006-03722).
 Fellow associa ed o Uni e si y o Se ille unde TIC-02268 g an .
J. Ruiz-Shulclope and W.G. K opa sch (Eds.): CIARP 2008, LNCS 5197, pp. 356–363, 2008.
c
Sp inge -Ve lag Be lin Heidelbe g 2008
In eg al Ope a o s o Compu ing Homology Gene a o s a Any Dimension 357
o a sequence o chain homo opies om C o ano he chain complex Cwi h
he same in ege homology. A e wa ds, he chain-homo opy e sion o he SNF
gi en in [7,8] can be applied o ob ain he in ege homology o C, wi h he impo -
an p ope y ha he inpu da a o such a compu a ion has been significan ly
simplified.
The pape is o ganized as ollows. In Sec ion 2, we define he elemen a y chain
homo opies in eg al ope a o s; we p o ide bo h geome ic and algeb aic e sions
o such ope a o s. Sec ion 3 is de o ed o desc ibe he p ocess o conca ena ing a
sequence o such in eg al ope a o s ha gua an ees he achie emen o a smalle
chain complex wi h he same homology han he o iginal one. We also p esen
an example o applica ion o he me hod on a eal bina y olume image o a
abecula bone. In he las sec ion, some conclusions a e d awn.
2 In eg al Ope a o s
The e exis se e al combina o ial s uc u es which can model n-dimensional ge-
ome ic objec s, based on diffe en cellula subdi isions (cells) o he objec
(see [11,2]). Fo example, up o dim 3, simplicial complexes a e made up by e -
ices, edges, iangles and e ahed a, while e ices, edges, squa es and cubes
cons i u e he collec ion o cells o a cubical complex. Adding a g oup s uc-
u e o a cell complex, an algeb aic s uc u e, called chain complex, is ob ained.
Coefficien s will be conside ed o e Z.
Chain complexes and homology. [13,12]. Gi en a cell complex K, ob ained
by a subdi ision o a geome ic objec in o cells o diffe en dimensions, one can
define, o each dimension q, he chain g oup Cqwhose elemen s, called q-chain,
a e linea combina ions o cells o dimension q(q-cells). Then, a fini e chain
complex Cis gi en by a couple {C,∂},whe eC={Cq}0≤q≤dis a fini e sequence
o such a chain g oups and he diffe en ial ∂={∂q}0≤q≤dis a sequence o ho-
momo phisms ∂q:Cq→C
q−1, such ha he composi ion o any wo consecu i e
maps is ze o: ∂q∂q−1=0 o all0<q≤d(and ∂0≡0). A chain complex C
can be encoded as a pai (C, ∂), whe e C=0≤q≤dCq,eachCq={u1
q,...,u
nq
q}
is a basis o Cq(in gene al, Cqwill be a se o q-cells) and he diffe en ials a e
exp essed wi h espec hese basis. Fo simplici y, we some imes omi he indices.
In an in o mal way, a chain complex can be seen as an algeb aic gene aliza ion
o di ec ed mul ig aphs. Le G=(V,E,iG) be he di ec ed mul ig aph d awn
in Figu e 1 whe e V={(1),(2),(3)}is he se o e ices, E={a, b, c, d, e}
is he se o edges and iG:E→V×Vmaps each edge wi h i s inciden
e ices (p ese ing he o de gi en by he o ien a ion o he edges). Adding a
g oup s uc u e o Vand E, hemapiGcan be edefined as an applica ion ∂G,
p ese ing he g oup s uc u e, om E o V(see Figu e 1 on he igh ). The
applica ion ∂Gcan be seen as he diffe en ial o he chain complex Cwhe e C0
( esp. C1)hasV( esp. E) as a basis. No ice ha eis a sel -loop, so ∂G(e)=0.
Gi en a chain complex C,aq-chain a∈C
qis called a q-cycle i ∂qa=0(in
he example, ∂G(b+d+c)=0).I a=∂q+1b o some b∈C
q+1 hen ais called
358 R. Gonzalez-Diaz e al.
Fig. 1. The di ec ed mul ig aph Gand he ma ix co esponding o ∂G
aq-bounda y (e.g. (3) −(2) is a 0-bounda y). Deno e he g oups o q-cycles and
q-bounda ies by Zqand Bq espec i ely. Thanks o he nilpo ence p ope y o
∂,i is ue ha Zq⊆Bq o all q≥0. Define he q h in ege homology g oup
o be he quo ien g oup Zq/Bq, deno ed by Hq(C). Fo each q, hein ege
q h homology g oup Hq(C) is a fini ely gene a ed abelian g oup isomo phic o
Fq⊕Tq,whe eFqand Tqa e he ee subg oup and he o sion subg oup o Hq(C),
espec i ely. We say ha cis a ep esen a i e q-cycle o he homology gene a o
c+Bq(deno ed by [c]). The ank o Fq, deno ed by βq, is called he q h Be i
numbe o C.In ui i ely,β0is he numbe o componen s o connec ed pieces,
β1 he numbe o independen holes and β2 he numbe o ca i ies. Going back
o he example, H0(C)≃Zand H1(C)≃Z⊕Z⊕Z. Rep esen a i e cycles o
he homology gene a o s o dim 1 a e: e,c+b+dand a+b. Hence, β0=1and
β1=3.
I ,g :C→C
a e chain maps, hen a chain homo opy φ:C→C
o o gis a
amily o homomo phisms {φq:Cq→C
q+1}such ha q−gq=d
q+1φq+φq−1dq.
Then, is called a chain equi alence and gi s chain homo opical in e se.
In eg al ope a o s. Le C=({u1,...,u
n},∂) be a chain complex. Le iand j
be wo in ege s such ha 1 ≤i<j≤n, and dim uj=1+dimui.Anin eg al
ope a o is a linea map φ:C→Csuch ha φ(ui)=λuj o some λ∈Z,λ=0
and φ(uk) = 0 o any 1 ≤k≤n,k=i. An in eg al ope a o φsa isfies he
chain-homo opy p ope y i φ∂φ =φ. In his pape , we will deal wi h in eg al
ope a o s wi h he chain-homo opy p ope y.
P oposi ion 1. Conside he map π=id −φ∂ −∂φ :C→imπ (whe e imπ =
({u1,...,ˆui,...,ˆuj,...,u
n},π∂π), he ha means ha he elemen is omi ed)
and he inclusion ι:imπ →C.I φis an in eg al ope a o sa is ying he chain-
homo opy p ope y, hen φis a chain homo opy o he iden i y map o C o ιπ.
The e o e, Cand imπ ha e isomo phic in ege homology g oups.
Lemma 2. Le φbe a linea map gi en by φ(ui)=∂uj,u
iuj(whe e ∂uj,u
i
deno es he coefficien o uiin he exp ession o ∂uj). I ∂uj,u
i=±1 hen φ
is an in eg al ope a o sa is ying he chain-homo opy p ope y.
Geome ic in eg al ope a o s. Collapse and ace educ ion. The e is a well-
known p ocess o hinning a simplicial complex using simplicial collapses [1].
I can be easily ex ended o chain complexes. Suppose C=(C, ∂)isachain
In eg al Ope a o s o Compu ing Homology Gene a o s a Any Dimension 359
Fig. 2. A cell complex K(on he le ) and he cell complex a e applying he in eg al
ope a o φ(1) = −a(on he igh )
complex, C={u1,...,u
n}. Conside wo cells ui,u
j∈Csuch ha uiis a
ace o uj. Then, define an in eg al ope a o in ol ing hese cells, φ(ui)=λuj:
(1) i ujis a maximal cell ( ha is, uj∈ im∂)anduiis a ee ace o uj,
(which means ha ∂uj,u
i =0and∂uk,u
i=0 o anyk=j) hen, C
collapses on o C=({u1,...,ˆui,...,ˆuj,...,u
n},∂); (2) i uiis a ace o a leas
wo cells, ujand uk, henCis educed o C=(C,∂). Ccoincides wi h C
excep o uiand ujwhich disappea . A chain equi alence be ween Cand Cis
gi en in [10]. The in eg al ope a o associa ed o his cons uc ion is gi en by
φ(ui)=∂uj,u
iuj. In he pa icula case ha φsa isfies he chain-homo opy
p ope y, we ob ain he geome ic collapse and ace educ ion. Edge con ac ions.
Le Kbe a simplicial complex. Le τbe and edge o Kand a, b wo e ices
o Ksuch ha ∂(τ)=±b±a.Anedge con ac ion is gi en by he e ex map
e :K(0) →L(0) =K(0) {b}whe e e (b)=a,and e ( )= o
all e ex =b.I isknown ha i Lk a ∩Lk b =Lk τ, hen edge con ac ion
p ese es homo opy in a ian s. An edge con ac ion is ob ained a e applying
he sequence o in eg al ope a o s gi en by φ(σ,μ)(σ)=∂μ,σμ, o all σha ing
a ace in Lkτ,σbeing a ace o μ,bbeinga e exo σand aa e exo μ.
Fig. 3. AcomplexK,Ka e collapsing d, a e educing he ace and a e con-
ac ing d
Algeb aic in eg al ope a o s. Gi en a chain complex C=(C, ∂), C=
{u1,..., u
n}, conside he ma ix co esponding o ∂. Some ans o ma ions
on he ma ix can lead o cases o in eg al ope a o s.
Case 1. I ui,u
j∈Csa is y ha ∂uj,u
i=±1, conside he in eg al ope a o
φgi en by φ(ui)=∂uj,u
iuj.Thenimπ =({u1,...,ˆui,...,ˆuk,...,u
n},π∂π).
This is equi alen o he geome ic ope a ions o collapse o ace educ ion.
Case 2. I ui,u
j,u
k∈Csa is y ha ∂uk,u
i·∂uk,u
j =±1 and gcd(∂uk,u
i,
∂uk,u
j) = 1. hen he e exis wo in ege s αand βsuch ha α∂uk,u
i+
β∂uk,u
j= 1. Conside he ‘in eg al ope a o ’ gi en by φ(∂uk,u
iui+∂uk,u
j
360 R. Gonzalez-Diaz e al.
uj)=uk(which is, in ac , a linea combina ion o he in eg al ope a o s φi(ui)=
αukand φj(uj)=βuk). Then imπ =({u1,...,ˆui, ...,ˆuk,...,u
n},π∂π).
Case 3. I ui,u
j,u
k∈Csa is y ha ∂uj,u
i·∂uk,u
i =±1 and gcd(∂uj,u
i,
∂uk,u
i) = 1; hen he e exis wo in ege s αand βsuch ha α∂uj,u
i+
β∂uk,u
i= 1. Conside he in eg al ope a o gi en by φ(ui)=αuj+βuk.
Then, imπ =({u1,..., ˆui,...,ˆuj,...,u
n},π∂π).
3 In eg al Ope a o s o Ob aining Small Chain
Complexes
Conside a cell complex Ko dimension dand he chain complex C=(K, ∂),
associa ed o i . In his sec ion, we es ablish a sequence o in eg al ope a o s in
o de o ob ain a small chain complex C=(C,∂) wi h he same homology
han he o me such ha Cis a subse o K.
Geome ic Pa . F om i=d o i= 0, cons uc a g aph Gias ollows: associa e
anode (i,u) o each i-cell u∈K, excep o he i-cells used in he s ep i+1.
Add an edge be ween wo nodes (i,u)and (i,u)o he g aph i uand usha e
ano -used(i−1)-cell. Cons uc a co e o es Tio he g aph Giusing, o
example, b ead h-fi s sea ch algo i hm wi h oo in he cen e o he g aph.
Now, o each node (i,u) om he lea es o he oo o Ti, conside he in eg al
ope a o s:
–φ(i,u,u)(u):=∂u,uui (i,u)is a lea o Tiand he e exis s a ee ace
u o uin K(isola ed nodes a e conside ed lea es).
–φ(i,u,u)(u):=∂u,uui (i,u)is a no -lea node o Tiand u is he
(i−1)-cell o Kco esponding o he edge o Ticonnec ing he nodes (i,u)
and (i,u)(a child node o (i,u)).
Obse e ha we do no ha e o upda e he diffe en ial ∂o he chain complex
Ceach ime we add an in eg al ope a o . On he con a y, we can upda e ∂a
he end o he p ocess o each i.Le mbe he numbe o he in e nal nodes
o he co e o es Tiassocia ed o he g aph Gi. Then, in he wo s case, we
elimina e mi-cells and m(i−1)-cells, o each i=d,...,0.
Algeb aic Pa . Now, ini ialize π=π,C=Cπand ∂=∂π. While πchanges
do:
S ep 1. While he e exis ±1 coefficien s in he ma ix o ∂a any dimension
do: le u, u∈Csuch ha ∂u,u=±1. Then, conside he in eg al ope a o
gi en by φ(u):=∂u,uu.Upda eπ:= id −φ∂−∂φ,C:= C {u, u}
and ∂:= π∂π.
S ep 2. While he e exis cop ime coefficien s in a column o he ma ix o ∂
a any dimension, do: le u, u,u
 ∈Csuch ha gcd(∂u,u,∂u,u
)=1.
Conside he ‘in eg al ope a o ’ gi en by φ(∂u,uu+∂u,u
u):=u.
Upda e π:= id −φ∂−∂φ,C:= C {u, u}and ∂:= π∂π.I he eisa

In eg al Ope a o s o Compu ing Homology Gene a o s a Any Dimension 361
coefficien ±1in hema ixo ∂a any dimension, go o S ep 1. In o he case,
go o S ep 3.
S ep 3. While he e exis cop ime coefficien s in a ow o he ma ix o ∂a
any dimension, do: le u, u,u
 ∈Csuch ha gcd(∂u,u,∂u,u)=1.Le
αand β∈Zsuch ha α∂u,u+β∂u,u= 1. Then, conside he in eg al
ope a o φ(u):=αu+βu.Upda eπ:= id −φ∂−∂φ,C:= C {u, u}
and ∂:= π∂π.Go oS ep1.
Obse e ha he final chain complex Chas he p ope y ha no any elemen
o i s diffe en ial is ±1 and no any column no ow con ains cop ime coefficien s.
Mo eo e , his small chain complex con ains he same o sion in o ma ion as he
o iginal one.
Example 1. Conside he simplicial complex Ko dim2showninFigu e4a).
The co e ee ob ained o dim 2 is shown in b). The geome ic pa o i=2
gi es place o he ollowing in eg al ope a o s: φ1(d)=−B,φ2(b)=−Cand
φ3(c)=A. The esul ing complex is c). Fo i= 1, we ob ain: φ4(0)=−a,
φ5(2)=e,φ6(3)= . The co e ee o dim 1 is shown in d) and he
esul ing complex is Cπ=(Cπ,∂π)(seee))whe e
∂π14hg
100−1−1
40011
Now, applying he algeb aic pa o Cπ, we ob ain ha φ7(1)=−g. Then,
C=(C,∂)isgi enbyC={4,h}and ∂is null (see Figu e 4 )). Then
C≃H(K). The e o e, H0(K)≃Zand H1(K)≃Z.
Example 2. Conside a digi al bone olume image ob ained om a mic o mag-
ne ic esonance o a abecula bone (i has 85×85×20 = 144500 oxeles). C ea e
a simplicial complex Kwhich is opologically equi alen o he bone using he
Fig. 4. a) Simplicial complex K; b) co e o es co esponding o dim 2; c) esul ing
complex a e applying he geome ic pa o i= 2; d) co e o es co esponding o
dim 1; e) esul ing complex a e applying he geome ic pa o i=1; ) hecell
complex esul ing a e applying he algeb aic pa o he me hod
362 R. Gonzalez-Diaz e al.
Fig. 5. a) Simplicializa ion o he o eg ound o a bina y bone olume; p ese ing-
homology hinning o he o eg ound (b) and he backg ound (c) ob ained using in eg al
ope a o s
Fig. 6. a) A simplicial complex; b) a hinned one p ese ing end poin s ob ained using
in eg al ope a o s
(26,6)-adjacency (26 o he abecula bone and 6 o he bone ma ow). The
comple e olume’s simplicializa ion o he o eg ound has 90530 oxels, 543327
edges, 826320 iangles and 376434 e ahed ons. The numbe o connec ed com-
ponen s, holes and ca i ies o he o eg ound is 1, 3718 and 806 espec i ely. In
Figu e 5, only 5 ames (wi h 74835 simplices) a e shown, in o de o ge a be e
isualiza ion.
4 Conclusions
In his pape , we ackle he p oblem o compu ing in ege homology o a chain
complex associa ed o a cell complex. The exis ing me hods, such as inc emen al
algo i hms o he pe o mance o he SNF ma ix, accomplish he compu a ion
om he ini ial chain complex. We ha e de eloped he e a powe ul echnique
ha allows, in each s ep, o mo e on a smalle chain complex wi h he same
homology han he o iginal one. This is done ia he cons uc ion o in eg al op-
e a o s (elemen a y chain homo opies) which ac as some kind o local in e se o
he diffe en ial o he chain complex. Mo eo e , his me hod ac s, in some sense,
as a pa allel algo i hm, since he in eg al ope a o s a e defined only once o each
pai o elemen s conside ed and independen ly o he es o he gi en alues. The
me hod de eloped he e find di ec applica ion in he wo k o Pel ie e al. [15]
since he au ho s use simplicial collapse, ace educ ions and edge con ac ions in
o de o compu e homology gene a o s o images ia i egula g aph py amids.
One ini ial wo k done in his di ec ion is [9]. Ano he ad an age o his me hod
is ha i is possible o euse he ou pu o his echnique o ob aining fine
In eg al Ope a o s o Compu ing Homology Gene a o s a Any Dimension 363
algeb aic opological in a ian s (such as, cohomology ing, cohomology ope a o s
and homo opy g oups) o he objec .
Re e ences
1. Bj¨o ne , A.: Topological Me hods. Handbook on Combina o ics 2, 1819–1872
(1995)
2. Dahmen, W., Micchelli, C.A.: On he Linea Independence o Mul i a ia e b-
Splines. T iangula ion o Simploids. SIAM J. Nume . Anal. 19 (1982)
3. Delfinado, C.J.A., Edelsb unne , H.: An Inc emen al Algo i hm o Be i Numbe s
o Simplicial Complexes on he 3–Sphe e. Compu . Aided Geom. Design 12(7),
771–784 (1995)
4. Dumas, J.G., Saunde s, B.D., Villad, G.: On Efficien Spa se In ege Ma ix SNF
Compu a ions. J. Symb. Compu . 32(1), 71–99 (2001)
5. Gonzalez-Diaz, R., Real, P.: Compu a ion o Cohomology Ope a ions on Fini e
Simplicial Complexes. HHA 5(2), 83–93 (2001)
6. Gonzalez-Diaz, R., Real, P.: On he Cohomology o 3D Digi al Images. Disc e e
Appl. Ma h. 147(2-3), 245–263 (2005)
7. Gonzalez-Diaz, R., Med ano, B., Real, P., Sanchez-Pelaez, J.: Reusing In ege Ho-
mology In o ma ion o Digi al Images. In: Kuba, A., Ny´ul, L.G., Pal´agyi, K. (eds.)
DGCI 2006. LNCS, ol. 4245, pp. 199–210. Sp inge , Heidelbe g (2006)
8. Gonzalez-Diaz, R., Jimenez, M.J., Med ano, B., Real, P.: Chain Homo opies o
Objec Topological Rep esen a ions. Disc e e Appl. Ma h. ( o appea )
9. Gonzalez-Diaz, R., Iglesias-Ham, M., Ion, A., K opa sch, W.G.: I egula G aph
Py amids, In eg al Ope a o s and Rep esen a i e Cocycles o Cohomology Gene a-
o s. In: Wo kshop on Compu a ional Topology in Image Con ex , Poi ie s, F ance
(2008)
10. Kaczynski, T., Mischaikow, K., M ozek, M.: Compu a ional Homology. In: AMS,
P o idence, Rhode Island, ol. 157 (2004)
11. Massey, W.M.: A Basic Cou se in Algeb aic Topology. G adua e Tex s in Ma h.,
ol. 127. Sp inge , New Yo k (1991)
12. MacLane, S.: Homology. Classics in Ma hema ics. Sp inge , Be lin (1995)
13. Munk es, J.R.: Elemen s o Algeb aic Topology. Addison-Wesley, Canada (1993)
14. Pel ie , S., Alay angues, S., Fuchs, L., Lachaud, J.: Compu a ion o Homology
G oups and Gene a o s. In: And `es, ´
E., Damiand, G., Lienha d , P. (eds.) DGCI
2005. LNCS, ol. 3429, pp. 195–205. Sp inge , Heidelbe g (2005)
15. Pel ie , S., Ion, A., Haxhimusa, Y., K opa sch, W.G., Damiand, G.: Compu ing
Homology Gene a o s Using I egula G aph Py amids. In: Escolano, F., Ven o,
M. (eds.) GbRPR 2007. LNCS, ol. 4538, pp. 283–294. Sp inge , Heidelbe g (2007)