Twodimensional approximately harmonic projection for gait recognition
Ziqiang Wang^{1} , Xia Sun^{2} , Lijun Sun^{3}
^{1, 2, 3}School of Information Science and Engineering, Henan University of Technology, Zhengzhou 450001, China
Journal of Vibroengineering, Vol. 15, Issue 2, 2013, p. 693702.
Received 2 February 2013; accepted 3 June 2013; published 30 June 2013
JVE Conferences
This paper presents a twodimensional approximately harmonic projection (2DAHP) algorithm for gait recognition. 2DAHP is originated from the approximately harmonic projection (AHP), while 2DAHP offers some advantages over AHP. 1) 2DAHP can preserve the local geometrical structure and cluster structure of image data as AHP. 2) 2DAHP encodes images as matrices or secondorder tensors rather than onedimensional vectors, so 2DAHP can keep the correlation among different coordinates of image data. 3) 2DAHP avoids the singularity problem suffered by AHP. 4) 2DAHP runs faster than AHP. Extensive experiments on gait recognition show the effectiveness and efficiency of the proposed method.
Keywords: dimensionality reduction, approximately harmonic projection, matrix representation, gait recognition.
1. Introduction
Recently, the average silhouettesbased human gait recognition has received extensive attention due to its potential applications in many fields [14], such as identity authentication and video surveillance. In general, a binary silhouette image of size 128×88 in the USF HumanID gait database is represented as a vector in the image space ${\mathbb{R}}^{\text{128\xd788}}$. Consequently, a major challenge of gait recognition is that the captured gait image often lies in a highdimensional image space. Due to the consideration of the curse of dimensionality, a common way to resolve this problem is to use dimensionality reduction techniques. Once we obtain lowerdimensional representations of the original gait images, the traditional classification methods can be applied in the reduced feature space. Therefore, the main objective of this paper is to find techniques that can introduce lowerdimensional feature representations of gait images with enhanced discriminatory power.
The most representative algorithms for dimensionality reduction are principal component analysis (PCA) and linear discriminant analysis (LDA) [5]. Although PCA and LDA have been successfully applied to face recognition, image retrieval, and gait recognition, they are designed for discovering only the global Euclidean structure, whereas the local manifold structure is ignored. In fact, the global statistics such as variance is often difficult to compute when there are no sufficient samples. In addition, a number of research efforts have shown that the images possibly reside on a nonlinear submanifold and the representation of image is fundamentally related to the problem of manifold learning [69]. Given a set of highdimensional data points, manifold learning techniques aim to discover the geometric properties of the data space. In the past years, a number of manifold learning algorithms have been developed, representative algorithms include locally linear embedding (LLE) [10], ISOMAP [11], and Laplacian eigenmaps (LE) [12]. LLE is designed to maintain the local linear reconstruction relationship among neighboring points in the lowerdimensional space. ISOMAP aims to preserve global geodesic distances of all pairs of samples. LE aims to preserve proximity relationships by manipulations on an undirected weighted graph, which indicates neighbor relations of pairwise samples. These nonlinear methods do yield impressive results on some artificial benchmarks and several real applications. However, they suffer from the out of sample problem, i.e., they can only obtain mappings that are defined on the training data points and how to explicitly calculate the mappings on novel testing data points remains unclear. Therefore, these nonlinear manifold learning algorithms might not be suitable for gait recognition. To cope with the out of sample problem, locality preserving projection (LPP) [13] applies a linearization procedure to construct explicit mappings over new samples. In the recent research, Lin et al. [14] point that utilizing the affine hulls of the manifold and the connected components is more effective for preserving the local geometrical structure and cluster structure of original data, and propose a new algorithm termed approximately harmonic projection (AHP) for dimensionality reduction. AHP is a linear manifold learning method based on the harmonic framework, and the optimal transformation can be obtained by approximating the Dirichlet integral. It is worth noting that all these methods unfold input data into vectors before dimensionality reduction. But images are naturally in the form of secondorder or higherorder tensors [1517]. For example, graylevel images represent secondorder (matrix), and Gaborfiltered image represents thirdorder tensors. Consequently, such kind of vectorization largely increases the computational costs and seriously destroys the intrinsic tensor structure of images. To cope with these issues, multilinear extensions of PCA, LDA, and LPP, namely 2DPCA [18], 2DLDA [19], and 2DLPP [20] are proposed, respectively. These methods aim to conduct subspace analysis by directly encoding images as twodimensional image matrices rather than onedimensional vectors. The advantages of using imageasmatrix representation have been indeed consistently pointed out in a number of recent research efforts [1520], especially when the number of training samples is small. Nevertheless, the multilinear (tensor) extension of AHP and its application to gait recognition are still a research area where few people have tried to explore.
This paper represents a graylevel average silhouette image of size ${n}_{1}\times {n}_{2}$ as the matrix (or secondorder tensor) in the tensor space ${\mathbb{R}}^{{n}_{1}}\times {\mathbb{R}}^{{n}_{2}}$. Then a twodimensional approximately harmonic projection (2DAHP) is proposed by tensorizing AHP. Compared with the original AHP, 2DAHP can directly process gait images in their original matrix form and utilize correlations among pixels within different dimensions (i.e., rows and columns). Moreover, the smaller number of data entries along each data dimension facilitates subspace learning with limited training data. 2DAHP is much more computational efficient since the decomposed matrices are of size ${n}_{1}\times {n}_{1}$ or ${n}_{2}\times {n}_{2}$, which is much smaller than that of size $n\times n(n={n}_{1}\times {n}_{2})$ in AHP. 2DAHP can avoid the singularity problem. In addition, the trace ratio optimization technique is also applied to efficiently solve 2DAHP.
The remainder of this paper is organized as follows. Section 2 briefly reviews AHP. Section 3 introduces our proposed 2DAHP algorithm. Experimental results on gait recognition are presented in Section 4. The concluding remarks are provided in Section 5.
2. Brief review of approximately harmonic projection (AHP)
AHP is a recently proposed linear manifold learning method for dimensionality reduction [14]. It is based on the approximate affine hull and explicitly utilizes the edge length to reflect the geometrical structure of the manifold structure of the data space.
Given a set of data points $\{{x}_{1},\cdots ,{x}_{n}\}\subset {\mathbb{R}}^{m}$, let $X=[{x}_{1},\cdots ,{x}_{n}]$. Let ${W}^{c}$ and ${W}^{b}$ be two weight matrices defined on the data points. The optimal projection of AHP can be obtained by solving the following minimization problem:
with the constraint:
where ${e}_{ij}={x}_{j}{x}_{i}$ represents an edge vector that has an orientation from ${x}_{i}$ to ${x}_{j},$${d}_{ij}=\Vert {x}_{j}{x}_{i}\Vert $ denotes the length of the edge between ${x}_{i}$ and ${x}_{j}$, $t$ is the arc length of ${e}_{ij}$. ${W}^{c}$ and ${W}^{b}$ are two matrices defined as follows: if ${x}_{i}$ and ${x}_{j}$ are connected, then ${W}_{ij}^{c}=1/{d}_{ij}$ and ${W}_{ij}^{b}={d}_{ij};$ otherwise, ${W}_{ij}^{c}={W}_{ij}^{b}=0.$${D}^{c}$and ${D}^{b}$ are two diagonal matrices defined as ${D}_{ii}^{c}={\sum}_{j}{W}_{ij}^{c}$, ${D}_{ii}^{b}={\sum}_{j}{W}_{ij}^{b}$. $\nabla {f}_{{e}_{ij}}$ denotes the gradient on each edge, its definition is as follows:
Unlike the standard spectral graph methods which mainly consider the connectivity of graph, AHP explicitly makes use of the edge length and edge orientation which reflect the geometrical structure of the manifold. Therefore, AHP can precisely model multiple connected components of the data manifold, which is especially important for discriminating data with different submanifold (cluster) structure.
The objective function in AHP aims to use the approximate affine hull of the graph to separate data points sampled from different components. Therefore, minimizing it is to ensure that if ${x}_{i}$ and ${x}_{j}$ lie in the multiple connected components, then ${y}_{i}(={a}^{T}{x}_{i})$ and ${y}_{j}(={a}^{T}{x}_{j})$ are made close by the optimal projection. Finally, the projection vector $a$ that minimizes (1) is given by the minimum eigenvalue solution to the generalized eigenvalue problem:
Note that, in the appearancebased image analysis, one is often confronted with the fact the dimension of image vector is much smaller than the number of images. Thus, the matrix $X(2{D}^{b}+{W}^{b}){X}^{T}$ is singular. To avoid the singularity problem, one may first apply PCA to remove the components corresponding to zero eigenvalues. Thus, the projection vector of AHP can be considered as the eigenvectors of the matrix ${\left(X\right(2{D}^{b}+{W}^{b}\left){X}^{T}\right)}^{1}X({D}^{c}{W}^{c}){X}^{T}$ associated with the smallest eigenvalues. In addition, since ${\left(X\right(2{D}^{b}+{W}^{b}\left){X}^{T}\right)}^{1}X({D}^{c}{W}^{c}){X}^{T}$ is not usually symmetric, the AHP projection axes are not orthogonal.
Let the column vector of ${a}_{1},{a}_{2},\cdots ,{a}_{d}$ be the solution of (4) ordered according to their eigenvalues ${\lambda}_{1}<{\lambda}_{2}<\cdots <{\lambda}_{d}$. Thus, the embedding is given by ${x}_{i}\to {y}_{i}={A}^{T}{x}_{i}$, where ${y}_{i}$ is a $d$dimensional vector and $A=({a}_{1},{a}_{2},\cdots ,{a}_{d})$ is an $n\times d$ matrix.
3. Twodimensional approximately harmonic projection (2DAHP)
Given a set of data points ${\left\{{X}_{i}\right\}}_{i=1}^{n}$ in the secondorder tensor (or matrix) space ${\mathbb{R}}^{{n}_{1}}\otimes {\mathbb{R}}^{{n}_{2}}$, let ${\left\{{u}_{i}\right\}}_{i=1}^{{n}_{1}}$ be an orthonormal basis of ${\mathbb{R}}^{{n}_{1}}$ and ${\left\{{v}_{j}\right\}}_{j=1}^{{n}_{2}}$ be an orthonormal basis of ${\mathbb{R}}^{{n}_{2}}$, it has been shown that $\{{u}_{i}\otimes {v}_{j}\}$ forms a basis of the tensor space ${\mathbb{R}}^{{n}_{1}}\otimes {\mathbb{R}}^{{n}_{2}}$ [20]. Thus, a secondorder tensor $X$ can be uniquely defined as $X=\sum _{i,j}\left({u}_{i}^{T}X{v}_{j}\right){u}_{i}{v}_{j}^{T}$.
Given a set of data points ${\left\{{X}_{i}\right\}}_{i=1}^{n}$ in ${\mathbb{R}}^{{n}_{1}}\otimes {\mathbb{R}}^{{n}_{2}}$, twodimensional approximately harmonic projection (2DAHP) aims to find two projection matrices $U\in {\mathbb{R}}^{{n}_{1}\times {l}_{1}}$ and $V\in {\mathbb{R}}^{{n}_{2}\times {l}_{2}}$ that maps each data point ${X}_{i}\left(i=1,\cdots ,n\right)$ to a lowerdimensional matrix representation ${Y}_{i}\in {\mathbb{R}}^{{l}_{1}}\times {\mathbb{R}}^{{l}_{2}}(i=1,\cdots n,{l}_{1}<{n}_{1},{l}_{2}<{n}_{2})$ by ${Y}_{i}={U}^{T}{X}_{i}V$ such that ${Y}_{i}$ represents ${X}_{i}$.
Let $U$ and $V$ be the projection matrices, according to (1) and (2), the optimal objective function of 2DAHP with the matrix representation can be rewritten as follows:
with the constraint:
where ${d}_{ij}$ is similarly defined as AHP.
Let ${Y}_{i}={U}^{T}{X}_{i}V$ and ${D}^{c}$ be a diagonal matrix, ${D}_{ii}^{c}={\sum}_{j}{W}_{ij}^{c}$. Since ${\Vert A\Vert}^{2}=\text{Tr}\left(A{A}^{T}\right)$, we have:
where ${P}_{V}^{c}=\sum _{i}{D}_{ii}^{c}{X}_{i}V{V}^{T}{X}_{i}^{T}$ and ${Q}_{V}^{c}=\sum _{i,j}{W}_{ij}^{c}{X}_{i}V{V}^{T}{X}_{j}^{T}$. Similarly, ${\Vert A\Vert}^{2}=\text{Tr}\left({A}^{T}A\right)$, so we can also obtain:
where ${P}_{U}^{c}=\sum _{i}{D}_{ii}^{c}{X}_{i}^{T}U{U}^{T}{X}_{i}$ and ${Q}_{U}^{c}=\sum _{i,j}{W}_{ij}^{c}{X}_{i}^{T}U{U}^{T}{X}_{j}.$ Consequently, we should simultaneously minimize $\text{Tr}\left({U}^{T}\right({P}_{V}^{c}{Q}_{V}^{c}\left)U\right)$ and $\text{Tr}\left({V}^{T}\right({P}_{U}^{c}{Q}_{U}^{c}\left)V\right)$.
In addition, similar to the above derivation process, the left side of constraint function equation (6) can be converted to:
where ${P}_{V}^{b}=\sum _{i}{D}_{ij}^{b}{X}_{i}V{V}^{T}{X}_{i}^{T}$, ${Q}_{V}^{b}=\sum _{i}{W}_{ij}^{b}{X}_{i}V{V}^{T}{X}_{j}^{T}$, ${P}_{U}^{b}=\sum _{i}{D}_{ij}^{b}{X}_{i}^{T}U{U}^{T}{X}_{i}$, ${Q}_{U}^{b}=\sum _{i}{W}_{ij}^{b}{X}_{i}^{T}U{U}^{T}{X}_{j},$ and ${D}^{b}$ is a diagonal matrix, ${D}_{ii}^{b}={\sum}_{j}{W}_{ij}^{b}$.
Finally, the optimal objective function (5) subject to (6) can be transformed as:
Because of difficulty in solving the optimal $U$ and $V$ simultaneously, we follows the similar computational methods as [20] to compute $U$ and $V$ iteratively. We first initialize $U$ with an identity matrix, then $V$ can be approximately computed with generalized eigenvalue decomposition (GED) by transforming the optimal objective function (11) into the tractable ratio trace form $\text{Tr}\left({\left({V}^{T}\right(2{P}_{U}^{b}+{Q}_{U}^{b}\left)V\right)}^{1}\right({V}^{T}({P}_{U}^{c}{Q}_{U}^{c})V\left)\right)$. That is, $V$ can be regarded as the eigenvectors associated with the minimum eigenvalues of the following generalized eigenvector problem:
Once $V$ is obtained, similarly, we can update $U$ by solving the following generalized eigenvector problem:
Therefore, we can obtain the final optimal $U$ and $V$ by iteratively solving the generalized eigenvector problems (12) and (13).
In the preceding section, we approximately computed the the optimal objective functions of (10) and (11) by converting them into ratio trace problems, which are solved by GED. However, the obtained solutions may deviate from the original objectives, which may lead to uncertainty in subsequent classification [21]. To address these problems, we describes how to directly solve (10) and (11) with the Iterative algorithm for the Trace Ratio (ITR) optimization problem introduced in [21]. To compute $U$, we first fix $V$ and initialize ${U}^{0}$ as an arbitrary columnly orthogonal matrix. In each iterative step, we solve a trace difference problem ${U}^{t}=\mathrm{a}\mathrm{r}\mathrm{g}\underset{{U}^{T}U=I}{\mathrm{m}\mathrm{i}\mathrm{n}}\text{Tr}\left({U}^{T}\right(({P}_{V}^{c}{Q}_{V}^{c}){\lambda}^{t}(2{P}_{V}^{b}+{Q}_{V}^{b})\left)U\right)$, where ${\lambda}^{t}$ is the trace ratio value calculated from the projection matrix ${U}^{t1}$ of the previous step, i.e., ${\lambda}^{t}=\text{Tr}\left({U}^{t{1}^{T}}\right({P}_{V}^{c}{Q}_{V}^{c}\left){U}^{t1}\right)/\text{Tr}\left({U}^{t{1}^{T}}\right(2{P}_{V}^{b}+{Q}_{V}^{b}\left){U}^{t1}\right)$. Once $U$ is obtained, similarly, we can update $V$ by solving ${V}^{t}=\mathrm{a}\mathrm{r}\mathrm{g}\underset{{V}^{T}V=I}{\mathrm{m}\mathrm{i}\mathrm{n}}\text{Tr}\left({V}^{T}\right(({P}_{U}^{c}{Q}_{U}^{c}){\lambda}^{t}(2{P}_{U}^{b}+{Q}_{U}^{b})\left)V\right)$ where ${\lambda}^{t}=\text{Tr}\left({V}^{t{1}^{T}}\right({P}_{U}^{c}{Q}_{U}^{c}\left){V}^{t1}\right)/\text{Tr}\left({V}^{t{1}^{T}}\right(2{P}_{U}^{b}+{Q}_{U}^{b}\left){V}^{t1}\right)$. Finally, output the final $U$ and $V$ when the iterative algorithm converges to optimal solutions. The detailed iteration algorithm for solving (10) and (11) can be presented as follows:
Algorithm1: The iteration algorithm for directly solving the optimal problem (10) and (11) in 2DAHP.
Step 1: Initialize ${U}^{0}$ and ${V}^{0}$ as two arbitrary columnwise orthogonal matrices.
Step 2: For $t=\mathrm{1,2},\cdots {T}_{\mathrm{m}\mathrm{a}\mathrm{x}}$, do
Step 2.1: Calculate the trace ratio value ${\lambda}^{t}$ according to the projection matrix ${U}^{t1}$:
Step 2.2: Obtain the new ${U}^{t}$ by solving the following eigendecomposition problem:
Step 2.3: For the given ${U}^{t}$, calculate the trace ratio value ${\lambda}^{t}$ according to the projection matrix ${V}^{t1}$:
Step 2.4: Obtain the new ${V}^{t}$ by solving the following eigendecomposition problem:
where ${\tau}_{0}^{t}\le {\tau}_{1}^{t}\le \cdots \le {\tau}_{d1}^{t}$ are the $d$ smallest eigenvalues, and ${V}_{i}^{t}$ is the eigenvector associated with eigenvalue ${\tau}_{i}^{t}$, which constitutes the ith column vector of the matrix ${V}^{t}$.
Step 2.5: If $\Vert {U}^{t}{U}^{t1}\Vert <\sqrt{d}\epsilon $ and $\Vert {V}^{t}{V}^{t1}\Vert <\sqrt{d}\epsilon $, then break.
Step 3: Output the projection matrices $U={U}^{t}$ and $V={V}^{t}$.
From the above algorithemic procedure, it can be easily observe that the obtained projection matrices $U$ and $V$ are orthogonal. In addition, following the conclusions in [21], the above iteration algorithm will converge to an optimal value. For more details about proof of convergence, please refer to [21].
4. Experimental results
In this section, to investigate the performance of our proposed 2DAHP algorithm for gait recognition, we compare the 2DAHP algorithm with 2DPCA [18], 2DLDA [19], 2DLPP [20], and the original AHP [14] algorithms for gait recognition on the wellknown USF HumanID gait database, where 2DPCA, 2DLDA, and 2DLPP are three popular tensor methods in face recognition and gait recognition, and the original AHP algorithm is a vectorbased algorithm. The settings of these compared algorithms are identical to the description in the corresponding papers. In addition, to cope with the singular problem existed in the original AHP, we apply PCA to remove the components corresponding to zero eigenvalues before carrying out AHP. For 2DAHP, we empirically set the optimal iteration number ${T}_{\mathrm{m}\mathrm{a}\mathrm{x}}$ as 5 for each probe set, since the latter experimental results show that the 2DAHP algorithm converges quite quickly.
The USF HumanID gait database is constructed by Sarkar et al. [1], it contains 1870 sequences from 122 individuals walking on an elliptical path in front of two cameras. This database provided one gallery set containing the sequences from 122 individuals and 12 probe sets containing different numbers of individuals varying from 33 to 122 for algorithm training and testing, respectively. More details information about the USF HumanID gait database can be found in [1]. In this gait database, we consider sequences of binary silhouette images. As in [22] and [23], we construct the average silhouettebased gait image representation: First, a complete sequence is partitioned into several subsequences according to the gait period length ${N}_{gait}$ provided by Sarkar et al. [1]. Then, the binary silhouette images within each gait cycle of a sequence are averaged to acquire several graylevel average silhouette images according to:
where $\left\{T\right(1),\cdots ,T(F\left)\right\}$ represents the binary images for one sequence with $F$ frames, $\lfloor F/{N}_{gait}\rfloor $ denotes the largest integer less than or equal to $F/{N}_{gait}$. Since numerous researches have experimentally shown that the average silhouette image is more effective and efficient than the original binary silhouette image for human gait recognition, we also utilize the average silhouette image for gait recognition. Fig. 1 shows some original binary images and the average silhouette images of two different individuals, where the first seven images and the last image in each row denote the binary silhouette images and the average silhouette images, respectively. As can be seen, different individuals have different average silhouette images.
To perform gait recognition, we first obtain the average silhouette image subspaces by dimensionality reduction algorithms. Then, all the averaged images from both the gallery set and probe sets are projected into the image subspaces. Finally, the nearestneighbor classifier is adopted to identify new average silhouette images, where the distance measure uses the median operator for its robust to noise [1, 23]:
where $L{S}_{P}\left(i\right)$, $i=1,\cdots ,{N}_{p}$ and $L{S}_{G}\left(j\right)$, $j=1,\cdots ,{N}_{g}$ are the lower representations from one probe sequence and one gallery sequence, respectively, ${N}_{p}$ and ${N}_{g}$ denote the total number of average silhouette images. For each dimensionality reduction algorithm, we only show its performance in the $l$ or $(l\times l)$ dimensional subspace. For each case, we average the results over 20 random splits of training and testing sets.
Fig. 1. Some original binary images and the average silhouette images of two different individuals in the USF HumanID gait database
The recognition accuracies are shown in Table 1 and Table 2, where Rank1 indicates that the correct subject is ranked as the top candidate, Rank5 means that the correct subject is ranked among the top five candidates, and Average denotes the recognition rate among all the probe sets. Moreover, we also plot the recognition rate variance with different numbers of iterations for probe sets A, B, C, D, E, F, G, H, I, J, K and L in Fig. 2. Finally, we report the running times of 2DAHP and AHP in Table 3.
From the experimental results listed in Table 13 and Fig. 2, we can have the following observations:
1) Our proposed 2DAHP consistently outperforms the 2DPCA, 2DLDA, 2DLPP, and AHP algorithms, which demonstrates that it is beneficial to use simultaneously twodimensional matrix representation as well as the local geometrical structure and cluster structure for gait recognition.
2) 2DPCA performs the worst among the compared algorithms. A possible explanation is as follows: similar to the traditional PCA, the 2DPCA is simply achieves object reconstruction and it is not necessarily useful for discriminating gait images with different subjects which is the ultimate goal of gait recognition.
3) The 2DLDA performs comparatively to 2DLPP. This demonstrates that it is hard to evaluate whether local manifold structure or class label information is more important, which is consistent with existing studies.
4) The 2DAHP algorithm converges quite quickly for probe sets A, B, C, D, E, F, G, H, I, J, K and L, and recognition rates changes slightly with different iteration numbers. After about 5 iterations, 2DAHP can converge to the optimal solution in all 12 probe sets.
5) 2DAHP achieves significant speed up comparing to AHP. Theses results are consistent with the theoretical analysis of the efficiency, i.e., 2DAHP can utilize the intrinsic tensor structure of gait images to improve running efficiency.
Table 1. Performance comparison in terms of Rank1 recognition results (%)
Probe

