Feature Encodings and Poolings for Action and Event Recognition: A Comprehensive Survey <s> Locality-Constrained Linear Encoding <s> We describe an approach to object and scene retrieval which searches for and localizes all the occurrences of a user outlined object in a video. The object is represented by a set of viewpoint invariant region descriptors so that recognition can proceed successfully despite changes in viewpoint, illumination and partial occlusion. The temporal continuity of the video within a shot is used to track the regions in order to reject unstable regions and reduce the effects of noise in the descriptors. The analogy with text retrieval is in the implementation where matches on descriptors are pre-computed (using vector quantization), and inverted file systems and document rankings are used. The result is that retrieved is immediate, returning a ranked list of key frames/shots in the manner of Google. The method is illustrated for matching in two full length feature films. <s> BIB001 </s> Feature Encodings and Poolings for Action and Event Recognition: A Comprehensive Survey <s> Locality-Constrained Linear Encoding <s> Recently SVMs using spatial pyramid matching (SPM) kernel have been highly successful in image classification. Despite its popularity, these nonlinear SVMs have a complexity O(n2 ~ n3) in training and O(n) in testing, where n is the training size, implying that it is nontrivial to scaleup the algorithms to handle more than thousands of training images. In this paper we develop an extension of the SPM method, by generalizing vector quantization to sparse coding followed by multi-scale spatial max pooling, and propose a linear SPM kernel based on SIFT sparse codes. This new approach remarkably reduces the complexity of SVMs to O(n) in training and a constant in testing. In a number of image categorization experiments, we find that, in terms of classification accuracy, the suggested linear SPM based on sparse coding of SIFT descriptors always significantly outperforms the linear SPM kernel on histograms, and is even better than the nonlinear SPM kernels, leading to state-of-the-art performance on several benchmarks by using a single type of descriptors. <s> BIB002 </s> Feature Encodings and Poolings for Action and Event Recognition: A Comprehensive Survey <s> Locality-Constrained Linear Encoding <s> The traditional SPM approach based on bag-of-features (BoF) requires nonlinear classifiers to achieve good image classification performance. This paper presents a simple but effective coding scheme called Locality-constrained Linear Coding (LLC) in place of the VQ coding in traditional SPM. LLC utilizes the locality constraints to project each descriptor into its local-coordinate system, and the projected coordinates are integrated by max pooling to generate the final representation. With linear classifier, the proposed approach performs remarkably better than the traditional nonlinear SPM, achieving state-of-the-art performance on several benchmarks. Compared with the sparse coding strategy [22], the objective function used by LLC has an analytical solution. In addition, the paper proposes a fast approximated LLC method by first performing a K-nearest-neighbor search and then solving a constrained least square fitting problem, bearing computational complexity of O(M + K2). Hence even with very large codebooks, our system can still process multiple frames per second. This efficiency significantly adds to the practical values of LLC for real applications. <s> BIB003
Wang et al. BIB003 pointed out that in order to achieve desirable performance in classification tasks, the most common combinational strategies adopt either linear encodings plus nonlinear classifiers, such as BOV BIB001 plus χ 2 -SVM, or nonlinear encodings plus linear classifiers, such as ScSPM BIB002 plus linear SVM. Usually, either the nonlinear encodings or the nonlinear classifiers are computationally expensive. As a result, Wang et al. proposed a fast linear encoding approach, called Locality-constrained Linear Coding (LLC) BIB003 for real-time classification applications. Suppose X = x i 1 ≤ i ≤ n, x i ∈ R l is a set of n local l dimensional feature vectors extracted from an image, and D = {d 1 , d 2 , · · · , d m } ⊂ R l×m is the encoding dictionary with m words. Then, the process of the proposed fast linear LLC encoding works as follows: (1) For each x i , find its k nearest neighbors from the dictionary D by using k-NN method, denoted as , where c i 0 = k and 1 T c i = 1. The authors showed that the promising LLC approach cannot only improve encoding velocity, but also classification performance even with linear classifier than several compared approaches.