图像分类学习笔记词袋模型和空间金字塔匹配

1、图像分类学习笔记：词袋模型和空间金字塔匹配Image Classification Framework: Bag-of-Words & Spatial Pyramid Matching一、基础：词袋模型（Bag of Words）Bag-of-Words（词袋、词包）模型，或称Bag of Features模型，源于文本分类技术。在信息检索中，假定对于一个文本，忽略其词序和语法、句法。将其仅仅看作是一个词的集合，每个词都是彼此概率独立的。这样可以通过文档中单词出现的频率来对文档进行描述与表达。Csurka等1 于2004年将其引入计算机视觉领域。其核心思想在于，图像可以视为一种文档对象

2、，图像中不同的局部区域或其特征可看作构成图像的词汇，其中相近的区域或其特征可以视作为一个词。这样，可以把每幅图像描述为一个局部区域/关键点(Patches/Key Points)特征的无序集合。理论对应关系如下：文档单词字典图像特征聚类中心特征聚类集合用词袋模型生成对一张图像的描述向量的处理步骤：1、局部特征提取通过兴趣点检测、密集采样或随机采集，结合图割区域、显著区域等方式获得图像各处的局部特征。常用的是SIFT特征和Dense SIFT特征。 2、构建视觉词典在整个训练集上提取局部特征后，使用某种聚类算法(如K-means)将局部特征进行聚类，每个聚类中心可以看作是词典中的一个视觉词汇(V

3、isual Word)，相当于文本检索中的词，视觉词汇由聚类中心对应特征形成的码字(code word)来表示（可看作一种特征量化过程）。所有视觉词汇形成一个视觉词典(Visual Vocabulary)，词典中所含词的个数反映了词典的大小。3、特征量化编码图像中的每个特征都将被映射到视觉词典的某个词上，然后统计每个视觉词在一张图像上的出现次数，即可将该图像描述为一个维数固定的直方图向量。4、训练分类模型并预测用于图像分类时，如上对训练集提取Bag-of-Features特征，在某种监督学习 （如SVM）的策略下，对训练集的Bag-of-Features特征向量进行训练，获得对象或场景的分类模

4、型；在分类模型下，对该特征进行预测，从而实现对待测图像的分类。（示意图片来源于网络）词袋模型中一些需要商榷的实现问题：1、使用k-means聚类，除了其K和初始聚类中心选择的问题外，对于海量数据，输入矩阵的巨大将使得内存溢出及效率低下。训练集变化时重新聚类的代价也很高。2、字典大小的选择也是问题，字典过大，单词缺乏一般性，对噪声敏感，计算量大，关键是图象投影后的维数高；字典太小，单词区分性能差，对相似的目标特征无法表示。3、相似性测度函数用来将图象特征分类到单词本的对应单词上，其涉及线型核，塌方距离测度核，直方图交叉核等的选择。4、将图像表示成一个无序局部特征集的特征包方法，丢掉了所有的关于空

5、间特征布局的信息，在描述性上具有一定的有限性。为此， Lazebnik2提出了基于空间金字塔的Bag-of-Features，下面部分中将会详述。此外，基于词袋模型的改进方法还有很多，见下一部分。二、综述：基于词袋模型的图像分类方法框架词袋模型提出后，图像分类领域大量的研究工作开始集中于该模型的相关研究，并逐渐形成了主要由以下四部分组成的图像分类方法框架：1、底层特征提取（SIFT、Dense SIFT、多特征）2、特征编码（硬量化编码、稀疏编码、fisher vector等）3、特征汇聚（空间金字塔SPM）4、分类器分类（SVM、Adaboost、Naïve Bayes等）其中第三

6、部分的基础是Lazebnik等人2 在CVPR 2006上提出的空间金字塔（SPM）方法，在当前基于词袋模型的分类框架中几乎已成为标准步骤。该论文也是完整实现了以上框架的经典文章。后面有进一步的介绍。（用于图像分类的另一主流框架：自从2006年Hinton教授于Science上发表文章，开启了深度学习在学术界和工业界的浪潮，深度学习框架也被大量应用于图像分类领域，并取得了更加优异的表现。此处不涉及。）e.g, SIFT, HOGVQ CodingAverage Pooling (obtain histogram)SVMLocal GradientsPooling（示意图来自于Kai Yu，CV

7、PR2012 tutorial）1、底层特征提取（describing）词袋模型的基础就是图像局部特征提取，底层特征是图像分类检测框架的第一步。在此方面的改进主要包括局部特征描述方法的设计和采集方式的优化。目前常用的是SIFT特征和Dense SIFT特征。特征采集方式主要包括兴趣点检测、密集采样或随机采集等。兴趣点检测通过某种准则选取一些像素点、角点等，可以在较小的开销下得到有一定意义的表达。常用兴趣点检测算子有Harris角点、FAST算子、高斯差分算子DoG、高斯拉普拉斯算子LoG等。密集采样则是用均匀网格划分图像，提取局部描述子向量。随机采样不必详述。在诸多的局部图像特征描述子中，SI

