摘要

雖然現(xiàn)在已經(jīng)是深度學(xué)習(xí)的時(shí)代了，傳統(tǒng)的機(jī)器學(xué)習(xí)方法日漸甚微，不過(guò)有些算法還是有著旺盛的生命力，比如SIFT、SVM，在一些深度學(xué)習(xí)算法中也能看到它們的影子。這些人工設(shè)計(jì)的經(jīng)典特征和分類(lèi)器可以讓我們感受到那個(gè)時(shí)代計(jì)算機(jī)視覺(jué)的魅力?；ヂ?lián)網(wǎng)上，需要處理識(shí)別的圖像越來(lái)越多，為此圖像分類(lèi)搜索引擎所需的分類(lèi)能力要求越來(lái)越高，在圖像處理領(lǐng)域內(nèi)也成為越來(lái)越熱點(diǎn)的課題。對(duì)目標(biāo)進(jìn)行分類(lèi)是人類(lèi)的天生能力，對(duì)于計(jì)算機(jī)，現(xiàn)實(shí)世界的呈現(xiàn)方式大多是以圖片的方式（視頻本質(zhì)上也是圖片）輸入，因而圖片的分類(lèi)是實(shí)現(xiàn)人工智能的重要部分。詞袋模型是基于自然語(yǔ)言模型而提出的一種文檔描述方法，被廣泛研究用于圖像的分析和處理中。本文介紹了一種基于詞袋的圖片分類(lèi)方法，首先提取圖片的SIFT特征通過(guò)聚類(lèi)得到“視覺(jué)詞典”，然后統(tǒng)計(jì)詞頻獲得突破的詞袋描述，最后通過(guò)SVM進(jìn)行有監(jiān)督的圖片分類(lèi)。

源碼及完整報(bào)告：

算法使用C++ MFC實(shí)現(xiàn)，基于OpenCV。https://mbd.pub/o/bread/ZJuTlZ5u 或https://www.syjshare.com/res/1TUR49UG

詞袋（Bag of Words, BoW）

在圖片的分類(lèi)中首先需要解決的是對(duì)圖像的描述，最初對(duì)圖像的描述是直接利用圖片的顏色信息，但是圖像的色彩往往隨著光強(qiáng)，物體方向等變化而變化，因此魯棒性很差?，F(xiàn)在的方式是在圖片中提取能夠表征圖片全局或局部的特征作為對(duì)圖像的描述，從而使得得到的圖像描述具有光照不變性、旋轉(zhuǎn)不變性、尺度不變性等特性。然而這種直接基于圖像底層基礎(chǔ)上的特征不含有語(yǔ)義信息，無(wú)法完成對(duì)圖像生成語(yǔ)義的理解。而基于詞袋的圖像描述則在一定程度上解決了這一問(wèn)題。

詞袋模型最先是由Josef等基于自然語(yǔ)言處理模型而提出的。在這種模型中，文本（段落或者文檔）被看作是無(wú)序的詞匯集合，忽略語(yǔ)法甚至是單詞的順序。詞袋模型的原理非常簡(jiǎn)單，詞袋模型是文本的簡(jiǎn)化描述模型。類(lèi)比一篇文章由很多文字 (textual words) 組合而成，如果將一張圖片表示成由許多 視覺(jué)單詞（visual words） 組合而成，就能將過(guò)去在文本檢索（text retrieval）領(lǐng)域的技巧直接利用在圖像檢索（image retrieval）中，以文字檢索系統(tǒng)現(xiàn)在的效率，圖像表示的“文字化”也有助于大規(guī)模(large-scale)圖像檢索系統(tǒng)的效率。

詞袋模型中關(guān)鍵的一步是要生成詞典，對(duì)圖片來(lái)說(shuō)即是要生成“視覺(jué)詞典”，而這首先需要提取圖片的特征形成圖片特征描述子集合，然后通過(guò)聚類(lèi)的方式形成視覺(jué)單詞，從而形成視覺(jué)詞典。再統(tǒng)計(jì)待分類(lèi)圖片的詞頻，通過(guò)分類(lèi)器即可實(shí)現(xiàn)對(duì)圖片的分類(lèi)或高級(jí)語(yǔ)義的理解。

