# A Fast Sparse Coding Method for Image Classification
## 1 Introduction  
Image classification is an important problem in computer vision. Pattern recognition and machine learning techniques have been widely applied in this field, which usually extract image features and then classify images according to the features. The setting of image features often significantly affects the performance of classification. Feature encoding methods, especially vector quantization (VQ) and sparse coding (SC), have attracted more and more attention because their well demonstrated performances. The bag-of-features (BoF) representation methods [1; 2; 3] are important application of VQ and have been used in image classification and 1-D signal recognition [4]. This kind of representation is regarded as high-level feature because it represents an image as a vector of occurrence counts of a vocabulary built on the low-level feature extracted from subregions. The high-level feature concerns with the interpretation or classification of a scene, thus may achieve higher accuracy on most images. However, the BoF model disregards all information about the spatial layout of the features, thus may decrease the accuracy when classifying spatially sensitive images. To overcome this disadvantage, two extensions of the BoF model have been developed in the task of image classification: generative models [5; 6; 7; 8] and spatial pyramid matching (SPM) [9]. Generative models are constructed by the latent variables learned from BoF, and classify images according to their intermediate semantics. They consider an image not only as a collection of codes [5; 7] but also as a more complicated structure [10; 11], which contains abundant image information andis close to the way that human beings see the image. This can explain why generative models have gained growing attention of the research community. Compared with generative models, SPM can achieve higher accuracy [12]. The SPM method [9] mines the spatial information through partitioning the image into increasingly finer spatial subregions and employs pyramid Match Kernel [1] to compare corresponding subregions. Typically, it partitions an image into \(4^{l}\) subregions in different level (\(l=0,1,2\) ) and computes the BoF histogram within each of the 21 subregions. The BoF is a special case of SPM because SPM reduces to a standard BoF when \(l=0\). Many image classification tasks such as Caltech-101 [6] and 15-Scenes [9] have shown very promising performance of SPM. Although the traditional SPM method works well for image classification, classifiers with nonlinear Mercer kernels, e.g., Chi-square kernel, are usually used to boost performance. Accordingly, the nonlinear SVM has a complexity \(O(n^{2}\sim n^{3})\) in training and \(O(n)\) in testing, where \(n\) is the number of training set images [13; 14]. When the training set contains many samples, this complexity will cause many calculations, which implies a poor scalability for SPM's real-world applications. To overcome this drawback, [PERSON] et al. [13] proposed an extension of SPM by using Sparse Coding (ScSPM) and achieved state-of-the-art performance on several benchmarks. The ScSPM computes a spatial-pyramid image representation by sparse coding (SC) instead of vector quantization (VQ).This method works better with employing linear classifiers, and thus reduces the computation of classification algorithm [14; 15; 16]. The ScSPM method represents an image through the following three modules: (1) SIFT extraction; (2) sparse coding; and (3) spatial pooling. The sparse coding contains dictionary learning and feature quantization, which are the most important and govern the quality of image presentation. The ScSPM employs efficient sparse coding method [17] that adopts Lagrange dual to learn dictionary whose components are linear combinations of low-level features. The method has been shown experimentally to be much faster than first-order gradient descent methods [17], and is capable of generating state-of-the-art features in image classification.