基于改進(jìn)BOF算法的圖像識別和分類

李康順，王福濱張麗霞李偉

（1. 華南農(nóng)業(yè)大學(xué) 信息學(xué)院，廣東 廣州，510642；2. 江西理工大學(xué) 信息工程學(xué)院，江西 贛州，341000）

基于改進(jìn)BOF算法的圖像識別和分類

李康順1，2，王福濱1，張麗霞1，李偉1，2

（1. 華南農(nóng)業(yè)大學(xué) 信息學(xué)院，廣東 廣州，510642；2. 江西理工大學(xué) 信息工程學(xué)院，江西 贛州，341000）

對bag of features（BOF）算法進(jìn)行研究與改進(jìn)，并將其應(yīng)用到圖像識別和分類中。針對傳統(tǒng)BOF算法執(zhí)行效率低以及分類精度不夠高等缺陷，提出一種結(jié)合SURF（speeded up robust feature）與空間金字塔匹配原理的優(yōu)化方法相結(jié)合的圖像識別與分類算法。SURF算法可提高執(zhí)行效率，而空間金字塔匹配原理的優(yōu)化方法可提高分類精度。首先對分類圖像應(yīng)用SURF算法提取特征描述符并生成視覺詞典，該算法提取的視覺詞典能更有效地表示圖像特征，且能應(yīng)對多變的尺度；然后應(yīng)用空間金字塔匹配原理對圖像采用視覺詞典的直方圖表示，進(jìn)一步提高分類的準(zhǔn)確度；最后利用LIBSVM分類器進(jìn)行分類。在Graz，Caltech-256和Pascal VOC 2012這3個數(shù)據(jù)集中進(jìn)行實驗測試。研究結(jié)果表明：該方法與傳統(tǒng)的 BOF算法相比提高了執(zhí)行效率和分類精度。在數(shù)據(jù)實驗中通過與近幾年一些相關(guān)研究工作在分類準(zhǔn)確率方面進(jìn)行對比，該方法具有很大的優(yōu)越性。

bag of features算法；圖像識別分類；SURF；空間金字塔匹配

隨著多媒體技術(shù)的不斷發(fā)展，圖像逐漸成為一種主流的視覺信息載體。在圖像處理和應(yīng)用領(lǐng)域，圖像識別和分類一直是研究的熱點。而隨著網(wǎng)絡(luò)全球化的發(fā)展以及涌現(xiàn)出來的各種門戶網(wǎng)站，使得圖像數(shù)量大量激增，這給圖像識別和分類帶來了巨大的困難。如何在浩瀚的數(shù)據(jù)中準(zhǔn)確地獲取用戶所需的信息并進(jìn)行處理，成為計算機(jī)視覺領(lǐng)域中亟待解決的問題之一。目前已經(jīng)有很多比較成熟的圖像識別和分類算法，BOF（bag of features）算法就是其中之一。BOF算法的思想來自于BOW（bag of words）［1-2］算法，BOW算法最初用于文檔匹配。近年來，由CSURKA等［3］將該算法的思想移植到圖像處理領(lǐng)域［4］，通過對圖像采用SIFT等相關(guān)的特征提取算法將圖像轉(zhuǎn)換為特征描述符，得到大量特征用來表示圖像的關(guān)鍵詞；然后采用K-Meams聚類方法對得到的大量單詞進(jìn)行聚類，將聚類的中心定義為視覺單詞，K-Meams算法得出所有的聚類中心構(gòu)成視覺詞典；最后將分類圖像進(jìn)行統(tǒng)一處理，通過SVM分類器對其進(jìn)行分類。有部分研究者將該算法應(yīng)用到行為識別［5］中，提高了識別率。還有部分研究人員創(chuàng)新地將該算法應(yīng)用到糖尿病患者的食品識別系統(tǒng)中［6］，大大地提高了系統(tǒng)的魯棒性。近年來，BOF算法在醫(yī)療領(lǐng)域中也取得了重要成果［7-8］，為醫(yī)療事業(yè)做出了不少的貢獻(xiàn)。然而，BOF算法在圖像識別和分類問題的應(yīng)用中存在一定的問題，執(zhí)行速度不夠快，分類精度不夠高，因此，需對其進(jìn)行優(yōu)化。傳統(tǒng)的 BOF算法采用 SIFT（scale-invariant feature transform）［9］特征描述符。K-Means聚類方法和 SVM（Support Vector Machine）分類器來實現(xiàn)。由于SIFT算法對復(fù)雜背景的特征提取魯棒性不足，為了提高算法的魯棒性，文獻(xiàn)［10］提出了一種基于部分模型的方法，但該方法復(fù)雜度比較高。簡單的應(yīng)用K-Means聚類方法和SVM分類器實現(xiàn)的BOF算法擬合度和分類的精度都不夠高，文獻(xiàn)［11］ 通過使用概率學(xué)的思想，通過最大期望（Expectation Maximization，EM）算法對BOF模型進(jìn)行擬合，雖然在一定程度上提高了精度，但對于復(fù)雜背景的圖像仍然存在著效率低以及分類精度不高的不足。本文作者針對BOF算法的缺點以及現(xiàn)有研究的不足，采用一種SIFT的改進(jìn)算法SURF（speeded up robust feature）［12］算法來提取圖像特征描述符，以降低BOF算法的復(fù)雜度、提高運(yùn)行效率以及解決存儲要求過高的問題；引入空間金字塔匹配原理并采用基于視覺詞典的直方圖表示，提高BOF算法分類的精度；為了提高分類的效率，采用快速有效的LIBSVM［13］分類器。將SURF算法和空間金字塔匹配原理結(jié)合用到BOF算法中，在Graz，Caltech-256以及Pascal VOC 2012這3個數(shù)據(jù)集下都可以達(dá)到較好的分類效果。

