基于視覺詞袋模型的圖像分類改進方法

曹寧，馮陽

（河海大學計算機與信息學院，江蘇南京210098）

分類和識別是圖像理解中的關(guān)鍵問題，由于圖像目標存在視角變化、亮度變化、尺度、目標變形、遮擋、復雜背景以及目標類內(nèi)差別等影響，使得圖像目標的分類識別非常困難。針對這些問題，已提出了各種具有不變性的局部特征提取的方法。在這些方法中，視覺詞袋（BOVW，Bag-Of-Visual-Word）模型是最具代表性的一種。BOVW模型是由Bag of word（BOW）模型應(yīng)用到計算機視覺領(lǐng)域演變而來的，BOW模型最初應(yīng)用于文檔分類領(lǐng)域并因其簡單而有效的優(yōu)點得到了廣泛的應(yīng)用，計算機視覺領(lǐng)域的研究者們嘗試將同樣的思想應(yīng)用到圖像處理和識別領(lǐng)域，從而建立了由文本處理技術(shù)向圖像處理領(lǐng)域的過渡。然而，視覺詞袋模型在計算機視覺領(lǐng)域的應(yīng)用仍存在一定的問題，例如在應(yīng)用于圖像分類時分類精度不夠高，為了進一步提高該模型的性能，使其在圖像識別和分類領(lǐng)域得到更好的應(yīng)用，研究者們一直致力于對模型的實現(xiàn)過程進行改進。

文中基于BOVW[1]模型來完成圖像原始特征的提取、特征聚類并形成統(tǒng)一的特征詞典來表達圖像?；贐OVW模型，我們選用D.G.Lowe提出的SIFT經(jīng)典描述子來提取描述圖像特征，并利用改進的Kmeans+聚類算法把提取的特征聚類構(gòu)建視覺詞典，為了增強識別性能，引入了一種基于視覺詞典的權(quán)重直方圖表達來表示圖像，文中僅僅應(yīng)用簡單的KNN分類器進行分類，并允許在訓練圖像數(shù)目較少的情況下即可達到良好的分類效果。

1 視覺詞袋模型的基本原理

在應(yīng)用BOVW模型來處理圖像時，圖像被看作是文檔，而圖像中的關(guān)鍵特征被看作“單詞”，其應(yīng)用于圖像分類識別時，主要包括3個步驟：特征的提取和描述；視覺詞典的構(gòu)建；選取合適的分類器進行分類和識別。

1.1 圖像特征提取和描述

文中選用D.G.Lowe提出的SIFT[2]經(jīng)典算子來提取描述圖像特征。SIFT描述子通過在尺度空間高斯差分圖像去找相鄰尺寸之間的局部極值點來確定圖像中顯著的位置和尺度，然后再找到這些顯著點的位置，提取歸一化的區(qū)域梯度直方圖獲取最終的SIFT局部描述子。SIFT描述子具有良好的判別性，對旋轉(zhuǎn)、尺度和光照等具有不變性，因此在計算機視覺領(lǐng)域得到了廣泛的應(yīng)用。具體實現(xiàn)步驟為：首先將圖像與高斯核函數(shù)進行卷積，得到高斯差分尺度空間，這一步為粗糙地探測興趣點的位置，因此得到的興趣點中含有大量的無用信息，下一步就要對這些關(guān)鍵點進行精確的定位，以得到其尺度、方向等信息，最后要給每一個興趣點分配方向和尺度，每一個特征便具備了是個參數(shù)，中心點的水平坐標，中心點的垂直坐標、尺度以及方向，接著用SIFT描述子對特征進行描述，每個特征都將被表示成128維的特征向量，首先以關(guān)鍵點為圓心取16×16的領(lǐng)域窗口，然后將該窗口分成4×4個子區(qū)域，在每個子區(qū)域中計算8個方向（0°，45°，90，135°，180°，225°，270°，315°）的梯度累加值，這樣每個特征便可以用4×4×8=128維的向量來表示。按照這種方法對特征進行描述可以避免尺度變換、旋轉(zhuǎn)變化的影響。

1.2 構(gòu)建視覺詞典

這一步的任務(wù)就是將特征提取環(huán)節(jié)得到的向量表示形式表示的特征轉(zhuǎn)換成圖像的“單詞”，然后利用這些單詞來構(gòu)建視覺詞典。這樣每一張圖像都可以表示為視覺單詞出現(xiàn)概率的集合，這樣就可以利用視覺詞典來表示圖像。通常采用聚類的方法來構(gòu)建視覺詞典，聚類的目的在于將具有最大相似性的特征歸為一類，聚類中心定義為“單詞”。將所有單詞進行組合就構(gòu)成了視覺詞典，通常詞典大小由單詞個數(shù)決定。K-means[3]聚類方法比較經(jīng)典而且簡單有效，基本的K-means的核心思想為：將向量空間中n個特征點按照類內(nèi)方差和最小的原則分為指定的k類，如式（1）所示。

