Integral operators for computing homology generators at any dimension

Integral Operators for Computing Homology Generators at Any Dimension Rocio Gonzalez-Diaz, Maria Jose Jimenez, Belen Medrano, Helena Molina-Abril, and Pedro Real Applied Math Department, University of Seville, Spain {rogodi,majiro,belenmg,habril,real}@us.es http://alojamientos.us.es/gtocoma Abstract. Starting from an nD geometrical object, a cellular subdivision of such an object provides an algebraic counterpart from which homology information can be computed. In this paper, we develop a process to drastically reduce the amount of data that represent the original object, with the purpose of a subsequent homology computation. The technique applied is based on the construction of a sequence of elementary chain homotopies (integral operators) which algebraically connect the initial object with a simplified one with the same homological information than the former. Keywords: integer homology generators, chain homotopies. 1 Introduction Algebraic Topology provides a great variety of tools that have potential applications to many fields such as Discrete Geometry, Data Analysis, Computer Graphics or nD Digital Image Processing. Some of these applications rely on the explicit computation of topological features. For instance, starting from an n-dimensional geometric or combinatorial object (mainly, n=3,4,...), one can compute associated topological invariants, such as Betti numbers (which represent the number of connected components, holes or cavities), Euler characteristic, as well as other advanced features, such as homology groups. The information provided by the latter includes the former, so homology provides a stronger characterization of the topology. When the ground ring is a field, the algebraic topological model given in [5,6] (inspired in the incremental technique of Delfinado-Edelsbrunner [3]) is a useful tool for computing homology and representative cycles of homology generators. Working in the integer domain, a chain homotopy version of the Smith Normal Form (SNF) method to compute homology [13,4,14] is given in [7,8]. In this paper, in order to reduce the number of generators of the initial chain complex C, we define very simple and elementary operators, which give place Partially supported by Junta de Andalucia (FQM-296 and TIC-02268) and Spanish Ministry for Science and Education (MTM-2006-03722).  Fellow associated to University of Seville under TIC-02268 grant. J. Ruiz-Shulcloper and W.G. Kropatsch (Eds.): CIARP 2008, LNCS 5197, pp. 356–363, 2008. c Springer-Verlag Berlin Heidelberg 2008 Integral Operators for Computing Homology Generators at Any Dimension 357 to a sequence of chain homotopies from Cto another chain complex Cwith the same integer homology. Afterwards, the chain-homotopy version of the SNF given in [7,8] can be applied to obtain the integer homology of C, with the important property that the input data for such a computation has been significantly simplified. The paper is organized as follows. In Section 2, we define the elementary chain homotopies integral operators; we provide both geometric and algebraic versions of such operators. Section 3 is devoted to describe the process of concatenating a sequence of such integral operators that guarantees the achievement of a smalle chain complex with the same homology than the original one. We also present an example of application of the method on a real binary volume image of a trabecular bone. In the last section, some conclusions are drawn. 2 Integral Operators There exist several combinatorial structures which can model n-dimensional geometric objects, based on different cellular subdivisions (cells) of the object (see [11,2]). For example, up to dim 3, simplicial complexes are made up by vertices, edges, triangles and tetrahedra, while vertices, edges, squares and cubes constitute the collection of cells of a cubical complex. Adding a group structure to a cell complex, an algebraic structure, called chain complex, is obtained. Coefficients will be considered over Z. Chain complexes and homology. [13,12]. Given a cell complex K, obtained by a subdivision of a geometric object into cells of different dimensions, one can define, for each dimension q, the chain group Cqwhose elements, called q-chain, are linear combinations of cells of dimension q(q-cells). Then, a finite chain complex Cis given by a couple {C,∂},whereC={Cq}0≤q≤dis a finite sequence of such a chain groups and the differential ∂={∂q}0≤q≤dis a sequence of homomorphisms ∂q:Cq→C q−1, such that the composition of any two consecutive maps is zero: ∂q∂q−1=0forall0<q≤d(and ∂0≡0). A chain complex C can be encoded as a pair (C, ∂), where C=0≤q≤dCq,eachCq={u1 q,...,u nq q} is a basis of Cq(in general, Cqwill be a set of q-cells) and the differentials are expressed with respect these basis. For simplicity, we sometimes omit the indices. In an informal way, a chain complex can be seen as an algebraic generalization of directed multigraphs. Let G=(V,E,iG) be the directed multigraph drawn in Figure 1 where V={(1),(2),(3)}is the set of vertices, E={a, b, c, d, e} is the set of edges and iG:E→V×Vmaps each edge with its incident vertices (preserving the order given by the orientation of the edges). Adding a group structure to Vand E,themapiGcan be redefined as an application ∂G, preserving the group structure, from Eto V(see Figure 1 on the right). The application ∂Gcan be seen as the differential of the chain complex Cwhere C0 (resp. C1)hasV(resp. E) as a basis. Notice that eis a self-loop, so ∂G(e)=0. Given a chain complex C,aq-chain a∈C qis called a q-cycle if ∂qa=0(in the example, ∂G(b+d+c)=0).Ifa=∂q+1bfor some b∈C q+1 then ais called 358 R. Gonzalez-Diaz et al. Fig. 1. The directed multigraph Gand the matrix corresponding to ∂G aq-boundary (e.g. (3) −(2) is a 0-boundary). Denote the groups of q-cycles and q-boundaries by Zqand Bqrespectively. Thanks to the nilpotence property of ∂,itistruethatZq⊆Bqfor all q≥0. Define the qth integer homology group to be the quotient group Zq/Bq, denoted by Hq(C). For each q,theinteger qth homology group Hq(C) is a finitely generated abelian group isomorphic to Fq⊕Tq,whereFqand Tqare the free subgroup and the torsion subgroup of Hq(C), respectively. We say that cis a representative q-cycle of the homology generator c+Bq(denoted by [c]). The rank of Fq, denoted by βq, is called the qth Betti number of C.Intuitively,β0is the number of components of connected pieces, β1the number of independent holes and β2the number of cavities. Going back to the example, H0(C)≃Zand H1(C)≃Z⊕Z⊕Z. Representative cycles of the homology generators of dim 1 are: e,c+b+dand a+b. Hence, β0=1and β1=3. If f,g :C→C are chain maps, then a chain homotopy φ:C→C of fto gis a family of homomorphisms {φq:Cq→C q+1}such that fq−gq=d q+1φq+φq−1dq. Then, fis called a chain equivalence and gits chain homotopical inverse. Integral operators. Let C=({u1,...,u n},∂) be a chain complex. Let iand j be two integers such that 1 ≤i<j≤n, and dim uj=1+dimui.Anintegral operator is a linear map φ:C→Csuch that φ(ui)=λujfor some λ∈Z,λ=0 and φ(uk) = 0 for any 1 ≤k≤n,k=i. An integral operator φsatisfies the chain-homotopy property if φ∂φ =φ. In this paper, we will deal with integral operators with the chain-homotopy property. Proposition 1. Consider the map π=id −φ∂ −∂φ :C→imπ (where imπ = ({u1,...,ˆui,...,ˆuj,...,u n},π∂π), the hat means that the element is omitted) and the inclusion ι:imπ →C.Ifφis an integral operator satisfying the chainhomotopy property, then φis a chain homotopy of the identity map of Cto ιπ. Therefore, Cand imπ have isomorphic integer homology groups. Lemma 2. Let φbe a linear map given by φ(ui)=∂uj,u iuj(where ∂uj,u i denotes the coefficient of uiin the expression of ∂uj). If ∂uj,u i=±1then φ is an integral operator satisfying the chain-homotopy property. Geometric integral operators. Collapse and face reduction. There is a wellknown process for thinning a simplicial complex using simplicial collapses [1]. It can be easily extended to chain complexes. Suppose C=(C, ∂)isachain Integral Operators for Computing Homology Generators at Any Dimension 359 Fig. 2. A cell complex K(on the left) and the cell complex after applying the integral operator φ(1) = −a(on the right) complex, C={u1,...,u n}. Consider two cells ui,u j∈Csuch that uiis a face of uj. Then, define an integral operator involving these cells, φ(ui)=λuj: (1) if ujis a maximal cell (that is, uj∈ im∂)anduiis a free facet of uj, (which means that ∂uj,u i =0and∂uk,u i=0foranyk=j) then, C collapses onto C=({u1,...,ˆui,...,ˆuj,...,u n},∂); (2) if uiis a face of at least two cells, ujand uk,thenCis reduced to C=(C,∂). Ccoincides with C except for uiand ujwhich disappear. A chain equivalence between Cand Cis given in [10]. The integral operator associated to this construction is given by φ(ui)=∂uj,u iuj. In the particular case that φsatisfies the chain-homotopy property, we obtain the geometric collapse and face reduction. Edge contractions. Let Kbe a simplicial complex. Let τbe and edge of Kand a, b two vertices of Ksuch that ∂(τ)=±b±a.Anedge contraction is given by the vertex map fvert :K(0) →L(0) =K(0) \{b}where fvert(b)=a,andfvert(v)=vfor all vertex v=b.ItisknownthatifLk a ∩Lk b =Lk τ, then edge contraction preserves homotopy invariants. An edge contraction is obtained after applying the sequence of integral operators given by φ(σ,μ)(σ)=∂μ,σμ, for all σhaving a facet in Lkτ,σbeing a facet of μ,bbeingavertexofσand aavertexofμ. Fig. 3. AcomplexK,Kafter collapsing d, after reducing the face fand after contracting d Algebraic integral operators. Given a chain complex C=(C, ∂), C= {u1,..., u n}, consider the matrix corresponding to ∂. Some transformations on the matrix can lead to cases of integral operators. Case 1. If ui,u j∈Csatisfy that ∂uj,u i=±1, consider the integral operator φgiven by φ(ui)=∂uj,u iuj.Thenimπ =({u1,...,ˆui,...,ˆuk,...,u n},π∂π). This is equivalent to the geometric operations of collapse or face reduction. Case 2. If ui,u j,u k∈Csatisfy that ∂uk,u i·∂uk,u j =±1 and gcd(∂uk,u i, ∂uk,u j) = 1. then there exist two integers αand βsuch that α∂uk,u i+ β∂uk,u j= 1. Consider the ‘integral operator’ given by φ(∂uk,u iui+∂uk,u j 360 R. Gonzalez-Diaz et al. uj)=uk(which is, in fact, a linear combination of the integral operators φi(ui)= αukand φj(uj)=βuk). Then imπ =({u1,...,ˆui, ...,ˆuk,...,u n},π∂π). Case 3. If ui,u j,u k∈Csatisfy that ∂uj,u i·∂uk,u i =±1 and gcd(∂uj,u i, ∂uk,u i) = 1; then there exist two integers αand βsuch that α∂uj,u i+ β∂uk,u i= 1. Consider the integral operator given by φ(ui)=αuj+βuk. Then, imπ =({u1,..., ˆui,...,ˆuj,...,u n},π∂π). 3 Integral Operators for Obtaining Small Chain Complexes Consider a cell complex Kof dimension dand the chain complex C=(K, ∂), associated to it. In this section, we establish a sequence of integral operators in order to obtain a small chain complex C=(C,∂) with the same homology than the former such that Cis a subset of K. Geometric Part. From i=dto i= 0, construct a graph Gias follows: associate anodev(i,u)to each i-cell u∈K, except for the i-cells used in the step i+1. Add an edge between two nodes v(i,u)and v(i,u)of the graph if uand ushare anot-used(i−1)-cell. Construct a cover forest Tiof the graph Giusing, for example, breadth-first search algorithm with root in the center of the graph. Now, for each node v(i,u)from the leaves to the root of Ti, consider the integral operators: –φ(i,u,u)(u):=∂u,uuif v(i,u)is a leaf of Tiand there exists a free facet u of uin K(isolated nodes are considered leaves). –φ(i,u,u)(u):=∂u,uuif v(i,u)is a not-leaf node of Tiand u is the (i−1)-cell of Kcorresponding to the edge of Ticonnecting the nodes v(i,u) and v(i,u)(a child node of v(i,u)). Observe that we do not have to update the differential ∂of the chain complex Ceach time we add an integral operator. On the contrary, we can update ∂at the end of the process for each i.Letmbe the number of the internal nodes of the cover forest Tiassociated to the graph Gi. Then, in the worst case, we eliminate mi-cells and m(i−1)-cells, for each i=d,...,0. Algebraic Part. Now, initialize π=π,C=Cπand ∂=∂π. While πchanges do: Step 1. While there exist ±1 coefficients in the matrix of ∂at any dimension do: let u, u∈Csuch that ∂u,u=±1. Then, consider the integral operator given by φ(u):=∂u,uu.Updateπ:= id −φ∂−∂φ,C:= C\{u, u} and ∂:= π∂π. Step 2. While there exist coprime coefficients in a column of the matrix of ∂ at any dimension, do: let u, u,u  ∈Csuch that gcd(∂u,u,∂u,u )=1. Consider the ‘integral operator’ given by φ(∂u,uu+∂u,u u):=u. Update π:= id −φ∂−∂φ,C:= C\{u, u}and ∂:= π∂π.Ifthereisa Integral Operators for Computing Homology Generators at Any Dimension 361 coefficient ±1inthematrixof∂at any dimension, go to Step 1. In other case, go to Step 3. Step 3. While there exist coprime coefficients in a row of the matrix of ∂at any dimension, do: let u, u,u  ∈Csuch that gcd(∂u,u,∂u,u)=1.Let αand β∈Zsuch that α∂u,u+β∂u,u= 1. Then, consider the integral operator φ(u):=αu+βu.Updateπ:= id −φ∂−∂φ,C:= C\{u, u} and ∂:= π∂π.GotoStep1. Observe that the final chain complex Chas the property that not any element of its differential is ±1 and not any column nor row contains coprime coefficients. Moreover, this small chain complex contains the same torsion information as the original one. Example 1. Consider the simplicial complex Kofdim2showninFigure4a). The cover tree obtained for dim 2 is shown in b). The geometric part for i=2 gives place to the following integral operators: φ1(d)=−B,φ2(b)=−Cand φ3(c)=A. The resulting complex is c). For i= 1, we obtain: φ4(0)=−a, φ5(2)=e,φ6(3)=f. The cover tree for dim 1 is shown in d) and the resulting complex is Cπ=(Cπ,∂π)(seee))where ∂π14hg 100−1−1 40011 Now, applying the algebraic part to Cπ, we obtain that φ7(1)=−g. Then, C=(C,∂)isgivenbyC={4,h}and ∂is null (see Figure 4 f)). Then C≃H(K). Therefore, H0(K)≃Zand H1(K)≃Z. Example 2. Consider a digital bone volume image obtained from a micro magnetic resonance of a trabecular bone (it has 85×85×20 = 144500 voxeles). Create a simplicial complex Kwhich is topologically equivalent to the bone using the Fig. 4. a) Simplicial complex K; b) cover forest corresponding to dim 2; c) resulting complex after applying the geometric part for i= 2; d) cover forest corresponding to dim 1; e) resulting complex after applying the geometric part for i=1;f)thecell complex resulting after applying the algebraic part of the method 362 R. Gonzalez-Diaz et al. Fig. 5. a) Simplicialization of the foreground of a binary bone volume; preservinghomology thinning of the foreground (b) and the background (c) obtained using integral operators Fig. 6. a) A simplicial complex; b) a thinned one preserving end points obtained using integral operators (26,6)-adjacency (26 for the trabecular bone and 6 for the bone marrow). The complete volume’s simplicialization of the foreground has 90530 voxels, 543327 edges, 826320 triangles and 376434 tetrahedrons. The number of connected components, holes and cavities of the foreground is 1, 3718 and 806 respectively. In Figure 5, only 5 frames (with 74835 simplices) are shown, in order to get a better visualization. 4 Conclusions In this paper, we tackle the problem of computing integer homology of a chain complex associated to a cell complex. The existing methods, such as incremental algorithms or the performance of the SNF matrix, accomplish the computation from the initial chain complex. We have developed here a powerful technique that allows, in each step, to move on a smaller chain complex with the same homology than the original one. This is done via the construction of integral operators (elementary chain homotopies) which act as some kind of local inverse of the differential of the chain complex. Moreover, this method acts, in some sense, as a parallel algorithm, since the integral operators are defined only once for each pair of elements considered and independently of the rest of the given values. The method developed here find direct application in the work of Peltier et al. [15] since the authors use simplicial collapse, face reductions and edge contractions in order to compute homology generators of images via irregular graph pyramids. One initial work done in this direction is [9]. Another advantage of this method is that it is possible to reuse the output of this technique for obtaining finer Integral Operators for Computing Homology Generators at Any Dimension 363 algebraic topological invariants (such as, cohomology ring, cohomology operators and homotopy groups) of the object. References 1. Bj¨orner, A.: Topological Methods. Handbook on Combinatorics 2, 1819–1872 (1995) 2. Dahmen, W., Micchelli, C.A.: On the Linear Independence of Multivariate b- Splines. Triangulation of Simploids. SIAM J. Numer. Anal. 19 (1982) 3. Delfinado, C.J.A., Edelsbrunner, H.: An Incremental Algorithm for Betti Numbers of Simplicial Complexes on the 3–Sphere. Comput. Aided Geom. Design 12(7), 771–784 (1995) 4. Dumas, J.G., Saunders, B.D., Villad, G.: On Efficient Sparse Integer Matrix SNF Computations. J. Symb. Comput. 32(1), 71–99 (2001) 5. Gonzalez-Diaz, R., Real, P.: Computation of Cohomology Operations on Finite Simplicial Complexes. HHA 5(2), 83–93 (2001) 6. Gonzalez-Diaz, R., Real, P.: On the Cohomology of 3D Digital Images. Discrete Appl. Math. 147(2-3), 245–263 (2005) 7. Gonzalez-Diaz, R., Medrano, B., Real, P., Sanchez-Pelaez, J.: Reusing Integer Homology Information of Digital Images. In: Kuba, A., Ny´ul, L.G., Pal´agyi, K. (eds.) DGCI 2006. LNCS, vol. 4245, pp. 199–210. Springer, Heidelberg (2006) 8. Gonzalez-Diaz, R., Jimenez, M.J., Medrano, B., Real, P.: Chain Homotopies for Object Topological Representations. Discrete Appl. Math. (to appear) 9. Gonzalez-Diaz, R., Iglesias-Ham, M., Ion, A., Kropatsch, W.G.: Irregular Graph Pyramids, Integral Operators and Representative Cocycles of Cohomology Generators. In: Workshop on Computational Topology in Image Context, Poitiers, France (2008) 10. Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. In: AMS, Providence, Rhode Island, vol. 157 (2004) 11. Massey, W.M.: A Basic Course in Algebraic Topology. Graduate Texts in Math., vol. 127. Springer, New York (1991) 12. MacLane, S.: Homology. Classics in Mathematics. Springer, Berlin (1995) 13. Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Canada (1993) 14. Peltier, S., Alayrangues, S., Fuchs, L., Lachaud, J.: Computation of Homology Groups and Generators. In: Andr`es, ´ E., Damiand, G., Lienhardt, P. (eds.) DGCI 2005. LNCS, vol. 3429, pp. 195–205. Springer, Heidelberg (2005) 15. Peltier, S., Ion, A., Haxhimusa, Y., Kropatsch, W.G., Damiand, G.: Computing Homology Generators Using Irregular Graph Pyramids. In: Escolano, F., Vento, M. (eds.) GbRPR 2007. LNCS, vol. 4538, pp. 283–294. Springer, Heidelberg (2007)