1 改進(jìn)的BOF算法

本文應(yīng)用BOF算法有3個步驟：特征提取和特征描述符的轉(zhuǎn)化、視覺詞典的構(gòu)建、識別和分類。圖1所示為BOF算法的基本流程。

圖1 BOF算法的基本流程Fig.1 Basic flow of BOF algorithm

根據(jù)圖1，應(yīng)用 BOF算法的實現(xiàn)過程可以歸納如下。

首先，本文采用SURF算法代替?zhèn)鹘y(tǒng)的SIFT算法，利用Hessian矩陣來檢測特征點，每個特征用64維的向量進(jìn)行表示，從圖像中抽取出具有代表性的全局特征和局部特征作為圖像的描述符。然后，采用K-Meams聚類方法，本文并沒有指定聚類中心，而是通過隨機(jī)選取聚類中心，通過有限次數(shù)的迭代，最終收斂出聚類中心即詞典。傳統(tǒng)的方法將圖像表示成為統(tǒng)計直方圖的形式，如圖2所示。而本文引用了空間金字塔匹配方案，提高了分類的準(zhǔn)確度。最后使用LIBSVM分類器對其進(jìn)行分類。

1.1 SURF算法

在BOF算法中進(jìn)行特征提取時，常用的特征描述符的算法有SIFT，GLOH（gradient location-orientation histogram）［14］和PCA-SIFT等［15］。SIFT算法是不變性特征檢測技術(shù)的一種基于尺度空間，對圖像縮放、旋轉(zhuǎn)、光照變化甚至仿射變換保持不變性的圖像局部特征描述方法。但是該算法計算數(shù)據(jù)量大，時間復(fù)雜度高，算法耗時較長。針對上述缺點，本文提出一種基于SURF算法的特征描述符方法，以提高BOF算法的運(yùn)算速度和性能。

圖2 基于視覺單詞的直方圖Fig.2 Histogram based on visual word

SURF算法的基本流程主要包括特征點檢測（構(gòu)建Hessian矩陣，構(gòu)建尺度空間，精確定位特征點），主方向確定以及生成特征點描述符。

1.1.1 特征點檢測

在圖像I中X=（x，y）處的點，在尺度σ上的Hessian矩陣定義為