基于詞袋模型的圖片分類(lèi)基本流程

如引言所述，基于詞袋的模型首先需要要在大量的已知類(lèi)別的訓(xùn)練圖片集中提取圖片特征形成多個(gè)預(yù)選詞，然后通過(guò)聚類(lèi)形成視覺(jué)詞典，然后通過(guò)詞典統(tǒng)計(jì)圖片的詞頻從而形成圖片的基于視覺(jué)詞典的特征描述。將得到圖片詞袋描述及其類(lèi)別作為輸入訓(xùn)練分類(lèi)器。分類(lèi)時(shí)，首先提取待分類(lèi)圖片的特征，然后形成圖片的詞袋描述，將描述輸入到訓(xùn)練得到的分類(lèi)器，即可得到待分類(lèi)圖片的類(lèi)別 特征提取是形成詞袋的關(guān)鍵一步，也是一個(gè)研究的熱點(diǎn)。目前比較著名的特征提取方法主要有HoG，SIFT，LBP等方法。SIFT（Scale-Invariant Feature Transform），即尺度不變特征最早于1999年由David Lowe 提出，并在2004年進(jìn)一步改進(jìn)。SIFT特征是圖像的局部特征，其對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對(duì)視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。SIFT特征提取通過(guò)尺度空間極值檢測(cè)、關(guān)鍵點(diǎn)定位、主方向確定、關(guān)鍵點(diǎn)描述四步最終形成128維的具有多種不變特性的特征點(diǎn)，能夠很好的表征圖片的局部特征。這些不變性使得SIFT成為目前最火的特征提取算法之一。

盡管有計(jì)算復(fù)雜度高的不足，SIFT算法仍然是性能最好、應(yīng)用最廣泛的基于局部特征的圖像特征提取方法。因而本文在特征提取部分選取SIFT算法作簡(jiǎn)要介紹。

SIFT特征提取通過(guò)尺度空間極值檢測(cè)、關(guān)鍵點(diǎn)定位、主方向確定、關(guān)鍵點(diǎn)描述四步最終形成128維的具有多種不變特性的特征點(diǎn)。

多尺度空間極值點(diǎn)檢測(cè)

SIFT要查找的點(diǎn)是一些十分突出的點(diǎn)，這些點(diǎn)不會(huì)因光照條件改變，尺度變化等環(huán)境變化而消失，比如角點(diǎn)、邊緣點(diǎn)、暗區(qū)域的亮點(diǎn)以及亮區(qū)域的暗點(diǎn)。要保證尺度不變性，首先要保證提取出的特征點(diǎn)不因目標(biāo)的尺度變化而變化。這個(gè)可以通過(guò)建立尺度空間來(lái)完成。 尺度空間中各尺度圖像的模糊程度逐漸變大，能夠模擬人在距離目標(biāo)由近到遠(yuǎn)時(shí)目標(biāo)在視網(wǎng)膜上的形成過(guò)程。 高斯核是唯一可以產(chǎn)生多尺度空間的核，一個(gè)圖像的尺度，決定圖像的平滑程度，值越大圖像越粗糙（模糊），反之越精細(xì)。通過(guò)卷積運(yùn)算，一幅圖像可以生成圖2所示的高斯金字塔空間，這個(gè)空間由幾塔（octave）圖像組成，一塔圖像包括幾層（interval）圖像。同塔圖像大小一致，尺度不同，塔間圖片是降采樣的關(guān)系。

