Bag of Visual Words and Fusion Methods for Action Recognition: Comprehensive Study and Good Practice

Introduction

Human action recognition AggarwalR11; TuragaCSU08 has become an important area in computer vision research, whose aim is to automatically classify the action ongoing in a video. It is one of the challenging problems in computer vision for serval reasons. Firstly, there are large intra-class variations in the same action class, caused by various motion speeds, viewpoint changes, and background clutter. Secondly, the identification of an action class is related to many other high-level visual clues, such as human pose, interacting objects, and scene class. These related problems are very difficult themselves. Furthermore, the determination of temporal extent for an actions is more subjective than a static object, which means there is no precise definition about when an action starts and finishes. Finally, the high dimension and low quality of video data usually add difficulty to developing robust and efficient recognition algorithm.

Early approaches interpret an action as a set of space-time trajectories of 2-dimensional or 3-dimensional points of human joints Webb81; NiyogiA94; CampbellB95; YacoobB99. These methods usually need dedicate techniques to detect body parts or track them at each frame. However, the detection and tracking of body part is still an unsolved problem in realistic videos. Recently, recognition methods using local spatiotemporal features Laptev05; LaptevMSR08; WangKSL13; WangQT14 have become the main stream and obtained the state-of-the-art performance on many datasets WangS13a. These methods do not require algorithms to detect human body, which treat the action volume as a rigid 3D-object and extract appropriate features to describe the patterns of each 3D volume. They are robust to background clutter, illumination changes, and noise.

Meanwhile, unlike static image, video data exhibits different views of visual pattern, such as appearance, motion, and motion boundary, and all of them play important roles in action recognition. Therefore, multiple descriptors are usually extracted from a cuboid and each descriptor corresponds to the specific aspect of the visual data WangKSL13; LaptevMSR08. BoVW is mainly designed for a single descriptor and ignores the problem of fusing multiple descriptors. Many research works have been devoted to fusing multiple descriptor for boosting performance GehlerN09; VedaldiGVZ09; TangYLK13; WangS13a; CaiWPQ14. Typical fusion methods include descriptor level fusion LaptevMSR08; WangWQ12, representation level fusion Wang13; WangKSL13, and score level fusion TangYLK13; MyersNHPNSHKSSS14. For descriptor level fusion, multiple descriptors from the same cuboid are concatenated as a whole one and fed into BoVW framework. For representation level fusion, the fusion is conducted in the video level, where each descriptor is firstly fed into BoVW framework independently and the resulting global representations are then concatenated to train a final classifier. For score level fusion, each descriptor is separately input into BoVW framework and used to train a recognition classifier. Then the scores from multiple classifiers are fused using arithmetic mean or geometric mean. In general, these fusion methods are developed in different scenarios and adapted for action recognition by different works. How these fusion methods influence the final recognition of BoVW framework and whether there exists a best one for action recognition is an interesting question and well worth of a detailed investigation.

Several related study works have been performed about encoding methods for image classification ChatfieldLVZ11; HuangWWT14 and action recognition WangWQ12. But these study works are with image classification task or lacking full exploration of all steps in BoVW framework. Meanwhile, the study work of action recognition WangWQ12 is limited regarding the evaluation dataset and ignores the influence of fusion methods. This article aims to provide a comprehensive study of all steps in BoVW and different fusion methods, and uncover some good practice to produce a state-of-the-art action recognition system. Our work is mainly composed of three parts:

Exploration of BoVW. We place an emphasis on extensively explorations about all components in BoVW pipeline and discovery of useful practice tips. Specifically, we investigate two widely-used local features, namely Space Time Interest Points (STIPs) with HOG, HOF Laptev05, and Improved Dense Trajectories (iDTs) with HOG, HOF, MBH WangS13a. For feature encoding methods, the current approaches can be roughly classified into three categories: (i) voting based encoding methods, (ii) reconstruction based encoding methods, (iii) super vector based encoding methods. For each type of encoding methods, we choose several representative approaches and totally analyze ten encoding methods. Meanwhile, we explore the relations among these different encoding methods and provide an unified and generative perspective over these encoding methods. We fully explored eight pooling and normalization strategies for each encoding method. From our extensive study of different components in BoVW, server good practice can be concluded:

Dense features with more descriptors are more informative in capturing the content of video data and suitable for action recognition. Meanwhile, dense features may exhibit different properties with sparse features with respect to variations of BoVW such as codebook size and encoding methods.

Data pre-processing is an important step in BoVW pipeline and able to greatly improve the final recognition performance.

Basically, high dimensional representation of super vector is more effective and efficient than the other two types of encoding methods.

In above, every step is crucial for contributing to the final recognition rate. Improper choice in one of the steps may counteract the performance improvement of other steps.

Investigation of Fusion Methods. As combination of multiple descriptors is very crucial for performance improvement, we also investigate the influence of different fusion methods inour designed action recognition system. Specifically, we study three kinds of fusion methods, namely descriptor level fusion, representation level fusion, and descriptor level fusion. We find that the way different descriptors correlate with each other determines the effectiveness of fusion methods. The performance gain obtained from fusing multiple descriptors mainly owns to their complementarity. We observe that this complementarity is not only with multiple descriptors, but also with multiple BoVW models. Based on this view, we propose a new representation, called hybrid representation, combining the outputs of multiple BoVW models of different descriptors. This representation utilizes the benefit of each BoVW and fully considers the complementarity among them. In spite of its simplicity, this representation turns out to be effective for improving final recognition rate.

