Action Recognition Using Log-Covariance Matrices of Silhouette and Optical-Flow (Proposed Framework)

20 Chapter 3 Proposed framework In the previous chapter, we reviewed state-of-the-art methods for action recognition. In this chapter, we will introduce our proposed framework, including action representation and action classification. Our approach represents an action using covariance matrix of local feature vectors. Then, an action video is classified using supervised learning algorithms: the nearest neighbor classifier or sparse linear approximation (SLA) classifier. 3.1 Action recognition as a supervised learning problem Action recognition is a supervised learning problem: given annotated training samples and a query sample, the goal is to classify the query sample based on the training set. There are roughly three classes of supervised learning methods: global methods, global methods with local structure, and local methods. Global methods treat data as abstract vectors living in high-dimensional Euclidean space and train classifiers directly in the high-dimensional representation, as shown in Fig. 3·1. The advantage of global methods is its compatibility with any classifier. Although it takes full consideration of the global structure of data, it ignores local structure that is useful for classification. Moreover, in the action recognition context, few training samples are available but they lie in extremely high-dimensional space (e.g., a 128×128×20 video clip is approximately vectorized into a 3×105-dimensional vector). It is thus unfeasible, in practice, to learn the global statistical characteristics 21 Figure 3·1: Action representation using global methods. of the high-dimensional vector. As an alternative to global methods, over the last decade or so, global methods with apriori local structure have emerged, as shown in Fig. 3·2. These methods only Figure 3·2: Action representation using global methods with local structure. consider partial correlation within data by using graphical models, e.g., Markov Random Fields (MRF), as an a priori local data structure. Such methods are, however, still complex and the parameters of a graphical model are difficult to estimate on the account of very few training samples. With data dimensionality orders of magnitude larger than the number of training samples, in order to reliably represent an action video, we can extract a dense set of localized features from this video, the so-called “bag of local features”, as illustrated in Fig. 3·3. The advantage of such a “bag-of-features” action representation is that even from a single training video clip one can extract a very large number of local 22 Figure 3·3: Action representation using local methods. features (one per pixel) from which one can reliably learn the statistical properties of local features. As an example, a single 128 × 128 × 20 training video provides more than 3 × 105 local features. If the local features are sufficiently discriminative, then a high classification accuracy can be realized. 3.2 3.2.1 Action representation Feature Covariance matrices One undesirable aspect of the bag of local features is that as a representation its dimensionality is even larger than the video clip from which it was extracted –the number of pixels is multiplied by the size of the feature vector. It is, therefore, desirable to reduce its dimensionality in the feature space. Ideally, one would like to learn the probability density function (pdf) of these local feature vectors. This, however, is not only computationally-intensive, but it may not lead to a lower-dimensional representation: a kernel-based density estimation algorithm needs to, in-effect, store all the samples used to form the estimate. The mean feature-vector, which is lowdimensional, can be learned reliably and rapidly but may not be sufficiently discriminative. This is corroborated by our results in Chapter 6.5, where action recognition based on just the mean feature vector performs poorly. Inspired by Tuzel et al.’s work (Tuzel et al., 2006; Tuzel et al., 2008), we discovered that if features are well- 23 chosen, then the feature-covariance matrix can provide a remarkably discriminative representation for action recognition. The main claim of this thesis is that a feature covariance matrix is “sufficient” for action recognition. In addition to their simplicity and effectiveness, covariance matrices of local features have low storage and processing requirements. Our action representation based on a bag of local features and their low-dimensional covariance matrix is illustrated in Fig. 3·4. For example, 13-dimensional local feature vectors described in Section 4.1 (see Fig. 4·3) lead to a 13 × 13 covariance matrix that has 91 independent entries due to its symmetry. Figure 3·4: Action representation based on a low-dimensional covariance matrix of a bag of local feature vectors. Let I(x, y, t) denote a video sequence and F = {fk } denote a “bag of feature vectors” extracted from the video. Let the size of the feature set |F | be N. The empirical covariance matrix defined on F is N 1 X C := (fk − µ)(fk − µ)T , N − 1 k=1 where µ is the mean feature vector: µ = PN k=1 fk . (3.1) The covariance matrix provides a natural way to fuse multiple feature vectors. The dimension of the covariance matrix is only related to the dimension of the feature vectors. If fk is d dimensional, then C is a d × d matrix. Due to its symmetry, C has only (d2 + d)/2 independent numbers. Since d is usually much less than N, C usually lies in a much lower dimensional space than the “bag of feature vectors” that need N × d dimensions. 24 3.2.2 Log-covariance matrices Covariance matrices do not lie in Euclidean space, but instead they form a convex cone. For example, the space of covariance matrices is not closed under multiplication with negative scalers. Most of the common machine learning methods work on Euclidean spaces and thus covariance matrices are not suitable features. One idea to solve this problem is to map the convex cone of covariance matrices to the vector space by using the matrix logarithm, proposed by Arsigny et al. (Arsigny et al., 2006), as shown in Fig. 3·5. The log-covariance matrix LS of a covariance matrix CS is computed as follows. Suppose that the eigen-decomposition of CS is given by CS = V DV ′ , where the columns of V are orthonormal eigenvectors and D is the e ′ , where D̃ is a diagonal diagonal matrix of eigenvalues. Then LS = log(CS ) = V DV matrix obtained from D by replacing D’s diagonal entries by their logarithms. Figure 3·5: Matrix logarithm that maps covariance matrices from a convex cone to Euclidean space. There are three key ingredients in our action representation method: • Dense bag of local features, • Feature covariance matrices, • Log-covariance matrices. 25 We define an operator Ψ which transforms an input video clip into an output logcovariance matrix representation, as shown in Fig. 3·6. Figure 3·6: Operator Ψ composed of three ingredients in action representation. 3.3 Classification We have introduced an action representation using low-dimensional log-covariance matrices of a “bag of features”. The next problem is how to classify a query action sample based on the representations of training samples. The general framework for action classification is shown in Fig. 3·7. In this thesis, we investigate two learning approaches for action classification: the nearest neighbor classification and sparse linear approximation (SLA) classification. 3.3.1 Nearest-neighbor classification Nearest-neighbor (NN) classification is one of the most widely used algorithms in supervised learning. The idea is simple and straightforward: given a query sample, find out the most similar sample (under some distance measure) in the annotated training set and assign its label to the query sample as described in Fig. 3·8. The success of NN classification strongly depends on the distance measure that is used. Therefore, we firstly introduce two appropriate distance metrics for covariance matrices: affine-invariant Riemannian metric and log-Euclidean metric. Then, 26 Figure 3·7: Ψ operator that includes the three ingredients in action representation. Figure 3·8: Diagram of NN-based classifier. we analyze the possible reason why log-Euclidean metric outperforms the Euclidean metric in NN classification. 27 Distance metrics The set of covariance matrices of a given dimension does not form a vector space (it forms a convex cone). The Euclidean distance does not correctly capture the topology of the convex cone of symmetric non-negative definite matrices. This is corroborated by the experimental results of Chapter 6.5, where a simple NN classification algorithm using the Euclidean metric to measure distances between covariance matrices performs poorly. There are at least two metrics defined on the Riemannian manifold of covariance matrices that have been studied in the literature, namely, the affineinvariant Riemannian metric (Forstner and Moonen, 1999) and the log-Euclidean metric (Arsigny et al., 2006). A. Affine-invariant Riemannian metric The affine-invariant Riemannian metric ρ1 defined below was proposed by Forstner and Moonen (Forstner and Moonen, 1999), and has been successfully used in object tracking and face localization (Tuzel et al., 2006; Tuzel et al., 2008). If C1 and C2 are two covariance matrices, then, v u d uX −1 log2 λk (C1 , C2 ), ρ1 (C1 , C2 ) : = || log(C2 C1 )||2 = t (3.2) k=1 where log(·) denotes the matrix-logarithm, || · ||2 denotes the Frobenius norm on matrices, and λk (C1 , C2 ) are the generalized eigenvalues of C1 and C2 , i.e., λk C1 uk = C2 uk , (3.3) where uk 6= 0 is the k-th generalized eigenvector. This distance measure captures the manifold structure of covariance matrices and satisfies the metric axioms of positivity, symmetry, and triangle inequality. It is also invariant to invertible affine transformations of the local features, that is, if C1 and C2 are respectively the covariance matrices 28 of F1 and F2 and C̄1 and C̄2 are respectively the covariance matrices of AF1 + b1 and AF2 + b2 , where A is an invertible matrix, then, ρ1 (C1 , C2 ) = ρ1 (C1 , C2 ). B. Log-Euclidean metric The log-Euclidean metric ρ2 defined below and proposed by Arsigny et al. (Arsigny et al., 2006), is another Riemannian metric on the manifold of covariance matrices. We know that log-covariance matrices lie in a vector space. Then, distances between covariance matrices can be simply measured by any norm (the Frobenius norm in particular) in the transformed Euclidean space, specifically, ρ2 (C1 , C2 ) : = || log(C1 ) − log(C2 )||2 (3.4) where log(·) denotes matrix-logarithm and || · ||denotes the Frobenius norm on matrices. 3.3.2 Sparse linear classification In this subsection, we exploit discriminative nature of sparse linear representations (Wright et al., 2009) to perform action classification. This approach is generic and has been applied to many vision tasks, such as face recognition, image super-resolution and image denoising. The key idea underlying this approach is that if the training vectors of all the classes are pooled together and a query vector is expressed as a linear combination of the fewest possible training vectors, then the majority of the training vectors in the linear combination are likely to be of the same class as the query vector. The pooling together of the training vectors of all the classes is important for classification because the training vectors of each individual class may well span the space of all query vectors. The pooling together induces a “competition” among 29 the training vectors of different classes to approximate the query using the fewest possible training vectors. We extend this approach to action recognition by applying it to (column-wise) vectorized log-covariance matrices that we refer to as samples. Specifically, we approximate the log-covariance matrix of a query segment by a sparse linear combination of log-covariance matrices of all training segments. If there are sufficiently many training samples, it is likely that the log-covariance vector of the query sample can be well-approximated by a sparse linear combination of the log-covariance vectors of training samples that only come from the category of the query sample. Thus, the sparse coefficients of the linear combination are very informative since the non-zero coefficients, especially large ones, are likely to indicate the label of the query sample. This sparse representation can be obtained by solving an l1 − minimization problem using linear programming. We can then annotate the query sample based on the coefficients of the sparse linear representation. In this section, we first explain how the log-covariance matrix of a query action segment can be approximated by a sparse linear combination of log-covariance matrices of all training action segments by solving an l1 −norm minimization problem. We then discuss how the locations of large non-zero coefficients in the sparse linear approximation can be used to determine the query label. The overall classification framework based on these ideas is shown in Fig. 3·9. Sparse linear combination Suppose we have obtained the log-covariance vectors of training samples for each action class: Pi = [pi,1 , pi,2 , · · · , pi,ni ], where i denotes the i-th class and ni is the number of training samples in class i. We can stack up all the training samples column by column to form a matrix P := [P1 , P2 , · · · , PM ] ∈ RK×N , where K is the dimensionality of log-covariance vectors, M is the number of training action classes P and N = M j=1 nj . 30 L a b e l ( 1 ) p 1 ´ C 1 M a t r i x e l o g P S E G 1 & t v L a b e l ( 2 e o r i z a t i o n . . . c ) C 2 p M S E G a t r i x U l o 2 g 2 & . t v C e o r i z a t i o . . n c N p L a b e l ( N N ) * M a t r i x E l o g # z a r g m i z n 1 & S E G N . . . P t o r i z a t i o s v C o v a a r t r i a i n c c e e " n . t z . c e 1 s d " e D a s c c r t i i p t o ! p q u e r y n o r s m T r a i n i n g * † g s m n e t e s p C q u e r E G ¾ q u e r u e r y y M S q a t r i x 5 l o g y & t v e o r i z a t i o n c E Q u e r o v a r i a n c m e t i m a t e d q u e r y l a b e l e 1 g s y C e n " D a c t i o n t s a t r i x d e s c r i p t o r m Figure 3·9: Diagram of SLA classification. Given a query sample pquery , one may attempt to express it as a linear combination of training samples by solving the matrix-vector equation given by: pquery = P α ∈ RK , (3.5) where α ∈ RN is the coefficient vector. Since N ≫ K, the system of linear equations associated with pquery = P α is underdetermined and thus its solution α is not unique. We seek a sparse solution to (3.5) where, under ideal conditions, the only nonzero coefficients in α are those which correspond to the class of the test sample. Such a sparse solution can be found, in principle, by solving the following NP-hard optimization problem: α∗ = arg min kαk0 , s.t. pquery = P α, (3.6) where k · k0 denotes the l0 -norm, which counts the number of non-zero entries in a 31 vector. A key result in the theory of compressive sensing is that if the optimal solution α∗ is sufficiently sparse, then solving the l0 -minimization problem (3.6) is equivalent to solving the following l1 -minimization problem α∗ = arg min kαk1 , s.t. pquery = P α. (3.7) This problem is a convex optimization problem that can be solved in polynomial time. So far we have dealt with the l1 -minimization problem where pquery = P α is assumed to hold exactly. Since action segments may be noisy, it is more accurate to introduce a noise term z in this system as follows: pquery = P α + z, (3.8) where z is an additive noise term whose length is assumed to be bounded by ε, i.e., kzk2 ≤ ε. This leads to the following robust l1 -minimization problem: α∗ = arg min kαk1 , s.t. kP α − pquery k2 ≤ ε. (3.9) SLA-based classification algorithm We have introduced the SLA framework in which we are interested in finding the sparsest linear approximation α∗ of a test sample using training samples from a dictionary. We now describe how to use this framework for action recognition. Each coefficient of α∗ weighs the contribution of its corresponding training sample to the representation of the test sample. Ideally, the sparse non-zero coefficients should be only associated with the class of the test sample. However, in practice non-zero coefficients often relate to multiple action classes. Therefore, we need to examine these classes and estimate the class of the test sample. To this end, we follow Wright et. al, 2009, and use a measure called the reconstruction residual error (RRE). Let ∗ ∗ ∗ α∗i = [αi,1 , αi,2 , · · · , αi,n ] denote the coefficients associated with class i, corresponding i 32 to training matrix Pi . The RRE measure of class i is defined as: Ri (pquery ) = kpquery − Pi α∗i k2 . (3.10) To annotate the sample pquery we assign the class label that leads to the minimum RRE. The action recognition algorithm based on sparse representation framework can be summarized as follows: 1. Compute the log-covariance descriptor for each action segment; 2. Given pquery , solve the l1 -minimization problem (3.9) to obtain α∗ ; 3. Compute RRE for each class i based on (3.10); 4. Annotate the query sample pquery as: label(pquery ) = arg mini Ri (pquery )