本文采用方框濾波（box filters）近似代替二階高斯濾波，采用計算量與模板大小無關(guān)的積分圖像［16］加速卷積以提高計算速度。如圖3所示，用一個9×9的方框濾波模板近似最低尺度2.1==σs的高斯二階導(dǎo)數(shù)。Dxx，Dyy和Dxy為方框濾波和圖像卷積后的值，用于分別代替Lxx，Lyy和Lxy，矩陣區(qū)域中的權(quán)值使用經(jīng)驗值 0.9，進(jìn)一步求得 Hessian矩陣的 det表達(dá)式為

要實現(xiàn)特征點的尺度不變性，本文采用圖像金字塔來實現(xiàn)尺度空間，通過圖像與不同尺度下的高斯函數(shù)卷積，并對初始圖像采樣處理，得到更高階的圖像金字塔，通過不同尺度下的濾波模板對原始圖像處理，使得原始圖像保持不變。

圖3 方框濾波對二階偏導(dǎo)的近似Fig.3 Box filter approximations for the second order partial derivative

1.1.2 主方向確定

為了保證圖像具有旋轉(zhuǎn)不變性，對于每個特征點，以該特征點為中心，畫出6s（s為特征點的尺度）為半徑的圓領(lǐng)域，并計算半徑內(nèi)所有特征點x和y方向上的Haar小波響應(yīng)，根據(jù)特征點與中心點的距離賦權(quán)值，越近權(quán)值較大；然后將 60°范圍內(nèi)響應(yīng)的特征點形成新的矢量，遍歷整個圓形區(qū)域后，選擇最長矢量方向作為該特征點的主方向。

1.1.3 生成特征點描述符

1.2 空間金字塔匹配下的BOF算法表示

圖4 SIFT與SURF特征點數(shù)的對比Fig.4 Contrast SIFT and SURF feature points

空間金字塔匹配［17］主要包含金字塔匹配核以及空間金字塔在BOF算法下的匹配方案［18］。金字塔匹配的核心思想是將特征集映射到高分辨率空間進(jìn)行匹配，在匹配的過程中，隨著層次劃分的密集性增加，分配的權(quán)值會變大。

1.2.1 金字塔匹配核

1.2.2 空間金字塔在BOF算法下的匹配方案

本文應(yīng)用空間金字塔的匹配方案，量化特征向量為 M個離散的類型，即表示視覺單詞的數(shù)量，采用K-Means聚類將圖像的特征聚類到視覺單詞類別中，再將視覺單詞采用直方圖的形式表示。本文方法極大簡化了匹配的計算，只需要比較2個視覺單詞是否一致。最終的核函數(shù)總和定義為空間金字塔的BOF表示如圖5所示。

圖5 空間金字塔的BOF表示Fig.5 BOF spatial pyramid representation

通過對圖像進(jìn)行不同層級的劃分，并且進(jìn)行基于視覺單詞的直方圖表示，根據(jù)式（4）計算每個視覺單詞的金字塔匹配核之后，利用式（5）對所有的視覺單詞求和，最終利用SVM分類器對其分類。從圖5可以看出：當(dāng)L=0時，就是標(biāo)準(zhǔn)的BOF算法。對于具有L層和M個視覺單詞時，結(jié)果集的向量維數(shù)如下：

本文將數(shù)據(jù)集中的圖像統(tǒng)一歸一化為 200×200像素，當(dāng)L增大時，維數(shù)會呈指數(shù)級增長，因此，要控制L的大小。本文通過大量測試，發(fā)現(xiàn)當(dāng)L=3時，在兼顧效率的同時分類準(zhǔn)確率較高，因此，本文的所有實驗都采用L=3。

1.3 LIBSVM軟件包

LIBSVM是由LIN開發(fā)設(shè)計的一個簡單、易于使用且快速有效的SVM模式識別和回歸的軟件包［13］，LIBSVM所涉及的參數(shù)調(diào)節(jié)相對較少，提供了很多的默認(rèn)參數(shù)，而且運(yùn)行速度比較快，完全可以解決本文的識別和分類問題。

