Graph Embedding based Tensor Analysis for Gait Recognition

Graph Embedding based Tensor Analysis for Gait Recognition

Mr. Yashodhan Mandke

PG Student, TSSMs , Bhivrabai

Sawant College of Engg. & Research Savitribai Phule Pune University, Pune, India

Prof. D. V. Jadhav,

Prof. Risil Chhatrala

International Institute of Information Technology,

Savitribai Phule Pune University Pune, India

TSSMs Bhivrabai Sawant College of Engg. & Research Savitribai Phule Pune University

Pune, India

Abstract Human gait recognition faces the challenge in feature extraction due to covariate conditions such as carrying and clothing, view angle, aging and other several. The large amount of data is generated while analyzing the silhouettes of anindividual subject through different covariates. This leads to the higher computational cost and curse of dimensionality. In interest of paring down the same a graph embedding framework technique isenforced wherein any dimensionality reduction algorithm can be characterized in a common framework. An image when considered as a second order tensor helps in capturing the spatial relationship between the pixels. In this paper the tensor based dimensionality reduction algorithm is expressedthrough a graph embedding framework which helps to find out the hidden information lying in the lower dimensions of the manifold.

KeywordsGait Recognition; Feature Extraction; Graph Embedding,Tensor.

extracted silhouette the gait cycle extraction method is helpful wherein video sequence of one complete gait cycle is being mapped to single template; the process is called as temporal normalization. Mapping of temporal information, on to single template improves computational efficiency. Features extraction and discriminant analysis on gait template of walking person gives robust discriminative featuresthat are stored in the database as training. In testing mode, discriminative features from sample under test are compared with the one from training set by classification scheme to recognize human identity.

1. INTRODUCTION

   Various biometrics like fingerprint, iris endeavor very good recognition rate but needs subject compliance under controlled environment. In contrast gait-as behavioral biometric allows flexibility to capture subject gait signature without approval and cooperation. The working resolution requirement offered by gait is very low. These set of advantages offer gait as unique candidate for video surveillance application. The number of attempts made by researchers to improve recognition rate under experimental environment but found to degrade performance in presence of diverse factor known as covariates. Thus robust human gait recognition offers unique challenge for feature extraction in presence of covariates. Different covariates can be classified as 1) Conditions that affect gait itself like shoes, injury, speed, pregnancy, affliction of the legs or feet, drunkenness and time i.e. increase in age and 2). Conditions that affect features extracted from gait are carrying condition, clothing condition, view angle etc.

2. OVERVIEW OF GAITRECOGNITION

   Basic block diagram showing processing of video sequence of the silhouettes is shown in Figure 1. The human detection is attained by background subtraction andsilhouette extraction methods. Since the obtained silhouette is in a raw format, it is normalized so as make it unaltered for variation in zoom angle and alignment. To extract a gait cycle for analysis from binary

   Figure. 1: Basic Block Diagram of Gait Recognition

   1. BackgroundSubtractionand Binary Silhoutte Extraction

      Baseline algorithm proposed by Sarkaret. al [10] extracts the motion silhouette in each frame by background subtraction, within the semi-manually defined bounding boxes. For SOTON database the gait sequences are derived in the laboratory, aiming for near-perfect conditions to obtain the best possible silhouette [22]. The dynamic signature is obtained by chroma-key subtraction in conjunction with a connected components algorithm followed by windowing. Liang Wang et.al [20] has adopted change detection based on background subtraction. The improved version of background subtraction procedure can be applied to any realistic scene to extract moving silhouettes of walking figures from the background. The silhouettes are made binary so as to remove the coloring, intensity and illumination variation.

   2. Silhouette Normalization

      The raw binary silhouettes are reprocessed for size and scale normalization so as to have uniform height. Also the horizontal alignment of each silhouette is achieved by centering the upper half silhouette part with respect to its horizontal centroid [14].

   3. Gait Cycle Extraction

   The temporal information in the gait progression can be perpetuated with the help of gait period detection since the human walking pattern may be considered as periodical motion.Sarkaret. al [10] had detected gait periodicity by a

   counting the number of foreground pixels Nf(t) mostly from leg region from bottom half of the silhouette in each frame over

   Let the silhouette sequence which is partitioned into subsequences of gait period length, denoted by Spk S k ,L S k N pk .

   For each subsequence the silhouettes are averaged to arrive at a set of average silhouettes.

   e. Gait Energy Image

   Anotherversion of average silhouettes is the Gait Energy Image (GEI) proposed by Han and Bhanu [2]. GEI represents gait averaged over a complete cycle in a single grey scale image. Given preprocessed binary gait silhouette images at time t in a sequence, the grey level gait energy image (GEI) is defined as

   N

   time. Gait period is estimated by computing averaging median 1 N

   of the distances between minima, skipping every other

   minimum. Chen wang et.al [9] has proposed to use degree of the individuals two legs apart from each other to represent regular human walking. Height and alignment normalization is used to improve gait period detection.