通過(guò)上面的操作，得到了塔數(shù)為O，塔內(nèi)層數(shù)為S+3的高斯金字塔。LoG(Laplacian of Gaussian) 算子能夠很好的找到圖像中的興趣點(diǎn)，但是需要大量的計(jì)算。而DoG(Difference of Gaussian)算子與LoG算子由直接關(guān)系，且計(jì)算量很小，所有可以用來(lái)代替LoG來(lái)進(jìn)行興趣點(diǎn)的查找。DoG：

通過(guò)DoG可以得到尺度空間的差分高斯金字塔

生成了DoG高斯金字塔，就可以在該尺度空間檢測(cè)極值點(diǎn)。?一個(gè)點(diǎn)如果在DOG尺度空間本層以及上下兩層的26個(gè)領(lǐng)域中是最大或最小值時(shí)，就認(rèn)為該點(diǎn)是圖像在該尺度下的一個(gè)特征點(diǎn)。

通過(guò)上面的步驟，就可以粗略的檢測(cè)到圖像中的關(guān)鍵點(diǎn)。

關(guān)鍵點(diǎn)精確定位

以上極值點(diǎn)的搜索是在離散空間中進(jìn)行的，檢測(cè)到的極值點(diǎn)并不是真正意義上的極值點(diǎn)。同時(shí)還要去除低對(duì)比度和邊界響應(yīng)這些不穩(wěn)定的關(guān)鍵點(diǎn)。

通過(guò)關(guān)鍵點(diǎn)周?chē)c(diǎn)的信息擬合三維二次函數(shù)可以精確確定關(guān)鍵點(diǎn)的位置, DoG函數(shù)在圖像邊緣有較強(qiáng)的邊緣響應(yīng)，而一旦特征落在圖形的邊緣上，這些點(diǎn)就是不穩(wěn)定的點(diǎn)，因此還需要排除邊緣響應(yīng)。這一點(diǎn)可以通過(guò)Hessian矩陣完成。

關(guān)鍵點(diǎn)主方向計(jì)算

上一節(jié)中確定了每幅圖中的特征點(diǎn)，為每個(gè)特征點(diǎn)計(jì)算一個(gè)方向，依照這個(gè)方向做進(jìn)一步的計(jì)算，?利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。

首先在與關(guān)鍵點(diǎn)尺度相應(yīng)的高斯圖像?上計(jì)算關(guān)鍵點(diǎn)領(lǐng)域窗口內(nèi)像素點(diǎn)的梯度幅度和方向：

然后用直方圖統(tǒng)計(jì)領(lǐng)域像素的梯度方向和幅值，梯度直方圖的范圍是0~360度，其中，每10度一個(gè)柱，共36個(gè)柱。直方圖的主峰值（最大峰值）代表了關(guān)鍵點(diǎn)處鄰域梯度的主方向，即關(guān)鍵點(diǎn)的主方向。

至此，圖像的關(guān)鍵點(diǎn)已檢測(cè)完畢，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息：位置、尺度、方向；同時(shí)也就使關(guān)鍵點(diǎn)具備平移、縮放、和旋轉(zhuǎn)不變性。

生成描述子

描述的目的是在關(guān)鍵點(diǎn)計(jì)算后，用一組向量將這個(gè)關(guān)鍵點(diǎn)描述出來(lái)，這個(gè)描述子不但包括關(guān)鍵點(diǎn)，也包括關(guān)鍵點(diǎn)周?chē)鷮?duì)其有貢獻(xiàn)的像素點(diǎn)。用來(lái)作為目標(biāo)匹配的依據(jù)，也可使關(guān)鍵點(diǎn)具有更多的不變特性，如光照變化、3D視點(diǎn)變化等。