LIBSVM沿用SVM分類器的思想，SVM的核心思想是尋找最優(yōu)的分類面，對空間中不同的數(shù)據(jù)集進(jìn)行分類。SVM可以描述為如下最優(yōu)化問題［19］：

使用LIBSVM軟件包代替?zhèn)鹘y(tǒng)的SVM，不僅減少了代碼量，而且提高了效率。

2 實驗結(jié)果及分析

本文采用識別分類中最著名的 3個數(shù)據(jù)集即Graz，Caltech-256和Pascal VOC 2012。這3個數(shù)據(jù)集具有圖像數(shù)量龐大，圖像種類繁多，對象類內(nèi)變化多樣等特點，用來測試識別和分類算法很具有代表性。其中Pascal VOC中具有較多的噪聲，分類的難度比較大，最具挑戰(zhàn)性。采用圖像數(shù)據(jù)的種類包括Bike，Car，Person，Ketch，Office，Outdoor，Running，Shooting，Watch，Biking，HorseRiding，PlayingGuitar，Bird，Cat，F(xiàn)lowers，Horse，Cake，Grasshopper和Helicopter。

為了突出本文方法的優(yōu)越性，將在人臉識別中識別率很高的Adaboost分類器與LIBSVM分類器進(jìn)行對比。

2.1 實驗結(jié)果

本文每類都統(tǒng)一使用40幅圖像作為訓(xùn)練樣本，使用20幅圖像作為測試樣本，保證了數(shù)據(jù)量的充足。圖6所示為節(jié)選的數(shù)據(jù)集的一部分。

表1所示為Graz，Caltech-256和Pascal VOC 2012這3個數(shù)據(jù)集中傳統(tǒng)的BOF算法與本文方法的比較結(jié)果。

表2所示為在Pascal VOC 2012數(shù)據(jù)集中使用本文方法采用Adaboost分類器與LIBSVM分類器的對比結(jié)果。

表3所示為本文方法與其他相關(guān)方法在Caltech-256數(shù)據(jù)集中的對比結(jié)果。

為了突出本文算法的效率，節(jié)選部分圖像中SIFT算法與SURF算法效率的對比。表4所示為這2種算法的平均特征點數(shù)與運(yùn)行時間的比對結(jié)果。

2.2 實驗分析

從表1可以看出：應(yīng)用SURF提取特征描述符以及對圖像進(jìn)行空間金字塔匹配，與傳統(tǒng)的BOF算法相比，在匹配準(zhǔn)確度方面得到了極大提高。因為 SURF算法產(chǎn)生的視覺單詞更具有代表性，而且本文通過歸一化處理，在一定程度上避免了背景信息和位置變化等帶來的干擾和影響，通過空間金字塔的劃分細(xì)化，極大地提高了算法的魯棒性。因此，本文算法在背景比較復(fù)雜、噪聲比較多的Pascal VOC 2012數(shù)據(jù)集中也具有優(yōu)越性。

圖6 所選數(shù)據(jù)集的部分圖像Fig.6 Part of image of selected dataset

表1 本文方法與傳統(tǒng)方法在3大數(shù)據(jù)集下的對比Table 1 Compare this method with traditional method at three datasets

表2 本文方法在不同分類器下的對比Table 2 Contrast to this method at different classifiers

表3 本文方法與其他相關(guān)方法的對比Table 3 Compare this method with other related methods

表4 SIFT算法與SURF算法效率對比Table 4 Compare efficiency of SURF and algorithm SIFT algorithm

圖7所示為Pascal VOC 2012這個數(shù)據(jù)集中的實驗結(jié)果（橫坐標(biāo)和縱坐標(biāo)代表圖像的類別，對角線深色部分代表分類的準(zhǔn)確率，其他格子代表誤差）。從圖7可見：雖然在這個最有挑戰(zhàn)性的數(shù)據(jù)集中有些分類結(jié)果不是很好，但整體上，本文的方法可以適應(yīng)復(fù)雜的圖像，并且具有良好的效果。

