Algebraic topological analysis of time-sequence of digital images

Algebraic Topological Analysis of Time-Sequence of Digital Images Rocio Gonzalez–Diaz, Belen Medrano,PedroReal, and Javier S´anchez–Pel´aez Depto. Matematica Aplicada I, E.T.S.I. Informatica, Universidad de Sevilla, Avda. Reina Mercedes, s/n 41012 Sevilla, Spain {rogodi, belenmg, real}@us.es http://www.us.es/gtocoma Abstract. This paper introduces an algebraic framework for a topological analysis of time-varying 2Ddigital binary–valued images, each of them defined as 2D arrays of pixels. Our answer is based on an algebraictopological coding, called AT–model, for a nD (n=2,3) digital binaryvalued image Iconsisting simply in taking Itogether with an algebraic object depending on it. Considering AT–models for all the 2D digital images in a time sequence, it is possible to get an AT–model for the 3D digital image consisting in concatenating the successive 2D digital images in the sequence. If the frames are represented in a quadtree format, a similar positive result can be derived. 1 Introduction In [6,7], a method for computing cohomology aspects of three–dimensional digital binary-valued images is described. That work is mainly based on two facts: (1)to consider a simplicial model K(I) for a digital image Iusinga(14,14)–adjacency relation between voxels; and (2)to apply an “algebraic homological process” in which an algebraic artifact c(a special type of chain homotopy equivalence [11]) connecting the chain complex canonically associated to the simplicial version of the digital image with its homology is constructed. An AT -model (algebraictopological model) for the 3Ddigital image Iis the couple (I,c). Roughly speaking, an AT-model is an extra algebraic-topological information of the image. This particular description for digital images used there for solving a problem of topological interrogation, is used in this paper for solving a problem of topological analysis. We are interested here in understanding the topological nature of a time-sequence of 2Ddigital binary-valued images. There are two ways for handling this question: (1) [the intraframe approach] to determine the ”topology” of each frame and to try to adequately join these pieces in order to give a correct three–dimensional topological interpretation, or (2) [the 3Dapproach] to This work has been partially supported by the PAICYT research project FQM–296 from Junta de Andalucia.  Fellow associated to University of Seville under a Junta de Andalucia research grant. V.G. Ganzha, E.W. Mayr, and E.V. Vorozhtsov (Eds.): CASC 2005, LNCS 3718, pp. 208–219, 2005. c Springer-Verlag Berlin Heidelberg 2005 Algebraic Topological Analysis of Time-Sequence of Digital Images 209 directly obtain the topological information from the 3Dimage consisting in concatenating the successive 2Dimages of the sequence. Using AT-models, we will see here that both strategies lead us to the same result. This is also valid in the case in which the 2D-images are represented under a quadtree format. To extend these positive results to time-sequences of 3Ddigital binary–valued images is an extremely interesting challenge which seems to be affordable. 2 Digital Images and Simplicial Representations In this paper, a nD (n=2,3) digital binary-valued image is a nD array of elements (pixels in 2D,voxelsin3D) whose positions are represented by integer coordinates and whose values can only be 1 (black) or 0 (white). Given a pixel (x1,x 2), its 6-adjacent pixels are (x1−1,x 2),(x1+1,x 2),(x1,x 2+1),(x1+1,x 2+ 1),(x1,x 2−1),(x1−1,x 2−1). It is immediate to define another 6-connectivity if we favour the direction 135ofor determining adjacent pixels instead of 45o. The 6-connectivity in 2Ddigital images satisfies the Jordan curve property. This ensures that a black simple closed curve (that is, a set of black pixels C such that each pixel in Chave exactly two 6-neighbours in C) will separate the background into two non-6-adjacent white regions, the interior and the exterior. Given a voxel (x1,x 2,x 3), its 14-neighbour voxels are showed in Figure 1. It is possible to define other types of 14-adjacency, favouring other directions. The 14-adjacency in 3Ddefined by the neighbour relations given in Figure 1, is an appropriate generalization of the 6-adjacency in 2D previously defined. In [7], the 14-adjacency relation is used in order to be able to naturally associate a three-dimensional simplicial complex K(I)toany3Ddigital binary– valued image I.K(I) is called a simplicial representation of Iandisdefinedasa subcomplex of the infinite simplicial complex Kobtained by the decomposition of the 3D euclidean space into unit cubes (which vertices are the points (a, b, c)∈ Z3), and the decomposition of each cube into six tetrahedra as shown in Figure 2 (the six tetrahedra are: 1,3,4,8,1,2,4,8,1,2,6,8,1,3,7,8,1,5,7,8, 1,5,6,8.) Two digital images, I1and I2, are isomorphic if and only if their simplicial representations K(I1)andK(I2) are homeomorphic. In order to give a formal definition of simplicial representation, we need to give some preliminaries. Our terminology follows [12]. Considering an ordered Fig. 1. The 14–neighbours of a voxel p(on the left) and the decomposition of a unit cube into six tetrahedra (on the right) 210 R. Gonzalez–Diaz et al. Fig. 2. A digital binary image and its simplicial representation using 14-adjacency relation between voxels vertex set V,aq–simplex with q+ 1 affinely independent vertices v0<···<v q of Vis the convex hull of these points, denoted by v0,...,v q.Ifi<q,an i–face of σis an i–simplex whose vertices are in the set {v0,...,v q}.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). Let Kand Lbe simplicial complexes and let |K|and |L|be the subsets of Rdthat are the union of simplices of Kand L, that is, the geometric realizations of Kand L, respectively. We say that Kand Lare homotopic if its respective geometric realization are homotopy equivalents. It is known that if two spaces are homeomorphic then they are homotopy equivalent. Given a nD (n=2,3) digital binary–valued image Iand considering the lexicographical ordering on Z3,asimplicial representation K(I)ofIis the simplicial complex described as follows: the i–simplices of K(I)(i∈{0,1,2,3})are constituted by the different sorted sets of (i+ 1) 14–neighbour black voxels of I. Moreover, let Ibe a 2Ddigital binary–valued image embedded in the 3D digital space. The simplicial representation K(I)ofIis the two-dimensional simplicial complex whose i–simplices (i∈{0,1,2}) are constituted by the different sorted sets of (i+ 1) 6–neighbour black pixels of I. 3 An AT-Model for a Digital Image In this section we briefly recall the notion of AT-model for digital images given in [6,7]. For explain it, we first define the concept of chain contraction that is an exotic notion in the field of Digital Topology but it is a common resource in Algebraic Topology (see, for example, [11]). Since the objects considered in this paper are embedded in R3then the homology groups vanish for dimensions greater than 3 and they are torsion– free for dimensions 0, 1 and 2 (see [1–ch.10]). 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. Algebraic Topological Analysis of Time-Sequence of Digital Images 211 Fig. 3. Two 2Dimages embedded in the 3Ddigital space and its respective simplicial representations Let Kbe a simplicial complex. A q–chain ais a formal sum of simplices of K(q).Wedenoteσ∈aif σ∈K(q)is a summand of a.Theq–chains form a group with respect to the component–wise addition; 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 acomplexinR3, only the ones for 0 ≤q≤3 may be non–trivial. The boundary of a q–simplex σ=v0,...,v qis the collection of all its (q−1)–faces which is a(q−1)–chain: ∂q(σ)=v0,...,ˆvi,...,v q, 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)intothe chain complex C(K) canonically associated to K:··· ∂2 →C1(K)∂1 →C0(K)∂0 →0. In a more general framework, a chain complex Cis a sequence ··· d2 −→ C1 d1 −→ C0 d0 −→ 0 of abelian groups Cqand homomorphisms dq, indexed with the non– negative integers, such that for all q,dqdq+1 =0.Achaina∈Cqis called aq–cycle if dq(a)=0.Ifa=dq+1(a)forsomea∈Cq+1 then ais called a q–boundary. Define the qth homology group to be the quotient group of q–cycles and q–boundaries, denoted by Hq(C). Let C={Cq,d q}and C={C q,d  q}be two chain complexes. A chain map f:C→C is a family of homomorphisms {fq:Cq→C q}q≥0such that d qfq=fq−1dq. Definition 1. [11] A chain contraction of a chain complex Cto another chain complex Cis a set of three homomorphisms c=(f,g,φ)such that: (i) f:C→C  (called projection) and g:C→C(called inclusion) are chain maps. (ii) fg is the identity map of C. (iii) φ:C→Cis a chain homotopy of degree +1 of the identity map idCof Cto gf, that is, idC+gf =φd+dφ,wheredis the boundary operator of C. Important properties of chain contractions are: (a) Chas fewer or the same number of generators than C;(b)Cand Chave isomorphic homology groups [12–p. 73]. Now, we are ready to define an AT-model for a digital image. 212 R. Gonzalez–Diaz et al. Definition 2. [7] An algebraic topological model (more briefly called AT-model) for a nD (n=2,3) digital image Iis the couple MI=(I,(fI,g I,φ I)) where cI=(fI,g I,φ I)is a chain contraction of the chain complex C(K)toachain complex H,being Ka simplicial complex homotopic to the simplicial representation K(I)and Ha chain complex isomorphic to the homology of I. It is necessary to emphasize that an AT- model is non–unique. First, Kcan be any simplicial complex homotopic to the simplicial representation K(I)and Hany chain complex isomorphic to the homology of I. Second, the morphisms fI,gIand φIcan admit different formulas, all of them allowing to define different cIof C(K)toH. Proposition 1. Let Ibe a nD (n=2,3) digital binary–valued image. There is an algorithm calculating an AT-model for I. We construct the desired chain contraction adequately modifying the classical algorithms for computing homology (matrix, incremental,.. . ) existing in the literature. For example, the matrix algorithm [12] is based on the reduction of the matrices defining the boundary operator to Smith normal form, from which one can read off the homology groups of the complex. A chain homotopy equivalence version of this process is given in [4]. An algebraic homological output for an incremental algorithm [3] for computing homology is given in [6]. The complexity of both algorithms computing AT-models is O(r3), where ris the number of black pictures elements (pixels or voxels). Example 1. The algebraic–topological model of the image Jshowed in Figure 4 is: 12341,22,32,43,42,3,4 f1111000 0 0 g1 φ01,22,32,40002,3,40 +1,2+1,2 Hhas only one generator in dimension 0 represented by the simplex 1.Since His isomorphic to H(J)wegetthatH(J) has only one generator, too. Let us suppose that we have computed an AT-model MI=(I,(fI,g I,φ I)for a digital image I. We are interested here in a full understanding of the structures and morphisms involved in MI. Interesting properties of the morphisms fI,gI Fig. 4. The black points of the image Jand its simplicial representation Algebraic Topological Analysis of Time-Sequence of Digital Images 213 and φIare that for all x∈C(K)andz∈H:(1)fI∂(x)=0;(2)∂gI(z)=0; In fact, gI(z) is a representative cycle of the homology generator z;(3)∂(x)= ∂φI∂(x); (4) If ∂(x)=0,thenx+gIfI(x)=∂φI(x); (5) If x=∂(y), then x=∂φI(x). It is possible to simplify the definition of an AT-model for a nD digital image. Proposition 2. An AT-model for a nD (n=2,3) digital image Ican be represented by a couple MI=(I,φI)where φI:K→C(K)is a linear map of degree 1 such that φφ =0,φ∂φ =φand ∂φ∂ =∂,where∂is the boundary operator in C(K(I)and Kis a simplicial complex homotopic to the simplicial representation K(I). Proof. The proof of the previous result is mainly based on two well-known facts. First, given a chain contraction c=(f,g,φ)fromCto C, it is possible to construct another contraction c=(f,g,φ)fromCto Csuch that the chain homotopy φsatisfies the following additional conditions: (iv)φφ=0;(v)φg= 0; (vi)fφ= 0. In fact, the formula for φis φ=(∂φ +φ∂)φ(∂φ +φ∂)∂(∂φ +φ∂)φ(∂φ +φ∂), being ∂the boundary operator of C. Second, a chain contraction c=(f,g,φ) from Cto Csatisfying (i)−(vi) conditions is equivalent to give a map φ:C→C (called splitting homotopy) satisfying the following conditions: (1) φis a linear map of degree +1; (2) φφ=0;and(3)φ∂φ=φ,being∂the boundary operator of C.Letc=(f,g,φ) be a chain contraction c=(f,g,φ)fromCto C satisfying (i)−(vi) conditions. Applying φto (iii) and using the other identities shows that φ∂φ =φ. Then, the desired φis φ.Conversely,letφ:C→Cbe a map satisfying (1) −(3). Let π=idC−∂φ−φ∂. Then, C=im(π)⊕ker(π). We define the chain contraction c=(f,g,φ )fromCto im(π), where fis the corestriction of πand gis the inclusion. Then, using the equality π2=πand the condition (3), it is easy to prove that c=(f,g,φ ) is the desired chain contraction. Now, we are going to prove the proposition. Let MI=(I,(f,g,φ)) be an AT-model for a nD digital image. Then, c=(f,g,φ) is a chain contraction from C(K)toH,beingHa chain complex isomorphic to the homology of I.Usingthe result previous, we can suppose that the contraction satisfies (i)−(vi)andthen we have a splitting homotopy φfrom C(K)toC(K) satisfying (1) −(3). From φ, we have the new chain contraction c=(f,g,φ )fromC(K)toim(π). Let us now show that im(π) has null boundary operator. If x=π(y)∈im(π), then ∂(x)=∂π(y)=∂gf(y)=g∂f(y)=0sinceHis a chain complex isomorphic to the homology of I. Using this last result and applying the operator ∂to condition (iii)ofc, we get the equality ∂=∂∂φ+∂φ∂.Since∂∂ =0,we finally obtain that ∂φ∂=∂.Conversely,letφ:C(K)→C(K) be a linear map of degree 1 such that φφ =0,φ∂φ =φand ∂φ∂ =∂. We now construct the chain contraction c=(f,g,φ):C(K)→im(π). We are going to show that c defines a AT-model for the digital image I.Letdbe the boundary operator of 214 R. Gonzalez–Diaz et al. im(π). We have to prove that d= 0. Applying ∂to condition (iii)ofcand using that ∂∂ =0and∂φ∂ =∂,weobtain∂−∂gf =∂. Therefore, ∂gf =gdf =0. Since fis onto and gis one-to-one, we show that d=0. Briefly, the additional algebraic-topological information showed in a AT- model for a nD (n=2,3) digital binary–valued image Ican be then codified in terms of a chain homotopy satisfying certain conditions. From that algebraic germ, one can form a chain contraction determining the homology of the simplicial complex K(I). 4 Determining AT-Models Using Other Representation Schemes of Digital Images It is possible to compute an AT-model for a digital image using other representation schemes. As an example, let us see how to compute this model using the quadtree representation of a 2Ddigital binary–valued image. Aquadtree representation (see, for example, [14]) of an image Iis a tree whose leaves represent quadrants of the image and are labelled with the color of the corresponding area, i.e, black or white. In order to obtain the quadtree representation of a digital image, first the whole image is decomposed into four equal–sized quadrants. If one of the quadrants does not contain a uniform region (black or white), it is again subdivided into four quadrants. The decomposition stops if only uniform quadrants are encountered. The recursive decomposition is then represented in a data structure known as tree. Each leaf node of a quadtree representation can be assigned a unique locational code corresponding to a sequence of directional codes that locate theleafnodealongapathstartingatthe root of the tree. A black node of a digital image is encoded as A=(A1A2...A n) with digits in the set S={1,2,3,4}for Ai, where each digit in the sequence represents the quadrant subdivision from which it originates (see Figure 5). The quadrant is defined as the collection of all black node descriptions. In order to construct the simplicial complex K(Q(I)) associated to the quadtree representation Q(I)ofthe2Ddigital image, we need first to find the neighbours of each leaf node of the quadtree Q(I). Node Bis said to be a neighbour of node Ain direction Dif Bcorresponds to the block adjacent to Ain direction Dof size equal, larger or smaller than the block corresponding to A. Hence a node can have no neighbour, one or more neighbours in a chosen direction. Using a method similar to that given in [15] and considering 6-adjacency in a 2Ddigital image I, it is a simple exercise to compute the neighbours of a leaf of the quadtree representation Q(I). Fig. 5. The quadrant subdivision Algebraic Topological Analysis of Time-Sequence of Digital Images 215 Now, starting from the quadtree representation Q(I) of a digital image I,we construct a simplicial complex K(Q(I)) as follows: the vertices (or 0–simplices) of K(Q(I)) are the leaves of Q(I). The i–simplices of K(Q(I)) (i∈{1,2})are constituted by the different sorted sets of i+1neighbourleavesofQ(I). Now, it is immediate to see that the geometric realization |K(Q(I))|can be obtained from |K(I)|continuously ”deforming” black nodes of Iinto points. Proposition 3. The simplicial representation K(I)of a digital image Iis homotopic to the simplicial representation K(Q(I)) of the quadtree representation Q(I)of I. Since K(Q(I)) have, in general, much less number of simplices than K(I), the computation of an algebraic topological model for Iusing K(Q(I)) may be much faster that using K(I). 5 The Topological Complexity of a Time-Sequence of 2D Digital Images We show here that the AT-model technique is well fitted to the problem of analysing the topology of a time-sequence of 2Ddigital images. Let us recall that there are two ways for handling this question: the intraframe and the 3D approaches. Let (I1,I 2,...,I s) be a time-sequence of 2Ddigital binary–valued images. Let Vr,with1≤r≤s,the3Ddigital image resulting of concatenating the successive 2Dimages I1,I 2,...,I r.ThisfactisnotedbyVr=I1+I2+...+Ir. Let us define an AT-model for a time-sequence of 2Ddigital images as an AT- model for the volume Vs. One method is to directly apply a known algorithm Fig. 6. Several frames of a simple time-sequence and the associated 3D binary image 216 R. Gonzalez–Diaz et al. Fig. 7. for computing an AT-model for the simplicial representation of Vs. On the other hand, starting from the respective AT-models {MI1,M I2,...,M Is}for all the frames in the sequence, it is possible to adequately ”gluing” them in order to form an AT-model for the ”concatenated” 3Dimage Vs. Let us suppose that we have constructed an AT-model MVrfor the 3Dimage Vr(with r<s). Starting from MVrand MIr+1 , it is possible to generate an AT-model for Vr+1. The chain complex C(K(Vr∪K(Ir+1))) coincides with the direct sum of the chain complexes C(K(Vr))⊕C(K(Ir+1)). It is immediate to construct the chain contraction cVr⊕cIr+1 from C(K(Vr+Ir+1)) to H(K(Vr))) ⊕H(K(Ir+1))). Let fr,grand φrbe the morphism of that chain contraction and let hrbe the set of all the representative homology generators of H(K(Vr)⊕H(K(Ir+1). Let {τ1,...,τ }be the simplices ”connecting” the simplicial complexes K(Vr)and K(Ir+1) such that {simplices of K(Vr)}∪{simplices ofK(Ir+1))}∪{τ1,...,τ r}, with r≤is a subcomplex of K(Vr+1)). These simplices are perfectly determined for each voxel in frame r+1.Asanexample,itisshowedtotheleftofFigure 7, the frame 5 (consisting in one voxel in red) and frames 4 and 6 (consisting respectively in nine voxels in green) of a sequence and to the right we have the simplicial representation of these frames using 14-adjacency relations. Now, let us use an incremental algorithm for computing an AT-model for a time-sequence of 2Ddigital binary-valued images knowing AT-models for the frames. Algorithm 1. Input: The sorted set of simplices {τ1,...,τ }of K(Vr+1) Output: a splitting homotopy defining an AT-model for the volume Vr+1 Initially,falg (σ):=fr(σ),φalg (σ):=φr(σ)∀σ∈K(Vr)∪K(Ir+1); and h:=hr For i=1 to i=do If falg ∂(σi)=0 then h:= h∪{σi} falg (σi):=σi. Else take any one σjof falg ∂(σi), then h:= h−{σj}, For k=1 to k=mdo If σjappears in falg(σk)then