Topological signature for periodic motion recognition

TOPOLOGICAL SIGNATURE FOR PERIODIC MOTION RECOGNITION A PREPRINT Javier Lamar-Leon, Edel Garcia-Reyes CENATAV, La Havana, Cuba email: {jlamar, egarcia}@cenatav.co.cu Rocio Gonzalez-Diaz School of Computer Engineering, University of Seville, Spain http:// personal.us.es/rogodi email: [email protected] April 15, 2019 ABSTRACT In this paper, we present an algorithm that computes the topological signature for a given periodic motion sequence. Such signature consists of a vector obtained by persistent homology which captures the topological and geometric changes of the object that models the motion. Two topological signatures are compared simply by the angle between the corresponding vectors. With respect to gait recognition, we have tested our method using only the lowest fourth part of the body’s silhouette. In this way, the impact of variations in the upper part of the body, which are very frequent in real scenarios, decreases considerably. We have also tested our method using other periodic motions such as running or jumping. Finally, we formally prove that our method is robust to small perturbations in the input data and does not depend on the number of periods contained in the periodic motion sequence. Keywords Feature extraction ·Periodic motion ·Video sequences ·Persistent Homology 1 Introduction Person recognition at distance, without the subject cooperation, is an important task in video surveillance. Nevertheless, very few biometric techniques can be used in such scenario. Gait recognition is a technique with special potential under these circumstances since features can be extracted from any viewpoint and at bigger distances than other biometric approaches. Currently, there are good results in the state of the art for persons walking under natural conditions (without carrying a bag or wearing a coat). See, for example, [ 1 , 2 , 3 ]. However, it is common for people to walk carrying things that change their natural gait. The accuracy in gait recognition for persons carrying bag or using coat can be consulted, for example, in [ 1 ] for the CASIA-B gait dataset 1 . Moreover, people usually perform movements with the upper body part unrelated to the natural dynamic of the gait. Up to now, the most successful approaches in gait recognition use silhouettes to get the features. Among the silhouettebased techniques, the best results have been obtained from the methods based in Gait Energy Images (GEI) [ 4 , 1 , 2 , 5 , 6 ]. Generally, these strategies are affected by a small number of silhouettes (one gait cycle or less). Moreover, the temporal order in which silhouettes appear is not captured in those representations, losing the relative relations of the movements in time. Besides, the features extracted by those methods are highly correlated with errors in the segmentation of the silhouettes [ 7 ] and these errors frequently appear in the existing algorithms for background segmentation. This implies that GEI methods are influenced by the shape of the silhouettes instead of the relative positions among the parts of the body while walking. In our previous conference papers [ 3 , 8 , 9 , 10 ], we concentrated our effort in overcoming most of the difficulties explained above. In these works, the gaits were modeled by a persistent-homology-based representation, called topological signature for the gait sequence, and used for human identification [ 3 ], gender classification [ 8 ], carried 1http://www.cbsr.ia.ac.cn/GaitDatasetB-silh.zip arXiv:1904.06210v1 [cs.CV] 11 Apr 2019 APREPRINT - APRIL 15, 2019 object detection [ 9 ] and monitoring human activities at distance [ 10 ]. Later, in [ 11 ], we computed our topological signature using only the lower part of the body (see Figure 1), avoiding many of the effects arising from the variability in the upper body part (related, for example, to hand gestures while talking on cell). This selection is endorsed by the result given in [ 12 ], which shows that this part of the body provides most of the necessary information for classification. The topological signature defined in our previous papers has been also used in [ 13 ] for recognizing 3D face expression and [14] for differentiating forehand and backhand strokes performed by a tennis player. The lowest fourth part of the body silhouette Figure 1: Lowest four part of the body occluded by a bag. Other papers using persistent homology for action recognition are the followings. In [ 15 ], topological features of the attractor of the dynamical system are used for modelling human actions and a nearest neighbor classifier is trained with the persistence-based features. In [ 16 ], point clouds describing the oscillatory patterns of body joints from the principal components of their time series using Taken’s delay embedding are computed. In [ 17 ], a novel framework, based on persistent cohomology can automatically detect, parameterize and interpolate periodic motion patterns obtained from a motion sequence. In none of those papers, theoretical results on the correct behaviour of the designed methods are provided. In this paper, in Section 2, we first recall the main background needed to understand it. We generalize the procedure given in our previous papers to obtain the topological signature for a periodic motion in Section 3. The input of the procedure is a sequence of silhouettes obtained from a video. A simplicial complex ∂K(I) which represents the periodic motion is then constructed in Subsection 3.1. Sixteen persistence barcodes are then computed considering the distance to eight fixed planes: 2 horizontal, 2 vertical, 2 oblique and 2 depth planes, completely capturing, this way, the motion in the sequence (see Subsection 3.2). More concretely, for each plane π , we compute two persistence barcodes (graphical tools encoding the persistent homology information). One persistence barcode detects the variation of connected components and the other one detects the variation of tunnels, when we go through ∂K(I) in a direction perpendicular to the plane π . Putting together all this information, we construct a vector called topological signature for each sequence in Subsection 3.3. We compare two topological signatures by the angle between the vectors forming the signatures. As an original contribution of this paper, we theoretically study the stability of the topological signature in Section 4. We formally prove, in terms of probabilities, that small perturbations in the input body silhouettes provoke small perturbations in the resulting topological signature. We also prove that the direction of each of the vectors that make up the topological signature for a sequence remains the same independently on the number of periods the sequence contains. Since we compare two topological signatures by the angle between the corresponding vectors, then the previous assertion implies that the topological signature is independent on the number of periods the sequence contains. Experimental results are showed in Section 5. Conclusions are given in Section 6. 2 Preliminaries Let us now introduce the definitions and concepts used throughout the paper. The main one is the concept of persistent homology, which is an algebraic tool for measuring topological features of shapes and functions. It is built on top of homology, which is a topological invariant that captures the amount of connected components, tunnels, cavities and higher-dimensional counterparts of a shape. Small size features in persistent homology are often categorized as noise, while large size features describe topological properties of shapes. For a more detailed introduction on the theoretical concepts introduced in this section see, for example, [18, 19, 20]. A3D binary image is a pair I= (Z3, B) , where B (called the foreground) is a finite set of points of Z3 and Bc=Z3\B is the background. The cubical complex Q(I) associated to I is a combinatorial structure constituted by a set of unit cubes with square faces parallel to the coordinate planes and vertices in Z3 . More concretely, the set of vertices V of 2 APREPRINT - APRIL 15, 2019 any cube c∈Q(I) satisfies that V={(i, j, k),(i+ 1, j, k),(i, j + 1, k),(i, j, k + 1),(i+ 1, j + 1, k),(i+ 1, j, k + 1),(i, j + 1, k + 1),(i+ 1, j + 1, k + 1)} for some (i, j, k)∈Z3 , and V⊆B . The 0 -faces of c are its 8 corners (vertices), its 1-faces are its 12 edges, its 2-faces are its 6squares and, finally, its 3-face is the cube citself. A p -simplex σ in Rn is the set of p+ 1 affinely independent points in Rn . Observe that always p≤n . A set µ in Rn is a face of σ if µ⊆σ . The simplices considered in this paper are 0 -simplices (representing vertices), 1 -simplices (representing edges) and 2 -simplices (representing triangles), all of them embedded in R3 . The formal definition of a simplicial complex K is as follows [ 21 , p. 7]: A simplicial complex K is a collection of simplices such that: (1) every face of a simplex of K is in K ; and (2) the intersection of any two simplices of K is a face of each of them. A simplicial complex is finite if it has a finite number of simplices. Let K be a simplicial complex. A p -chain on K is a formal sum of p -simplices of K . The group of p -chains is denoted by Cp(K) . The p -boundary operator ∂p:Cp(K)→Cp−1(K) is a homomorphism such that for each p -simplex σ of K , ∂p(σ) is the sum of its (p−1) -faces. For example, if σ is a triangle, ∂2(σ) is the sum of its edges. The kernel of ∂p is called the group of p -cycles in Cp(K) and the image of ∂p+1 is called the group of p -boundaries in Cp(K) . The p -homology Hp(K) of K is the quotient group of p -cycles relative to p -boundaries (see [ 21 , Chapter 5]). The 0 -homology classes of K (i.e. the classes in H0(K) ) represent the connected components of K , the 1 -homology classes its tunnels and the 2-homology classes its cavities. Afiltration F of a simplicial complex K is an ordering of the simplices of K dictated by a filter function f:K→R , satisfying that if a simplex σ is a face of another simplex σ0 in K then f(σ)≤f(σ0) and σ appears before σ0 in the filtration. The associated filtered simplicial complex is the sequence: ∅ ⊂ Ki1⊂ ··· ⊂ Ki`=K where i1<··· < i`and Kij=f−1(−∞, ij]for 1≤j≤`. Consider a filtration F= (σ1, σ2, . . . , σm) of a simplicial complex K obtained from a given filter function f:K→R . If σi completes a p -cycle ( p being the dimension of σi ) when σi is added to Fi−1= (σ1, . . . , σi−1) , then a p -homology class α is born at time f(σi) ; otherwise, a (p−1) -homology class dies at time f(σi) . The difference between the birth and death times of a homology class γ is called its persistence, which quantifies the significance of a topological attribute. If αnever dies, we set its persistence to infinity. For a p -homology class that is born at time f(σi) and dies at time f(σj) , we draw a bar [f(σi), f(σj)) with endpoints f(σi) and f(σj) . The set of bars {[f(σi), f(σj)) ⊂R} (resp. points {(f(σi), f(σj)) ∈R2} ) representing birth and death times of homology classes is called the persistence barcode B(F) (resp. persistence diagram dgm(F) ) for the filtration F . Analogously, fixed i , the set of bars (resp. points) representing birth and death time of i -homology classes is called the i-persistence barcode (resp. the i-persistence diagram) for F. For example, in Figure 2, the filtration F={b , c , bc , e , be , ec , a , ab , ac , abc , d , bd , de , bde , f , ef , cf , cef} of the simplicial complex which consists of a composition of three triangles, can be read on the x -axis of the picture. Bars corresponding to the persistence of 0 -homology classes (i.e. the persistence of connected components) are colored in blue and bars corresponding to the persistence of 1 -homology classes (i.e., the persistence of tunnels) are colored in red. Observe that only two bars survive until the end: one corresponding to the connected component and one corresponding to the tunnel of the simplicial complex. The bottleneck distance (see [ 18 , page 229]) is classically used to compare two persistence diagrams dgm(F) = {a1, . . . , ak} and dgm(F0) = {a0 1, . . . , a0 k0} for two filtrations F and F0 of, respectively, two finite simplicial complexes Kand K0. The bottleneck distance between dgm(F)and dgm(F0)is: db(dgm(F), dgm(F0)) = min γ{max a{||a−γ(a)||∞}} where γ:dgm(F)→dgm(F0) is a bijection that can associate a point off the diagonal with another point on or off the diagonal, where diagonal is the set D={(x, x)} ⊂ R2 . For points a= (x, y)∈F∪D and γ(a)=(x0, y0)∈F0∪D , the expression ||a−γ(a)||∞ means max{|x−x0|,|y−y0|} . Observe that since K and K0 are finite then so are dgm(F) and dgm(F0). Table 2 in page 9 shows the bottleneck distance between the persistence diagrams pictured in Figure 8. The following definitions are taken from [ 20 ]. Let W and W0 be the vertex set of, respectively, two simplicial complexes K and K0 . A correspondence C:W⇒W0 from W to W0 is a subset of W×W0 satisfying that for any v∈W there exists v0∈W0 such that (v, v0)∈C and, conversely, for any v0∈W0 there exists v∈W such that (v, v0)∈C . Besides, for a subset σ of W , C(σ) denotes the subset of W0 satisfying that a vertex v0 is in C(σ) if and only if there exists a vertex v∈σ such that (v, v0)∈C . Finally, given filter functions f:K→R and f0:K0→R , and the corresponding filtrations F and F0 , we say that C:W⇒W0 is  -simplicial from F to F0 if for any t∈R and simplex σ∈K such that f(σ)≤t , every simplex µ∈K0 with vertices in C(σ) satisfies that f0(µ)≤t+ . The transpose of C, denoted by CT, is the image of Cthrough the symmetry map (x, y)→(y, x). 3 APREPRINT - APRIL 15, 2019 Figure 2: An example of a persistence barcode obtained from a simplicial complex. The following results will be used later in the paper. Proposition 1 [ 20 , Proposition 4.2] Let S and T be filtered complexes with vertex sets X and Y respectively. If C:X⇒Y is a correspondence such that C and CT are both  -simplicial, then together they induce a canonical -interleaving between H(S)and H(T), the interleaving homomorphisms being H(C)and H(CT). The homology groups of each subcomplex in a filtered complex together with the morphism between homology groups induced by the inclusion maps is an example of a q -tame module if all the subcomplexes are finite which is the case we deal with in this paper. Theorem 1 [ 20 , Theorem 2.3] If U is a q -tame module then it has a well-defined persistence diagram dgm(U) . If U , V are q -tame persistence modules that are  -interleaved then there exists an  -matching between the multisets dgm(U) and dgm(V). Thus, the bottleneck distance between the diagrams satisfies the bound db(dgm(U), dgm(V)) ≤. 3 Topological signature for a periodic motion In this section, we explain how to compute the topological signature for a sequence of silhouettes. First, in Subsection 3.1, a simplicial complex is built from the given sequence. Then, in Subsection 3.2, eight filtrations of the simplicial complex are computed in order to capture the movements that characterize the motion recorded in the sequence. In Subsection 3.3 we finally explain how to obtain the signature from the persistence barcodes for the given filtrations. 3.1 From sequences of silhouettes to simplicial complexes In this subsection we introduce the construction of the simplicial complex ∂K(I) which models the input sequence, which is a sequence of silhouettes obtained from a periodic motion sequence. See, for example, Figure 3.a. In our previous papers [ 3 , 8 , 9 , 10 , 11 ], we got the sequences from the background segmentation provided in CASIA-B dataset2for gait silhouettes. We build a 3D binary image I= (Z3, B) by stacking k consecutive silhouettes. The cubical complex Q(I) associated to the 3D binary image I is then computed. The height of each silhouette is set to 1 and the width changes accordingly to preserve the original proportion between height and width. Besides, z -coordinates that represented the amount of silhouettes in the stack is also set to 1 . Then, by construction, x -, y - and z -coordinates of the vertices in Q(I) have their values in the interval [0,1] . Finally, the squares that are faces of exactly one cube in Q(I) are divided into two triangles. These triangles together with their faces (vertices and edges) form the simplicial complex ∂K(I) . See Figure 3.b and Figure 4.b. The different colors in the figures are used just to recognize each silhouette in the complex. 2http://www.cbsr.ia.ac.cn/GaitDatasetB-silh.zip 4 APREPRINT - APRIL 15, 2019 Figure 3: a) Left: sequence of gait silhouettes. b) Right: associated simplicial complex ∂K(I). Figure 4: a) Left: sequence of leg-silhouettes. b) Right: associated simplicial complex ∂K(I). 3.2 Filtration of the simplicial complex ∂K(I) The next step in our process is to compute filtrations of the previously computed simplicial complex ∂K(I) , in order to capture the movements recorded in the sequence. Figure 5: From left to right: the eight planes used to compute the eight filtrations of ∂K(I) : two vertical, two horizontal and four oblique planes. In this figure, ∂K(I)is the simplicial complex showed in Figure 4.b. Eight different filtrations of ∂K(I) are computed using, respectively, eight planes: two vertical planes ( x= 0 and x= 1 ), two horizontal planes ( y= 0 and y= 1 ) and four oblique planes ( x−y= 1 , y−x= 1 , x+y= 0 and x+y= 2). See Figure 5. More concretely, for each plane π , we define the filter function fπ:∂K(I)→R which assigns to each vertex of ∂K(I) its distance to the plane π , and to any other simplex of ∂K(I) , the greatest distance of its vertices to π . A filtration ∂Kπof ∂K(I)is then computed dictated by the filter function fπ. 5 APREPRINT - APRIL 15, 2019 00.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 5 10 15 20 25 30 35 40 00.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 5 10 15 20 25 30 35 40 45 50 video sequence 001-nm-01-090 Blue 1-persistence barcode Red 0-persistence barcode video sequence 002-nm-01-090 Figure 6: Persistence barcodes for two filtrations obtained, respectively, from the sequences 001-nm-01-090 and 002-nm-01-090 of CAISA-B dataset. Horizontal axis represents the distance to the reference plane x= 0. Observe that for a vertex v∈∂K(I) , the value of fπ(v) is: (a) less or equal than 1 if π is an horizontal o vertical plane; and (b) less or equal than √2 if π is an oblique plane. Finally, observe that not any filtration involves z -coordinate. The reason for this is that our aim is to obtain a topological signature robust to the number of silhouettes (which was one of the weaknesses of previous approaches as mentioned in the introduction) used to compute the simplicial complex ∂K(I). 3.3 Topological signature The final step in our process is to compute the persistence barcode for each filtration ∂Kπ associated to each plane π (see Figure 5). We only consider bars in the persistence barcode with length strictly greater than 0 . This way, we do not take into account any topological event e that is born and dies at the same distance to the reference plane. This is not a problem in the sense that we could lose information, since that event ewill be captured using a different reference plane. As an example, the persistence barcodes for two filtrations dictated by the distance to the plane x= 0 and obtained, respectively, from the video sequences 001-nm-01-090 and 002-nm-01-090 of the CAISA-B dataset, are shown in Figure 6. The set of red bars forms the 0 -persistence barcode and the set of blue bars forms the 1 -persistence barcode. Notice the green circle showing topological features that are born and die at the same time. Now, for each plane π , the 0 - and 1 -persistence barcode for the filtration ∂Kπ are explored according to a uniform sampling. More concretely, given a positive integer n (being n= 24 in our experimental results, obtained by cross validation), we compute the value h=k n , which represents the width of the “window” we use to analyze the persistence barcode, being k the greatest distance of a vertex in ∂K(I) to the plane π . Since the distance to the plane π has been normalized then k≤√2, so h≤√2 24 . Procedure 1 A vector V0 π(resp. V1 π) of 2nentries is constructed as follows. For s= 0, . . . , n −1: 6 APREPRINT - APRIL 15, 2019 (a) entry 2s contains the number of 0 - (resp. 1 -) homology classes that are born before s·h and persist or die after s·h; (b) entry 2s+ 1 contains the number of 0 - (resp. 1 -) homology classes that are born in s·h or later and before (s+ 1) ·h. For example, suppose that a homology class is born and dies within the interval [s·h, (s+ 1) ·h) . Then, in this case, we add 1 in entry 2s+ 1 . On the other hand, suppose that a homology class is born in the interval [s·∆h, (s+ 1) ·h) and dies in [t·h, (t+ 1) ·h) for some s, t such that s<t≤n . Then, in this case, we add 1 in entry 2s+ 1 , and in entries 2jfor s < j ≤t. Dividing the entries in two categories (a) and (b), small details in the object are highlighted, which is crucial for distinguishing two different motions. For example, let us suppose a scenario in which m0 -homology classes are born in [s·h, (s+ 1) ·h) and persist or die at the end of [(s+ 1) ·h, (s+ 2) ·h) and not any other 0 -homology class is born, persists or dies in these intervals. Then, we put 0 in entries 2s and 2s+ 3 of V0 π , and m in entries 2s+ 1 and 2s+ 2 of V0 π . On the other hand, let us suppose that m0 -homology classes are born and die in [s·h, (s+ 1) ·h) and in [(s+ 1) ·h, (s+ 2) ·h) and not any other 0 -homology class is born, persists or dies in these intervals. Then, we put 0 in entries 2s and 2s+ 2 of V0 π and m in entries 2s+ 1 and 2s+ 3 of V0 π . Therefore, considering (a) and (b) separately, we can distinguish both scenarios. Fixed a plane π , we then obtain two 2n -dimensional vectors for ∂Kπ , one for the 0 -persistence barcode and the other for the 1 -persistence barcode for the filtration ∂Kπ . Since we have eight planes, {π1,...π8} , and two vectors per plane, {V0 πi,V1 πi}:i= 1,...,8 , we have a total of sixteen 2n -dimensional vectors which form the topological signature for a periodic motion sequence. Finally, to compare the topological signatures for two periodic motion sequences, we add up the angle between each pair of vectors in the signatures. Since a signature consists of sixteen vectors, the best comparison for two sequences is obtained when the total sum is 0 and the worst is 90o·16 = 1440o . Observe that in our previous papers [ 3 , 8 , 9 , 10 ], we used the cosine distance 3 to compare two given topological signatures. In that case, the best comparison for two sequences is obtained when the total sum is 16 and the worst comparison when it is 0. Remark 1 We have noticed that using the angle instead of the cosine to compare two topological signatures, the efficiency (accuracy) of gait recognition increases by 5% . This comparison is made in Table 5. The reason for this phenomena is that angle is more discriminative than cosine when the angle between vectors is close to zero4. 4 Stability of the topological signature for a periodic motion sequence Once we have defined the topological signature for a periodic motion sequence, our aim is to prove its stability under small perturbations on the sequence (Theorem 2) and/or under variations on the number of periods in the sequence (Theorem 3). The following technical statements will be used to prove Theorem 2. Proposition 2 Let F (resp. F0 ) be a filtration of a simplicial complex K (resp. K0) dictated by a filter function f:K→R(resp. f0:K0→R). Let W(resp. W0) be the vertex set of K(resp. K0). If C:W⇒W0is a correspondence from Wto W0satisfying that f0(v0)≤f(v) + for every (v, v0)∈C, then C:W⇒W0is -simplicial from Fto F0. Proof. Let t∈R and σ∈K such that f(σ)≤t . Then, every simplex µ∈K0 with vertices in C(σ) satisfies that f0(µ)≤t+. Then, C:W⇒W0is -simplicial from Fto F0by definition.  Proposition 3 Let F (resp. F0 ) be a filtration of a simplicial complex K (resp. K0) dictated by a filter function f:K→R(resp. f0:K0→R). Let W(resp. W0) be the vertex set of K(resp. K0). If the correspondence C:W⇒W0is -simplicial from Fto F0, then db(dgm(F), dgm(F0)) ≤. Proof. The statement is a direct consequence of Proposition 1 in page 4 and Theorem 1.  3The cosine distance between two vectors vand wis v·w ||v||·||w|| . 4Recall that limx→0 x 1−cos(x)=∞. 7 APREPRINT - APRIL 15, 2019 In the following theorem, we prove, in terms of probabilities, that the topological signature is stable under small perturbations on the input data (i.e., the input sequence). Theorem 2 Let I (resp. I0 ) be a 3D binary image. Let W (resp. W0 ) be the vertex set of ∂K(I) (resp. ∂K(I0) ). Let ∂Kπ (resp. ∂K0 π ) be the filtration of ∂K(I) (resp. ∂K(I0) ) dictated by the distance function fπ:∂K(I)→R (resp. f0 π:∂K(I0)→R ) to a given plane π . Let Vj π (resp. Xj π ), where j= 0,1 , be the two vectors obtained by applying Proc. 1 to the persistence barcode for ∂Kπ (resp. ∂K0 π ). Let mi (resp. m0 i ) be the number of bars in the i -persistence barcodes for the filtration ∂Kπ(resp. ∂K0 π). If C:W⇒W0is a correspondence from Wto W0satisfying that f0 π(v0)≤fπ(v) + for every (v, v0)∈C, then Vi π=Xi πwith probability greater or equal than 1−2(n−1) kmi+m0 i where: •kis the maximum distance of a point in ∂Kπto the plane π; •nis the number of subintervals (“windows") in which the interval [0, k]is divided. Proof. By Proposition 2, we have that C:W⇒W0 is  -simplicial from ∂Kπ to ∂K0 π . By Proposition 3, we have that db(dgm(∂Kπ), dgm(∂K0 π)) ≤. Let γ:dgm(∂Kπ)∪ {(x, x)} → dgm(∂K0 π)∪ {(x0, x0)} be the bijection such that maxa{||a−γ(a)||∞}= db(dgm(∂Kπ), dgm(∂K0 π)). Now, let a= (x, y)∈dgm(∂Kπ) and a0= (x0, y0)∈dgm(∂K0 π) , being x<y and x0< y0 . On the one hand, if γ(a) = a0 , then |x−x0| ≤  and |y−y0| ≤  . On the other hand, if γ(a) lies in the diagonal, then |x−y| ≤  . Similarly, if γ−1(a0)lies in the diagonal, then |x0−y0| ≤ . Now, observe that Vi π can be different from Xi π if there exists a point (α, β) in dgm(∂Kπ) or dgm(∂K0 π) satisfying that α or β belongs to (sh −, sh +) for h=bk nc and s∈ {1, . . . , n −1} . Any of both situations ( α or β belongs to (sh −, sh +)) can occur with probability 2(n−1) k. Now, on the one hand, suppose that γ(a) = a0 . If x and y do not belong to (sh −, sh +) then x0 and y0 either. On the other hand, suppose γ(a)=(x0, x0) then |x−y| ≤  . If x6∈ (sh −, sh +) then y either. Respectively, suppose γ−1(a0)=(x, x). If x06∈ (sh −, sh +)then y0either. Therefore, Vi π=Xi πwith probability greater or equal than 1−2(n−1) kmi+m0 i. As we will see next, the result given in Theorem 2 only makes sense when is “small" enough. Corollary 1 The probability of being Vi π=Xi π tends to 1 when  tends to 0 . Besides, such probability is non-negative when  is less or equal than k 2(n−1) (recall that h=k n is the width of the“window” we use to analyze the persistence barcode). Proof. First, it is clear that if  tends to 0 then 1−2(n−1) kmi+m0 i tends to 0 . Second, 1−2(n−1) k≥0 when ≤k 2(n−1) . Take two 3D binary images I and I0 , and a plane π such that there exists a correspondence C between the vertices of ∂K(I) and ∂K(I0) satisfying that fπ(v0)≤fπ(v) +  for any pair of vertices v∈∂K(I) and v0∈∂K(I0) matched by C . Recall that, by construction, fπ(v) and f0 π(v0) are less or equal than 1 (resp. √2 ) if π is an horizontal or vertical plane (resp. oblique plane). Then k≤1 (resp. k≤√2 ) if π is an horizontal or vertical plane (resp. oblique plane). Now fix, for example, k= 0.9 , n= 24 and m0=m0 0= 20 . Recall that n= 24 is the one used in our experimentation obtained by cross validation. Half window size for this example is 0.9/(2 ·24) = 0.01875 . We have that V0 π=X0 π with probability greater or equal than P for P= 0.814672814702977 if = 0.0001 and P= 0.979758005555892 if = 0.00001. Finally, the following result shows that the topological signature does not depend on the number of periods in a given sequence. Theorem 3 The direction of the topological signature {V0 πi,V1 πi}i=1,...,8 is independent on the number of periods the sequence contains. 8 APREPRINT - APRIL 15, 2019 Proof. Let I1 be a stack of consecutive silhouettes taken from a sequence of a periodic motion. Let I2 be obtained by stacking twice the silhouettes of I1 . That is, for any point v= (x, y, z) in I1 there exist exactly two points v= (x, y, z) and v0= (x, y, z +k) in I2 for a fixed k . Let ∂K(I1) (resp. ∂K(I2) ) be the simplicial complex obtained from I1 (resp. I2) ). Let π be the referred plane, as one of the eight planes considered in this paper, used to compute the respective filtrations ∂K1 π and ∂K2 π . Since all the planes considered in this paper are perpendicular to plane z= 0 , then if the distance of a vertex v in ∂K(I1) to the plane π is d , then the distance of vertices v and v0 in ∂K(I2) to the plane π is also d . Therefore, for any bar in the persistence barcode associated to the filtration ∂K1 π , there exist exactly two bars in the persistence barcode associated to the filtration ∂K2 π having the same birth and death times. Consequently, the vector corresponding to the topological signature for I2 is exactly twice the vector corresponding to the topological signature for I1. Pc1 S1 Pc2 S1 Pc1 S2 Pc2 S2 Figure 7: The silhouettes extracted from two gait sequences S1and S2of the same person. For instance, let S1 and S2 be the silhouettes extracted from two gait sequences of the same person from CASIA-B dataset, both S1and S2having two gait cycles. Let Pc1 S1 and Pc1 S2 (resp. Pc2 S1 and Pc2 S2 ) be the silhouette sequences of exactly one gait cycle (resp. two gait cycles) on S1 and S2 . See Figure 7. Then, use the same reference plane π to obtain the four filtrations Fc2 S1 , Fc2 S2 , Fc1 S1 and Fc1 S2 for the simplicial complexes associated to the 3D binary images obtained from the sequences Pc2 S1 , Pc2 S2 , Pc1 S1 and Pc1 S1 , respectively. The 0 -persistence diagrams dgm(Fc2 S1) , dgm(Fc2 S2) , dgm(Fc1 S1) and dgm(Fc1 S2) are showed in Figure 8. We can observe that the diagrams dgm(Fc2 S1) and dgm(Fc2 S2) have approximately the double of persistent points than the diagrams dgm(Fc1 S1) and dgm(Fc1 S2) (look at the area inside of the red circles in Figure 8). Since the topological signature is computed using “windows” in the persistence barcode (or equivalent, in the persistence diagram), then the modules of the topological signature obtained from the persistence diagrams dgm(Fc2 S1) and dgm(Fc2 S2) is approximately the double of the modules of the topological signature obtained from the persistence diagrams dgm(Fc1 S1) and dgm(Fc1 S2) . Nevertheless, the direction remains approximately the same. Observe that we do not have exactness since we do not stack the same silhouettes twice, but we take one or two cycles from a sequence, so small errors and variations may appear. Table 1: Cosine distance between the topological signatures obtained from the persistence diagrams showed in Figure 8. dgm(Fc1 S2)dgm(Fc2 S2) dgm(Fc1 S1)0.985 0.987 dgm(Fc2 S1)0.981 0.990 Table 2: Bottleneck distance between persistence diagrams showed in Figure 8. dgm(Fc1 S2)dgm(Fc2 S2) dgm(Fc1 S1)855727 1319872 dgm(Fc2 S1)2273559 5446584 In Table 1 we show the results of the comparison between the topological signatures obtained from the persistence diagrams dgm(Fc2 S1) , dgm(Fc2 S2) , dgm(Fc1 S1) and dgm(Fc1 S2) using the cosine distance. Observe that, in all the cases, the cosine distance is almost 1 (i.e., all the vectors have almost the same direction), which makes sense since all the gait sequences correspond to the same person and the corresponding filtrations are computed using the same reference plane. Finally, in Table 2 we show that if we consider the classical bottleneck distance to compare the different persistence 9 APREPRINT - APRIL 15, 2019 Figure 12: Similitude between skip and run action poses. Top: Daria-skip silhouettes. Bottom: Daria-run silhouettes. Table 11: Cluster according to similar lower clothes used. Cluster (code) Lower clothes Upper clothes 2349ABCXY RP: regular pant 2) HS HS: Half Shirt 3) HS,Ht FS: Full Shirt 4) HS,Cs Ht: Hat 9) FS PK: Parka A) PK Cs: Casquette Cap B) DJ DJ: Down Jacket C) DJ,Mf Mf: Muffler X) FS,Ht Y) FS,Cs samples with clothes combination 9, A and B and to train, and C and X to test for the rest of the persons, due to people do not have the same combination clothes. Considering only the lower part of the body, we obtain a rate of 79.4 % of accuracy. More examples and the source code written in Matlab can be obtained visiting our web page10. 6 Conclusion In this paper, we have presented a persistent-homology-based signature successfully applied in the past to gait recognition. We have shown that such topological signature can be applied to any periodic motion (not only gait), such as running or jumping. We have formally proved that such signature is robust to noise and independent to the number of periods used to compute it. Funding. This work has been partially funded by the Applied Math department and Institute of Mathematics at the University of Seville, Andalusian project FQM-369 and Spanish project MTM2015-67072-P. References [1] Shiqi Yu, Daoliang Tan, and Tieniu Tan. A framework for evaluating the effect of view angle, clothing and carrying condition on gait recognition. In Pattern Recognition, 2006. ICPR 2006. 18th International Conference on, volume 4, pages 441–444. IEEE, 2006. [2] Chin Poo Lee, Alan WC Tan, and Shing Chiang Tan. Time-sliced averaged motion history image for gait recognition. Journal of Visual Communication and Image Representation, 25(5):822–826, 2014. [3] Javier Lamar-Leon, Edel Garcia-Reyes, and Rocio Gonzalez-Diaz. Human gait identification using persistent homology. In Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications - 17th Iberoamerican Congress, CIARP 2012, Buenos Aires, Argentina, September 3-6, 2012. Proceedings, pages 244–251, 2012. 10http://grupo.us.es/cimagroup/ 16 APREPRINT - APRIL 15, 2019 [4] Yuanyuan Zhang, Shuming Jiang, Zijiang Yang, Yanqing Zhao, and Tingting Guo. A score level fusion framework for gait-based human recognition. In Multimedia Signal Processing (MMSP), 2013 IEEE 15th International Workshop on, pages 189–194. IEEE, 2013. [5] Imad Rida, Somaya Almaadeed, and Ahmed Bouridane. Gait recognition based on modified phase-only correlation. Signal, Image and Video Processing, 10(3):463–470, 2016. [6] Zifeng Wu, Yongzhen Huang, Liang Wang, Xiaogang Wang, and Tieniu Tan. A comprehensive study on cross-view gait based human identification with deep cnns. IEEE transactions on pattern analysis and machine intelligence, 39(2):209–226, 2017. [7] Changhong Chen, Jimin Liang, Heng Zhao, Haihong Hu, and Jie Tian. Frame difference energy image for gait recognition with incomplete silhouettes. Pattern Recognition Letters, 30(11):977–984, 2009. [8] Javier Lamar-Leon, Andrea Cerri, Edel Garia-Reyes, and Rocio Gonzalez-Diaz. Gait-based gender classification using persistent homology. In Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications - 18th Iberoamerican Congress, CIARP 2013, Havana, Cuba, November 20-23, 2013, Proceedings, Part II, pages 366–373, 2013. [9] Javier Lamar-Leon, Raul Alonso-Baryolo, Edel Garcia-Reyes, and Rocio Gonzalez-Diaz. Gait-based carried object detection using persistent homology. In Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications - 19th Iberoamerican Congress, CIARP 2014, Puerto Vallarta, Mexico, November 2-5, 2014. Proceedings, pages 836–843, 2014. [10] Javier Lamar-Leon, Raul Alonso-Baryolo, Edel Garcia-Reyes, and Roio Gonzalez-Diaz. Topological features for monitoring human activities at distance. In Activity Monitoring by Multiple Distributed Sensing - Second International Workshop, AMMDS 2014, Stockholm, Sweden, August 24, 2014, pages 40–51, 2014. [11] Javier Lamar-Leon, Raul Alonso Baryolo, Edel Garcia-Reyes, and Rocio Gonzalez-Diaz. Persistent homologybased gait recognition robust to upper body variations. In 23rd International Conference on Pattern Recognition, ICPR 2016, Cancún, Mexico, December 4-8, 2016, pages 1083–1088, 2016. [12] Khalid Bashir, Tao Xiang, and Shaogang Gong. Gait recognition without subject cooperation. Pattern Recognition Letters, 31(13):2052–2060, 2010. [13] Zhen Zhou, Yongzhen Huang, Liang Wang, and Tieniu Tan. Exploring generalized shape analysis by topological representations. Pattern Recognition Letters, 87:177–185, 2017. [14] Maria Jose Jimenez, Belén Medrano, David S. Monaghan, and Noel E. O’Connor. Designing a topological algorithm for 3d activity recognition. In Computational Topology in Image Context - 6th International Workshop, CTIC 2016, Marseille, France, June 15-17, 2016, Proceedings, pages 193–203, 2016. [15] V. Venkataraman, K. N. Ramamurthy, and P. Turaga. Persistent homology of attractors for action recognition. In 2016 IEEE International Conference on Image Processing (ICIP), pages 4150–4154, Sep. 2016. [16] A. Dirafzoon, N. Lokare, and E. Lobaton. Action classification from motion capture data using topological data analysis. In 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 1260–1264, Dec 2016. [17] Mikael Vejdemo-Johansson, Florian T. Pokorny, Primoz Skraba, and Danica Kragic. Cohomological learning of periodic motion. Applicable Algebra in Engineering, Communication and Computing, 26(1):5–26, Mar 2015. [18] Herbert Edelsbrunner and John Harer. Computational topology: an introduction. American Mathematical Soc., 2010. [19] Robert Ghrist. Barcodes: The persistent topology of data. Bull. Amer. Math. Soc. 45 (2008), 61-75, 45:61–75, 2008. [20] Frédéric Chazal, Vin de Silva, and Steve Oudot. Persistence stability for geometric complexes. Geometriae Dedicata, 173(1):193–214, 2014. [21] James R Munkres. Elements of algebraic topology, volume 2. Addison-Wesley Reading, 1984. [22] Shamsher Singh and KK Biswas. Biometric gait recognition with carrying and clothing variants. In Pattern Recognition and Machine Intelligence, pages 446–451. Springer, 2009. [23] Ait O Lishani, Larbi Boubchir, and Ahmed Bouridane. Haralick features for gei-based human gait recognition. In Microelectronics (ICM), 2014 26th International Conference on, pages 36–39. IEEE, 2014. 17