引入

Recently SVMs using spatial pyramid matching (SPM) kernel have been highly successful in image classification. Despite its popularity, these nonlinear SVMs have a complexity 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

非线性SVM的计算代价巨大

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.

In recent years the bag-of-features (BoF) model has been extremely popular in image categorization. The method treats an image as a collection of unordered appearance descriptors extracted from local patches, quantizes them into discrete “visual words”, and then computes a compact histogram representation for semantic image classification

The method partitions an image into    segments in different scales L = 0; 1; 2, computes the BoF histogram within each of the 21 segments, and finally concatenates all the histograms to form a vector representation of the image. In case where only the scale L = 0 is used, SPM reduces to BoF.

用sparsecoding 替代VQ

Furthermore, unlike the original SPM that performs spatial pooling by computing histograms, our approach, called ScSPM, uses max spatial pooling that is more robust to local spatial translations and more biological plausible

用max pooling 来替代 spatial pooling

经过稀疏编码之后，用一个线性分类器就能取得很好的效果

Despite of such a popularity, SPM has to run together with nonlinear kernels, such
as the intersection kernel and the Chi-square kernel, in order to achieve a good performance, which requires intensive computation and a large storage.

交叉核，卡方核

Linear SPM Using SIFT Sparse Codes

VQ

在训练阶段主要是学习出基向量V，在测试阶段学习出基向量系数U

稀疏编码，给损失函数上加上了稀疏性的约束

同VQ一样，训练阶段学基（过完备），测试阶段得到稀疏

优点：重构误差少；捕获的图像特征突出；据说图像块就是稀疏信号

注意：local sparse coding

所以，用听投票的VQ会造成很大的量化误差，即使使用非线性的SVM效果也不明显，而且计算代价大

In this work, we defined the pooling function F as a max pooling function on the absolute sparse codes

据说这个 max pooling 有生物学依据 ~~ 而且更加鲁棒

Similar to the construction of histograms in SPM, we do max pooling Eq. on a spatial pyramid constructed for an image.

成功原因分析：

This success is largely due to three factors: (1) SC has much less quantization errors than VQ; (2) It is well known that image patches are sparse in nature, and thus sparse coding is particularly suitable for image data; (3) The computed statistics by max pooling are more salient and robust to local translations.

实现

1，Sparse Coding

求解SC的损失函数方程。当U固定或V固定时是凸的，但两者若都不固定则非凸。所以传统的解决办法是固定一个求解另一个，最新提出的 feature-sign search algorithm 计算速度更快

确定基V在线下，可以达到实时的确定特征的表达系数

2，Multi-class Linear SVM

LBFGS

Linear Spatial Pyramid Matching Using Sparse Coding for Image Classification