首先，將坐標(biāo)軸旋轉(zhuǎn)到關(guān)鍵點(diǎn)的主方向。只有以主方向?yàn)榱泓c(diǎn)方向來(lái)描述關(guān)鍵點(diǎn)才能使其具有旋轉(zhuǎn)不變性。 其次，以關(guān)鍵點(diǎn)為中心取1616的窗口。然后計(jì)算每個(gè)44的小塊上計(jì)算8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累加值（高斯加權(quán)），即可形成一個(gè)種子點(diǎn)。每個(gè)種子點(diǎn)有8個(gè)方向向量信息。 這樣就可以對(duì)每個(gè)特征點(diǎn)形成一個(gè)448=128維的描述子，每一維都可以表示4*4個(gè)格子中一個(gè)的scale/orientation.?將這個(gè)向量歸一化之后，就進(jìn)一步去除了光照的影響。 這個(gè)128維的描述向量就可以用于圖像匹配等應(yīng)用中了。

特征詞典的生成

上一節(jié)得到的SIFT特征點(diǎn)即是預(yù)選的“視覺(jué)單詞”，當(dāng)提取了若干特征點(diǎn)后，其數(shù)量往往巨大，而且特征點(diǎn)是局部特征。但是在龐大的特征數(shù)據(jù)庫(kù)中，僅僅幾個(gè)單一的特征點(diǎn)無(wú)法完成圖像描述的重大任務(wù)。此時(shí)，聚類(lèi)就顯得格外重要，它將大量相似的128維特征向量通過(guò)一定的規(guī)則進(jìn)行整合，尋找出若干相似的特征點(diǎn)聚為一類(lèi)作為詞典中的一個(gè)詞，以此來(lái)代表一類(lèi)特征點(diǎn)，方便后期的圖像描述，增加描述的可信度，提高描述的速度。 K-means算法是很典型的基于距離的聚類(lèi)算法，采用距離作為相似性的評(píng)價(jià)指標(biāo)，即認(rèn)為兩個(gè)對(duì)象的距離越近，其相似度就越大。該算法認(rèn)為簇是由距離靠近的對(duì)象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。其算法過(guò)程如下： 1）從N個(gè)文檔隨機(jī)選取K個(gè)文檔作為質(zhì)心 2）對(duì)剩余的每個(gè)文檔測(cè)量其到每個(gè)質(zhì)心的距離，并把它歸到最近的質(zhì)心的類(lèi) 3）重新計(jì)算已經(jīng)得到的各個(gè)類(lèi)的質(zhì)心 4）迭代2～3步直至新的質(zhì)心與原質(zhì)心相等或小于指定閾值，算法結(jié)束。 ?

經(jīng)過(guò)K-means聚類(lèi)，圖片中提取出的SIFT特征就形成了對(duì)應(yīng)的視覺(jué)詞典。

SVM分類(lèi)器

通過(guò)聚類(lèi)得到的詞典，即可將圖片的特征轉(zhuǎn)化為對(duì)應(yīng)的詞頻表（如統(tǒng)計(jì)直方圖）。這樣每幅圖片就可以用一個(gè)詞典向量來(lái)表示了，然后將這些向量作為分類(lèi)器的輸入進(jìn)行訓(xùn)練即可得到分類(lèi)器。本文中選擇的是SVM（支持向量機(jī)）進(jìn)行分類(lèi)。 支持向量機(jī)（英語(yǔ)：Support Vector Machine，常簡(jiǎn)稱為SVM）是一種監(jiān)督式學(xué)習(xí)的方法，可廣泛地應(yīng)用于統(tǒng)計(jì)分類(lèi)以及回歸分析。 支持向量機(jī)將向量映射到一個(gè)更高維的空間里，在這個(gè)空間里建立有一個(gè)最大間隔超平面。在分開(kāi)數(shù)據(jù)的超平面的兩邊建有兩個(gè)互相平行的超平面。建立方向合適的分隔超平面使兩個(gè)與之平行的超平面間的距離最大化。其假定為，平行超平面間的距離或差距越大，分類(lèi)器的總誤差越小。支持向量機(jī)通過(guò)學(xué)習(xí)已知樣本來(lái)獲得決策邊界，來(lái)完成對(duì)未知樣本的分類(lèi)。這種學(xué)習(xí)是有監(jiān)督的學(xué)習(xí)。 本文中訓(xùn)練時(shí)，是將多類(lèi)問(wèn)題看作二類(lèi)問(wèn)題，即訓(xùn)練某類(lèi)時(shí)以此類(lèi)為正樣本，其它類(lèi)為負(fù)樣本。測(cè)試時(shí)，計(jì)算測(cè)試樣本分作某一類(lèi)的概率，取最大概率的分類(lèi)為測(cè)試樣本的類(lèi)別。

