Integral operators for computing homology generators at any dimension

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)