3. GAIT REPRESENTATION APPROACHES

   Most of the gait recognition methods focus on gait representation approaches in order to make it robust against covariate conditions and computationally efficient. A good representation of gait should be able to discriminate, be robust to noise and changing covariate conditions, be space efficient and be easy to compute and manipulate. Based on the way gait is represented, the existing gait recognition approaches can be divided into two categories: model based and model free approaches.

   1. Model Based Approach

      Model based approach represents gait using the parameters of a model of the body configuration. But this approach has menial achievement due to demand of high resolution images as input and subtlety to image noise, self-occlusion, shadows and view changes. This incurs a higher computational requirement.

   2. Model-Free Approach

      The approach constructs gait descriptor from motion dynamics of human bodies and/or static shape information of silhouettes in compact form. This presentation is more robust to noise, insensitive to the quality of silhouettes and has the advantage of low computational costs. However, they are usually not robust to viewpoints and scale.

   3. Single Template Based Gait Recognition Approach

      For the compact representation of gait sequence the approach converts video frames into a single image template. A gait cycle represented using a single image offers unique advantage of low computational complexity and robustness for noise in silhouette extraction. However, they ae vulnerable to appearance changes of the human silhouette.

   4. Average Silhouette Representation

      The average silhouette representation proposed by Liu and Sarkar[10] captures the shape of the template and temporal dynamics of gait. Thus many researchers have adapted this method as a choice.

      G(x, y) Bt (x, y) (1)

      t 1

      This simple representation loses the dynamical variation between successive frames but has useful properties. (1) No silhouette alignment is required. (2) Space efficient compact representation of gait. (3) Reduced effect of noise because of the averaging procedure.

      GEI representation captures explicitly the shape and dynamics of the subject. Pixels with high intensity values in a GEI correspond to body parts that move little during a walking cycle (e.g. head, torso), while pixels with low intensity values correspond to body parts that move constantly (e.g. lower parts of legs and arms). This explicit representation of shape makes the average silhouette (GEI) representation of gait vulnerable to appearance changes of the human silhouette caused by common conditions such as clothing and carrying.

      1. Average Silhouette (b) Gait Energy Image Figure. 2: Preprocessed Silhouettes

4. SPECTRAL REGRESSION AND SUBSPACE

LEARNING

Dimensionality reduction has been always a challenge in pattern recognition andmachine learning field. It preserves low dimensional features in order of increasing importance, making computationally efficient without compromising with discriminative effectiveness. The linear dimensionality algorithms such as PCA and LDAshows acceptable performance but face the challenges in real world problem when the data is sampled from nonlinear high dimensional space[5][12][13].Other methods such as Locally Linear Embedding (LLE), ISOMAP and Laplacian Eigenmap(LE)which are classified as manifold learning methods reduces the dimensionality and preserves the

significant inter relationship. LLE and LE tries to preserve the local geometry of data by mapping the neighboring points in the lower dimensional subspace of manifold [7][16].ISOMAP works with the global geometry by preserving it to local and global scales and mapping close points on the manifold to nearby points in low dimensional space and similar to farther points in the training dataset[7][18].