Comparison with the State of the Art. Guided by the practice tips concluded from our insightful analysis of BoVW variants and feature fusion methods, we design an effective action recognition system using our proposed hybrid representation, and demonstrates its performance on three challenging datasets: HMDB51 KuehneJGPS11, UCF50 ReddyS13, and UCF101 SOOMRO12. Specifically, we leverage the richness and effectiveness of low-level features, design a hybrid super vector, a combination of Fisher vector PerronninSM10 and SVC-$k$, and resort to representation level fusion to boost final recognition performance. From comparison with other methods, we conclude that our recognition system reaches the state-of-the-art performance on the three datasets, and our hybrid representation acts as a new baseline for further research of action recognition.

The rest of this paper is organized as follows. In Section 2, we give an detailed description of each step in BoVW framework of action recognition system. Meanwhile, we uncover several useful techniques commonly adopted in these encoding methods, and provide a unified generative perspective over these encoding methods. Then, several fusion methods and a new representation are introduced in Section 3. Finally, we empirically evaluate the BoVW frameworks and fusion methods on three challenging datasets. We analyze these experiment results and uncover good practice for constructing a state-of-the-art action recognition system. We conclude the paper in Section 5.

Framework of Bag of Visual Words

As shown in Figure 1, the pipeline of Bag of Visual Words (BoVWs) framework consists of five steps: (i) feature extraction, (ii) feature pre-processing, (iii) codebook generation, (iv) feature encoding, and (v) pooling and normalization. Then the global representation is fed into a classifier such as linear SVM for action recognition. In this section, we will give detailed descriptions of the popular technical choices in each step, which are very important for constructing a state-of-the-art recognition system. Furthermore, we summarize several use techniques in these encoding methods and provide a unified generative perspective over these different encoding methods.

Low-level local features have become popular in action recognition due to their robustness to background clutter and independence on detection and tracking techniques. These local features are typically divided into two parts: detecting a local region (detector) and describing the detected region (descriptor) WangUKLS09. Many feature detectors have been developed such as 3D-Harris Laptev05, 3D-Hessian WillemsTG08, Cuboid DollarRCB05, Dense Trajectories WangKSL13, and Improved Dense Trajectories WangS13a. These detectors try to select locations and scales in video by maximizing certain kind of function or using dense sampling strategy. To describe the extracted region, several hand-crafted features have been designed such as Histogram of Oriented Gradients (HOG) LaptevMSR08; WangKSL13, Histogram of Oriented Flow (HOF) LaptevMSR08; WangKSL13, and Motion Boundary Histogram (MBH) WangKSL13; WangS13a. Multiple descriptors are usually adopted to represent the local region, each of which corresponds to a certain aspect of visual pattern such as static appearance, motion, and motion boundary.

Among these local features, Space Time Interest Points (STIPs) Laptev05 and Improved Dense Trajectories (iDTs) WangKSL13 are widely used due to their easy usages and good performance. STIPs resort to 3D-Harris to extract regions of high motion salience, which resulting a set of sparse interest points. For each interest point, STIPs extracted two kinds of descriptors, namely HOG and HOF. iDTs features are an improved version from Dense Trajectories (DTs), where a set of dense trajectories are firstly obtained by tracking pixels with median filter, and five kinds of descriptors are extracted, namely trajectory shape, HOG, HOF, MBHx, and MBHy. iDTs improve the performance of DTs by taking into account camera motion correction. Generally speaking, iDTs resort to more sophisticated engineering skills and integrate much richer low-level visual cues compared with STIPs. Therefore, they represent two different kinds of low level features, namely sparse features and dense features, and may exhibit different properties with respect to variants of BoVWs.

2 Feature Pre-processing

The low-level local descriptors are usually high dimensional and strong correlated, which results in great challenges in the subsequent unsupervised learning such as $k$-means clustering and GMM training. Principal component analysis (PCA) Bishop06 is a statistical procedure to pre-process these features, which uses orthogonal transform to map feature into a set of linearly uncorrelated variables called principal components. Typically, the number of used principal components is less than the number of original variables, thus resulting in dimension reduction. Whitening technique usually follows the PCA, which aims to ensure the feature have the same variance through different dimensions. The transform formula of pre-processing is as followings:

where $\mathbf{f}\in R^{M}$ is the original feature, $\mathbf{x}\in R^{N}$ is the PCA-whitened result, $U\in R^{M\times N}$ is the dimension reduction matrix from PCA, $\Lambda$ is the diagonal whitening matrix $diag(\Lambda)=[1/\sqrt{\lambda_{1}},\cdots,1/\sqrt{\lambda_{N}}]$, and $\lambda_{i}$ is the $i^{th}$ largest eigenvalue of covariance matrix.

It is worth noting that this step is not necessary and many previous encoding approaches skip this step, such as Vector Quantization SivicZ03, Sparse Coding YangYGH09, and Vector of Locally Aggregated Descriptor JegouPDSPS12. However, in our evaluation, we found this step is of great importance to improve the recognition performance.

3 Codebook Generation

In this section, we present the codebook generation algorithms used for the following feature encoding methods. Generally there are two kinds of approaches: (i) partitioning the feature space into regions, each of which is represented by its center, called codeword, and (ii) using generative model to capture the probability distribution of features. $k$-mean Bishop06 is a typical method for the first type, and Gaussian Mixture Model (GMM) Bishop06 is widely used for the second.

