首先介绍一下写这篇博客的背景，最近在看视频无监督的paper，无监督最早采用特征提取+聚类的模型，其中一篇提到了利用LLC进行快速聚类，所以了解了一下图像的稀疏表示。
图像的稀疏表示方法经历了ScPM到LLC的发展历程，但是他们两者是建立在对BoW和SPM的修改上，因此本文将后者也纳入稀疏表示的范畴。
Bag Of Word（词袋）模型，是现在一种用于图像检索的一种方法。它最早用于对于文章内容的检索，原理是将文本看作是单词的集合，通过建立词典，对每个单词出现次数进行统计，以便得到文本内容的分类。计算机视觉研究从中获得灵感，将其用于图像的检索中，就有了Bag Of Features（原理类似Bag of word)。
具体而言，其分为以下步骤：
特征提取：将图像看成一个由各种图像块组成的集合，通过特征提取，获得图像的关键图像特征：
学习“视觉词典”（visual vocabulary）：获得了多张图像的特征之后，这些特征并没有通过分类处理，其中有的特征点之间是极其相似，所以这一步骤通过K-means聚类算法，将我们提取出来的特征点进行分类处理。聚类是学习视觉词典的重点操作。将聚类出来的聚类中心称为视觉单词（codevector）。而将视觉单词组成的集合称为视觉词典/码本（codebook）。
对输入特征集进行量化：将输入的特征集合，映射到上一步做来的码本之中。通过计算输入特征到视觉单词的距离，然后将其映射到距离最近的视觉单词中，并计数。
把输入图像转化成视觉单词（ visual words）的频率直方图：这一步骤通过对图像特征提取，然后将提取出来的特征点，根据第三步，转换为频率直方图。如图所示：
后续可能还有构造倒排表等操作，但是对于接下来理解SPM和LLC而言，掌握到这一步即可。
将BoW用于图像分类的一张流程图如下： 其中值得一提的是，step 1中的descriptors 就是图像的浅层特征，然后对所有图像中计算的描述符进行聚类，也叫向量矢量（VQ），机器学习领域通常叫做是字典学习。然后统计每个簇中的特征数量（计算直方图），每个聚类中心就是直方图中的一个bin，后面也叫字典中的一个原子。这一步也是提取图像的深层信息。
但是很显然的事，BoW有一个问题：因为全图的所有特征进行直方图计算，所以原图像新的表示（特征）失去了空间信息。保留图像的空间信息就是后面所讲内容的出发点。
SPM 全称是Spatial Pyramid Matching，和分块直方图其实是一个道理------将图像分成若干块(sub-regions)，分别统计每一子块的特征，最后将所有块的特征拼接起来，形成完整的特征。这就是SPM中的Spatial。在分块的细节上，作者采用了一种多尺度的分块方法，即分块的粒度越大越细(increasingly fine)，呈现出一种层次金字塔的结构，这就是SPM中的Pyramid。M就是Matching。简单来说，也就是将图像分块，每块采用BoW，这样左上角的特征就不会跑到右下角的直方图中。如下图： 详细地来说，SPM的分层概念非常像多媒体技术的视频编码里profile的概念，就是说级别越高，特征直方图统计的粒度越细，如下图： 用cell表示划分的区域，bin表示每个cell的特征的点数，对于第l层，每一维可以划分2l个cell，如果有d维，就可以总共划分为2ld个cell。
而划分了cell并统计了直方图之后，就是非常关键的Pyramid Matching即匹配算法， 原文中提出，可以把特征提取+SPM看作一个CNN的过程： 关于这个部分，我思考了一下可以用密码学里Feistel提出的用替换置换网络近似分组密码的思想来理解，首先特征提取就是靠近输入的coding+pooling，然后构造字典就是进一步coding，获取直方图就是高层的pooling，最后都是通过SVM进行分类。
手动分割线，以下内容高能
SPM在coding一步采用的是Hard-VQ，也就是说一个descriptor只能投影到dictionary中的一个term上。这样就造成了明显的重建误差（worse reconstruction，large quantization errors），其目标函数是： 其实就是K-means,xi表示特征集合中的第i个特征，B表示字典，这里就是K-means的聚类中心，ci表示第i个特征的编码。如果xi属于第1类，ci=[1,0,0,0,…];
SPM的pooling: SPM的输出结果是一幅图像的直方图。直方图就是做加法，将该幅图像的所有点的编码排成矩阵C，C的第i行就是ci，C的每一列就是字典中的atom，或者说是最终直方图中的每一个bin，所以最后将C的每一列求和，然后归一化获得的向量就是该幅图的特征，最后用于分类，所以是Averaging pooling。
这样，原本很相似的descripors经过coding之后就会变得非常不相似了。ScSPM为此取消了这一约束，它认为descripor可以投影到某几个terms上，而不仅仅是一个。因此，其目标函数变成了：
就是用稀释编码代替K-means，原因是:
重建性能好;parse有助于获取salient patterns of descripors;image statistics方面的研究表明image patches都是sparse signals;biological visual systems的研究表明信号的稀疏特征有助于学习;稀疏的特征更加线性可分.ScSPM的Pooling: 选取矩阵C每一列的最大值，也就是Maxpooling。现在学术界普遍认为max pooling 比averaging pooling更加鲁棒。因此，ScSPM输出的是非线性特征，所以只需要线性分类器就可以获得很好的效果；而SPM输出的线性特征，需要采用非线性的分类器。线性分类器无论是训练还是测试速度都快于非线性分类器。
LLC和ScSPM差不多，也是利用了Sparsity,LLC对ScSPM的改进，则在于引入了locality。原论文的图： LLC引入了locality的约束，即不仅仅是sparse要满足，非零的系数还应该赋值给相近的dictionary terms。作者解释到，locality 很重要是因为：
nonlinear function的一阶近似要求codes是local的；locality能够保证codes的稀疏性，而稀疏却不能保证locality；稀疏的coding只有在codes有局部性的时候有助于learning。LLC 的目标函数是： 加号前的一项最小化是为了减少量化误差（学习字典、确认投影系数）；加号后的一项则是做出假设约束（包括是一些参数的regularization）。这个求解是可以得到闭合解的，同时也有快速的近似算法解决这个问题，因此速度上比ScSPM快。
di描述的是xi到每个dictionary term的距离。显然这么做是为了降低距离大的term对应的系数。
locality体现出的最大优势就是，相似的descriptors之间可以共享相似的descriptors，因此保留了codes之间的correlation。而ScSPM为了最小化重建误差，可能引入了不相邻的terms，所以不能保证smooth。Hard-VQ则更不用说了。
[1]. K. Grauman and T. Darrell. Pyramidmatch kernels: Discriminative classification with sets of image features. InProc. ICCV, 2005.
[2]. S. Lazebnik, C. Schmid, and J. Ponce.Beyond bags of features: Spatial pyramid matching for recognizing natural scenecategories. InCVPR, 2006.
[3]. J. Yang, K. Yu, Y. Gong, and T. Huang.Linear spatial pyramid matching using sparse coding for image classification.Proc. of CVPR’09, 2009.
[4]. Wang, Jinjun, et al. “Locality-constrained linear coding for image classification.” Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010.
