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