A

B

C

D

E

F

G

H

I

J

K

L

Average

2DPCA

86

87

75

26

27

18

19

56

61

53

10

11

44.1

2DLDA

89

91

82

33

33

23

25

67

78

67

19

19

52.2

2DLPP

90

92

81

34

36

22

24

69

82

65

18

20

52.8

AHP

88

90

78

32

40

21

20

64

79

61

13

15

50.1

2DAHP

93

94

85

45

48

26

33

84

84

69

27

22

59.2

Fig. 2. Some original binary images and the average silhouette images of two different individuals in the USF HumanID gait database
a)
b)
c)
d)
e)
f)
g)
h)
i)
j)
k)
l)
Table 2. Performance comparison in terms of Rank5 recognition results (%)
Probe

A

B

C

D

E

F

G

H

I

J

K

L

Average

2DPCA

89

94

88

51

53

44

42

80

79

64

22

17

60.3

2DLDA

97

99

95

58

57

50

50

86

93

77

43

40

70.5

2DLPP

95

98

93

59

60

48

51

88

91

75

45

41

70.3

AHP

91

95

89

60

59

49

48

85

82

69

29

26

65.2

2DAHP

99

100

96

75

77

56

60

94

94

83

46

38

76.4

Table 3. Running time(s) comparison on the USF HumanID gait database
Probe