The problem is to find values for $\{r_{mk}\}$ and $\{\mathbf{d}_{k}\}$ to minimize the objective function $\mathcal{J}$. Usually, we can optimize it in an iterative procedure where each iteration involves two successive steps corresponding to optimization with respect to the $r_{nk}$ and $\mathbf{d}_{k}$. The details can be found in Bishop06.

GMM. Gaussian Mixture Model is a generative model to describe the distribution over feature space:

where $K$ is mixture number, and $\theta=\{\pi_{1},\mu_{1},\Sigma_{1},\cdots,$ $\pi_{K},\mu_{K},\Sigma_{K}\}$ are model parameters. $\mathcal{N}(\mathbf{x};\mu_{k},\Sigma_{k})$ is $D$-dimensional Gaussian distribution.

$k$-means algorithm performs a hard assignment of feature descriptor to codeword, while the EM algorithm of GMM makes soft assignment of feature to each mixture component based on posterior probabilities $p(k|x)$. But unlike $k$-means, GMM delivers not only the mean information of code words, but also the shape of their distribution.

4 Encoding Methods

In this section, we provide a detailed description of thirteen feature encoding methods. According to the characteristics of encoding methods, they can be roughly classified into three groups, namely (i) voting based encoding method, (ii) reconstruction based encoding method, and (iv) super vector encoding method, as shown in Table 1.

Voting based encoding methods SivicZ03; GemertVSG10; LiuWL11; HuangHYT11; WuHWT12 are designed from the perspective of encoding process and each descriptor directly votes for the codeword using a specific strategy. A $K$-dimensional ($K$ is the size of codebook) code $\mathbf{s}$ is constructed for each single descriptor to represent the votes of the whole codebook. Methods along this line include Vector Quantization(or Hard Voting) SivicZ03, Soft Assignment (or Kernel Codebook Coding) GemertVSG10, Localized Soft Assignment LiuWL11, Salient Coding HuangHYT11, and Group Salient Coding WuHWT12, as shown in Figure 2.

For each descriptor $\mathbf{x}$, the voting value for the codeword $\mathbf{d}_{i}$ can be viewed as a function of $\mathbf{x}$, namely $\mathbf{s}(i)=\phi(\mathbf{x})$. Different encoding methods differ in the formulation of $\phi(\mathbf{x})$. For encoding of Vector Quantization (VQ):

where each descriptor $\mathbf{x}$ only votes for its nearest codeword. The VQ encoding method can be viewed as a hard quantization and may cause much information loss. To encounter this problem, Soft Assignment (SA) encoding method votes for all the codewords:

where $\omega_{i}$ is the normalized weight of descriptor $\mathbf{x}$ with respect to codeword $\mathbf{d}_{i}$:

where $\beta$ is a smoothing factor controlling the softness of the assignment. Considering the manifold structure in the descriptor space, localized Soft Assignment (SA-$k$) votes for its $k$-nearest codewords:

where $I(\mathbf{x},\mathbf{d}_{i})$ is the indicator function to identify whether $\mathbf{d}_{i}$ belongs to the $k$ nearest neighbor of $\mathbf{x}$:

Note that VQ can be viewed as a special case of SA-$k$ when $k$ is set as $1$.

Figure 2 illustrates the difference of these voting based encoding methods. VQ, Salient coding, and Group salient coding are all hard assignment strategies. Unlike VQ, the Salient coding employs the difference between the closest visual word and the other $k-1$ closest ones to obtain the voted weight but not 1. The detailed formulations of Salient coding and Group salient coding can be found in Table 1.

4.2 Reconstruction based encoding methods

Reconstruction based encoding methods YangYGH09; WangYYLHG10; YuZG09; TroppG07 are designed from the perspective of decoding process, where the codes $\mathbf{s}$ are enforced to reconstruct the input descriptor $\mathbf{x}$. This kind of algorithm includes Orthogonal Matching Pursuit (OMP) TroppG07, Sparse Coding (SPC) YangYGH09, Local Coordinate Coding(LCC) YuZG09, and Locality-constrained Linear Coding (LLC) WangYYLHG10. Typically, these encoding methods are formulated in a least square framework with a regularization term:

where the least square term enforce the small reconstruction error, $\psi(\mathbf{s})$ encourages some properties of codes $\mathbf{s}$, $\lambda$ is a weight factor to balance this two terms.

OMP and SPC is empirically observed to tend to be local, i.e. nonzero coefficients are often assigned to bases nearby to the encoded data YuZG09. But this locality can not be ensured theoretically and they suggested a modification to SPC, called Local Coordinate Coding (LCC). This encoding method explicitly encourages the coding to be local, and they theoretically pointed out that under certain assumptions locality is more essential than sparsity, for successful nonlinear function learning using the obtained codes. Specifically, the LCC is defined as follows:

where $\odot$ denotes the element-wise multiplication, $\mathbf{\hat{e}}$ is the locality adaptor that give weights for each basis vector proportional to its similarity to the input descriptor $\mathbf{x}$:

where $\mathbf{e}$ is the exponentiation of $\mathbf{\hat{e}}$:

where $\sigma$ is used for adjusting the weighted decay speed for the locality adaptor. The constraint $\mathbf{1}^{T}\mathbf{s}=1$ follows the shift-invariant requirements of the final code vector. In practice, an approximate solution can be used to improve the computational efficiency of LLC. It directly selects the $k$ nearest basis vectors of $\mathbf{x}$ to minimize the first term in Equation (9) by solving a much smaller linear system. This gives the code coefficients for the selected $k$ basis vectors and other code coefficients are simply set to be zero.

4.3 Super vector based encoding methods