圖7 在Pascal VOC 2012下的實驗結(jié)果Fig.7 Result of Pascal VOC 2012 dataset

從表2可以看出：在人臉識別中具有極好表現(xiàn)的Adaboost分類器，應(yīng)用于BOF算法中的效果遠(yuǎn)遠(yuǎn)沒有LIBSVM分類器的效果突出，LIBSVM不僅在分類的準(zhǔn)確性上超越了Adaboost，在執(zhí)行效率方面也有明顯的優(yōu)勢。

從表3可以看出：本文與當(dāng)前一些相關(guān)研究工作對比，本文算法的分類準(zhǔn)確率較高。

從表4可以看出：經(jīng)過改良的算法其執(zhí)行效率提高了將近1倍，這對于圖片量比較大時進(jìn)行分類與識別具有重大意義。

3 結(jié)論

1） 將 SURF算法和空間金字塔相結(jié)合，應(yīng)用到BOF算法中進(jìn)行圖像識別與分類。SURF算法用特征描述符生成視覺詞典更能代表所要分類圖像的特征，比傳統(tǒng)方法更具魯棒性，并且在一定程度上適應(yīng)了多邊尺度的圖像。

2） 基于空間金字塔匹配原理，通過對圖像進(jìn)行劃分，充分利用圖像的空間信息，使得匹配精確度得到極大提高。通過實驗結(jié)果對比，本文算法達(dá)到了良好的分類效果，并且與近幾年來的相關(guān)算法相比具有一定的優(yōu)越性。

［1］ WU Lei， HOI S C H， YU Nenghai. Semantics-preserving bag-of-words models and applications［J］. IEEE Transactions on Image Processing， 2010， 19（7）： 1908-1920.

［2］ ZHENG Zhenzhu， YAN Luxin. Global and local explotation for saliency using bag-of-words［J］. IET Computer Vision， 2014，8（4）： 299-304.

［3］ CSURKA G， DANCE C， FAN L， et al. Visual categorization with bags of keypoints［C］// Proceedings of IEEE Conference on Workshop on Statistical Learning in Computer Vision. Centre Europe， 2004： 1-22.

［4］ SIVIC J， LAB D， ECOLE N， et al. Efficient visual search of videos cast as text retrieval［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（4）： 591-606.

［5］ YU J， JEON M， PEDRYCZ W. Weighted feature trajectories and concatenated bag-of-features for action recognition［J］. Neurocomputing， 2014， 131（2）： 200-207.

［6］ ANTHIMOPOULOS M M， GIANOLA L， SCAMATD L， et al. A food recognition system for diabetic patients based on an optimized bag-of-fetures model［J］. IEEE Journal of Biomedical and Health Informatics， 2014， 18（4）： 1261-1271.

［7］ SHEN Linlin， LIN Jiaming， WU Shengyin， et al. HEp-2 image classification using intensity order pooling based features and bag of words［J］. Pattern Recognition， 2013， 47（7）： 2419-242.

［8］ PIRES R， HELINEK H F， WAINER J， et al. Advancing bag-of-visual-words representations for lesion classification inretinal images［J］. Plos One， 2014， 9（6）： e96814.

［9］ LOWE D G. Distinctive image features from scale-invariant key points［J］. International Journal of Computer Vision， 2004， 60（2）：91-110.

［10］ LI Feifei， FERGUS R， PERONS P. Learning generative visual models from few training examples： an incremental Bayesian approach tested on 101 object categories［J］. Special Issue on Generative Model Based Vision， 2007， 106（1）： 59-70.

［11］ LEUNG T， MAILIK J. Representing and recognizing the visual appearance of materials using three-dimensional textons［J］. International Journal of Compute Vision， 2001， 43（1）： 29-44.

［12］ BAY H， TUYTELAARS T， VAN GOOL L. SURF： speeded up robust features［C］// Computer Vision-ECCV 2006. Graz：Springer Berlin Heidelberg， 2006： 404-417.

［13］ CHANG C C， LIN C J. LIBSVM： a library for support vector machines［J］. ACM Transactions on Intelligent Systems and Technology， 2011， 2（3）： 27-53.