A

B

C

D

E

F

G

H

I

J

K

L

AHP

2.51

1.17

1.18

2.64

1.29

2.48

1.32

2.41

1.31

2.40

1.06

1.08

2DAHP

0.32

0.15

0.15

0.34

0.21

0.30

0.19

0.30

0.18

0.28

0.10

0.11

5. Conclusions
This paper introduces a tensor dimensionality reduction algorithm called twodimensional approximately harmonic projection (2DAHP). Compared with the original AHP, 2DAHP can directly conducts subspace analysis by encoding an image as a twodimensional matrix and has higher computational efficiency. Experimental results on gait recognition have demonstrated the effectiveness and efficiency of our proposed approach.
Acknowledgements
This work is supported by NSFC (Grant No. 70701013), the National Science Foundation for PostDoctoral Scientists of China (Grant No. 2011M500035), and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No.20110023110002).
References
 Sarkar S., Phillips P. J., Liu Z., Vega I. R., Grother P., Bowyer K. W. The HumanID gait challenge problem: data sets, performance, and analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, Issue 2, 2005, p. 162177. [Search CrossRef]
 Han J., Bhanu B. Individual recognition using gait energy image. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 28, Issue 2, 2006, p. 316322. [Search CrossRef]
 Wang L., Tan T., Ning H., Hu W. Silhouette analysisbased gait recognition for human identification. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 25, Issue 12, 2003, p. 15051518. [Search CrossRef]
 Xu D., Yan S., Tao D., Lin S., Zhang H.J. Marginal fisher analysis and its variants for human gait recognition and content based image retrieval. IEEE Transactions on Image Processing, Vol. 16, Issue 11, 2007, p. 28112821. [Search CrossRef]
 Duda R. O., Hart P. E., Stork D. G. Pattern Classification. Second Edition, WileyInterscience, Hoboken, 2000. [Search CrossRef]
 He X., Yan S., Hu Y., Niyogi P., Zhang H.J. Face recognition using laplacianfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, Issue 3, 2005, p. 328340. [Search CrossRef]
 Cai D., He X., Han J., Zhang H.J. Orthogonal laplacianfaces for face recognition. IEEE Transactions on Image Processing, Vol. 15, Issue 11, 2006, p. 36083614. [Search CrossRef]
 Yan S., Xu D., Zhang B., Zhang H.J., Yang Q., Lin S. Graph embedding and extensions: a general framework for dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 29, Issue 1, 2007, p. 4051. [Search CrossRef]
 Mu Y., Tao D. Biologically inspired feature manifold for gait recognition. Neurocomputing, Vol. 73, Issue 46, 2010, p. 895902. [Search CrossRef]
 Roweis S. T., Saul L. K. Nonlinear dimensionality reduction by locally linear embedding. Science, Vol. 290, Issue 5500, 2000, p. 23232326. [Search CrossRef]
 Tenenbaum J. B., Silva V., Langford J. C. A global geometric framework for nonlinear dimensionality reduction. Science, Vol. 290, Issue 5500, 2000, p. 23192323. [Search CrossRef]
 Belkin M., Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, Vol. 15, Issue 6, 2003, p. 13731396. [Search CrossRef]
 He X., Niyogi P. Locality preserving projections. Advances in Neural Information Processing Systems, 2003, p. 585591. [Search CrossRef]
 Lin B., He X., Zhou Y., Liu L., Lu K. Approximately harmonic projection: theoretical analysis and an algorithm. Pattern Recognition, Vol. 43, Issue 10, 2010, p. 33073313. [Search CrossRef]
 Tao D., Li X., Wu X., Maybank S. General tensor discriminant analysis and Gabor features for gait recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 29, Issue 10, 2007, p. 17001715. [Search CrossRef]
 Xu D., Yan S., Tao D., Zhang L., Li X., Zhang H.J. Human gait recognition with matrix representation. IEEE Transactions on Circuits and Systems for Video Technology, Vol. 16, Issue 7, 2006, p. 896903. [Search CrossRef]
 Yan S., Xu D., Yang Q., Zhang L., Tang X., Zhang H. Multilinear discriminant analysis for face recognition. IEEE Transactions on Image Processing, Vol. 16, Issue 1, 2007, p. 212220. [Search CrossRef]
 Yang J., Zhang D., Frangi A. F., Yang J. Y. Twodimensional PCA: a new approach to appearancebased face representation and recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, Issue 1, 2004, p. 131137. [Search CrossRef]
 Ye J., Janardan R., Li Q. Twodimensional linear discriminant analysis. Neural Information Processing Systems, 2005, p. 15691576. [Search CrossRef]
 He X., Cai D., Niyogi P. Tensor subspace analysis. Advances in Neural Information Processing Systems, 2005, p. 499506. [Search CrossRef]
 Wang H., Yan S., Xu D., Tang X., Huang T. Trace ratio vs. ratio trace for dimensionality reduction. Proceedings of the 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2007, p. 18. [Search CrossRef]
 Han J., Bhanu B. Statistical feature fusion for gaitbased human recognition. Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004, p. 842847. [Search CrossRef]
 Liu Z., Sarkar S. Simplest representation yet for gait recognition: averaged silhouette. Proceedings of the 17th International Conference on Pattern Recognition, 2004, p. 211214. [Search CrossRef]