Super vector based encoding methods yield a very high dimensional representation by aggregating high order statistics. Typical methods include Local Tangent-based Coding (LTC) YuZ10, Super Vector Coding (SVC) ZhouYZH10, Vector of Locally Aggregated Descriptors (VLAD) JegouPDSPS12, and Fisher Vector (FV) PerronninSM10 .

Local Tangent-based Coding YuZ10 assumes that codebook and descriptors are embedded in a smooth manifold. The main contents of LTC are manifold approximation and intrinsic dimensionality estimation. Under the Lipschitz smooth condition, the nonlinear function $f(\mathbf{x})$ can be approximated by a local linear function as:

where $\alpha$ is a positive scaling factor to balance the two types of codes. Super Vector Coding (SVC) ZhouYZH10 is a simple version of LTC. Unlike LTC, SVC yields the $\mathbf{s}(i)$ via VQ and does not apply PCA to the term of $\mathbf{s}(i)(\mathbf{x}-\mathbf{d}_{i})$. Consequently, the coding vector of SVC is defined as follows:

where $\mathbf{s}(i)=1$, $\mathbf{d}_{i}$ is the closest visual word to $\mathbf{x}$, and $\alpha$ is a positive constant.

Fisher vector is another super vector based encoding method derived from fisher kernel JaakkolaH98 and is introduced for large-scale image categorization PerronninSM10. The fisher kernel is a generic framework which combines the benefits of generative and discriminative approaches. As it is known, the gradient of the log-likelihood with respect to a parameter can describe how that parameter contributes to the process of generating a particular example. Then the video can be described by the gradient vector of log likelihood with respect to the model parameters JaakkolaH98:

Note that the dimensionality of this vector depends on the number of parameters in $\theta$. Perronnin et al. PerronninSM10 developed an improved fisher vector which is as follows,

where $\gamma_{k}$ is the weight of local descriptor $\mathbf{x}$ to $k^{th}$ Gaussian Mixture:

The final fisher vector is the concatenation this two gradients:

Vector of Locally Aggregated Descriptors (VLAD) JegouPDSPS12 can be viewed as a hard version of FV and only keeps the $1^{st}$ order statistics:

where $\mathbf{s}(i)=1$, $\mathbf{d}_{i}$ is the closest visual word to $\mathbf{x}$.

4.4 Relations of Encoding Methods

In this section, we summarize several practical techniques widely used in these encoding methods, and give a unified generative perspective of these encoding methods. This analysis will uncover the underline relations between these methods and provide insights for developing new encoding methods.

From “hard” to “soft”. These encoding methods transform local features from descriptor space to codeword space. There are two typical transformation rules in these methods, namely hard assignment and soft assignment. Hard assignment quantizes the feature descriptor into a single codeword, while soft assignment enables the feature descriptor to vote for multiple codewords. In general, soft assignment accounts for the codeword uncertainty and plausibility GemertVSG10, and reduces the information loss during encoding. This technical skill of soft assignment can be found in several encoding algorithms, such as SA-$all$ vs. VQ, and VLAD vs. Fisher Vector. By the same techniques, we can extend the VLAD to VLAD-$all$, SVC to SVC-$all$:

where $\omega_{i}$ is the normalized weight of feature descriptor $\mathbf{x}$ with respect to codeword $\mathbf{d}_{i}$ defined in Equation (6).

From “global” to “local”. In several encoding methods, the manifold structure in descriptor space is captured to improve the stability of encoding algorithms. In the traditional soft assignment, each descriptor is assigned with all the codewords, which is called global assignment. However, in the high dimensional space of feature descriptor, Euclidian distance may be not reliable especially when the codeword is outside the neighborhood of feature descriptor. Therefore, in the encoding methods such as SA-$k$ and LLC, each descriptor is enforced to only vote for these codewords belonging to its $k$-nearest neighbors, called local assignment. In general, the incorporation of local structure in encoding methods is able to improve the stability and reduce the sensitivity to noise in descriptor. Using the same techniques, we can also extend the VLAD-$all$ to VLAD-$k$, SVC-$all$ to SVC-$k$ by replacing the $\omega_{i}$ in Equation (25), (26) with localized $\omega_{i}^{\prime}$ defined in Equation (7):

From “zero order statistics” to “high order statistics”. In these super vector based encoding methods, they preserve not only the affiliations of descriptors to codewords (zero order statistics), but also the high order information such as the difference between descriptors mean and codeword, thus resulting a high-dimensional super vector representation. As these super vectors keep much richer information for each codeword, the codebook size is usually much smaller than that of voting and reconstruction based encoding methods. Above all, these super vector is with high dimension, storing more information, and is proved to outperform the other two kinds of encoding methods in Section 4. The high dimensional super vector will be a promising representation and designing effective dimension reduction algorithms for super vector will be an interesting problem.

Generative perspective of encoding methods. Although these encoding methods are developed in different scenarios, a unified generative probabilistic model can be used to uncover the underline relations among them. These encoding methods can be interpreted in a latent generative model:

For encoding methods such as VQ, SA-$all$, VLAD-$all$, and Fisher vector, they choose the prior distribution $p(\mathbf{h})$ as follows:

VLAD-$all$ and SVC-$all$ can be viewed as the gradient embedding in this extreme case.

For encoding methods such as sparse coding, the latent variable $\mathbf{h}$ is continuous and its corresponding prior distribution is specified as:

This prior distribution is called Laplace prior and sparse coding can be viewed as the latent variable embedding of this generative model using the maximum a posteriori value (MAP), i.e. $\mathbf{s(x)}=\arg\max_{\mathbf{h}}p(\mathbf{h}|\mathbf{x})$.

5 Pooling and Normalization Methods

Given the code coefficients of all local descriptors in a video, a pooling operation is often used to obtain a global representation $\mathbf{p}$ for the video. Specifically, there are two common pooling strategies:

Sum Pooling. With sum pooling scheme LazebnikSP06, the $k^{th}$ component of $\mathbf{p}$ is $p_{k}=\sum_{n=1}^{N}\mathbf{s}_{n}(k)$.

Max Pooling. With max pooling scheme YangYGH09, the $k^{th}$ component of $\mathbf{p}$ is $p_{k}=\max(\mathbf{s}_{1}(k),\cdots,\mathbf{s}_{N}(k))$, where $N$ is the number of extracted local descriptors, $\mathbf{s}_{n}$ denotes the code of descriptor $\mathbf{x}_{n}$.

In BoureauPL10, the authors presented a theoretical analysis of average pooling and max pooling. Their results indicate sparse features may prefer max pooling.

To make this representation invariant to the number of extracted local descriptors, the pooling result $\mathbf{p}$ is further normalized by some methods. Generally, there are three common normalization techniques:

Power Normalization. In power normalization PerronninSM10, we apply in each dimension the following function:

Recently, a special normalization strategy is proposed for the VLAD, called intra-normalization ArandjelovicZ13. In this paper, we extend it to all the super vector based encoding algorithms. This method carries out normalization operation in a block by block manner, where each block denotes the vector related to one codeword. Generally, the intra-normalization can be formulated as follows:

Feature Fusion

Fusing multiple local features has turned out to be an effective method to boost the performance of recognition system in computer vision community GehlerN09; VedaldiGVZ09; TangYLK13; WangS13a; CaiWPQ14. The video data is usually characterized in multiple views, such as static appearance, motion pattern, and motion boundary. The essence of multi-view data requires fusing different features for action recognition. In this section, we present several feature fusion methods for action recognition, and analyze its corresponding properties. Meanwhile, based on the analysis of fusion methods, we propose a simple yet effective representation, called hybrid representation.

As shown in Figure 3, the fusion methods are usually conducted in different levels, typically including: descriptor level, representation level, and score level. For descriptor level fusion, it is performed in the cuboid level, where multiple descriptors from the same cuboid are concatenated into a single one, and then it is fed into the BoVW to obtain the global representation. For representation-level fusion, it is performed in the video level, where different descriptors are input into BoVW separately and the resulting global representations are fused as a single one, which is further fed into classifier for recognition. For score-level fusion, it is also performed in the video level, but the representations of different descriptors are used independently for classifier training. The final recognition score is obtained by fusing the scores from multiple classifiers. For fusing the scores, arithmetical mean or geometrical mean is often used.

In general, these fusion methods at different levels owns their pros and cons, and the choice of fusion method should be guided by the dependence of descriptors. If these multiple descriptors from the same cuboid are highly correlated, it will be better to resort to descriptor level feature fusion. Otherwise, the choice of descriptor level fusion is not a good one, as descriptor level fusion usually results in a higher dimension and adds the difficulty for unsupervised feature learning such as $k$-means and sparse coding. For the case where different views of features are less correlated in cuboid level but highly correlated in video level, representation level fusion is usually a good choice. When these different features are independently with each other, it will be appropriate to choose score level fusion, as this fusion reduce the dimension for classifier training and make the learning faster and more stable.

The performance boosting of fusing multiple features mainly owns the complementarity of these features. However, the complementarity can be explored not only for different features, but also for different types of BoVW methods. As shown in Figure 3, we propose a simple yet effective representation, called hybrid representation, which combines the outputs from multiple variants of BoVW and multiple descriptors. The resulting hybrid representation effectively explores the complementarity of different encoding methods and greatly enhances the descriptive power for action recognition. As we shall see in Section 4.7, this representation will improve the recognition rate of a single BoVW model and obtain the state-of-the-art results on the three challenging datasets.

Empirical Study

In this section, we describe the detailed experimental settings and the empirical study of variants of BoVW and different fusion methods. We first introduce the datasets used for evaluation and their corresponding experimental setup. We then extensively study different aspects of BoVW, including pre-processing techniques, encoding methods, pooling strategies, and normalization approaches. After that, we explore the different choices of fusion methods for multiple features. Finally, we compare the performance of our hybrid representation with that of the state-of-the-art methods on three challenging datasets.

We conduct experiments on three public datasets: HMDB51 KuehneJGPS11, UCF50 ReddyS13, and UCF101 SOOMRO12. Some examples of video frames are illustrated in Figure 4. Totally, we work with 26,704 videos in this paper.

The HMDB51 dataset has 51 action classes with total 6,766 videos and each class has more than 100 videos http://serre-lab.clps.brown.edu/resources/HMDB/index.htm. All the videos are obtained from real world scenarios such as: movies, youtube. The intra-class variation is very high due to many factors, such as viewpoint, scale, background, illumination etc. Thus, HMDB51 is a very difficult benchmark for action recognition. There are three training and testing splits released on the website of this dataset. We conduct experiments based on these splits and report average accuracy for evaluation.

The UCF50 dataset has 50 action classes with total 6,618 videos, and each action class is divided into 25 groups with at least 100 videos for each class. The video clips in the same group are usually with similar background. We choose the suggested evaluation protocols of Leave One Group Out cross validation (LOGO) and report the average accuracy ReddyS13.