［14］ HUANG L， CHEN C， SHEN H， et al. Adaptive registration algorithm of color images based on SURF［J］. Measurement，2015， 66： 118-124.

［15］ 唐建鑫. 基于Bag of Features的圖像分類和檢索研究［D］. 西安： 西安電子科技大學(xué)信息學(xué)院. 2012： 1-70. TANG Jinxin. Research on image classification and retrieval based-on Bag of Features［D］. Xi’an： Xidian University. College of Information， 2012： 1-70.

［16］ VIOLA P， JONES M J. Rapid object detection using a boosted cascade of simple features［C］// Conference on Computer Vision and Pattern Recognition. USA， 2001： 511-518.

［17］ LAZEBNIK S， SCHMID C， PONCE J. Beyond bags of features：spatial pyramid matching for recognizing natural scene categories［J］. IEEE Computer Society on Computer Vision and Pattern Recognition， 2006， 2： 2169-2178.

［18］ HUANG M， MU Z， ZENG H. Efficient image classification via sparse coding spatial pyramid matching representation of SIFT-WCS-LTP feature［J］. Iet Image Processing， 2016， 10（1）：61-67.

［19］ 徐淵， 許曉亮， 李才年， 等. 結(jié)合SVM分類器與HOG特征提取的行人檢測［J］. 計算機(jī)工程， 2016， 42（1）： 56-60. XU Yuan， XU Xiaoliang， LI Cainian， et al. Pedestrian detection combining with SVM classifier and HOG feature extraction［J］. Computer Engineering， 2016， 42（1）： 56-60.

［20］ 趙春暉， 王瑩. 一種基于詞袋模型的圖像優(yōu)化分類方法［J］.電子與信息學(xué)報， 2012， 34（9）： 2064-2070. ZHAO Chunhun， WANG Ying. An optimized method for image classification based on bag of words model［J］. Electronics & Information Technology， 2012， 34（9）： 2064-2070.

（編輯 楊幼平）

Image recognition and classification based on improved BOF algorithm

LI Kangshun1，2， WANG Fubin1， ZHANG Lixia1， LI Wei1，2

（1. College of Information， South China Agricultural University， Guangzhou 510642， China；2. School of Information Engineering， Jiangxi University of Science and Technology， Ganzhou 341000， China）

Improved bag of features （BOF） algorithm was applied to image recognition and classification. In view of the low efficiency and low classification accuracy of the traditional BOF algorithm， a new recognition and classification algorithm combined SURF （speeded up robust feature） with spatial pyramid matching principle was proposed. SURF algorithm can improve the efficiency， and spatial pyramid matching principle can improve the classification accuracy. Firstly， the image feature was extracted by SURF algorithm and the codebook was generated using the features which were able to respond the changing scales. Secondly， the spatial pyramid matching principle was applied to the image histogram’s codebook which can improve the accuracy of the classification. Finally， the image histogram’s codebook was used to be the input of LIBSVM classifier. The experiments were carried out based on Graz， Caltech-256 and Pascal VOC 2012. The results show that the proposed method is better than the traditional method in the efficiency and classification accuracy. In addition， the proposed method is compared with some related research work in classification accuracy， and the proposed method has obvious advantages.

bag of features algorithm； image recognition and classification； SURF； spatial pyramid matching

TP391

A

1672-7207（2016）05-1599-07

10.11817/j.issn.1672-7207.2016.05.020

2015-05-26；

2015-07-12

國家自然科學(xué)資金資助項目（70971043）；廣東省自然科學(xué)基金資助項目（2015A030313408）；江西理工大學(xué)科研基金資助項目（NSFJ2015-K13） （Project（70971043） supported by the National Natural Science Foundation of China； Project（2015A030313408） supported by the Natural Science Foundation of Guangdong Province of China； Project（NSFJ2015-K13） supported by the Science Foundation of Jiangxi University of Science and Technology）

李康順，教授，博士生導(dǎo)師，從事圖像處理研究；E-mail： likangshun@sina.com