其中Ci表示中心為μi的第i個聚類類別，xj表示屬于類別Ci的數(shù)據(jù)點。K-means聚類方法的具體步驟：1）隨機選取k個初始中心；2）計算每個數(shù)據(jù)與聚類中心距離，將數(shù)據(jù)按最短距離分配到k個初始中心為代表的聚類類別中；3）根據(jù)上一步的結(jié)果對新形成的k個類別進行中心計算，重新得到新的聚類中心；4）重復2）、3）操作直到結(jié)果收斂為止。

1.3 分類器進行分類和識別

文中選用最簡單有效的k最近鄰（KNN，K-Nearest-Neighbors）分類算法。KNN算法的核心思想是如果一個樣本在特征空間中的k個最近鄰的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別，并具有這個類別上樣本的特性。該方法在確定分類時采用投票決策，即主要靠周圍鄰近的有限樣本投票而不是靠判別類域的方法來確定所屬類別。

2 改進型K-means算法

由于K-means算法初始中心選取的隨機性，大大增加了迭代的計算花銷。本文采用了它的改進算法K-means+[4]，兩者的不同之處在于初始中心的選取方式，K-means+算法選取初始中心是基于彼此之間距離大小選取K個可能性最大的特征點，也即是假如一個特征矢量與其他所有的特征矢量有最大的歐式距離，那么它被選舉為一個初始中心的概率最大，這是因為類別差異越大，它們類別中的視覺單詞的歐式距離也應(yīng)該越大。基于這種思想，我們定義待聚類的特征矢量為：F={f1，f2，f3，…，fn}，然后從中任選一個特征矢量，計算它與其余所有特征矢量的歐式距離得到n-1個距離，我們把它寫為距離矢量形式為：D={d1，d2，…，dn-1}，最后計算基于距離的概率大小為：p={p1，p2，…，pn-1}其中

因此，第1）步選取可能性最大的k個特征點作為初始中心點，其余步驟同k-means相同。使用k-means+算法可以加快中心點收斂的速度，以減輕對計算機硬件的壓力。

3 加權(quán)統(tǒng)計直方圖詞典表達

利用BOVW模型完成特征提取描述和視覺特征詞典的構(gòu)建后，最重要的是要利用視覺詞典完成圖像的表示，對每圖像的表達時，不同于傳統(tǒng)的統(tǒng)計直方圖表達，本文提出了一種加權(quán)的統(tǒng)計直方圖表達[5]，傳統(tǒng)直方圖統(tǒng)計表達時是統(tǒng)計圖像特征到視覺單詞的距離最短的特征單詞，而加權(quán)統(tǒng)計直方圖詞典表達在圖像表達時考慮了鄰近特征的貢獻[6]，也即是說如果一個特征距離該視覺單詞距離最短，那么該特征對該視覺單詞統(tǒng)計值具有最大的影響，而非最短的其余特征也按距離的遠近對該視覺單詞的統(tǒng)計值分配不同的權(quán)重值。

這里我們假設(shè)訓練圖像集完整表示為ma={ma（i），F(xiàn)a（i），Ra（i）|1≤i≤na}，其中ma（i）表示第i張圖片；Fa（i）={fa（i1），fa（i2），fa（i3），fa（in）}表示第i張圖片的sift特征；Ra（i）是第i張圖片的權(quán)重直方圖表達。同理，我們用mb表示測試圖像集mb={mb（i），F(xiàn)b（i），Rb（i）|1≤i≤na}。假設(shè)V={v1，v2，…，vk}是k個視覺單詞組成的詞典。單詞vj的權(quán)值為wj，對于任意一張?zhí)囟ǖ膱D片ma（i），它可以被表示為Ra（i）={w1，w2，…，wk}。Fa（i）到Vj的距離Dj可用下式（3）求解。

Dj=sort（dj1，dj2，dj3，…，djni），djn=pdist（vj，fa（in））1≤n≤ni（3）

其中sort函數(shù)是一個升序的排序函數(shù)；pdist函數(shù)是歐式距離計算函數(shù)。假設(shè)一張圖片的特征最大不超過M個，因此通過Dj，可獲得權(quán)值wj，即權(quán)值如下：

其中cosin函數(shù)是計算余弦距離函數(shù)。對每一個視覺單詞計算Dj和Wj，這樣訓練集圖片ma（i）都可以基于視覺單詞分配的權(quán)值大小表達出來，mb（i）同理也能按其對應(yīng)視覺單詞分配的權(quán)值大小統(tǒng)計表達出來。

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

我們選用Caltech101，Caltech256這兩組經(jīng)典的數(shù)據(jù)集作為實驗數(shù)據(jù)庫。為了方便起見我們兩組數(shù)據(jù)集都隨機選取訓練集和測試集，但選取不能雷同。實驗部分將通過反復實驗演示統(tǒng)計直方圖詞典表達（NWR）和加權(quán)統(tǒng)計直方圖詞典表達（WR）的對分類性能的表現(xiàn)。