There are various endeavor have been made by minimizing objective function either with embedding function in linear or Hilbert space. But the computationturns up complex in time as well as in memory as it implicates Eigen decomposition of dense matrices[4][5][7][8]. Thus applying these methods to large datasets is futile. Some alternative approaches were attemptedby applying a kernel view but these techniques are data dependent and produce no result for unnoticed data. Spectral Regression (SR) algorithm proposed by Deng Caiet.al.[7] is based on regression and spectral graph theory. TheSR algorithm works with supervised, semi supervised and unsupervised data and provides efficient dimensionality reduction. To uncover intrinsic discriminative structure in the data, theSR technique constructs an affinity graph for labeled as well as unlabeled points in data and inturn the graph learns the responses from both types of points [7][19]. Moreover the general regression technique is then applied for learning the

B. Graph Embedding Framework

Graph embedding is a common framework which offers the unified view for the analysis of popular dimensionality reduction algorithms [1][3][5]. In order to minimize computational complexity of dimensionality reduction algorithms these are represented in graph embedding framework. Graph embedding methods represent each vertex of a graph as a low-dimensional vector that preserves similarities between the vertex pairs, where similarity is measured by a graph similarity matrix that characterizes certain statistical or geometric properties of the data set. The vector representations of the vertices can be obtained from the eigenvectors corresponding to the leading eigenvalues of the graph Laplacian matrix with certain constraints. [1][3][5]

VI. TENSOR LOCALITY PRESERVING PROJECTION

Tensor Locality Preserving Projection (TLPP) method which can be applied in a supervised or semi supervised fashion provides a way to linearly approximate the eigenfunctions of the Laplace Beltrami operator in a tensor space. Hence it can model the geometric and topological properties of an unknown manifold embedded in a tensor space with some data points sampled randomly from the manifold. Based on n data points

A , , A from a manifold M RI1…Ik , local geometric

embedding function.SR provides the regression framework to 1 n

learn the embedding functions which sidestep the issues with

structure of Mcan be constructed using graph G. The affinity

the Eigen decomposition computation for dense matrices.