The UCF101 dataset is an extension of the UCF50 dataset and has 101 action classes. The action classes can be divided into five types: human-object interaction, body-motion only, human-human interaction, playing musical instruments, and sports. Totally, it has 13,320 video clips, with fixed frame rate and resolution 25 FPS and 320 $\times$ 240 respectively. To our best knowledge, this dataset has been the largest dataset so far. We perform evaluation according to the three train/test splits released in Thumos’13 challenge http://crcv.ucf.edu/ICCV13-Action-Workshop/ and report the mean average accuracy of these splits.

In our evaluation experiment, we choose linear Support Vector Machine (SVM) as our recognition classifier. Specifically, we use the implementation of LIBSVM ChangL11. For multiclass classification, we adopt one-vs-all training scheme and choose the prediction with highest score as our predicted label.

2 Local Features and Codebook Generation

In our evaluation, we choose two widely-used local features, namely Space Time Interest Points (STIPs) Laptev05 with HOG, HOF descriptors LaptevMSR08, and improved Dense Trajectories (iDTs) with HOG, HOF, MBHx, MBHy descriptors WangKSL13. Specifically, we use the implementation released on the website of Laptev http://www.di.ens.fr/ laptev/download.html for STIPs and Wang https://lear.inrialpes.fr/people/wang/improved_trajectories for iDTs. We choose the default parameter settings for both local features. STIPs and iDTs represent two types of local features: sparse interest points and densely-sampled trajectories. They may exhibit different properties with varying BoVW settings, and thus it is well worth exploring both STIPs and iDTs.

Regarding codebook generation, we randomly sample $100,000$ features to conduct $k$-means, where codebook size range from 1,000 to 10,000 for STIPs, and from 1,000 to 20,000 for iDTs. For GMM training, we randomly sample 256,000 features to learn GMMs with mixture number ranging from 16 to 512 for both STIPs and iDTs.

3 Importance of Pre-processing

We conduct experiments on the UCF101 dataset and investigate the importance of pre-processing for these encoding methods. With pre-processing step, the descriptors of STIPs are firstly reduced to $100$-dimension and then whitened to have unit variance. The results are shown in Figure 5. We observe that the pre-processing technique of PCA-Whiten is very important to boost the performance of encoding methods. Surprisingly, the performance of FV (state-of-the-art) without PCA-Whiten is lower than or comparable to VQ and LLC with PCA-Whiten. In previous research work, PCA-Whiten is often done for FV encoding methods but seldom used for other encoding methods. Our study suggests that using PCA-Whiten techniques enable us to greatly improve final recognition rate for all encoding methods. We obtain the recognition rate $56.1\%$ for VQ, which significantly outperform over the result $43.9\%$ reported in SOOMRO12, where the same local feature and encoding method is used.

In the remaining part of evaluation, we will use PCA-Whiten to de-correlate the descriptor, reduce the dimension, and normalize the variance. For descriptor level fusion of STIP, the dimension of concatenated descriptor is reduced from $162$ to $100$. For HOG and HOF, the dimension is reduced from $72$ to $40$, and from $90$ to $60$, respectively. For descriptor level fusion of iDT, the dimension of concatenated descriptor is reduced from $396$ to $200$. For separate descriptor, the dimensions of HOG, MBHx, and MBHy are all reduced from $96$ to $48$. HOF descriptor is reduced from $108$ to $54$.

4 Exploration of Encoding Methods

In this section, we compare and analyze the performance of different encoding methods. For each encoding method, we fix other settings, such as parameter setting, pooling and normalization strategy, the same with previous papers. We explore these encoding methods with descriptor level fusion, for both STIPs and iDTs. The influence of different pooling and normalization strategy, and fusion methods will be investigated in the following sections.

Encoding methods selection and setting. We select six popular encoding methods according to categorization in Table 1. For voting based encoding methods, we choose VQ as a baseline and SA-$k$ as a representative method. LLC is selected as the representative of reconstruction-based encoding methods due to its computational efficiency and performance WangWQ12. Super vector based encoding methods have shown the state-of-the-art performance on several datasets WangS13a . We choose three super vector based encoding methods for evaluation, namely FV, VLAD, and SVC.

Results and analysis. The experimental results of STIPs and iDTs on the three datasets are shown in Figure 6. Several rules can be found from these experimental results:

Basically, the recognition performance of all selected encoding methods increases as the size of codebook (GMM) becomes larger and will reach a plateau when the size exceeds a threshold. For super vector based encoding methods, the performances reach a saturation when size of codebook (GMM) becomes $256$ for both STIPs and iDTs. There is a slight change of the recognition rate when GMM size grows from $256$ to $512$. For the other two types of encoding methods, the performances are saturated as the size of codebook reaches $8,000$. We also notice that these encoding methods using iDTs have slight improvements when the codebook size varies from 8,000 to 20,000 , while the performances using STIPs start shaking when the codebook size becomes larger than 8,000 due to the over-fitting effect. This difference may be ascribed to the dimension of local descriptors and sampling strategy. The descriptors dimension of iDTs is twice of STIPs and requires more codewords to divide the feature space. Meanwhile, STIPs is a set of interest points and the extracted descriptors distribute sparsely in the feature space. The codebook with large size will result in an over-partition of feature space, which means for a specific video, there may be no descriptors falling into the corresponding regions for some codewords. iDTs are more densely sampled features and codebook with large size is more suitable to divide the space of dense features. Above all, for a good balance between performance and efficiency, sizes of $256$ and $8,000$ are good choices for super vector based encoding and other encoding respectively.

