圖像分類(lèi)學(xué)習(xí)筆記-詞袋模型和空間金字塔匹配

1、圖像分類(lèi)學(xué)習(xí)筆記：詞袋模型和空間金字塔匹配Image Classification Framework: Bag-of-Words & Spatial Pyramid Matching一、基礎(chǔ)：詞袋模型（Bag of Words）Bag-of-Words（詞袋、詞包）模型，或稱(chēng)Bag of Features模型，源于文本分類(lèi)技術(shù)。在信息檢索中，假定對(duì)于一個(gè)文本，忽略其詞序和語(yǔ)法、句法。將其僅僅看作是一個(gè)詞的集合，每個(gè)詞都是彼此概率獨(dú)立的。這樣可以通過(guò)文檔中單詞出現(xiàn)的頻率來(lái)對(duì)文檔進(jìn)行描述與表達(dá)。Csurka等1 于2004年將其引入計(jì)算機(jī)視覺(jué)領(lǐng)域。其核心思想在于，圖像可以視為一種文檔對(duì)象

2、，圖像中不同的局部區(qū)域或其特征可看作構(gòu)成圖像的詞匯，其中相近的區(qū)域或其特征可以視作為一個(gè)詞。這樣，可以把每幅圖像描述為一個(gè)局部區(qū)域/關(guān)鍵點(diǎn)(Patches/Key Points)特征的無(wú)序集合。理論對(duì)應(yīng)關(guān)系如下：文檔單詞字典圖像特征聚類(lèi)中心特征聚類(lèi)集合用詞袋模型生成對(duì)一張圖像的描述向量的處理步驟：1、局部特征提取通過(guò)興趣點(diǎn)檢測(cè)、密集采樣或隨機(jī)采集，結(jié)合圖割區(qū)域、顯著區(qū)域等方式獲得圖像各處的局部特征。常用的是SIFT特征和Dense SIFT特征。 2、構(gòu)建視覺(jué)詞典在整個(gè)訓(xùn)練集上提取局部特征后，使用某種聚類(lèi)算法(如K-means)將局部特征進(jìn)行聚類(lèi)，每個(gè)聚類(lèi)中心可以看作是詞典中的一個(gè)視覺(jué)詞匯(V

3、isual Word)，相當(dāng)于文本檢索中的詞，視覺(jué)詞匯由聚類(lèi)中心對(duì)應(yīng)特征形成的碼字(code word)來(lái)表示（可看作一種特征量化過(guò)程）。所有視覺(jué)詞匯形成一個(gè)視覺(jué)詞典(Visual Vocabulary)，詞典中所含詞的個(gè)數(shù)反映了詞典的大小。3、特征量化編碼圖像中的每個(gè)特征都將被映射到視覺(jué)詞典的某個(gè)詞上，然后統(tǒng)計(jì)每個(gè)視覺(jué)詞在一張圖像上的出現(xiàn)次數(shù)，即可將該圖像描述為一個(gè)維數(shù)固定的直方圖向量。4、訓(xùn)練分類(lèi)模型并預(yù)測(cè)用于圖像分類(lèi)時(shí)，如上對(duì)訓(xùn)練集提取Bag-of-Features特征，在某種監(jiān)督學(xué)習(xí) （如SVM）的策略下，對(duì)訓(xùn)練集的Bag-of-Features特征向量進(jìn)行訓(xùn)練，獲得對(duì)象或場(chǎng)景的分類(lèi)模

4、型；在分類(lèi)模型下，對(duì)該特征進(jìn)行預(yù)測(cè)，從而實(shí)現(xiàn)對(duì)待測(cè)圖像的分類(lèi)。（示意圖片來(lái)源于網(wǎng)絡(luò)）詞袋模型中一些需要商榷的實(shí)現(xiàn)問(wèn)題：1、使用k-means聚類(lèi)，除了其K和初始聚類(lèi)中心選擇的問(wèn)題外，對(duì)于海量數(shù)據(jù)，輸入矩陣的巨大將使得內(nèi)存溢出及效率低下。訓(xùn)練集變化時(shí)重新聚類(lèi)的代價(jià)也很高。2、字典大小的選擇也是問(wèn)題，字典過(guò)大，單詞缺乏一般性，對(duì)噪聲敏感，計(jì)算量大，關(guān)鍵是圖象投影后的維數(shù)高；字典太小，單詞區(qū)分性能差，對(duì)相似的目標(biāo)特征無(wú)法表示。3、相似性測(cè)度函數(shù)用來(lái)將圖象特征分類(lèi)到單詞本的對(duì)應(yīng)單詞上，其涉及線型核，塌方距離測(cè)度核，直方圖交叉核等的選擇。4、將圖像表示成一個(gè)無(wú)序局部特征集的特征包方法，丟掉了所有的關(guān)于空