利用決策邊界進(jìn)行有監(jiān)督分類(lèi)

實(shí)驗(yàn)結(jié)果

測(cè)試圖片使用corel圖片庫(kù)，選擇了其中5個(gè)類(lèi)別各20張圖作為訓(xùn)練集訓(xùn)練分類(lèi)器，并選擇同類(lèi)別各20張作為測(cè)試集測(cè)試分類(lèi)的準(zhǔn)確性。并且與K階最近鄰分類(lèi)器作對(duì)比（取K為9）。測(cè)試平臺(tái)為T(mén)6600CPU，系統(tǒng)為WINDOWS8.1。

訓(xùn)練圖片集

測(cè)試時(shí)通過(guò)加大Kmeans聚類(lèi)的類(lèi)數(shù)可以達(dá)到不同的效果，基本上Kmeans類(lèi)數(shù)越大，SVM分類(lèi)的效果越好。這也很容易理解，K-means聚類(lèi)個(gè)數(shù)即代表了生成的詞典中詞的個(gè)數(shù)，詞數(shù)越多，對(duì)圖像的描述更精確。但隨著詞數(shù)的增加，字典的生成時(shí)間會(huì)增加。

2者的關(guān)系如下表：

????由表可以看出，對(duì)比KNN分類(lèi)，SVM在單詞個(gè)數(shù)不太小時(shí)，都會(huì)好于KNN，并且在單詞數(shù)較大時(shí)，效果遠(yuǎn)好于KNN的分類(lèi)，準(zhǔn)確率達(dá)到了94%。

總結(jié)

本文介紹了一個(gè)典型的基于詞袋和SVM分類(lèi)器的圖片分類(lèi)方法?；谠~袋的圖片分析技術(shù)由于具有對(duì)圖片進(jìn)行語(yǔ)義理解的潛力，因此得到廣泛研究。SVM分類(lèi)器也是目前非?；馃岬姆诸?lèi)方法之一。實(shí)驗(yàn)結(jié)果表明，二者結(jié)合用于圖片的有監(jiān)督分類(lèi)可以得到很好的效果。但由于詞袋沒(méi)有考慮詞的順序，對(duì)于圖片也就是沒(méi)有考慮特征的空間分布信息，因而還有待改進(jìn)，也有人提出了Spatial pyramid matching方法進(jìn)行分尺度，分塊的處理，得到了一定改善，但仍有待研究。

參考文獻(xiàn)

[1]?Lowe, David G. "Distinctive image features from scale-invariant keypoints." International journal of computer vision?60.2 (2004): 91-110.

[2] Wallach, Hanna M. "Topic modeling: beyond bag-of-words." Proceedings of the 23rd international conference on Machine learning. ACM, 2006.

[3] Dalal, Navneet, and Bill Triggs. "Histograms of oriented gradients for human detection." Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on. Vol. 1. IEEE, 2005.

[4] Chang, Chih-Chung, and Chih-Jen Lin. "LIBSVM: a library for support vector machines." ACM Transactions on Intelligent Systems and Technology (TIST) 2.3 (2011): 27.

[5] Tong, Simon, and Edward Chang. "Support vector machine active learning for image retrieval." Proceedings of the ninth ACM international conference on Multimedia. ACM, 2001.

源碼及完整報(bào)告：

算法使用C++ MFC實(shí)現(xiàn)，基于OpenCV。https://mbd.pub/o/bread/ZJuTlZ5u 或https://www.syjshare.com/res/1TUR49UG