Spatiotemporal Barcodes for Image Sequence Analysis

Spatiotemporal Barcodes for Image Sequence Analysis Rocio Gonzalez-Diaz, Maria-Jose Jimenez, and Belen Medrano Department of Applied Mathematics (I), University of Seville, Av. Reina Mercedes, s/n, 41012 Seville, Spain {rogodi,majiro,belenmg}@us.es Abstract. Taking as input a time-varying sequence of two-dimensional (2D) binary images, we develop an algorithm for computing a spatiotemporal 0–barcode encoding lifetime of connected components on the image sequence over time. This information may not coincide with the one provided by the 0–barcode encoding the 0–persistent homology, since the latter does not respect the principle that it is not possible to move backwards in time. A cell complex K is computed from the given sequence, being the cells of K classified as spatial or temporal depending on whether they connect two consecutive frames or not. A spatiotemporal path is defined as a sequence of edges of K forming a path such that two edges of the path cannot connect the same two consecutive frames. In our algorithm, for each vertex v ∈ K, a spatiotemporal path from v to the “oldest” spatiotemporally-connected vertex is computed and the corresponding spatiotemporal 0–bar is added to the spatiotemporal 0–barcode. Keywords: Persistent homology · Barcodes · Spatiotemporal data · Digital image sequence analysis 1 Introduction Persistent homology [3,5,12] and zigzag persistence [2] provides information about lifetime of homology classes along a filtration of cell complexes. Such a filtration might be determined by time in a set of spatiotemporal data. Our general aim is to compute the “spatiotemporal” topological information of such filtration, taking into account that it is not possible to move backwards in time (which is not obvious if we use the known algorithms for computing (zigzag) persistent homology). In the context of mobile sensor networks, [4] is devoted to a problem related with the one posed here: can a moving intruder avoid being detected by the sensors? If the answer is yes, the path that describes the intruder over time is called an evasion path. In the study of evasion paths in [4], the region covered Author partially supported by IMUS, Junta de Andalucia under grant FQM-369, Spanish Ministry under grant MTM2012-32706 and ESF ACAT program. by sensors at time tis encoded using Rips complex. A single cell complex SR is computed by stacking the Rips complexes R(t) for all times t. Theorem 7 of [4] proves that there is no evasion path in a given mobile sensor network under a “homological” criterion. Using zig-zag persistent homology, an equivalent condition is provided in [1]. Nevertheless, no general necessary and sufficient condition for the existence of an evasion path is given. The problem is how to capture in the cell complex SR, the idea that an intruder cannot move backwards in time. In [6], the authors analyze time-varying coverage properties in dynamic sensor networks by means of zigzag persistent homology. Coverage holes are tracked in the network by using representative cycles of 1–homology classes. In this paper, we are concerned with the treatment of time-varying sequences of 2D binary images and the tracking of connected components over time inspired by persistent homology methods. An overview of the main tools used in this paper: basics of persistent homology and AT-models are given in Sect. 2. We state the problem of computing the “correct” topological information of spatiotemporal data encoded in a single cell complex in Sect. 3, through two simple examples. Our method to solve the problem in dimension 0 is then introduced in Sect. 4. Cell complexes encoding spatiotemporal information of time-varying sequences of 2D binary images is given in Sect. 5. We conclude in Sect. 6and describe possible directions for future work. 2 Persistent Homology Through AT-models Roughly speaking, a cell complex Kis a general topological structure by which a space is decomposed into basic elements (cells) of different dimensions that are glued together by their boundaries (see the definition of CW-complex in [10]). If the cells in Kare p–dimensional cubes (vertices, edges, square faces, cubes, ...) then Kis a cubical complex. The dimension of a cell σ∈Kis denoted by dim(σ). A cell μ∈Kis a p–face of a cell σ∈Kif μlies in the boundary of σand p=dim(μ)<dim(σ). Ap–chain is a formal sum of p–cells in K. Since we work with coefficients that are either 0 or 1, we can think of a p–chain as a set of p–cells, namely those with coefficients equals to 1. In set notation, the sum of two p–chains is their symmetric difference. The p–chains together with the addition operation form a group denoted as Cp(K). Besides, the set {Cp(K)}pis denoted by C(K). A set of homomorphism {fp:Cp(K)→Cp(K)}pis called a chain map and denoted by f:C(K)→C(K). Given two p–cells σ∈Kand σ∈K, we say that σ∈f(σ)ifσbelongs to the p–chain fp(σ) (in set notation). The boundary map ∂:C(K)→C(K) is defined on a p–cell σas the sum of its (p−1)–faces. This way, for a p–chain, c=i∈Iσi, the boundary of cis the sum of the boundaries of its cells, ∂pc=i∈I∂pσi. Afiltration of Kis an increasing sequence of cell complexes: ∅=K0⊂ K1⊂ ··· ⊂ Kn=K. The partial ordering given by such a filtration can be extended to a total ordering of the cells of K:{σ1,...,σ m}, satisfying that for each i,1≤i≤m, the faces of σilies in the set {σ1,...,σ i}. Then, the map index :K→Zis defined by index(σi):=i. Informally, the p–th persistent homology groups [3,12] can be seen as a collection of p–homology classes (representing connected components when p=0, holes when p= 1, cavities when p= 2, ...) that are born at or before we go from Ki−1to Kiand die after we go from Kito Ki+1.Ap–barcode [7]isa graphical representation of the p–th persistent homology groups as a collection of horizontal line segments (bars) in a plane. Axis corresponds to the indices of the cells in K. For example, if a p–homology class was born at time i(i.e. when σiis added) and died at time j(1 ≤i<j≤m), then a bar with endpoints (i, i) and (j, i) is added to the p–barcode. In [8] the authors establish a correspondence between the incremental algorithm for computing AT-models [9] and the one for computing persistent homology. The first approach provides a rich algebraic information encoded by a chain homotopy operator φ, that “connects” any p–cell to the corresponding surviving cell. An AT-model for a cell complex Kis a quintuple (f,g,φ,K,H), where: –Kis the cell complex. –H⊆Kdescribes the homology of K, in the sense that it contains a distinct p–cell for each p–homology class of a basis, for all p. The cells in Hare called surviving cells. The set of all the surviving p–cells together with the addition operation form the group Cp(H) for all p. –g:C(H)→C(K) is a chain map that maps each p–cell hin Hto one representative cycle gp(h) of the corresponding homology class [gp(h)]. –f:C(K)→C(H) is a chain map that maps each p–cell in Kto a sum of surviving cells, satisfying that if a, b ∈Cp(K) are two homologous p–cycles then fp(a)=fp(b). –φ:C(K)→C(K)isachain homotopy (see [11]). Intuitively, for a p–cell σ,φp(σ) returns the (p+ 1)–cells needed to be contracted to “bring” σto a surviving p–cell contained in fp(σ). In the case of a 0–cell v∈K,φ0(v) will provide a path in K(a sequence of edges of Kconnecting a sequence of different vertices) from the vertex vto the oldest (i.e., with lowest index) vertex in the same connected component. 3 Stating the Problem Our general goal is to compute spatiotemporal p–barcodes for a time-varying sequence of nD binary images in the sense that they can represent evolution of homology classes over time. In this paper, we focus our effort in computing spatiotemporal 0–barcodes for time-varying sequences of 2D binary images. In order to give some intuition about the problem we want to state, let us consider the simple examples given in Fig. 1, in which two sequences of a few 4–connected pixels appearing, moving and disappearing over time, are shown. (a) (b) (c) (d) (e) (f) (g) (h) Fig. 1. Pixels appearing, moving and disappearing over time. To encode the spatiotemporal information of the two sequences, we construct associated cell complexes by replacing each pixel by a vertex and adding an edge between two vertices if: – The corresponding pixels are 4–connected (in the same frame). – The vertices correspond to the same pixel at different times. The resulting cell complexes Kand Kare shown in Fig. 2. (a) Cell complex K. (b) Cell complex K. Fig. 2. Cell complexes Kand Kobtained, respectively, from the sequence showed in Fig. 1(a)–(d) and (e)–(h). Now, to compute 0–persistent homology on these two cell complexes Kand K, we should select an appropriate filtration. Since we want to capture the variation of homology classes over time, we first classify the cells of Kand K in spatial and temporal: – All vertices are spatial (since vertices represent pixels). – An edge is spatial if its endpoints represent pixels of the same frame. – If an edge is not spatial then it is temporal. Therefore, we have the following spatial subcomplexes of K:T1={1},T2= {2,3,4,5,6,7},T4={9,10,11,12,13,14},T6={18}. And the following sets of temporal cells: T3={8},T5={15,16,17},T7={19}, where numbers correspond to the labels of the cells showed in Fig. 2(a). The filtration ∅=K0⊂K1⊂ ··· ⊂ K7=Kis obtained by interleaving the temporal cells after the correspondent spatial subcomplexes. That is, Ki=Ki−1∪Ti, i=1,...,7. Besides, the filtration on Kcoincides with the filtration on K, where numbers now correspond to the labels of the cells showed in Fig. 2(b). If we compute 0–persistent homology of Kand Kusing the above filtrations, we will obtain, in both cases, that a connected component (0–homology class) is born when cell 1 is added and survives until the end. So, in both cases, a bar with endpoints (1,1) and (19,1) is added to the 0–barcode. However, we can observe that Fig. 1(a)–(d) cannot represent a connected component that is moving from the very beginning until the end while Fig. 1(e)– (h) can. So we wonder if we could modify the 0–barcode of the first sequence (Fig. 1(a)–(d)) so that it codifies the connected components that can survive along time. The idea is to replace the bar with endpoints (1,1) and (19,1) by respective bars from (1,1) to (13,1) and from (3,3) to (19,3), what will be formally described in next section. 4OurMethod In this section, our aim is to design an algorithm to compute the spatiotemporal 0–barcode of a cell complex Kencoding spatiotemporal data. Suppose that Kis composed by a stack of (spatial) complexes and a set of (temporal) cells such that each temporal cell connects two (consecutive) spatial complexes. Hence, our starting point is a (spatiotemporal) filtration of K, that is, a filtration ∅=K0⊂K1⊂···⊂Kn=Ksuch that, for all i,1≤i≤n,the set Ti=Ki\Ki−1is: – a set of spatial cells if i=1oriis even; – a set of temporal cells if i>1 is odd. Aspatiotemporal path cin Kis a path in Ksuch that #(c∩Ti)≤1, for any iodd, 1 <i≤n. That is, there are not two temporal edges connecting the same consecutive spatial complexes, which follows from the idea that it is not possible to move backwards in time. Two vertices are spatiotemporally-connected if there is a spatiotemporal path between them. Algorithm 1extends the incremental algorithm for computing AT-models given in [9]. The eleven last lines of Algorithm 1are original in this paper. Although Algorithm 1follows the same idea behind the algorithm given in [9] (by which, for each cell σ,φ(σ) “connects” the cell σto a surviving cell), the computation of the map φis new in this paper. In Algorithm 1, we compute a path φ(v)fromvto a surviving cell and, if φ(v) is not spatiotemporal, we break it in pieces that are spatiotemporal paths. Then, a spatiotemporal path φ(v) is obtained from each vertex v∈Kto the Algorithm 1. Spatiotemporal 0–barcode. 1Input: An ordering of the cells of Kextending the partial ordering imposed by a spatiotemporal filtration. 2Output: An AT-model for Kand a spatiotemporal 0–barcode B. 3H:= ∅. 4for i=1to mdo 5f(σi):=0,φ(σi):=0,φ(σi):=0. 6for i=1to mdo 7if f∂(σi)=0then 8f(σi):=σi,g(σi):=σi+φ∂(σi), H:= H∪{σi}. 9if dim(σi)=0then 10 Add to Ba point at (i, i). 11 if f∂(σi)=0then 12 Let σj∈f∂(σi)st.j=max{index(μ):μ∈f∂(σi)} 13 H:= H\{σj} 14 foreach x∈Ks.t. σj∈f(x)do 15 f(x):=f(x)+f∂(σi), φ(x):=φ(x)+σi+φ∂(σi). 16 if dim(σi)=1then 17 Let v,w,v,w ∈Ks.t. ∂(σi)=v+w,v=∂φ(v)+v, w=∂φ(w)+wand index(v)<index(w). 18 Add to Bthe bar with endpoints {(index(v),index(v)), (i, index(v))}and the bar with endpoints {(index(w),index(w)), (i, index(w))}. 19 if v∈Tand w, w∈Tfor some , ,s.t.1≤≤≤nthen 20 foreach x∈K,x=w, ws.t. ∂φ(x)+x=wdo 21 φ(x):=φ(x)+φ(w)+σi+φ(v). 22 φ(w):=φ(w)+σi+φ(v); 23 φ(w):=σi+φ(v). “oldest” spatiotemporally-connected vertex. Regarding the spatiotemporal 0– barcode, at time i, we elongate a bar only if dim(σi) = 1 and the connected component that represents the bar is spatiotemporally connected to some of the endpoints of the edge σi. Otherwise, we do not elongate the bar. This is different from classical barcodes in which, for example, the bar corresponding to a connected component that appear in time iand does not merge to other connected component later, is elongated until the very end. Proposition 1. If vis a vertex in Kthen, φ(v)is a spatiotemporal path. Proof. Let us prove the proposition by construction. At the beginning of the algorithm, φ(v) = 0 for every vertex v∈K. Suppose the algorithm is running andweareinstepi,1≤i≤m. Suppose that σiis an edge of K. Then, ∂(σi)=v+wbeing vand wtwo vertices of K. Besides, by induction, φ(v)and φ(w) are spatiotemporal paths. Then, ∂φ(v)+v=vand ∂φ(w)+w=wfor some vertices v∈Tand w∈Tbeing 1 ≤, ≤n. We can assume that index(v)< index(w). The case index(v)=index(w) can only occur when v=w, what means that f∂(σi) = 0 (a 1-cycle is being closed) and neither Bnor φare modified in this case. Now, let cw=σ+φ(v), cw=φ(w)+σ+φ(v)andcx=φ(x)+φ(w)+ σ+φ(v), for any x∈Ksuch that ∂φ(x)+x=w. Then, ∂(cw)=w+v, ∂(cw)=w+vand ∂(cx)=x+v. We have to consider the following cases: –Ifσiis spatial, then σi,v,w ∈Tjfor some j,1≤j≤n. We have to consider the following cases: •If <jthen φis not updated. •If =jthen φ(x)⊆Tjfor any x∈Ks.t. ∂φ(x)+x=wand, therefore, cw,cwand cxare spatiotemporal paths. –Ifσiis temporal, then v∈Tjand w∈Tjfor some j=j,1≤j, j≤n. •If j<j . We consider two cases: ∗If =jthen φ(x)⊆Tjfor any x∈Ks.t. ∂φ(x)+x=wand, therefore, cw,cwand cxare spatiotemporal paths. ∗If <j then φis not updated. •If j<jthen φis not updated.  Fig. 3. Top: Three simple examples of stacked cubical complexes (tbeing the temporal dimension). Middle: The associated spatiotemporal barcodes obtained by applying Algorithm 1. Bottom: The spatiotemporal paths of the longest-lived 0–homology classes (in blue) (Color figure online). 5 Spatiotemporal Representation of Image Sequences In this section, we explain how to compute a spatiotemporal filtration representing a time-varying sequence of 2D binary images, inspired by the stack complexes described in [1,4]. Consider Z2as the set of points with integer coordinates in 2D space R2. A2D binary image is a set I=(Z2,8,4,B), where B⊂Z2is the foreground, Bc=Z2\Bthe background,and(8,4) is the adjacency relation for the foreground and background, respectively. A point p∈Z2can be interpreted as a unit closed square (called pixel)inR2centered at pwith edges parallel to the coordinate axes. The set of pixels centered at the points of Btogether with their faces (edges and vertices) constitute a cubical complex denoted by Q(I). A p–cell in Ican be identified by its barycentric coordinates (xσ,y σ)∈R2. Following the construction given in [4], a cubical complex in which consecutive images are stacked to include a third, temporal dimension, is defined. Definition 1. Consider a sequence of 2D binary images S={I1,...,I n}and the associated (2D) cubical complexes Q(I1),...,Q(In). The stacked (3D) cubical complex SQ[S]is obtained as follows. Let Q(Ii)×{i},1≤i≤n, be the cubical complex obtained by adding a third coordinate ito the barycentric coordinates of the cells of Q(I). Initially, SQ[S]=n i=1(Q(Ii)×{i}). Now, if a p-cell σwith barycentric coordinates (xσ,y σ)belongs to Q(Ii)∩Q(Ii+1)for some i,1≤i<n, add to SQ[S]the (p+1)–cell τ=σ×[i, i +1]. This way, the barycentric coordinates of τare (xσ,y σ,i+1 2). Fig. 4. A sequence Sof two 2D images, the associated 3D cubical complexes SQ[S] and DQ[S] and the corresponding spatiotemporal 0–barcodes. Since each cell σ∈SQ[S] can be identified by its barycentric coordinates (xσ,y σ,t σ)∈R3, then σis spatial if, for some i∈Z,tσ=i; and it is temporal otherwise. For example, a cube τ∈SQ[S] is always temporal, and with respect to its faces we find: 6 spatial vertices; 8 spatial and 4 temporal edges; and 2 spatial and 4 temporal squares. Let us denote by Q(Ii,I i+1) the set of temporal cells with faces in Q(Ii)and Q(Ii+1). The spatiotemporal filtration ∅⊂SQ0⊂SQ1⊂ ··· ⊂ SQn=SQ[S] is given by: SQi=Q(I1), if i=1;SQi=SQi−1∪Q(Ij+1), if i=2jand j>0; and SQi=SQi−1∪Q(Ij,I j+1), if i=2j+1andj>0. Figure 3shows three simple examples of stacked cubical complexes. The associated spatiotemporal 0–barcodes are computed using Algorithm 1. From left to right, the first and second spatiotemporal 0–barcodes have only one long bar, while third one has two. Notice that in this last case, the classical 0–barcode would produce only one long bar. Observe that we could construct the 3D cubical complex DQ[S], just considering every pixel centered at point (x, y, t) as a voxel (unit cube with faces parallel to the coordinate planes) centered at point (x, y, t). We have the following result: Proposition 2. Given a sequence of 2D binary images S={I1,...,I n}, the 3D cubical complexes SQ[S]and DQ[S]are homotopy equivalent. Proof. In our approach, to construct the 3D cubical complex SQ[S], we build a cube only when two pixels in same spatial locations (i.e., with identical barycentric coordinates) belong to two consecutive frames; the other approach is to consider pixels as voxels (cubes) to directly obtain a 3D cubical complex DQ[S](see Fig. 4). To prove that SQ[S]andDQ[S] are homotopy equivalent, we describe how to collapse one complex, DQ[S], to the other one, SQ[S]. For this aim, we first apply the translation τ(x, y, t)=(x, y, t +1/2) to cells in DQ[S]. Consider a pixel (square cell) σ∈SQ[S] centered at (xσ,y σ,t σ) that belongs to a cube c centered at (xσ,y σ,t σ+1/2) in SQ[S]. Let cσbe the voxel in DQ[S] centered at (xσ,y σ,t σ). Then clearly τ(cσ)=c∈SQ[S]. Now, the idea is to successively collapse all the cells that are in τ(DQ[S]) but not in SQ[S]. First, if σdoes not belongtoanycubeinSQ[S] centered at (x, y, t) with t=tσ+1/2, then collapse the square face centered at (xσ,y σ,t σ+1)inDQ[S]. Similarly if an edge eof σ centered at (xe,y e,t σ)doesnotbelongtoanycubeinSQ[S] centered at (x, y, t) with t=tσ+1/2, then collapse the edge centered at (xe,y e,t σ+ 1). Finally, if a vertex vof σwith coordinates (xv,y v,t σ) does not belong to any cube in SQ[I] Fig. 5. A sequences of collapses starting from the complex DQ[S] and ending at the complex SQ[S]. First, 4 square faces collapse, then 12 edges collapse and finally, 9 vertices collapse.