For local features of both SITPs and iDTs, super vector based encoding methods outperform the other types of encoding methods on the three datasets. According to previous introduction, these super vector encoding methods not only preserve the affiliations of descriptors to codewords, but also keep high order information such as the difference of means and variances. These high order information enables the encoding methods to better capture the distribution shape of descriptor in feature space. In these super vector based methods, FV is typically better than VLAD and SVC, whose performance is quite similar. This can be own to two facts: (i) FV keeps both $1^{st}$ and $2^{nd}$ statistics, which is more informative than VLAD (only $1^{st}$ statistics) and SVC ($0^{th}$ statistics and $1^{st}$ statistics). (ii) FV is based on GMM and each descriptor is softly assigned to codewords using posterior probability, while VLAD and SVC are based on $k$-means results and use hard assignment. We also notice that the difference between FV and the other two methods (VLAD, SVC) for iDTs seems smaller than STIPs. The more dense descriptors may make the learned codebook more stable for SVC and VLAD, and reduce the influence of soft assignment in FV. Meanwhile, the information contained in $2^{nd}$ statistics may be less complementary to $1^{st}$ statistics for iDTs. In conclusion, super vector based representation, aggregating high order information, is a more suitable choice for good performance, when the high dimension of representation is acceptable.

For reconstruction based and voting based encoding methods, VQ reaches the lowest recognition rate for STIPs and iDTs on the three datasets. This can be ascribed to the hard assignment and descriptor ambiguity in the VQ method. In essence, the LLC and SA-$k$ are quite similar in spirt, for that they both consider locality when mapping descriptor into codeword. The performance of LLC is better than SA-$k$ for STIPs, while the performances of them are almost the same for iDTs. This can be explained by the mapping strategy in LLC and SA-$k$. The mappings of descriptor to the nearest codewords in LLC are determined jointly according to their effect in minimizing the reconstruction error, while the mappings in SA-$k$ are calculated independently for each individual codeword according to the Euclidean distance. The mapping method in LLC may be more effective to deal with manifold structure than just considering Euclidean distance in SA-$k$. For sparse features such as STIPs, the descriptors distribute sparsely around each codeword, and using Euclidean distance may introduce noise and instability for SA-$k$. For dense features such as iDTs, the descriptors are usually sampled densely and more compact around codewords, reducing the influence caused by the usage of Euclidean distance. In a word, compared with hard assignment, locality and soft assignment is an effective strategy to improve the performance of encoding methods.

STIPs and iDTs represents two types of local features, namely sparsely-sampled and densely-sampled features. In general, they exhibit consistent performance trends for different encoding methods, for example, super vector encoding methods outperforms others, soft-assignment is better than hard-assignment. However, there is a slight difference between them in some aspects, such as sensitivity to codebook size and encoding methods, performance gaps among super vector based methods, difference between LLC and SA-$k$, as previously observed. From the perspective of data manifold, the more densely-sampled features can help us more accurately describe the data structure in the feature space. We can obtain a more compact clustering result using $k$-means, and the local Euclidean distance is more stable. Thus, when choosing codebook size and encoding method, the type of local feature can be a factor needed to be considered.

Computational costs. We also compare the efficiency of different encoding methods and the running time is shown in Figure 7. Our codes are all implemented in Matlab, and running on a workstation with 2x Intel Xeon 5560 2.8GHz CPU and 32G RAM. We randomly sample 50 videos from the UCF101 dataset and report the total time for these videos. For super vector based methods, FV is much slower due to the calculation of posterior probability during encoding, and the time of VLAD and SVC is almost the same. For the other types of encoding methods, LLC is less efficient as it solves a least square problem. The computational cost of super vector encoding methods are usually lower than that of the other types of encoding methods, due to their smaller codebook sizes.

Based on the above analysis, super vector based encoding methods are more promising for high performance and fast implementation, especially for SVC, VLAD. However, the feature dimension of super vector methods is much higher than the other two kinds of encoding methods, for example, when the codebook size is 256, the dimension of FV and VLAD is 102,400 and 51,200 respectively for iDT features. The effective dimension reduction may be a future research direction for super vector encoding methods.

5 Exploration of Pooling and Normalization

In this section, we mainly investigate the influence on recognition rate for different pooling and normalization strategies on the UCF101 dataset. Based on the performances of different encoding methods on the UCF101 dataset in previous section, we choose the codebook (GMM) size as $512$ for super vector based methods and codebook size as $8,000$ for the other two types of encoding approaches. Meanwhile, according to our conclusion that super vector based encoding is a promising method and soft assignment is an effective way to improve the encoding methods, we extend VLAD to VLAD-$k$ and VLAD-$all$, SVC to SVC-$k$ and SVC-$all$ as described in Section 2.4.4. Thus, there are totally $10$ kinds of encoding methods.

The experimental results are shown in Figure 8 and Figure 9. Several observation can be concluded from these results:

For super vector based encoding methods, intra-normalization is an effective way to balance the weight of different codewords and suppress the burst of features corresponding to background. We found this technique works very well when dense features are chosen. A large number of features in iDTs are irrelevant with the action class and intra-normalization can suppress this influence. However, for sparse features, the effect of intra normalization is not so evident, and even cause performance degradation in the case of hard assignment such as VLAD, SVC. We ascribe this phenomenon to the fact that the STIPs features are usually located in the moving foreground and related with action class. Thus, these descriptors only vote for a subset of codewords, that are highly related with action class. In this case, intra-normalization can decrease the discriminative power of action-related codewords and increase the influence of irrelevant codewords. In conclusion, intra-normalization is effective in handling burst of irrelevant features in the case of dense-sampling strategy.