4.1 實驗一：Caltech 101數(shù)據(jù)庫

Caltech 101[7]由加利福尼亞理工學院的李飛飛提出的，共包括101類常見對象類別，每一類包含31到800張圖片，本文隨機選取其中的8類，示例圖像如圖1所示。

圖1 Caltech101數(shù)據(jù)庫選取圖像示例Fig.1 Example images of Caltech101 database

實驗中，每類中隨機選取20張圖片作為訓練集，選取其余40張作為測試集，然后提取圖像特征，采用K-means+算法把訓練集特征聚類得到視覺單詞，視覺單詞的數(shù)量按間隔50從100到300逐次遞增，分別統(tǒng)計2種圖像表達下圖像識別平均準確率（AP，Average Precision），定義AP如下：

其中nc表示類別總數(shù)，ei表示第i類正確識別的概率。分別在2種詞典表達下進行實驗，隨不同的詞典長度變化識別的平均準確率，如下表1。

表1 實驗在不同詞典長度下AP值（Caltech101）Tab.1 The AP results of WR and NWR（Caltech-101）

為了描述每一類識別的正確率，我們定義詞典長度固定為250時，每一類識別的正確率，如圖2所示。

圖2 采用WR和NWR表示圖像時每類識別正確率Fig.2 The per class recognition correct rate of the WR and NWR represent

實驗結(jié)果表明，采用權(quán)重直方圖詞典表達圖像均比采用傳統(tǒng)統(tǒng)計直方圖平均識別率要高，尤其是當詞典長度為300時，平均識別正確率比非加權(quán)的統(tǒng)計直方圖表達高出4.58%。

4.2 實驗二Caltech 256數(shù)據(jù)庫

Caltech 256可以看作是Caltech 101的擴展，它包括256個常見對象類別。相比Caltech101數(shù)據(jù)庫，Caltech 256的對象變化更加多樣性，因此也就增加了分類的難度。我們從中隨機選取6類（分別為：Baseball，Computer mouse，Eiffel，F(xiàn)ish，Skeleton，AK）中的20張圖片作為訓練集，40張作為測試集。進行兩組實驗并計算平均識別正確率，如表2和圖3所示。

圖3可以直觀地看出相比傳統(tǒng)統(tǒng)計直方圖表達圖像，引入權(quán)重統(tǒng)計直方圖表達圖像性能提升顯著。尤其在詞典長度為200時，分類性能提高了12.09%

5 結(jié)論

圖像的表示和分類是圖像處理中的關(guān)鍵技術(shù)[8]，文中主要從圖像的表達入手，將圖像處理中常用的加權(quán)技術(shù)引入對圖像基于視覺詞典的直方圖表示中，文中沒有過多地涉及分類器部分，如果對分類器加以改進或者改用更加有效的新的分類器將是改進BOVW模型的另一個研究領(lǐng)域。為使視覺詞典的構(gòu)造方法更加穩(wěn)定，特征聚類時采用改進的K-means算法，結(jié)合權(quán)重表達圖像，利用最簡單有效的KNN分類器就取得了優(yōu)異的分類效果。

表2 實驗在不同詞典長度下AP值（Caltech256）Tab.2 The AP results of WR and NWR（Caltech256）

圖3 權(quán)重直方圖表達（WR）和非權(quán)重表達（NWR）下平均識別正確率Fig.3 The average correct recognition rate of expression of weight histogram expression and non-weighting

[1] Jégou H，Douze M，Schmid C.Improving bag-of-features for large scale image search[J].International Journal of Computer Vision，2010，87（3）:316-336.

[2] Lowe D.G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）:91-110.

[3] 嚴華.一種改進的K-means算法[J].計算機與現(xiàn)代化，2009，161（1）:56-59.YAN Hua.An improved K-means Algorithm[J].Computer and Modernization，2009，161（1）:56-59.

[4] Arthur D，Vassilvitskii S.K-means++:The advantages of careful seeding[C].Proceedings of the eighteenth annual ACM-SIAMsymposium on discrete algorithms.Society for Industrial and Applied Mathematics，2007:1027-1035.

[5] 曾璞.面向語義提取的圖像分類關(guān)鍵技術(shù)研究[D].長沙：國防科學技術(shù)大學，2009.

[6] Sivic J，Zisserman A.Video Google:A text retrieval approach to object matching in videos[J].In ICCV，2003（2）:1470-1477.

[7] Fei-Fei L，F(xiàn)ergus R，Perona P.Learning generative visual models from few training examples:An incremental bayesian approach tested on 101 object categories[J].Computer Vision and Image Understanding，2007，106（1）:59-70.

[8] 牛志彬.圖像識別中圖像表達的關(guān)鍵技術(shù)研究[D].上海：上海交通大學，2001.