5、間特征布局的信息，在描述性上具有一定的有限性。為此， Lazebnik2提出了基于空間金字塔的Bag-of-Features，下面部分中將會(huì)詳述。此外，基于詞袋模型的改進(jìn)方法還有很多，見(jiàn)下一部分。二、綜述：基于詞袋模型的圖像分類(lèi)方法框架詞袋模型提出后，圖像分類(lèi)領(lǐng)域大量的研究工作開(kāi)始集中于該模型的相關(guān)研究，并逐漸形成了主要由以下四部分組成的圖像分類(lèi)方法框架：1、底層特征提?。⊿IFT、Dense SIFT、多特征）2、特征編碼（硬量化編碼、稀疏編碼、fisher vector等）3、特征匯聚（空間金字塔SPM）4、分類(lèi)器分類(lèi)（SVM、Adaboost、Naïve Bayes等）其中第三

6、部分的基礎(chǔ)是Lazebnik等人2 在CVPR 2006上提出的空間金字塔（SPM）方法，在當(dāng)前基于詞袋模型的分類(lèi)框架中幾乎已成為標(biāo)準(zhǔn)步驟。該論文也是完整實(shí)現(xiàn)了以上框架的經(jīng)典文章。后面有進(jìn)一步的介紹。（用于圖像分類(lèi)的另一主流框架：自從2006年Hinton教授于Science上發(fā)表文章，開(kāi)啟了深度學(xué)習(xí)在學(xué)術(shù)界和工業(yè)界的浪潮，深度學(xué)習(xí)框架也被大量應(yīng)用于圖像分類(lèi)領(lǐng)域，并取得了更加優(yōu)異的表現(xiàn)。此處不涉及。）e.g, SIFT, HOGVQ CodingAverage Pooling (obtain histogram)SVMLocal GradientsPooling（示意圖來(lái)自于Kai Yu，CV

7、PR2012 tutorial）1、底層特征提?。╠escribing）詞袋模型的基礎(chǔ)就是圖像局部特征提取，底層特征是圖像分類(lèi)檢測(cè)框架的第一步。在此方面的改進(jìn)主要包括局部特征描述方法的設(shè)計(jì)和采集方式的優(yōu)化。目前常用的是SIFT特征和Dense SIFT特征。特征采集方式主要包括興趣點(diǎn)檢測(cè)、密集采樣或隨機(jī)采集等。興趣點(diǎn)檢測(cè)通過(guò)某種準(zhǔn)則選取一些像素點(diǎn)、角點(diǎn)等，可以在較小的開(kāi)銷(xiāo)下得到有一定意義的表達(dá)。常用興趣點(diǎn)檢測(cè)算子有Harris角點(diǎn)、FAST算子、高斯差分算子DoG、高斯拉普拉斯算子LoG等。密集采樣則是用均勻網(wǎng)格劃分圖像，提取局部描述子向量。隨機(jī)采樣不必詳述。在諸多的局部圖像特征描述子中，SI

8、FT（Scale Invariant Feature Transform）是其中應(yīng)用最廣的。SIFT算法包括興趣點(diǎn)提取和局部描述兩步。Dense-SIFT則是用密集采樣方法結(jié)合SIFT的局部描述形成描述圖像的一組特征向量。用于圖像分類(lèi)的PHOW描述子3是Dense-SIFT 的變體，結(jié)合其他算法步驟在Caltech數(shù)據(jù)集上可以取得很好的分類(lèi)效果?；赟IFT改進(jìn)的局部描述子還包括SURF、PCA-SIFT、Color-SIFT等，一篇PAMI 2013的論文4提供了一個(gè)改進(jìn)的p-sift描述子。此外還有HOG、LBP、MSER等重要描述方法，以及近年來(lái)興起的一系列二值特征描述子BRIEF、OR

9、B、BRISK、FREAK等。（上圖：OpenCV 2.4.8 支持的局部描述子）此外，BOF為基礎(chǔ)的圖像分類(lèi)方法主要依賴(lài)于低級(jí)局部形狀特征。而融合多種線索如顏色、紋理、形狀的工作，足以提升分類(lèi)準(zhǔn)確度。采取多種特征融合的分類(lèi)框架也都取得了不錯(cuò)的結(jié)果，如Fernando等人5（CVPR2012）。2、特征編碼（coding）提取的底層特征中包含大量冗余和噪聲，或者向量沒(méi)有歸一化，為提高特征表達(dá)的魯棒性，使之適用于圖像分類(lèi)任務(wù)，需要對(duì)提取到的特征向量集合進(jìn)行一定變換，獲得更具有區(qū)分性的圖像層級(jí)表達(dá)。這就是特征編碼（coding）。這一步對(duì)識(shí)別性能具有至關(guān)重要的作用，因而大量的研究工作都集中在尋找更

