On the cohomology of 3D digital images

arXiv:1105.4477v1 [cs.CV] 23 May 2011 On the Cohomology of 3D Digital Images Rocio Gonzalez–Diaz, Pedro Real Depto. de Matem´atica Aplicada I, Escuela Superior de Ingenier´ıa Inform´atica, Universidad de Sevilla, Avda. Reina Mercedes, s/n, 41012, Sevilla (Spain) Abstract We propose a method for computing the cohomology ring of three–dimensional (3D) digital binary–valued pictures. We obtain the cohomology ring of a 3D digital binary–valued picture I, via a simplicial complex K(I) topologically representing (up to isomorphisms of pictures) the picture I. The usefulness of a simplicial description of the “digital” cohomology ring of 3D digital binary– valued pictures is tested by means of a small program visualizing the different steps of the method. Some examples concerning topological thinning, the visualization of representative (co)cycles of (co)homology generators and the computation of the cup product on the cohomology of simple pictures are showed. Keywords: Digital topology, chain complexes, cohomology ring. 1. Introduction The homology groups (given in terms of number of connected components, holes and cavities in the 3D digital picture), the digital Euler characteristic or the digital fundamental group are well–known operations in Digital Topology [16, 11]. All of them can be considered as translations into the discrete setting of classical continuous topological invariants. In order to prove that a digital topology operation πD(associated with a continuous operation πC) correctly reflects the topology of digital pictures considered as Euclidean spaces, the main idea is to associate a “continuous analog” C(I) with the digital picture I. In most cases, each digital picture Iis associated with a polyhedron Email addresses: [email protected] (Rocio Gonzalez–Diaz), [email protected] (Pedro Real) URL: http://www.personal.us.es/rogodi (Rocio Gonzalez–Diaz), http://www.pdipas.us.es/r/real (Pedro Real) Preprint submitted to Elsevier May 24, 2011 C(I) [11, 12, 10, 1]. It is clear that C(I) “fills the gaps” between the black points of Iin a way that strongly depends on the grid and the adjacency relations chosen for the digital picture I. Recent attempts to enrich the list of computable digital topological invariants in such a way can be found in [9]. In this paper, starting from a 3D digital binary–valued picture I, a simplicial complex K(I) associated with Iis constructed, in such a way that an isomorphism of pictures is equivalent to a simplicial homeomorphism of the corresponding simplicial complexes. Therefore, we are able to define the digital cohomology ring of Iwith coefficients in a commutative ring G, as the classical cohomology ring of K(I) with coefficients in G(see [15]). In order to compute this last algebraic object, it is crucial in our method to“connect” the chain complex C(K(I)) canonically associated to K(I) and its homology H(K(I)), via an special chain equivalence [15]: a chain contraction [14]. We will obtain this goal in several steps. Using the technique of simplicial collapses [6], we topologically thin K(I), obtaining a smaller simplicial complex MtopK(I) (with the same homology as K(I)) and a chain contraction connecting their respective chain complexes C(K(I)) and C(MtopK(I)). The following step is the construction of a chain contraction from C(MtopK(I)) to its homology H(MtopK(I)). Having all this information at hand, it is easy to compute the digital cohomology ring of Ifor a given commutative ring G. In this way, cohomology rings are computable topological invariants which can be used for “topologically” classifying (up to isomorphisms of pictures) and distinguishing (up to cohomology ring level) 3D digital binary–valued pictures. A small program for visualizing these cohomology aspects in the case G=Z/Z2 has been designed by the authors and developed by others1. This software allows us to test in some simple examples the potentiality and topological acuity of the method. We deal with digital pictures derived from a tessellation of three–space by truncated octahedra. This is equivalent to using a body–centered–cubic–grid whose grid points are the points (x, y, z)∈Z3in which x≡y≡c(mod 2) (see [13]). The only Voronoi adjacency relation on this grid is 14–adjacency. Using this adjacency, it is straightforward to associate to a digital picture 1The 1st version was programmed by J.M. Berrio, F. Leal and M.M. Maraver [3]; the 2nd version by F.Leal. http://www.us.es/gtocoma/editcup.zip. 2 I, a unique simplicial complex K(I) (up to isomorphisms of pictures) with the same topological information as I. This grid is important in medical imaging applications due to its outstanding topological properties and its higher contents of symmetries. One advantage of the voxels in this grid is that they are more “sphere–like” than the cube, so that the volumetric data represented on this grid need fewer samples that on Cartesian cubic grid [17]. Since the objects considered in this paper are embedded in R3then the homology groups vanishes for dimensions greater than 3 and they are torsion– free for dimensions 0, 1 and 2 (see [2, ch.10]). The qth Betti number is defined as the rank of the qth homology group. In general, the 0th Betti number is the number of connected components, the 1st and 2nd Betti numbers have intuitive interpretations as the number of independent non–bounding loops and the number of independent non–bounding shells. According to the Universal Coefficient Theorem for Homology, the Betti numbers are independent of the group of coefficients (see [15, ch. 7]). Moreover, since the homology groups are torsion–free, the cohomology groups with coefficients in Gare isomorphic to the homology groups with coefficients also in G(see [15, ch. 5]). Therefore, for simplicity we can consider that the ground ring is Z/Z2 throughout the paper. Nevertheless, all the procedure we explain here, is valid for any commutative ring G. The paper is organized as follows. In Section 2, the technique associating a simplicial complex to a 3D digital binary–valued picture is detailed. In Section 3, we explain a procedure for computing the cohomology ring of general simplicial complexes. In Section 4, we introduce the notion of digital cohomology ring of a 3D digital binary–valued picture and we show some examples concerning the visualization of representative (co)cycles of (co)homology generators and the computation of the cup product on the cohomology of simple pictures. Finally, Section 5 is devoted to conclusions and comments. 2. From Digital Images to Simplicial Complexes Digital Images. We follow the terminology given in [12] for representing digital pictures. A 3D digital binary–valued picture space (or, briefly, DPS) is a triple (V, β, ω), where Vis the set of grid points in a 3D grid and each of βand ωis a set of closed straight line segments joining pairs of points of V. The set β(resp. the set ω) determines the neighbourhood relations between black points (resp. white points) in the grid. A 3D digital binary–valued 3 Figure 1: The 14–neighbours of a grid point pof the BCC grid. picture is a quadruple I= (V, β, ω, B),where (V, β, ω) is a DPS and B(the set of black points) is a finite subset of V. An isomorphism of a DPS (V1, β1, ω1) to a DPS (V2, β2, ω2) is a homeomorphism hof the Euclidean 3–space to itself such that hmaps V1onto V2, each β1-adjacency onto a β2-adjacency and each ω1-adjacency onto an ω2- adjacency, and h−1maps each β2-adjacency onto a β1-adjacency and each ω2adjacency onto an ω1-adjacency. An isomorphism of a picture I1= (V1, β1, ω1, B1) to a picture I2= (V2, β2, ω2, B2) is an isomorphism of the DPS (V1, β1, ω1) to the DPS (V2, β2, ω2) that maps B1onto B2. The DPS used in this paper, is the 3D body–centered cubic grid (BCC grid) [12]: The grid points Vare the points (a, b, c)∈Z3such that a≡b≡c (mod 2). The 14–neighbours of a grid point pwith coordinates (a, b, c) are: (a±2, b, c), (a, b ±2, c), (a, b, c ±2), (a±1, b ±1, c ±1). Simplicial Complexes. The four types of non–empty simplices in R3are: a 0–simplex which is a vertex, a 1–simplex which is an edge, a 2–simplex which is a triangle and a 3–simplex which is a tetrahedron. In general, considering an ordering on a vertex set V, a q–simplex with q+ 1 affinely independent vertices v0<··· < vqof Vis the convex hull of these points, denoted by hv0,...,vqi. If i < q, an i–face of σis an i–simplex whose vertices are in the set {v0,...,vq}. A facet of σis a (q−1)–face of it. A simplex is shared if it is a face of more than one simplex. Otherwise, the simplex is free if it belongs to one higher dimensional simplex, and maximal if it does not belong to any. 4 Asimplicial complex Kis a collection of simplices such that every face of a simplex of Kis in Kand the intersection of any two simplices of Kis a face of each of them or empty. The set of all the q–simplices of Kis denoted by K(q). A subset K′⊆Kis a subcomplex of Kif it is a simplicial complex itself. Let Kand Lbe simplicial complexes and let |K|and |L|be the subsets of Rdthat are the union of simplices of Kand L, respectively. Let f:K(0) → L(0) be a map such that whenever the vertices v0,...,vnof Kspan a simplex of K, the points f(v0),...,f(vn) are vertices of a simplex of L. Then fcan be extended to a continuous map g:|K| → |L|such that if x=Ptivithen g(x) = Ptif(vi). The map gis called a simplicial homeomorphism if fis bijective and the points f(v0),...,f(vn) always span a simplex of L. Simplicial Representations. Given a 3D digital binary–valued picture I= (V,14,14, B) on the BCC grid, there is a process to uniquely associate a 3–dimensional simplicial complex K(I). This simplicial complex is constructed on the triangulation of the Euclidean 3–space determined by the previous 14–neighbourhood relation. The simplicial representation K(I) of the digital picture Iis described as follows: consider the lexicographical ordering on V(if v= (a, b, c) and w= (x, y, z) are two points of V, then v < w if a < x, or a=xand b < y, or a=x,b=yand c < z). The vertices (or 0–simplices) of K(I) are the points of I. The i–simplices of K(I) (i∈ {1,2,3}) are constituted by the different sorted sets of i14–neighbour black points of I(analogously, we could construct another simplicial complex whose i–simplices are the different sets of i14–neighbour white points of I). Example 2.1. Consider the digital picture J= (V,14,14, B)where Bis the set {v0= (−1,−1,1), v1= (−1,1,1), v2= (0,0,0), v3= (0,0,2), v4= (0,2,0)};then K(J)is the simplicial complex with set of maximal simplices {hv0, v1, v2, v3i,hv1, v2, v4i} (see Figure 2). In the next section, we give a satisfactory algorithmic solution to the problem of the computation of the cohomology ring of finite simplicial complexes. This positive solution together with the naive simplicial construction described above will allow us to “cohomologically control” 3D digital binary– valued pictures (up to isomorphisms of pictures), since the following result holds. Theorem 2.2. Two digital binary–valued pictures, I1= (V,14,14, B1)and 5 Figure 2: On the left, the black points of the digital picture Jand, on the right, the simplicial representation K(J). I2= (V,14,14, B2), are isomorphic if and only if their simplicial representations K(I1)and K(I2)are simplicially homeomorphic. The proof of this theorem is straightforward and left to the reader. 3. Computing the Cohomology Ring of Simplicial Complexes First of all, we briefly explain the main concepts from Algebraic Topology we use in this paper. Our terminology follows Munkres book [15]. In the next subsections, we reinterpret classical methods in Algebraic Topology in terms of chain contractions [14] that will enable us to design an algorithm for computing the cohomology ring of general simplicial complexes. Chains and Homology. Let Kbe a simplicial complex. A q–chain ais a formal sum of simplices of K(q). Since the group of coefficient is Z/Z2, aq–chain can be seen as a subset of q–simplices of K; the sum of two q– chains cand dis the symmetric difference of the two sets c∪dand c∩d. The q–chains form a group with respect to the component–wise addition mod 2; this group is the qth chain group of K, denoted by Cq(K). There is a chain group for every integer q≥0, but for a complex in R3, only the ones for 0 ≤q≤3 may be non–trivial. The boundary of a q–simplex σ=hv0,...,vqiis the collection of all its facets which is a (q−1)–chain: ∂q(σ) = Pq i=0hv0, . . . , ˆvi,...,vqi, where the hat means that viis omitted. By linearity, the boundary operator ∂qcan be extended to q–chains. The collection of boundary operators connect the chain groups Cq(K) into the chain complex C(K): ··· ∂4 →C3(K)∂3 →C2(K)∂2 →C1(K)∂1 →C0(K)∂0 →0. Aq–chain a∈Cq(K) is called a q–cycle if ∂q(a) = 0. If a=∂q+1(a′) for some a′∈Cq+1(K) then ais called a q–boundary. We denote the groups of q–cycles and q–boundaries by Zqand Bqrespectively. An essential property 6 of the boundary operators is that the boundary of every boundary is empty, ∂q∂q+1 = 0. This implies that Bq⊆Zqfor q≥0. Define the qth homology group to be the quotient group Zq/Bq, denoted by Hq(K). Given a∈Zq, the coset a+Bqis the homology class of Hq(K) determined by a. We denote this class by [a]. For a complex Kin R3, only Hq(K) for 0 ≤q≤2 may be non–trivial. Cochains and Cohomology. With each simplicial complex K, we have associated a sequence of abelian groups called its homology groups. Now, we associate with Kanother sequence of abelian groups called its cohomology groups. They are geometrically much less natural than the homology groups. Their origins lie in algebra rather than in geometry; in a certain algebraic sense, they are “dual” to the homology groups. Let Kbe a simplicial complex. The group of q–cochains of Kwith coefficients in Z/Z2 is the group Cq(K) = {c:Cq(K)→Z/Z2 such that cis a homomorphism}. Observe that a q–cochain ccan be defined on the q–simplices of Kand it is naturally extended to Cq(K). Therefore, a q–cochain can be expressed as a formal sum of elementary cochains σ∗:Cq(K)→Z/Z2 whose value is 1 on the q–simplex σ∈Kand 0 on all other q–simplices of K. The boundary operator ∂q+1 on Cq+1(K) induces the coboundary operator δq:Cq(K)→Cq+1(K) via δq(c) = c∂q+1, so that δqraises dimension by one. The collection of coboundary operators connect the cochain groups Cq(K) into the cochain complex C∗(K): C0(K)δ0 →C1(K)δ1 →C2(K)δ2 →C3(K)δ3 → · · · .We define Zq(K) to be the kernel of δqand Bq+1(K) to be its image. These groups are called the group of q–cocycles and q–coboundaries, respectively. Noting that δ2 q= 0 because ∂2 q= 0, define the qth cohomology group,Hq(K) = Zq(K)/Bq(K) for q≥0. The cochain complex C∗(K) is an algebra with the cup product ⌣:Cp(K)× Cq(K)→Cp+q(K) given by: (c ⌣ c′)(σ) = c(hv0,...,vpi)•c′(hvp,...,vp+qi) where σ=hv0, . . . , vp+qiis a (p+q)–simplex and •is the natural product defined on Z/Z2 [15, p. 292]. It induces an operation ⌣:Hp(K)×Hq(K)→ Hp+q(K), via [c]⌣[c′] = [c ⌣ c′], that is bilinear, associative, commutative (up to a sign if the ground ring is not Z/Z2), independent of the ordering of the vertices of Kand topological invariant (more concretely, homotopy–type invariant) [15, p. 289], since the coboundary formula δp+q(c ⌣ c′) = δp(c)⌣ c′+c ⌣ δq(c′) holds for any c∈Cp(K) and c′∈Cq(K). 7 Figure 3: A triangulation of a torus. Figure 4: On the left, the 1–cycles aand b, and on the right, the 1–cocycles cand d. Example 3.1. Consider the complex Kpictured in Figure 3 which is obtained from a triangulation of a torus. It is easy to check that the two 1–chains a=h3,7i+h7,9i+h3,9iand b=h3,7i+h6,7i+h6,8i+h8,9i+h3,9i(see Figure 4) are 1–cycles. For example, ∂1(a) = h3i+h7i+h7i+h9i+h3i+h9i= 0. Moreover, aand bare homologous: ∂2(h6,7,8i+h7,8,9i) = a+b. On the other hand, c= h2,3i∗+h3,6i∗+h6,7i∗+h7,8i∗+h8,9i∗+h2,9i∗and d=h4,5i∗+h5,6i∗+ h6,8i∗+h7,8i∗+h7,9i∗+h4,9i∗are two 1–cocycles. To check this, we have to verify that δ1(c)and δ1(d)vanishes on all the 2–simplices of K. For example δ1(c)(h2,3,6i) = c(∂2(h2,3,6i)) = c(h2,3i) + c(h2,6i) + c(h3,6i) = 0. To check that both 1–cocycles are not coboundaries is a more difficult task since we have to verify that δ2(f)6=c, d for any fbeing a 2–cochain. The cup product of cand dis a new 2–cocycle c ⌣ d. By direct computation, we have that c ⌣ d =h6,7,8i∗. We obtain this by applying it on all the 2–simplices of K. For example, (c ⌣ d)(h6,7,8i) = c(h6,7i)•d(h7,8i) = 1 and (c ⌣ d)(h7,8,9i) = c(h7,8i)•d(h8,9i) = 0. The example illustrates that while we can think of a 1–cycle as being a closed curve, the best way to think of a 1–cocycle is a picket fence. Chain Contractions. In a more general framework, a chain complex Cis a sequence ··· ∂4 −→ C3 ∂3 −→ C2 ∂2 −→ C1 ∂1 −→ C0 ∂0 −→ 0 of abelian groups Cq and homomorphisms ∂q, indexed with the non–negative integers, such that 8 for all q,∂q∂q+1 = 0 .The qth homology group is the quotient group Ker ∂q/Im ∂q+1, denoted by Hq(C). Let C={Cq, ∂q}and C′={C′ q, ∂′ q}be two chain complexes. A chain map f:C → C′is a family of homomorphisms {fq:Cq→C′ q}q≥0such that ∂′ qfq=fq−1∂q.A chain map f:C → C′induces a homomorphism f∗:H(C)→H(C′). Let us emphasize that a fundamental notion here is that of chain contraction. Definition 3.1. [14] A chain contraction of a chain complex Cto another chain complex C′is a set of three homomorphisms (f, g, φ)such that: •f:C → C′and g:C′→ C are chain maps. •fg is the identity map of C′. •φ:C → C is a chain homotopy of the identity map idCof Cto gf, that is, φ∂ +∂φ =idC+gf. Important properties of chain contractions are: • C′has fewer or the same number of generators than C. • C and C′have isomorphic homology groups [15, p. 73]. Let us recall that the key of our method for computing the cohomology ring of chain complexes, is the construction of chain contractions (f, g, φ) of a given chain complex Cto another chain complex H(isomorphic to the homology of C). In this case, for each cycle a∈ C, the chain f(a)∈ H determines the homology class of a. Conversely, for each α∈ H (which corresponds to a homology class of H(C)), g(a)∈ C determines a representative cycle of it. Finally, if a∈ C is a boundary, then a′=φ(a) is a chain in C such that ∂(a′) = a. 3.1. Topological Thinning Topological thinning is an important preprocessing operation in Image Processing. The aim is to shrink a digital picture to a smaller, simpler picture which retains a lot of the significant information of the original.Then, further processing or analysis can be performed on the shrunken picture. There is a well–known process for thinning a simplicial complex using simplicial collapses [4]. Suppose Kis a simplicial complex, σ∈Kis a 9 algorithm for computing the cohomology ring of Kwill run in time at most O(m6) if Khas msimplices. Let us note that the cohomology ring of Kis not suitable in general for topological classification tasks. This is due to the fact that determining whether two rings are isomorphic or not by means of their respective multiplication tables is an extremely difficult computational question. In order to avoid this problem, we will put the information of the cup product table into a different form. If we restrict our interest in simplicial complexes are embedded in R3, observe that the possible non–trivial cup products are the ones α ⌣ β where both αand βare elements of hcorresponding to cohomology classes of dimension 1. In order to design a new algorithm for computing the cup product in a way that we can determine whether two cohomology rings are isomorphic or not by means of their respective multiplication tables, we need to define a new concept. Given a chain contraction (f, g, φ) of C(K) to a chain complex H (isomorphic to H∗(K)) with set of generators h, and a simplex σ=hv0, v1, v2i of dimension 2, suppose that {α1,...,αp}is the set of elements of hof dimension 1, f(hv0, v1i) = Pi∈Iαiand f(hv1, v2i) = Pj∈Jαjwhere Iand Jare subsets of the set {1,2,...,p}. Define (f⊙f)(σ) = Pi∈IPj∈J(αi, αj). This definition can be extended to 2–chains by linearity. Algorithm 3.7. Cup Product Algorithm Input: A simplicial complex K and a chain contraction (f, g, φ)of C(K) to a chain complex H(isomorphic to H∗(K)) with set of generators h. Initially, q:= the number of elements of hof dimension 2, bi:= 0 for 1≤i≤qand M:= ( ). For i= 1 to i=qdo bi:= (f⊙f)g(αi). End for. M:= (b1,...,bq). Output: The sorted set M. Let {α1,...,αp}be the set of elements of hof dimension 1 and {β1,...,βq} the ones of dimension 2. Each bi, 1 ≤i≤q, is of the form Pλi jk(αj, αk) where the sum is taken over the set {(j, k) : 1 ≤j, k ≤p}and λi j,k = (α∗ jf ⌣ 16 α∗ kf)g(βi) could be 0 or 1. Since the cup product is commutative, we have that λi jk =λi kj. Therefore, the output of this algorithm can be put into a matrix form Mof (cohomology classes βi, 1 ≤i≤q)×(pairs of cohomology clases (αj, αk), 1 ≤j≤k≤p). The column of Mcorresponding to the pair (αj, αk), 1 ≤j≤k≤p, gives the value of the cup product αj⌣ αk. This algorithm for computing the matrix Mruns in time at most O(m4) if Khas msimplices. From the diagonalization Dof the matrix M, a first cohomology invariant HB1(K) for distinguishing non–homeomorphic simplicial complexes with isomorphic (co)homology groups appears. We define this cohomology number in order to have a handy numerical tool for distinguishing 3D digital pictures. Definition 3.2. Given a simplicial complex K, the integer HB1(K)is a cohomology invariant defined as the rank of the matrix M. 4. A First Approach to the Digital Cohomology Ring Since an isomorphism of pictures on the 3D body centered cubic grid is equivalent to a simplicial homeomorphism of the corresponding simplicial representations, we are able to define the digital cohomology ring of Iwith coefficients in Z/Z2 as the cohomology ring of K(I) with coefficients in Z/Z2. Moreover, the following definitions hold: Definition 4.1. Given a digital picture I= (V,14,14, B), the digital cohomology ring of Iwith coefficients in Z/Z2is defined as the cohomology ring of K(I)with coefficients in Z/Z2. The cohomology invariant HB1(I) is defined as HB1(K(I)). In the previous sections, we have showed that it is possible to compute the digital cohomology ring of Iwith coefficients in Z/Z2. The steps of the method are: first, we construct the simplicial complex K(I). Second, we topologically thin K(I), obtaining a smaller simplicial complex MtopK(I) and a chain contraction (ftop, gtop, φtop) of C(K(I)) to C(MtopK(I)). Third, we compute Hwhich is isomorphic to H(I) and a chain contraction (falg, galg, φalg) of C(MtopK(I)) to H. Four, we calculate the cohomology ring of Ivia the cohomology ring of MtopK(I) and the invariant HB1(I) via HB1(MtopK(I)), using the chain contractions constructed before. All the information obtained in this way is useful for topologically classifying and distinguishing binary 3D digital pictures. 17 4.1. Some Examples In order to show examples of the computation and visualization of the cohomology ring of simple pictures, we expose a small prototype called EditCup. We use a free program for building 3D worlds. In our case, a world is a particular 3D simplicial complex Krepresenting a digital picture Iconsidering the 14–adjacency. A way for distinguishing the different maximal simplices of a simplicial representation is by using different colours: red for tetrahedra, green for triangles, blue for edges, and black for vertices. All the computations are done considering Z/Z2 as the ground ring. For visualizing (co)chains, the simplices on which a given (co)chain is non–null, are lighted in a different color. On the other hand, the “visualization” of any (co)homology class on Kis given by lighting the simplices of Kon which the representative cochain of this class is non–null. Moreover, the “visualization” of any (co)homology class on the original 3D digital binary–valued picture I could be given by lighting the points of Isuch that the corresponding vertices span simplices on which the representative cochain of this class is non–null. The DPS used in these examples, that we call (14,14)–DPS, is (Z3,14,14), in which the underlying grid is the set of points with integer coordinates in the Euclidean 3–space E3and the 14–neighbours of a grid point (black or white) with integer coordinates (x, y, z) are: (x±1, y, z), (x, y ±1, z), (x, y, z ±1), (x+1, y −1, z), (x−1, y + 1, z), (x+1, y, z −1), (x−1, y, z +1), (x, y + 1, z −1), (x, y −1, z + 1), (x+ 1, y + 1, z −1), (x−1, y −1, z + 1) (see Figure 7). The (14,14)–DPS and the BCC grid are isomorphic DPSs: each grid point (x, y, z) of the (14,14)–DPS can be associated to a point (a, b, c) via the formula: (a, b, c) = (x+y−2z, −x+y, −x−y)). Let us consider now the following pictures: a torus I= (Z3,14,14, BI) and a wedge of two topological circles and a topological 2–sphere J= (Z3,14,14, BJ) (see Figure 8). In the volumetric representation of the picture I(resp. J), we use voxels with centres the points BI(resp. BJ). It is clear that the (co)homology groups of Iare isomorphic to those of J. They are Z/Z2, Z/Z2⊕Z/Z2 and Z/Z2 of dimension 0, 1 and 2, respectively. So, the (co)homology information is not enough for topological distinguishing both pictures. Let K(I) and K(J) be the simplicial representations of Iand Jrespectively (see Figure 9). In order to compare the cohomology ring of both pictures, the first step is the computation of chain contractions (fI, gI, φI) of C(K(I)) to HIand (fJ, gJ, φJ) of C(K(J)) to HJusing the topological 18 Figure 7: The 14–neighbours of a grid point pof the (14,14)–DPS. Figure 8: The volumetric representation of the pictures I(on the left) and J(on the right). and algebraic thinning algorithms explained before, where HI(resp. HJ) is a chain complex isomorphic to the (co)homology of I(resp. J). Let us denote by α1and α2(resp. α′ 1and α′ 2) the generators of HI (resp. HJ) of dimension 1 and α3(resp. α′ 3) the generator of HI(resp. HJ) of dimension 2. Let us also denote by aithe representative cycles of the generators of H(I) (that is, ai=gI(αi)); and by a′ ithe same of H(J). We visualize these cycles on K(I) and K(J) in Figure 10. In Figure 11, the representative cocycles bi(resp. b′ i) obtained via the formula bi=α∗ ifI(resp. b′ i=α′∗ ifJ) of the generators of H∗(I) (resp. H∗(J)) are shown. Recall that we do it by lighting the simplices on which the cochains is non–null. The output of Algorithm 3.7 for HIand HJare MI= ((α1, α2)+(α2, α1)) and MJ= (0), respectively. The matrices corresponding to the cohomology rings of the pictures Iand Jare: 19 Figure 9: The simplicial complexes K(I) (on the left) and K(J) (on the right). Figure 10: The cycles a1,a2and a′ 1,a′ 2(in yellow); and a3and a′ 3(in green). Figure 11: The cocycles b1,b2and b′ 1,b′ 2(in yellow); and b3and b′ 3(in green). I(α1, α1) (α1, α2) (α2, α2) α3010 J(α′ 1, α′ 1) (α′ 1, α′ 2) (α′ 2, α′ 2) α′ 3000 Therefore, HB1(I) = 1 and HB1(J) = 0. We conclude that K(I) and K(J) are not homeomorphic (more precisely, we conclude that they are not homotopy equivalent), then Iand Jare not isomorphic. Let us expose another example (see Figure 12): the picture Ais a wedge of two torus; the picture Bconsists in a wedge of a sphere and a genus–2 torus 20 Figure 12: The pictures A(on the left) and B(on the right). Figure 13: The simplicial complexes K(A) (on the left) and K(B) (on the right). (a sphere with two handles and two holes). Both pictures have 1 connected component, 4 holes and 2 cavities. The simplicial representations of Aand B,K(A) and K(B) are showed in Figure 13. In Figure 14 (resp. Figure 15), the representative cycles and cocycles of the generators of the (co)homology of A(resp. B) are showed. Let us denote by αi(resp. α′ i), i= 1,2,3,4, the generators of HA(resp. HB) of dimension 1; and by βi(resp. β′ i), i= 1,2, the generators of HA(resp. HB) of dimension 2. All of them are obtained using the algebraic thinning algorithm explained in the previous section. The output of Algorithm 3.7 for HAand HBis MA= ((α1, α2)+(α1, α3)+(α2, α1)+(α3, α1),(α3, α4)+(α4, α3)) and MB= (0,(α1α4)+(α2, α3)+(α3, α2)+(α4, α1)) .Therefore, the matrices corresponding to the cohomology rings of Aand Bare: A(1,1) (1,2) (1,3) (1,4) (2,2) (2,3) (2,4) (3,3) (3,4) (4,4) β10 1 1 0 0 0 0 0 0 0 β20 0 0 0 0 0 0 0 1 0 21 Figure 14: On the left (resp. on the right), the representative cycles (resp. cocycles) of the generators of H(A) (resp. of H∗(A)). Figure 15: On the left (resp. on the right), the representative cycles (resp. cocycles) of the generators of H(B) (resp. of H∗(B)). B(1,1) (1,2) (1,3) (1,4) (2,2) (2,3) (2,4) (3,3) (3,4) (4,4) β′ 10 0 0 0 0 0 0 0 0 0 β′ 20 0 0 1 0 1 0 0 0 0 where (i, j) represents the pair (αi, αj) (resp. (α′ i, α′ j)). We conclude that HB1(A) = 2 and HB1(B) = 1, and then K(A) and K(B) are not homeomorphic (more precisely, we conclude that they are not homotopy equivalent), therefore Aand Bare not isomorphic. 5. Conclusions and Future Work We have seen that there is a true algorithm for computing the digital cohomology ring (with coefficients in Z/Z2) of a 3D binary picture on the BCC grid. It is also possible to compute the digital cohomology ring of Iwith coefficients in any commutative ring G, thanks to the fact the simplicial complex 22 K(I) is embedded in R3and, consequently, it have torsion–free homology. We deal here with Z/Z2 coefficients, in order to simplify and avoiding signs in the explanation of our algorithmic formulation, to give an easy geometric interpretation of ”digital” cohomology classes and to work with binary arithmetic. Moreover, there is no problem to define the cohomology ring of Iwith coefficients in a commutative ring Gas the cohomology ring of K(I) with coefficients in G; and the cohomology invariant HB1(I;G) with coefficients in Gas HB1(K(I); G). On the other hand, since HB1(K(I); G) can be obtained from the first homology group of the reduced bar construction ¯ B(C∗(K(I); G)) [14] associated to the cochain complex C∗(K(I); G) with coefficients in G, we will confine ourselves to say that the rest of homology groups of this last algebraic object give rise to more complicated cohomology invariants for a digital binary–valued picture. In this paper, we talk about topological and algebraic thinning. Concerning the first one, we do not use here well–known direct (without passing to simplicial framework) topological thinnings of digital binary–valued pictures because we are interested in constructing chain contractions which allow us to obtain cohomology results. Concerning the second one, the idea of computing a chain contraction of a chain complex to its homology has also been used in [7] for computing primary and secondary cohomology operations. Another important question is to try to improve the complexity of the algorithm computing digital cohomology ring on the BCC grid detailed in this paper. We do not take advantage here neither of the particular simplicial structure of the simplicial complex K(I) (determined by the BCC grid) associated to I, nor of representing in a compressed form (without loss of information) the 3D digital picture (for example, in an octree format). To obtain positive results in these directions and to eliminate from our algorithm the intermediary simplicial objects will allow us to specify a more refined algorithm computing digital cohomology on the BCC grid. Finally, another important question that it is necessary to deal with in a near future is to try to generalize this work to other natural digital picture spaces. References [1] Ayala R., Dom´ınguez E., Franc´es A.R., Quintero A.: Homotopy in Digital Spaces. DGCI 2000. LNCS, Springer–Verlag 1953 (2000) 3–14 [2] Alexandroff P., Hopf H.: Topologie I. Springer, Berlin 1935 23 [3] Berrio J.M., Gonz´alez–D´ıaz R., Leal F., L´opez M.M., Real P.: Visualizing Cohomology Aspects of 3D Objects. Proc. of the 6th Asian Tech. Conf. in Math. (2001) 459–468 [4] Bj¨orner A.: Topological Methods. Handbook on Combinatorics. Elsevier Sci. 2(1995) 1819–1872 24 [5] Delfinado C.J.A., Edelsbrunner H.: An Incremental Algorithm for Betti Numbers of Simplicial Complexes on the 3–Sphere. Comput. Aided Geom. Design 12 (1995) 771–784 [6] Forman R.: Combinatorial Differential Topology and Geometry. New Perspective in Geom. Combinatorics. MSRI Public. 8(1999) 177–206 [7] Gonz´alez–D´ıaz R., Real P.: Computation of Cohomology Operations on Finite Simplicial Complexes. Homology, Homotopy and Applications 5 (2) (2003) 83–93 [8] Gonz´alez–D´ıaz R., Real P.: Towards Digital Cohomology. DGCI 2003, LNCS, Springer 2886 (2003) 92–101 [9] Kenmochi Y., Imiya A.: Polyhedral Set Operations for 3D Discrete Object Deformation. Scale–Space 2001, LNCS, Springer–Verlag and IEEE/CS 2106 (2001) 417–425 [10] Khalimsky E.D., Kopperman R.D., Meyer P.R.: Computer Graphics and Connected Topologies on Finite Ordered Sets. Topology and Appl. 36 (1990) 1–17 [11] Kong T.Y.: A Digital Fundamental Group. Computer Graphics 13 (1989) 159–166 [12] Kong T.Y., Roscoe A.W., Rosenfeld A.: Concepts of Digital Topology. Topology and its Applications 46 (1992) 219–262 [13] Kovalevsky V.A.: Discrete Topology and Contour Definition. Pattern Recognition Letter 2(1984) 281–288 [14] MacLane S.: Homology. Classic in Math., Springer–Verlag 1995 [15] Munkres J.R.: Elements of Algebraic Topology. Addison–Wesley Co. 1984 [16] Rosenfeld A.: 3D Digital Topology. Inform. and Control 50 (1981) 119– 127 [17] Theussl T., Moller T., Groller M.E.: Optimal Regular Volume Sampling. Proc. IEEE Conference on Visualization (2001). 25