Generating Second Order (Co)homological Information within AT-Model Context

Generating Second Order (Co)homological Information within AT-Model Context Pedro Real1, Helena Molina-Abril1, Fernando D´ıaz del R´ıo1, and Darian Onchis2,3 1H.T.S. Informatics’ Engineering, University of Seville, Seville, Spain {real,habril}@us.es, [email protected] 2Faculty of Mathematics, University of Vienna, Vienna, Austria [email protected] 3Faculty of Mathematics and Computer Science, West University of Timisoara, Timi¸soara, Romania Abstract. In this paper we design a new family of relations between (co)homology classes, working with coefficients in a field and starting from an AT-model (Algebraic Topological Model) AT (C) of a finite cell complex CThese relations are induced by elementary relations of type “to be in the (co)boundary of” between cells. This high-order connectivity information is embedded into a graph-based representation model, called Second Order AT-Region-Incidence Graph (or AT-RIG) of C.This graph, having as nodes the different homology classes of C, is in turn, computed from two generalized abstract cell complexes, called primal and dual AT-segmentations of C. The respective cells of these two complexes are connected regions (set of cells) of the original cell complex C, which are specified by the integral operator of AT (C). In this work in progress, we successfully use this model (a) in experiments for discriminating topologically different 3D digital objects, having the same Euler characteristic and (b) in designing a parallel algorithm for computing potentially significant (co)homological information of 3D digital objects. Keywords: Cell complex ·Algebraic-topological model Homology computation ·Primal and dual AT-segmentation AT-model region-incidence-graph ·nD digital object 1 Introduction (Co)homology (see for instance [33]) provides valuable information about topological spaces, by observing sets that intuitively have no (co)boundary, but are This work has been supported by the Spanish research projects MTM2016-81030-P (AEI/FEDER, UE) and TEC2012-37868-C04-02, and by the VPPI of the University of Seville. Darian Onchis gratefully acknowledges the support of the Austrian Science Fund FWF-P27516. on the (co)boundary of other sets. These sets are representative (co)cycles of a (co)homology hole, seen as an equivalence class. Algebraic (co)homological information with coefficients in a field could be defined as the set of processed and structured linear algebraic data describing in some sense its (co)homology classes and the relations between them. We talk about homology and cohomology information as a whole due to the fact that homology and cohomology classes are measured using different strategies (delineating or cutting holes) for detecting homological holes over the initial topological data. A simple example of (co)homology information is provided by the numerical topological invariants called Betti numbers. For instance, if Xis a cell complex embedded in R3, Betti numbers β0,β 1and β2respectively measure the number of different connected components, tunnels and cavities of X. Roughly speaking, (co)homotopy holes of objects (those related to delineating or cutting generalized “parametrized and oriented closed curves”) are theoretically attainable from homology’s ones [23], but these methods have an enormous complexity in time and space [4]. An easier relation between homology and homotopy is given by the Euler characteristic (see [1]), defined in local terms as the alternate sum of the number of cells in each dimension. This number is the most simple example of homotopy invariant, that can also be obtained from the global homological information provided by the Betti numbers. Now, (co)homology information of Xis not reduced in general to that provided by Betti numbers. For example, a torus Tand a three-dimensional sphere with two handles Shave the same Betti numbers (and, consequently the same Euler characteristic) but they are not (co)homologically equivalents. The two tunnels of Tare related to its cavity in a much more “stronger” way that the tunnels of Sare with regards to the corresponding cavity. We progress here in discovering the homotopy nature of homology, by creating two (non-unique) abstract cell complexes, called primal and dual AT- segmentations, both with significantly smaller number of cells than the original geometric cell complex Cand from which it is possible to detect topological relationships between (co)homology classes of Cwith coefficient in a field F. We construct the primal and dual segmentation with the help of an algebraictopological model AT (C)ofC(or AT-model for short) [17,18,34,35]. Using the bounding functions of a primal and dual AT-segmentations and the relationship between cells “to be in the boundary of”, we are finally able to compute a graphbased model P(AT (C)), called AT-model Region-Incidence-Graph (or, AT-RIG, for short), whose nodes are the different homology classes of C. We successfully use this technique in a set of experiments for discriminating topologically different 3D digital objects with the same Euler characteristic. We also use this modus operandi in designing a parallel algorithm for computing potential high-order homology statistics for a 3D digital objects. In a near future, we intend to study the corresponding degrees of independence with regards the AT-model chosen and of homology and homotopy invariances of an AT-RIG. 1.1 Related Works Focusing on homotopy representation models of digital objects and images, there are numerous works that arise from sources of digital topology [2,21,25], continuous or cellular topology [9,20,26] and nD shape search with three clearly differentiated notions: Reeb graphs [5,13], skeletons [6,36,41] and boundary representations [3,16,28]. Relative to the intermediary step of homological computation of cell complexes, there is plenty of literature based on a pure algebraic perspective devoted to this issue. The classical method is based on the diagonalization of cell-incidence matrices to Smith normal form (SNF) [33]. Some advances in the computation of the SNF have been achieved [10], but the most successful approaches consist of reducing the number of cells in the complex using discretevector-field dynamics (Discrete Morse theory [12]) before computing the SNF for the small resulting cell complex (see, for instance, [7,14,19,22,32,35,39,40]). This paper goes beyond homological computation and designs (sequential and parallel) algorithms for computing a new graph-based representation that allows to discriminate homologically different geometric objects embedded in Rnhaving the same Betti numbers. In this sense, AT-segmentation theory extend and greatly improve both the algebraic model called Algebraic-Topological model [17,18,34,35,37] and the combinatorial model called Homological Spanning Forest (HSF, for short) [8,30,31,38] in this search of topological representations within digital image context. 2 Cell Complexes and Algebraic-Topological Models We work in this paper with cell complex representations (composed of cells and bounding relations between them), that allow to model, for example, not only an n-dimensional digital object at sub-n-xel level but also significant algebraic (co)homological information (with coefficient in a field F). First at all, we provide a slightly modified version of the classical abstract cell complex notion (see [24]forasurvey). We say that C=(C, B, dms)isanabstract cell complex (or ACC, for short) if: –C={Cq}q∈N∪{0}is a finite set with a gradation dms :C→N{0}defined by dms(c)=qfor c∈Cq; –B:C×C→N∪{0}is a map such that satisfies the following condition: B(c, c)= 0 implies c∈Cq−1,c∈Cq. We refer to the elements of Cas cells and to B(c, c) as the bounding function of the ACC Capplied to the couple (c, c). If we extend the bounding function of the ACC in an antisymmetric and transitively way, we recover the classical notion of ACC. The connectivity-graph G(C, B, dms)=(V,E) of an abstract cell complex (C, B, dms) is the graph whose set of nodes is Cand an edge {c, c}∈Eif B(c, c)orB(c,c) is different from zero. Now, let us define the (algebraic) notion of geometric cell complex. We say that C=(C, κ, dms)isaLefschetz complex [27]if: –C={Cq}q∈N∪{0}is a finite set with a gradation dms :C→N{0}defined by dms(c)=qfor c∈Cq; –κ:C×C→Fis a map such that κ(c, c)= 0 implies c∈Cq−1,c∈Cq.For any c, c ∈Cwe have c∈Cκ(c, c)κ(c,c )=0. We refer to the elements of Cas cells and to κ(x, y) as the incidence coefficient of x,y. In fact, an equivalent definition of a Lefschetz complex is that of a free chain complex (F[C],∂ C) with boundary ∂C:F[C]→F[C] defined on generators by ∂C(c)=c∈Cκ(c,c)c.Itscoboundary δC:F[C]→F[C] is defined on generators by δC(c)=c∈Cκ(c, c)c. The Lefschetz homology (resp. cohomology) of (C, κ, dms), denoted H(C,∂ C)(resp.H(C,δ C)) is the homology of the chain complex (F[C],∂)(resp.(F[C],δ)). We are interested here in Lefschetz complexes satisfying that for any c, c∈Cthe incidence coefficient κ(c, c) is either zero or ±1ofF. These structures are simply called here geometric cell complexes. The identity function 1C:C→Cis defined by 1C(c)=c,∀c∈C. Associated to a geometric cell complex (C, κ, dms), there is a bounding function B:C×C→N∪{0}defined by B(c, c)=1ifκ(c, c)=0andB(c, c)=0in the rest of cases. If c∈Cand Ris a set of cells of (C, κ, dms), we define the bounding function B(c, R)=c∈RB(c, c)(resp.B(R, c)=c∈RB(c, c)). From now on, we use the triplet (C, ∂, dms) for denoting a geometric cell complex. We use the notation c∈f, being f∈F[C], for indicating that the cell cis involved as a non-null summand in this linear combination. It is straightforward to specify geometric cell complexes structures modeling n-dimensional digital images at sub-n-xel level. In fact, we are mainly interested in running the designed algorithms for “cellularizations” of digital objects and images, in order to progress in topological acuity and representation within digital image context. Now, we are able to define an algebraic-topological model (or AT-model, for short) (C, ∂, φ, dms) of a geometric cell complex (C, ∂, dms)(see[17]). The homomorphism φ:F[Cq]→F[Cq+1], called integral operator, satisfies the following three conditions: (a) φφ =0;(b)∂φ∂ =∂;(c)φ∂φ =φ. From this data, we can construct an explicit homology equivalence between the chain complex (F[C],∂) and a free chain complex with null differential (which, obviously, is isomorphic to the homology H(C,∂)). The germ idea of the AT-model comes back to the original notion of chain contraction exhaustively used by Samuel Eilenberg and Saunder Mac Lane in their works of homological computation (see, for example, [11]) in the fifties of the twentieth century. 3 AT-Segmentations In this section and with the help of an AT-model (C, ∂, φ, dms), we construct two special partitions of Cinto connected regions from which it is possible to compute “strong” topological relations between homology classes, derived from the elementary relation “to be in the boundary of”. From now on, we work with F=Z2, in order to avoid the use of signs in the AT-model construction. Let us emphasize that all the study done here can be correctly developed for any ground field. Some terminology relative to primal regions of the primal AT-segmentation we want to construct is necessary. The dimension of a primal region Rcomposed by cells of Cof dimension t(0 ≤t≤n−1) and, possibly, of dimension t+1 is dimpr(R)=(t, t + 1). Its criticality number crt(R) is given by the difference between the number of t-cells and (t+ 1)-cells. All the regions of a primal AT- segmentation have criticality number greater or equal to zero. A primal region Rwith crt(R)>0 is called homologically essential.Ifcrt(R) = 0 is called homologically inessential. Algorithm 1uses as input a filtration of the geometric cell complex C.Itis possible to design an algorithm for computing a primal AT-segmentation independent of this restriction. Such algorithm is based on the construction of hierarchical “spanning forests” within the global connectivity graph of Cas ACC. There is no space here to address this question in detail. The reference [37]can be of help in the planning of such algorithm. Figure 1shows a primal AT-segmentation over an ACC version Cell(O)ofa 2D digital object. Fig. 1. (Left) ROI consisting of the set of black pixels. The implicit cellularization of the ROI -using 8-adjacency and being the 0-cells the square physical pixelsis superimposed. (Center) Vectors of cracks involved in the AT-model construction of Algorithm 1 are highlighted. (Right) The associated AT-segmentation of the ROI. There are three regions. Region A is drawn in red and is composed by all the 24 (NA 0) 0-cells and 23 (NA 1) 1-cells (a subdivision of the spanning tree of the 0-cells). Region B is drawn in yellow and is composed by 18 (NB 1) 1-cells and 16 (NB 2) 2-cells. Region C is drawn in green and its tree has one 1-cell and one 2-cell (thus, it is inessential). Regions A and B are homologically essential, due to the fact that crt(R)=NR i−NR i+1 =1>0, for (R, i)={(A, 0),(B,1)}.Infact,Adetects one 0-dimensional homology class and B two 1-dimensional holes. (Color figure online) Let us note that the connectivity graph of regions of the primal AT-segmenta- tion HSpr(C) is not necessarily a tree. For each critical cell edq q,(1≤q≤m) its corresponding primal segmentation region Spr (edq q) of dimension (dq,d q+1) has a criticality number crt(Spr (edq q)) greater than zero. The rest of the primal segmentation regions have a criticality number equal to zero. Algorithm 1. [primal AT-segmentation] Input: A geometric cell complex C:= {C, ∂, dms}.Cis a list with all the cells of Cordered by increasing dimension c0 1,...c 0 1,c 1 1, ..., c 1 2, ...,c n 1,...,c n n. Here, dms(ck j)=k,∀k, j and 1≤q≤nq=. Let us also use the cell ordering ck j=cj+q<k q. The boundary operator ∂|F[c1,...,ci]is denoted by ∂i. 1: H∂ 0←∅;Kφ 0←∅;Jφ 0←∅;Spr 0←∅; 2: for k=0tondo 3: for j=1tokdo 4: i←j+q<k q; 5: φi−1(ci)←0; 6: Ri←{ci}; 7: Spr i←S pr i−1∪{Ri}. Let us denote by Spr i(cq) the region of Spr icontaining the cell cq (1 ≤q≤i). In this way, Spr iis handled as the union 1≤q≤i{Spr i(cq)}. 8: Bndi←{e∈∂i(ci)};Boundary of the current cell 9: ¯ci←ci+φi−1∂i(ci); Potential cycle associated to ci 10: Bndi←{e∈∂i(¯ci)};Algebraic boundary of ¯ci 11:  Bndi←{e∈(1C+∂iφi−1)(c),for some c∈Bndi};Combinatorial boundary of ¯ci 12: Ni←{e∈Bndi:dimpr(Spr i(e)) = (dms(ci)−1,dms(ci)) ∧crt(Spr i(e)) = 0}; Homologically inessential regions in the boundary of ci 13: H∂ i←H∂ i−1{¯ci};Kφ i←K φ i−1{ci};Jφ i←Jφ i−1{ci};Homology generators, combinatorial kernel, critical cells 14: if ∂i(¯ci)==0then Equivalent to Bndi== ∅ 15: for r=1toido 16: φi(cr)←φi−1(cr); 17: else In case in which cidoes not generate a cycle 18: Ji←BndiJφ i 19:  Ji← BndiJφ i 20: Spr i(ci)←S pr i(ci)e∈˜ Ji∪NiSpr i(e); Updating the primal partition 21: for e∈˜ Ji∪N ido 22: Spr i(e)←S pr i(ci); 23: Choose one of the cells e∈ J iUpdating AT-model 24: ˜ φ(e)←ci; 25: ˜ φ(c)←0foreachc∈K φ i−1\{e}; 26: ¯ e←e+φi−1∂i(e); 27: for q=1toi−1do 28: φi(cq)←(φi−1+(idCi−φi−1∂i−1)˜ φ(idCi−∂i−1φi−1))(cq), ∀cq∈Ci 29: H∂ i←H ∂ i\{ ¯ e,¯ci};Updating homology generators 30: Kφ i←K φ i\{e};Updating combinatorial homology kernel 31: Jφ i←Jφ i\{e,c i};Updating set of critical cells 32: Bpr[C](R, R)←#{c∈R:dms(c)=t∧B(R, c)=c∈RB(c, c)=0} ∀R, R∈S pr ,with dimpr(R)=(t−1,t)anddimpr(R)=(t, t +1) (1≤t≤n). Specifying primal AT-segmentation bounding function Output: ·An AT-model (C, ∂,φ ,dms) and a combinatorial basis (set of critical cells) specified by Jφ and ordered by increasing dimension {ed1 1,...,e dm m}(with dms(edq q)=dq,1≤q≤m) for the homology H(C,φ) given by Hφ . ·An abstract cell complex HSpr(C), called primal AT-segmentation of C, whose set of cells is the partition in regions Spr of Cand its bounding function is Bpr[C]. From this output, it is possible to define a dual AT-segmentation HSdl(C) in this simple manner: –[Initial dual AT-partition]. We consider as initial dual AT-partition Sdl a refinement of the primal segmentation partition Spr , in which each critical cell (as sets formed by one element) is considered as a new region of the partition. Let us note that all the regions of Sdl have now zero as criticality number, excepting the sets formed by one critical cell, which have one as criticality number. –[Updating initial dual AT-partition]. For each critical cell edq q∈H φ  (1 ≤q≤m), let us construct the region of the dual segmentation Sdl (edq q)= {edq q}c∈∂(edq q)Spr (c) of dimension dimdl(Sdl (edq q)) = (dq−1,d q). After updating the regions of the partition corresponding to the critical cells, the rest of regions of Sdl remain unaltered. The resulting partition describes at set level the desired dual AT-segmentation and it is denoted by Sdl . Let us emphasize that the ranks (that is, the difference between the number of cells of Cand the number of regions of the partition) of the primal and dual AT- partitions can be different. This is mainly due to the fact that, in general, there is no one-to-one relation between critical cells and regions of the primal or dual AT-segmentations. –[Dimension and Bounding Function]. The dimension of a region R∈S dl , having t-cells and, possibly t−1 cells is dimdl(R)=(t, t −1). Its bounding function is defined by Bdl[C](R, R)=#{c∈R:dms(c)=t∧B(c, R)= c∈RB(c, c)=0}∀R, R∈S dl ,with dimdl(R)=(t, t −1) and dimdl (R)=(t+1,t)(1≤t≤n). At the end of this process, we get a dual AT-segmentation HSdl(C)= (Sdl ,Bdl[C],dim dl). Let us note that the connectivity graph of regions of HSdl(C) is not necessarily a tree. We are now ready to build a second order AT-RIG associated with the primal and dual AT-segmentations. AT-RIGs measure all the relationships between two homology classes of dimension tand t+1, ∀0≤t≤n. Let us write in pseudocode the construction of the second order primal AT-RIG (see Algorithm 2). The construction of the dual one is completely analogous. Finally, the second order AT-RIG G1(AT (C)) is the graph whose nodes are the different homology classes (represented by their corresponding critical cell) and whose edges are those belonging to both primal and dual AT-RIGs. 4 Operations with AT-Segmentations Given a primal (or dual) AT-segmentation, it is possible to create a new one changing only the participation of two cells. This operation is called crack transport and is exhaustively used in the parallel methods for computing homology information designed in [38]. Algorithm 2. [Second order Primal AT-RIG] Input: – an AT-model (C, ∂,φ ,dms) and a combinatorial basis (set of critical cells) ordered by increasing dimension {ed1 1,...,e dm m}(with dms(edq q)=dq,1≤q≤m) for the homology H(C,φ). – a primal AT-segmentation HSpr(C)=(Spr ,Bpr[C],dim pr) 1: for i=1tomdo 2: vi←edi i;the nodes of the RIG are the critical cells 3: N(vi)←∅ The set of all the neighbors of the region of the primal AT-segmentation containing vi 4: Ns(vi)←∅ the set of neighbors of viin the second order AT-RIG 5: for j=1toido 6: if Bpr[C](Spr (vj),Spr (vi)) =0then 7: N(vi)←N(vi)∪{vj}; 8: if Bpr[C](Spr (vj),Spr (vi)) = #{di−cells ∈S pr (vi)}then 9: Ns(vi)←Ns(vi)∪{vj}; 10: Bpr rig[C](vj,v i)←1; 11: else 12: Bpr rig[C](vj,v i)←0 Output: The region-incidence-graph Gpr 1(AT (C)) associated to the abstract cell complex ({ed1 1,...,e dm m},Bpr rig[C],dms). Algorithm 3shows the admissible Crack Transport Algorithm. Crack transports can be used for AT-segmentation parallel computation. Algorithm 3. [Admissible Crack Transport Algorithm]. Let HS(C) be a primal AT-segmentation of a geometric cell complex C.LetR1 and R2be two regions of dimension (k−1,k)and(k, k + 1) respectively, and c∈R 1 and c∈R 2be two k-cells. Let us denote by ˜ HS(C) the segmentation HS \ {c,c}. The new segmentation [c↔c]HS(C) resulting from the initial one, assigning cto R2and cto R1is a new primal AT-segmentation if (a) cis incident to R2,cis incident to R1;(b) there is at least a pair (S1,S 2)ofregionsof ˜ HS(C)withS1⊂R 1 (dimpr(S1)=(k−1,k)) and S2⊂R 2(dimpr(S−2) = (k, k + 1)), satisfying that: –#(S1∩∂c)=1and#(S1∩∂c)=1; –#(S2∩δc)=1and#(S2∩δc)=1; –Bpr[C](S1,S 2)>1. In Fig. 2, an internal (within the ROI) crack transport defined as an admissible interchange of cells between “connected” homological regions of the AT-segmentation of Fig. 1is shown. Another example of application of crack transport is shown in Fig. 3. Fig. 2. (Left) AT-segmentation of Fig. 1. 1-cells involved in the internal crack transport are surrounded by black closed curves; (Right) Result of the crack transport. There are now three 1–2 regions B, B’, C being the first two ones homologically essentials (βB=1=βB). Both AT-segmentations present the same second order AT-RIG: a tree with three hole-nodes (α0,β1,γ1), connecting α0with β1and γ1. Fig. 3. A ROI composed of three segments parallel to the axis (a total of 5 black voxels). Points represent 0-cells (voxels), triangles 1-cells, squares 2-cells and stars 3- cells. Two AT-segmentations of the whole image that embeds the ROI are drawn. The AT-segmentation on the right is the result of several crack transport operations on the AT-segmentation on the left. Obviously, both have the same trivial AT-RIG: a trivial tree composed by one node (0-dimensional homology class of the image) 5 AT-RIG: Homological Tool or Topological Invariant? The proof of homology and homotopy invariance of the AT-RIG is an issue out of the scope of this paper. The first part of this section is employed in supporting the thesis that the AT-RIG notion allows us to discriminate two non homologically equivalent objects having the same Betti numbers. Different instances (configurations spheres with handles, Menger sponges, torus, double torus, etc) are successfully examined with specific AT-segmentations. We only show here the example of AT-segmentations of simple cellular versions of the torus and the sphere with two handles.