10、加強(qiáng)大的特征編碼方法上。硬編碼與軟編碼：Bag of Words 模型使用的編碼方式是向量量化編碼，這種編碼方式最為簡(jiǎn)單直觀，只是利用量化的思想進(jìn)行距離計(jì)算與聚合，因此又稱(chēng)為硬編碼。作為一種改進(jìn)，Gemert等人6（ECCV2008）提出了軟量化編碼（核視覺(jué)詞典編碼），其思想是局部特征不再使用一個(gè)視覺(jué)單詞描述，而是由距離最近的K個(gè)視覺(jué)單詞加權(quán)后進(jìn)行描述，可以有效解決視覺(jué)單詞的模糊性問(wèn)題。稀疏編碼：2009年，Yang等人7（CVPR2009，ScSPM）將稀疏編碼應(yīng)用到圖像分類(lèi)領(lǐng)域，用于替代向量量化等編碼方法，得到一個(gè)高位的高度系數(shù)的特征表達(dá)，提高了特征表達(dá)的線性可分性，因此僅用線性分類(lèi)器就可

11、得到當(dāng)時(shí)最佳的結(jié)果。在其上的改進(jìn)包括局部線性約束編碼8（CVPR2010，LLCSPM）等。Fisher vector、super vector向量編碼：Fisher向量9-10、超向量編碼11是兩種近年提出的性能最好的特征編碼方法，它們都可以認(rèn)為是編碼局部特征與視覺(jué)單詞的差。（出現(xiàn)于ECCV 2010）。Fisher向量編碼同時(shí)融合了產(chǎn)生式模型和判別式模型的能力，與傳統(tǒng)的基于重構(gòu)的特征編碼方法不同，它記錄了局部特征與視覺(jué)單詞之間的一階差分和二階差分。超向量編碼則直接使用局部特征與最近的視覺(jué)單詞的差來(lái)替換之前簡(jiǎn)單的硬投票。這種特征編碼方式得到的特征向量表達(dá)通常是傳統(tǒng)基于重構(gòu)編碼方法的M倍（這里

12、M 是局部特征的維度）。盡管維數(shù)很高，這兩種方法在許多數(shù)據(jù)集上取得了最先進(jìn)的性能，被應(yīng)用于圖像分類(lèi)、標(biāo)注、檢索等方面。局部特征聚合描述符VLAD(vector of locally aggregated descriptors)也類(lèi)似，方法是如同BOF先建立出含有K個(gè)visual word的codebook，而不同于BOF將一個(gè)local descriptor分類(lèi)到最近的visual word中，VLAD所采用的是計(jì)算出local descriptor和每個(gè)visual word在每個(gè)分量上的差距，將每個(gè)分量的差距形成一個(gè)新的向量來(lái)代表圖片。VLAD是CVPR 2010的論文12，其目標(biāo)應(yīng)用是

13、圖像檢索領(lǐng)域。其他：顯著性編碼13 引入了視覺(jué)顯著性的概念，如果一個(gè)局部特征到最近和次近的視覺(jué)單詞的距離差別很小，則認(rèn)為這個(gè)局部特征是不“顯著的”，從而編碼后的響應(yīng)也很小。顯著性編碼通過(guò)這樣很簡(jiǎn)單的編碼操作，在Caltech 101/256, PASCAL VOC 2007 等數(shù)據(jù)庫(kù)上取得了非常好的結(jié)果，而且由于是解析的結(jié)果，編碼速度也比稀疏編碼快很多。該思想出自Huang等人的論文（CVPR2011），他們發(fā)現(xiàn)顯著性表達(dá)配合最大值匯聚在特征編碼中有重要的作用，并認(rèn)為這正是稀疏編碼、局部約束線性編碼等之所以在圖像分類(lèi)任務(wù)上取得成功的原因。概率密度函數(shù)(p.d.f) 分布圖14是一個(gè)較為新穎的思