The influence of power operation in normalization is highly related with pooling method. We observe that power normalization is an effective approach to boost the performance of representation obtained from sum pooling, such as super vector based representation, LLC, SA-$k$ with sum pooling. However, power normalization have little effect for max pooling and sometimes even cause the performance degradation for LLC, SA-$k$. The operation of power usually reduces the difference between different codewords, which means smoothing the histogram. This smooth effect can reduce the influence of high frequent codeword on the kernel calculation and improve the influence of less frequent codeword. For sum pooling, the resulting histogram is usually very sharp and unbalanced due to feature burst, and the smooth operation has a positive effect for suppress the high frequent codeword. However, for max pooling, the histogram is itself not so sharp as sum pooling, and thus the power normalization may have a side effect. In above, power operation is an effective strategy to smooth the resulting histogram and can greatly improve the performance of sum pooling representation.

6 Exploration of Fusion Methods

The local features usually have multiple descriptors, such as HOG, HOF, MBHx, and MBHy, each of which corresponds to a specific view of video data. For the empirical study in previous section, we choose a simple method to combine these multiple descriptors, where we just concatenate them into a single one, namely descriptor level fusion. In this section, we mainly analyze the influence of different fusion methods on final recognition performance.

The experimental results on three datasets are shown in Table 2, Table 3, and Table 4. From these results, we observe serval trends:

For iDTs features, representation level fusion is the best choice for all of the selected encoding methods on the three datasets. This result indicates that these multiple descriptors are most correlated in the video level. Descriptor level fusion emphasizes the dependance in cuboid and results in high dimension features for codebook training and encoding. This may make these unsupervised learning algorithm unstable.

For STIPs features, representation level fusion is more effective for reconstruction based and voting based encoding methods. For super vector based encoding methods, the performance of representative level fusion is comparable to that of descriptor level fusion. This trend is consistent with the finds with iDTs features.

For both features, SA-$k$, LLC, and VQ encoding methods are much sensitive to fusion methods than those super vector based encoding methods. Great improvement can be obtained for SA-$k$, LLC, and VQ when using representation level fusion, but slight improvements happen to those super vector methods. We analyze this is due to two facts. Firstly, for reconstruction and voting based encoding methods, the final dimension of representation level fusion is $M$ (the number of descriptors) times of the dimension of descriptor level fusion. However, for super vector based encoding methods, the dimension of descriptor level fusion is the same with representation level fusion. The higher dimension of final representation may enable SVM to classify more easily. Secondly, the codebook size $K$ of super vector methods is much smaller than that of other types of encoding methods, where clustering algorithm may be more stable for high dimensionality in descriptor level fusion method.

Based on the observation and analysis above, we conclude that fusion method is a very important component for handling combination of multiple descriptors in the action recognition system. Representation level fusion method is a suitable choice for different kinds of encoding methods due to its good performance. From our analysis, we know that the performance boosting of fusing multiple features mainly owns the complementarity of these features. This complementarity may be not limited to the exploration of different descriptors, but also can be extended to the different BoVWs. From the perspective of statistics, FV aggregates information using $1^{st}$ and $2^{nd}$ order statistics, while SVC is about zero and $1^{st}$ order statistics. Intuitively, these two kinds of super vector encoding methods are complementary to each other. Thus, we present a new feature representation, called hybrid representation, combining the outputs FV and soft version SVC of multiple descriptors, including HOG, HOF, MBHx, and MBHy. This representation is simple but proved to be effective in next section.

7 Comparison to the State-of-the-Art Results

Table 5 shows our final recognition rates and compare our results to that of state-of-the-art approaches. For the HMDB51 dataset, we obtain a recognition rate of $61.1\%$, which is superior to the best result WangS13a by $3.9\%$. Our system reaches classification accuracy of $92.3\%$ on the dataset of UCF50 and $87.9\%$ on the dataset of UCF101, which outperform the best results by $1.2\%$ and $2.0\%$ respectively. It is worth noting that UCF101 is newest and largest dataset, so few published papers have reported results on this dataset. We mainly compare with those top performers in the Thumos’13 Action Recognition Challenge THUMOS13. We also compare with three latest papers in CVPR 2014. Karpathy et al. Karpathy14 resorts to a large deep Convolutional Neural Network trained with an extra 1-M training dataset. Cai et al. CaiWPQ14 propose a complex and less efficient encoding method by considering the correlation of different descriptors. Wu et al. WuZL14 propose a simple, lightweight, but powerful bimodal encoding method. Our results outperform these top performer and latest papers on the UCF101. From these comparisons, our hybrid representation is an efficient and effective method and obtains the state-of-the-art performance on the three challenging datasets.

Conclusion

In this paper, we have comprehensively studied each step in the BoVW pipeline and tried to uncover good practice to build a more accurate and efficient action recognition system. Specifically, we mainly explore five aspects, namely local features, pre-processing techniques, encoding methods, pooling and normalization strategy, fusion methods. We conclude that every step is crucial for contributing to the final recognition rate and improper choice in one of the steps may counteract the performance improvement of other steps. Meanwhile, based on the insights from our comprehensive study, we propose a simple yet effective representation, called hybrid representation. Using this representation, our action recognition system obtains the state-of-the-art performance on the three challenging datasets.

References