1. GRAPH BASED TENSOR SUBSPACE ANALYSIS

   matrix is defined as

   on heat kernel as:

   S Sij n which is defined based

   n

   ANDGRAPH EMBEDDING FRAMEWORK

   The correlation between the nearby pixels of an image is

   F if A j O(K , A j )

   2

   s exp Ai A j / t

   (2)

   essential for finding a projection.Recently there has been a lot of interest in extending the ordinary vector-based subspace

   ij

   or Ai O(K , Ai );

   0 otherwise.

   learning approaches to tensor space. [6][15]

   A. Graph Based Tensor Subspace Analysis

   Let Ui Rli Ii i 1, , k be the corresponding transformation matrices. Based on the neighborhood graph G,

   Let

   T Rm1 Rm2

   be image represented as second order

   the optimization problem for TLPP can be expressed as:

   tensor capturing spatial relationship between the pixels and

   arg min Q(U1, . . . ,Uk )

   {uk }m1

   {vl }m2

   m m

   B s B 2

   k 1 ,

   l 1 be an orthonormal basis of

   R 1 and R 2

   i ij j F

   respectively. Further, Deng Cai et.al [7] has shown that i j

   {ui v j } forms a basis of tensor space

   Rm Rm

   .The

   A U A U 2 s

   projection of T on the basis

   1 2

   ui v j is computed as their inner

   i, j

   i1…k k j1…k k F

   ij,

   i1…k k F ii

   product as

   i j i

   Y T ,ui v j T ,u vT uTTv j

   s.t A U 2 d 1

   i

   (3)

   The vector based approaches are linear i.e.

   yi aT Xi where

   If the points

   Ai and

   Aj are far apart then the objective function

   Xi Rm , a

   is projection vector and yi

   is single dimensional

   suffer from high penalty. Higher the value of the dii the point that is represented by Aiis more important in the tensor

   embedding on the projection vector. Hence tensor based approach is multilinear with yi uT Tiv . The tensor basis uvT

   space.Let yif be denoted as Ai 1 U1 f 1 U f 1,…, Uk .The optimization function that is based on tensor properties as well

   will have m1 m2 degrees of freedom with m values. The

   as on trace is as follows:

   constraint for tensor approach by considering as a special case of the vector approach is as follows:

   arg min Pf U f

   aim1( j1) uiv j

   = T ' ( f ) ( f ) ( f ) ( f ) T

   tr U f si, j Yi

   -Yj

   Yi

   -Yj

   U f ;

   whereai,ui and vj are the i-th elements in a,u and v respectively.

   i, j

   T '

   s.t tr U s

   Y( f ) -Y( f ) Y( f ) -Y( f ) T

   U f =1 (4)

   1. EXPERIMENTAL RESULTS:

      The USF gait dataset consists of 1870 silhouette sequences

      f i, j i j i j

      i, j

      Since the information lies in the lower dimension of manifold; solving for the eigenvectors corresponding to the lfsmallest eigenvalues in the generalized eigenvalue eqation

      from 122 subjects spanning 5 covariate conditions. Each sample is third-order tensors of size 32x22x10.The total samples used are 731. The histogram count computed is a vector of 71 values.

      T

      Y( f ) -Y( f ) Y( f ) -Y( f )

      s u

      Y( f ) Y( f )T d

      u (5)

      i j i j ij i i ii

      i, j

      i

      The computation of the matrix U f called as transformation

      matrix which is unknown can be obtained by solving for the smallest eigenvalue as above.

      TLPP Algorithm:[1][3][5][8]

      Input:

      A1, , An

      from

      M RI1…Ik and l1 … lk .

      Step 1. Construct G and compute S;

      Step 2. Steps for computation of embedding are as follows:

      Results:

      Figure. 3: Binary Silhouettes

      Initialize

      U 0 I

      1

      I

      1

      ,…,U 0 I

      k Ik ;

      Table I. shows results for proposed algorithm on USF dataset for rank 1 and rank 5 recognition rates.

      For t = 1,,Tmaxdo For f = 1,..,kdo

      Table I: Recognition Rate on USF database

      Probe	Variation	Total Objects	Covariates Difference Between Gallery and Probe	Rank 1	Rank 5
      A	(G, A, L, NB, t1)	122	View	73	85
      B	(G, B, R, NB, t1)	54	Shoe	62	75
      C	(G, B, L, NB, t1)	54	View, Shoe	35	65
      D	(C, A, R, NB, t1)	121	Surface	22	32
      E	(C, B, R, NB, t1)	60	Surface, Shoe	14	28
      F	(C, A, L, NB, t1)	121	Surface, View	8	25
      Average				35.67	51.6

      y f A U … U U … U

      i i 1 1 f 1 f 1 f 1 f 1 k k ;

      yif f Yi( f )

      i, j

      ;

      i j i j ij

      H1

      H2

      (Y( f ) -Y( f ) )(Y( f ) -Y( f ) )T s

      i i ii

      ;

      Y( f ) Y( f )T d

      i ;

      H1U t H U t ,U t Rlf I f ;

      f 2

      U t U t 1

      f k f

      if f f F

      for each fthen

   2. CONCLUSION

      break; end if end for end for

      i

      Output:

      Ui U t Rli Ii (i 1,.., k)

      Pertaining to the tensor embedding methods which accepts data directly in the form of tensors of arbitrary order as input, TLPP algorithm has been applied to the gait images.This method exploits the intrinsic local geometric and topological properties of the manifold; they are pleading in terms of dimensionality reduction. Forgait recognition experiments based on the USFdataset, tensor embedding methods gives a profound result with binary silhouettes.

   3. ACKNOWLEDGMENT

The authors would like to thank Prof. M.S.Deshpande, Head, Electronics & Telecommunication department, B.S.C.O.E.R, Pune and Dr. Mrs.A.M.Deshpande,Professor Electronics & Telecommunication department, B.S.C.O.E.R, Pune for the constant support and guidelines .

REFERENCES