14、想，來(lái)自CVPR 2013，基本思想是在詞袋模型框架下，采取對(duì)特征概率密度圖的方向梯度編碼方法。該方法通過(guò)計(jì)算特征的pdf（概率密度函數(shù)）來(lái)獲得特征的表達(dá)，其中計(jì)算pdf采用KDE（核密度估計(jì)）算法。這樣一幅圖像得到一個(gè)pdf，再套用HOG的計(jì)算模式表達(dá)一幅圖像，也屬于對(duì)特征的進(jìn)一步加工，因此將其歸類(lèi)于編碼方法。3、特征匯聚（pooling）主要是空間特征匯聚?？臻g金字塔匹配（Spatial Pyramid Matching, SPM）方法在當(dāng)前基于詞袋模型的分類(lèi)框架中是極為常見(jiàn)的步驟。SPM在論文2（Lazebnik等，CVPR 2006）上被提出，截至本文落筆時(shí)在Google Schola

15、r上的引用已高達(dá)4000余次。該論文完整實(shí)現(xiàn)了基于詞袋模型的圖像分類(lèi)框架。如下圖。VQ Coding Dense SIFTSpatial PoolingClassifier Image Classification（示意圖來(lái)自于Kai Yu，CVPR2012 tutorial）下面簡(jiǎn)要介紹一下這篇論文的思想和實(shí)現(xiàn)。Bag of Visual Words模型被大量地用在了圖像表示中，但是BOVW模型完全缺失了特征點(diǎn)的位置信息。本文的提出即旨在解決此問(wèn)題。該論文所提出的分類(lèi)方法大致包括三個(gè)方面的要點(diǎn)，一是提取Dense-SIFT特征并用矢量量化(VQ)方式進(jìn)行編碼；二是對(duì)硬編碼之后的特征向量進(jìn)行空

16、間匯聚，采用直方圖統(tǒng)計(jì)方法；三是用SVM分類(lèi)時(shí)，采用histogram intersection核。首先，密集采樣提取局部特征點(diǎn)。用邊長(zhǎng)為8像素的均勻網(wǎng)格(grid)劃分圖像，在4個(gè)grid形成的patch上提取SIFT描述子。每個(gè)patch是16*16像素的矩形，包含4*4個(gè)bin，每個(gè)bin是4*4像素。在每個(gè)bin中計(jì)算8個(gè)方向的梯度信息，于是每個(gè)patch由4*4*8=128維向量表征。patch移動(dòng)的步長(zhǎng)是網(wǎng)格邊長(zhǎng)8像素，整張圖像的表征維度是patch的個(gè)數(shù)乘以128維。其次，空間匯聚方法?？臻g金字塔(spatial pyramid)是局部無(wú)序圖像在不同空間分辨率上的聚集，相比圖像分

17、塊再計(jì)算局部特征的直方圖具有多分辨率的優(yōu)勢(shì)。作者采用了一種多尺度的分塊方法，呈現(xiàn)出一種層次金字塔的結(jié)構(gòu)，在Caltech數(shù)據(jù)集上一般采取1*1、2*2、4*4空間分塊的三層金字塔。每層金字塔的提取方式和分塊直方圖類(lèi)似：將圖像分成若干塊，分別統(tǒng)計(jì)每一子塊的特征，最后將所有塊的特征拼接起來(lái)，形成完整的特征。這樣就有了空間信息(Spatial)。最后，在分類(lèi)器方面采取的直方圖匹配方法，在SVM分類(lèi)器中用直方圖正交核進(jìn)行分類(lèi)。直方圖匹配(Pyramid Matching)方法最初來(lái)自The Pyramid Match Kernel: Discriminative Classification with

18、 Sets of Image Features這篇論文，用來(lái)對(duì)特征構(gòu)成的直方圖進(jìn)行相似度匹配。大致思想是在多分辨率的直方圖上每層進(jìn)行區(qū)間的匹配計(jì)算，每?jī)蓚€(gè)樣本之間可以計(jì)算出一個(gè)匹配值，該值越高說(shuō)明兩樣本越相似。整體得到一個(gè)樣本數(shù)目為邊長(zhǎng)的匹配方陣，稱(chēng)為直方圖正交核，用于SVM分類(lèi)。 關(guān)于SPM方法的改進(jìn)這里不做詳述。4、分類(lèi)（classifying）經(jīng)過(guò)以上各個(gè)特征提取和匯聚的步驟后，最終要采取一種分類(lèi)器完成分類(lèi)。常見(jiàn)用于此任務(wù)的分類(lèi)器有SVM、AdaBoost、Naïve Bayes等。許多方法采取非線性SVM分類(lèi)器。分類(lèi)核可以用常用的RBF核，也可以用上文提過(guò)的直方圖正交核。采取

19、直方圖正交核的分類(lèi)準(zhǔn)確率更高。線性SVM分類(lèi)器由于其自身的優(yōu)勢(shì)，也為許多研究者所采用。這具體涉及到各個(gè)方法所形成最終分類(lèi)特征的線性可分性。參考文獻(xiàn)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