8、FT（Scale Invariant Feature Transform）是其中应用最广的。SIFT算法包括兴趣点提取和局部描述两步。Dense-SIFT则是用密集采样方法结合SIFT的局部描述形成描述图像的一组特征向量。用于图像分类的PHOW描述子3是Dense-SIFT 的变体，结合其他算法步骤在Caltech数据集上可以取得很好的分类效果。基于SIFT改进的局部描述子还包括SURF、PCA-SIFT、Color-SIFT等，一篇PAMI 2013的论文4提供了一个改进的p-sift描述子。此外还有HOG、LBP、MSER等重要描述方法，以及近年来兴起的一系列二值特征描述子BRIEF、OR

9、B、BRISK、FREAK等。（上图：OpenCV 2.4.8 支持的局部描述子）此外，BOF为基础的图像分类方法主要依赖于低级局部形状特征。而融合多种线索如颜色、纹理、形状的工作，足以提升分类准确度。采取多种特征融合的分类框架也都取得了不错的结果，如Fernando等人5（CVPR2012）。2、特征编码（coding）提取的底层特征中包含大量冗余和噪声，或者向量没有归一化，为提高特征表达的鲁棒性，使之适用于图像分类任务，需要对提取到的特征向量集合进行一定变换，获得更具有区分性的图像层级表达。这就是特征编码（coding）。这一步对识别性能具有至关重要的作用，因而大量的研究工作都集中在寻找更

10、加强大的特征编码方法上。硬编码与软编码：Bag of Words 模型使用的编码方式是向量量化编码，这种编码方式最为简单直观，只是利用量化的思想进行距离计算与聚合，因此又称为硬编码。作为一种改进，Gemert等人6（ECCV2008）提出了软量化编码（核视觉词典编码），其思想是局部特征不再使用一个视觉单词描述，而是由距离最近的K个视觉单词加权后进行描述，可以有效解决视觉单词的模糊性问题。稀疏编码：2009年，Yang等人7（CVPR2009，ScSPM）将稀疏编码应用到图像分类领域，用于替代向量量化等编码方法，得到一个高位的高度系数的特征表达，提高了特征表达的线性可分性，因此仅用线性分类器就可

11、得到当时最佳的结果。在其上的改进包括局部线性约束编码8（CVPR2010，LLCSPM）等。Fisher vector、super vector向量编码：Fisher向量9-10、超向量编码11是两种近年提出的性能最好的特征编码方法，它们都可以认为是编码局部特征与视觉单词的差。（出现于ECCV 2010）。Fisher向量编码同时融合了产生式模型和判别式模型的能力，与传统的基于重构的特征编码方法不同，它记录了局部特征与视觉单词之间的一阶差分和二阶差分。超向量编码则直接使用局部特征与最近的视觉单词的差来替换之前简单的硬投票。这种特征编码方式得到的特征向量表达通常是传统基于重构编码方法的M倍（这里

12、M 是局部特征的维度）。尽管维数很高，这两种方法在许多数据集上取得了最先进的性能，被应用于图像分类、标注、检索等方面。局部特征聚合描述符VLAD(vector of locally aggregated descriptors)也类似，方法是如同BOF先建立出含有K个visual word的codebook，而不同于BOF将一个local descriptor分类到最近的visual word中，VLAD所采用的是计算出local descriptor和每个visual word在每个分量上的差距，将每个分量的差距形成一个新的向量来代表图片。VLAD是CVPR 2010的论文12，其目标应用是

13、图像检索领域。其他：显著性编码13 引入了视觉显著性的概念，如果一个局部特征到最近和次近的视觉单词的距离差别很小，则认为这个局部特征是不“显著的”，从而编码后的响应也很小。显著性编码通过这样很简单的编码操作，在Caltech 101/256, PASCAL VOC 2007 等数据库上取得了非常好的结果，而且由于是解析的结果，编码速度也比稀疏编码快很多。该思想出自Huang等人的论文（CVPR2011），他们发现显著性表达配合最大值汇聚在特征编码中有重要的作用，并认为这正是稀疏编码、局部约束线性编码等之所以在图像分类任务上取得成功的原因。概率密度函数(p.d.f) 分布图14是一个较为新颖的思