1. S.Yan,Benyu Zhang,H.J.Zhang,Q.Yang and Stephen Lin, Graph Embedding and Extensions: A General Framework for Dimensionality ReductionIEEE Transaction on Pattern Analysis and Machine Intelligence, Vol.29, No.1, January 2007.

2. Ju Han and Bir Bhanu, Individual Recognition UsingGait Energy Image, IEEE Transaction on Pattern Analysis and Machine Intelligence,American Association for Artificial Intelligence, 2006.

3. Guang Dai and Dit-Yan Yeung, Tensor Embedding Methods, in Magnetism, vol. III, G.T. Rado and H. Suhl, Eds. New York: Academic, 1963, pp. 271-350.

4. Deng Cai, Xiaofei He and Jiawei Han, Spectral Regression: A Unified Subspace Learning Framework for Content-Based Image Retrieval, ACM Multimedia,Augsburg, Germany, Sep. 2007.

5. Xinaofei He, Deng Cai and ParthaNiyogi, Tensor Subspace Analysis Advances in Neural Information Processing Systems 18 (NIPS'05),Vancouver, Canada, 2005.

6. Deng Cai, Xiaofei He, Haifeng Liu, and Jiawei Han, Image Clustering with Tensor Representation,,Advances in Pattern Recognition, Springer Edition, ISBN 978-0-85729-123-3.

7. Deng Cai, Spectral Regression: A Regression Framework for Efficient Regularized Subspace Learning, PhD Thesis, Department of Computer Science,UIUC, 2009.

8. Xiaofei He and ParthaNiyogi,Locality preserving projections,Advances in Neural Information Processing Systems, Vol.16, 2004.

9. C. Wang, J. Zhang, J. Pu, X. Yuan, and L. Wang,Chrono-Gait Image: A Novel Temporal Template for Gait Recognition,Springer Computer Vision ECCV 2010,vol. 21, no. 4, .

10. S.Sarkar, P. Phillips, Zongyi Liu, I.Robledo Vega, P.Grother, and K. Bowyer,The HumanID Gait Challenge Problem: Data Sets, Performance, and Analysis,IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. 27, no. 2, Feb. 2005.

11. Deng Cai, Xiaofei He and Jiawei Han,''Spectral Regression: A Unified Subspace Learning Framework for Content-Based Image Retrieval'', ACM Multimedia 2007, Augsburg, Germany, Sep. 2007.

12. USF Gait Database. Available: http://figment.csee.usf.edu/GaitBaseline/

13. I. Joliffe, Principal Component Analysis,Springer-Verlag, 1986.

14. A.M. Martinez and A.C. Kak, PCA versus LDA,IEEE Transaction Pattern Analysis and Machine Intelligence,vol. 23, no. 2, pp. 228-233, Feb. 2001.

15. H.-T. Chen, H.-W. Chang, and T.-L. Liu,Introduction to Smooth Manifolds,Internal Conference on Computer Vision and Pattern Recognition, New York, 2002.

16. Z. Zhang, Maodi Hu and Y. Wang, A Survey of Advances in Biometric Gait Recognition,CCBR,2011:244-251.

17. Deng Cai, Xiaofei He, and Jiawei Han. "Isometric Projection", Proc. 22nd Conference on Artifical Intelligence (AAAI'07), Vancouver, Canada, July 2007.,

18. M.Belkin and ParthaNiyogi,"Laplacian eigenmaps for dimensionality reduction and data representation, Neural Computation,Vol.16, 2004.

19. F. R. K. Chung. "Spectral Graph Theory", volume 92 ofRegional Conference Series in Mathematics. 1997.

20. Liang Wang, Tieniu Tan, HuazhongNing, Weiming Hu, "Silhoutte analysis based gait recognition for human identification, ",, IEEE transaction Pattern Analysis and Machine Intelligence, Vol. 25, No. 12, pp. 1505-1518, 2003.

21. Ju Han and Bir Bhanu,Human Recognition at a Distance in Video,ACM Multimedia 2005,Nov. 2005, Hilton, Singapore.

22. Southampton Human ID at a Distance database,Available

:http://www.gait.ecs.soton.ac.uk/database/.