14、想，来自CVPR 2013，基本思想是在词袋模型框架下，采取对特征概率密度图的方向梯度编码方法。该方法通过计算特征的pdf（概率密度函数）来获得特征的表达，其中计算pdf采用KDE（核密度估计）算法。这样一幅图像得到一个pdf，再套用HOG的计算模式表达一幅图像，也属于对特征的进一步加工，因此将其归类于编码方法。3、特征汇聚（pooling）主要是空间特征汇聚。空间金字塔匹配（Spatial Pyramid Matching, SPM）方法在当前基于词袋模型的分类框架中是极为常见的步骤。SPM在论文2（Lazebnik等，CVPR 2006）上被提出，截至本文落笔时在Google Schola

15、r上的引用已高达4000余次。该论文完整实现了基于词袋模型的图像分类框架。如下图。VQ Coding Dense SIFTSpatial PoolingClassifier Image Classification（示意图来自于Kai Yu，CVPR2012 tutorial）下面简要介绍一下这篇论文的思想和实现。Bag of Visual Words模型被大量地用在了图像表示中，但是BOVW模型完全缺失了特征点的位置信息。本文的提出即旨在解决此问题。该论文所提出的分类方法大致包括三个方面的要点，一是提取Dense-SIFT特征并用矢量量化(VQ)方式进行编码；二是对硬编码之后的特征向量进行空

16、间汇聚，采用直方图统计方法；三是用SVM分类时，采用histogram intersection核。首先，密集采样提取局部特征点。用边长为8像素的均匀网格(grid)划分图像，在4个grid形成的patch上提取SIFT描述子。每个patch是16*16像素的矩形，包含4*4个bin，每个bin是4*4像素。在每个bin中计算8个方向的梯度信息，于是每个patch由4*4*8=128维向量表征。patch移动的步长是网格边长8像素，整张图像的表征维度是patch的个数乘以128维。其次，空间汇聚方法。空间金字塔(spatial pyramid)是局部无序图像在不同空间分辨率上的聚集，相比图像分

17、块再计算局部特征的直方图具有多分辨率的优势。作者采用了一种多尺度的分块方法，呈现出一种层次金字塔的结构，在Caltech数据集上一般采取1*1、2*2、4*4空间分块的三层金字塔。每层金字塔的提取方式和分块直方图类似：将图像分成若干块，分别统计每一子块的特征，最后将所有块的特征拼接起来，形成完整的特征。这样就有了空间信息(Spatial)。最后，在分类器方面采取的直方图匹配方法，在SVM分类器中用直方图正交核进行分类。直方图匹配(Pyramid Matching)方法最初来自The Pyramid Match Kernel: Discriminative Classification with

18、 Sets of Image Features这篇论文，用来对特征构成的直方图进行相似度匹配。大致思想是在多分辨率的直方图上每层进行区间的匹配计算，每两个样本之间可以计算出一个匹配值，该值越高说明两样本越相似。整体得到一个样本数目为边长的匹配方阵，称为直方图正交核，用于SVM分类。 关于SPM方法的改进这里不做详述。4、分类（classifying）经过以上各个特征提取和汇聚的步骤后，最终要采取一种分类器完成分类。常见用于此任务的分类器有SVM、AdaBoost、Naïve Bayes等。许多方法采取非线性SVM分类器。分类核可以用常用的RBF核，也可以用上文提过的直方图正交核。采取

19、直方图正交核的分类准确率更高。线性SVM分类器由于其自身的优势，也为许多研究者所采用。这具体涉及到各个方法所形成最终分类特征的线性可分性。参考文献1Csurka G, Dance C, Fan L, et al. Visual categorization with bags of keypoints: ECCV 2004C.2Lazebnik S, Schmid C, Ponce J. Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories: CVPR 2006C.3

20、 A. Bosch, A. Zisserman, and X. Munoz. Image classifcation using random forests and ferns. In Proc. ICCV, 2007.4Seidenari L, Serra G, Bagdanov A, et al. Local pyramidal descriptors for image recognitionJ. PAMI 2013, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013.5Fernando B, Fr

21、omont E, Muselet D, et al. Discriminative feature fusion for image classification: CVPR 2012, 2012C.6van Gemert J C, Geusebroek J, Veenman C J, et al. Kernel codebooks for scene categorization: ECCV 2008, 2008C. Springer.7Yang J, Yu K, Gong Y, et al. Linear spatial pyramid matching using sparse codi

22、ng for image classification: CVPR 2009C.June.8Wang J, Yang J, Yu K, et al. Locality-constrained Linear Coding for image classification: CVPR 2010C.June.9Perronnin F, Dance C. Fisher Kernels on Visual Vocabularies for Image Categorization: CVPR 2007, 2007C.June.10Florent Perronnin, Jorge Sánchez, and Thomas Mensink. Improving the fisher kernel for lar