一種基于視覺詞袋模型的圖像檢索方法

金 銘 汪友生 邊 航 王雨婷

(北京工業(yè)大學電子信息與控制工程學院 北京 100124)

一種基于視覺詞袋模型的圖像檢索方法

金 銘 汪友生 邊 航 王雨婷

(北京工業(yè)大學電子信息與控制工程學院 北京 100124)

為了提高圖像檢索的效率，提出一種基于視覺詞袋模型的圖像檢索方法。一方面在圖像局部特征提取算法中，使用添加漸變信息的盒子濾波器構造尺度空間，以保留圖像更多的細節(jié)信息，另一方面在特征表達時僅計算一次特征點圓形鄰域內(nèi)的Haar小波響應，避免了Haar小波響應的重復計算，并在保證描述子旋轉(zhuǎn)不變性的同時做降維處理。同時，以改進k-means對特征庫聚類構建加權的視覺詞典，基于概率計算的方式選取k-means初始聚類中心，降低了傳統(tǒng)k-means聚類效果對初始聚類中心選擇的敏感性。實驗結(jié)果表明該方法比傳統(tǒng)方法具有更高的效率，特征提取速度提高48%左右，查準率提高2%以上。

圖像檢索 視覺詞袋模型 局部特征提取 特征聚類

0 引 言

與圖像的全局特征相比，圖像的局部特征在面對復雜背景、噪聲干擾較大、光照條件變化、存在多個事物和語義復雜等場景時都能更好地描述圖像，近年來廣泛使用于圖像處理任務中[1-5]。直接使用局部特征進行圖像分類、圖像檢索時，由于圖像庫中每一幅圖像所檢測到的特征點數(shù)目不統(tǒng)一，并且常用局部特征如SIFT、SURF、DAISY特征等都是高維特征[6-9]，每幅圖像都由多個不同的高維特征表示，逐一匹配計算相似性時效率很低。為了解決上述問題，文獻[10]首先將視覺詞袋模型BoVW(Bag of Visual Words)運用到圖像處理領域。視覺詞袋模型將圖像庫中所有圖像特征提取后聚類成為k個視覺單詞，將每幅圖像以各個單詞出現(xiàn)頻率表示為k維向量[11-12]。這樣可以很好地解決不同圖像提取出的局部特征不統(tǒng)一的問題，并且能將多幅圖像用一定量的視覺單詞表示，節(jié)約空間，處理方便，可擴展性強，可以很大程度上提高多圖像處理任務的效率。

視覺詞袋模型效率的高低取決于圖像特征的選取。比如采用SIFT的改進算法SURF，其處理速度比SIFT提高了三倍左右[7]。然而SURF算法用積分圖像和盒子濾波代替高斯濾波，雖然提高了速度，但也損失了圖像中的細節(jié)信息[7,13-14]；SURF描述子生成時，需要先計算一次圓形鄰域的Haar小波響應得到特征點的主方向，再計算一次方形鄰域的Haar小波響應以得到64維向量，這樣的重復計算過程對SURF的效率有很大影響[7,15]。

為此，本文提出一種基于視覺詞袋模型的圖像檢索新方法，使用改進的SURF算法提取圖像特征，以改進k-means算法聚類建立詞袋模型，基于此詞袋模型實現(xiàn)圖像檢索，提高圖像檢索的效率。

1 視覺詞袋模型

建立視覺詞袋模型的步驟主要包括三部分：圖像特征提取、視覺詞袋學習以及利用視覺詞袋量化圖像特征，并由詞頻表示圖像。首先對圖像庫中所有的圖像提取局部特征，存入特征庫。要求選取的特征對圖像的代表性強，并且提取速度快。本文使用改進的SURF特征，其比SURF特征對圖像更具代表性，并且提取效率更高。然后統(tǒng)計圖像數(shù)據(jù)庫中的所有特征，用聚類算法聚類結(jié)果組成詞袋。為了使聚類結(jié)果更穩(wěn)定，本文使用改進的k-means聚類算法，采用一種基于概率的方式來選取初始聚類中心，削弱初始聚類中心選擇隨機性對聚類效果的影響。最后將一幅圖像映射到視覺詞袋，根據(jù)視覺詞袋中每個單詞在這幅圖像中出現(xiàn)的頻率，將每幅圖像表示成k維向量。不同圖像帶給人的視覺效果不同，所包含的視覺單詞種類及頻率也應不相同，但相近的圖像包含的視覺單詞及頻率是相似的，根據(jù)這個原則可以通過計算k維向量之間的距離來計算圖像之間的相似度，實現(xiàn)圖像檢索任務。考慮到不同的視覺單詞對一幅圖像的描述作用不同，圖像表示時不區(qū)別對待每個視覺單詞，會對圖像檢索的效果有所影響，所以在這里用加權的視覺詞典來表示圖像。本文使用視覺詞袋模型進行圖像檢索的流程如圖1所示。

圖1 檢索流程圖

2 一種改進的圖像局部特征提取算法

建立視覺詞袋模型，首先要提取圖像特征。SIFT算法因其具有較強的匹配能力和魯棒性而被廣泛應用，但它計算復雜、實時性差，用于圖像檢索時導致用戶體驗變差。與SIFT相比，SURF算法在尺度空間生成時使用了積分圖像和盒子濾波，將圖像與高斯二階微分模板的卷積過程簡化成了簡單的積分圖像盒子濾波運算，降低了SIFT算法的復雜度，提高了特征點檢測和匹配的實時性，但同時由于盒子濾波對高斯二階微分模板的簡化損失了圖像細節(jié)信息，而降低了匹配準確度。并且，SURF特征描述子表達時計算了兩次Haar小波響應，一定程度上影響了算法的效率。為此，本文使用添加漸變信息的盒子濾波模板[13-14]，該模板與SIFT和SURF的9×9濾波模板比較如圖2所示?？梢钥闯觯cSURF盒子濾波模板相比，本文算法模板與SIFT的高斯二階微分模板更加接近，并且模板仍由簡單的矩形框構成，保證算法在高效運算的同時保留圖像的細節(jié)信息。將濾波模板中矩形框的四個頂點標上字母，每個字母代表相應點的積分圖像值，設三個不同方向模板的面積分別為Sxx、Syy、Sxy(Sxx=Syy)，三個方向盒子濾波的響應值為Dxx、Dyy、Dxy，則：

(B+F-D-E+K+N-L-M)+(-1)×

(E+H-F-G+I+L-J-K)+(-2)×

(G+J-H-I)

(1)

(B+F-D-E+K+N-L-M)+(-1)×

(E+H-F-G+I+L-J-K)+(-2)×

(G+J-H-I)

(2)

(3)

圖2 SIFT、SURF、本文算法濾波模板比較

其中，Sxx、Syy、Sxy的大小可以根據(jù)模板的大小直接得到，而字母代表的積分圖像值可通過查積分圖像值表得到。由上述過程可知，SURF模板對大塊區(qū)域賦單一值進行處理，而改進的模板在矩形區(qū)域里填入了漸變的值，使處理過程更近似于高斯二階模板濾波過程，保留了更多的圖像細節(jié)信息，并且濾波計算仍然很簡單，計算量沒有大的增加。

構造尺度空間時，將9×9模板作為尺度空間金字塔中的初始層(由于每一層的響應長度為模板大小的1/3，即初始層的響應長度l0=3)，并在每一層都采用與SURF算法一樣的模板大小，如圖3(a)所示。模板大小變化時，給盒子濾波器中填充漸變值遵守初始層響應為模板大小的1/3的原則，先將顏色最深的地方填充后，再填充漸變值。圖3(b)為yy方向盒子濾波模板大小由9×9變?yōu)?5×15的示例。

圖3 不同尺度模板大小變化

得到不同大小的模板后，圖像尺寸不變，用不同大小的模板與圖像進行卷積，構成三維尺度空間。在三維尺度空間中，每個3×3×3的局部區(qū)域里，使用非最大值抑制將像素點與其周圍的26個像素點進行比較來檢測極值點，并記下極值點的位置作為特征點。

在傳統(tǒng)SURF特征描述子計算時，為了保證算法的旋轉(zhuǎn)不變性，通過計算特征點周圍圓形鄰域內(nèi)Haar小波響應的大小，確定每個特征點描述子的主方向；接下來又需要計算一次特征點周圍方形鄰域內(nèi)的Haar小波響應，得到64維的特征向量。這樣的重復計算勢必對算法的效率有所影響。本文對每一個特征點，以特征點為圓心，以10S(S為樣本所處空間的尺度值)為半徑作圓形鄰域，在該圓形鄰域內(nèi)統(tǒng)計Haar小波響應值，能同樣實現(xiàn)局部特征描述子的計算和表達。具體做法是：以尺寸為2S×2S的Haar小波模板對圓形鄰域內(nèi)圖像進行處理，計算鄰域內(nèi)所有特征點在x、y方向的Haar小波響應，并賦給每個向量不同的高斯權重，權重與距離成正比，越靠近圓心(貢獻值越大)的特征點賦值權重越大。以一個圓心角為π/4的扇形旋轉(zhuǎn)遍歷整個圓形鄰域，如圖4所示，共有8個扇形窗口，每一次滑動到一個窗口內(nèi)時，統(tǒng)計該窗口內(nèi)Haar小波響應值的和。設dx、dy分別代表水平和垂直方向的Haar小波響應，mi為方向矢量，θi為方向矢量的角度，則：

(4)

(5)

(6)

圖4 本文算法特征表達

為了保證描述子的旋轉(zhuǎn)不變形，比較得到的8個窗口的mi矢量的模值，按從大到小的順序排序，排第一位的(矢量最長)mi的方向為特征點的主方向；按照mi值序列的順序，將對應的8個Vi矢量排列，得到8×4=32維的特征描述子。改進的局部特征描述子由原算法的64維變成了32維，并且避免了Haar小波響應的重復計算，提高了算法效率。生成描述子時，從主方向開始按照mi值遞減的順序生成特征向量，主方向的權重最大，從而保證了旋轉(zhuǎn)不變性。

綜上所述，本文的特征提取算法對圖像表達能力更強，并且提取特征時間更短，更適合于圖像檢索。

3 加權視覺詞典生成

按照上述步驟得到圖像庫中所有圖像特征后，按照傳統(tǒng)詞袋模型構造的步驟，應當用k-means聚類算法對所有特征進行聚類。但k-means算法聚類性能的好壞依賴于k個初始中心點的選擇，當k個初始中心的位置在數(shù)據(jù)空間中分布不均勻時，將導致收斂迭代所需的次數(shù)增多，甚至陷入局部最優(yōu)，而得不到準確的聚類結(jié)果。為了減少初始聚類中心對聚類性能結(jié)果的影響，選擇初始聚類中心時必須遵從一個原則：初始的聚類中心之間的距離應當盡可能遠[16-18]。基于這個思想，結(jié)合本文上述工作，使用改進的k-means算法對特征聚類生成視覺詞典，具體步驟如下：

步驟1 從特征數(shù)據(jù)集S={s1,s2,…,sm}中隨機選取一個種子點c，作為一個初始聚類中心；

步驟2 對于數(shù)據(jù)集S中的每一個點，計算它與最近聚類中心的距離D(si,c)，其中i≤m；

步驟3 按照式(7)計算下個點被選為聚類中心的概率，選擇概率最大的點作為下一個聚類中心c；

(7)

步驟4 重復步驟2和步驟3，直到得到k個初始聚類中心:C={c1,c2,…,ck}；

步驟5 計算數(shù)據(jù)集S中非聚類中心的對象到k個聚類中心的歐式距離，根據(jù)距離將它們分配到最相似的類中；

步驟7 不斷重復步驟5和步驟6，計算直到標準測度函數(shù)收斂至最小值，標準測度函數(shù)的計算公式如式(8)：

(8)

步驟8 步驟7得到的k個聚類中心定義為k個視覺單詞，k個視覺單詞共同構成視覺詞典。

以這種計算概率的方法選擇初始聚類中心，避免了經(jīng)典k-means的初始聚類中心隨機性對聚類效果帶來的影響，使生成的詞典對圖像數(shù)據(jù)庫更具有代表性。

由于不同的視覺單詞對一幅圖像的描述作用是不同的，圖像表示時不區(qū)別對待每個視覺單詞，會對圖像檢索的效果有所影響。所以在這里使用tf-idf加權方法，用加權的視覺詞典來表示圖像。tf-idf是信息檢索領域常用的一種權重機制，其思想主要是基于統(tǒng)計方法。tf指詞頻(TermFrequency)，如果某個視覺單詞在一幅圖像中出現(xiàn)的頻率tf高，并且在其他圖文件頻率(InverseDocumentFrequency)，如果在圖像庫中包含視覺單詞w的圖像很少，則w的idf值越大，說明視覺單詞w具有很好的區(qū)分能力，應當增大它的權重。根據(jù)以上規(guī)則，用帶有權重的視覺詞典將圖像庫中的N幅圖像表示為向量，圖像In表示為：Wn=[wn1,wn2,…,wnk]T，其中：

wj=tfnj×idfnjn=1,2,…,Nj=1,2,…,k

(9)

得到N幅圖像的向量表示后，建立倒排索引表，至此視覺詞袋模型建立完成。

4 實驗結(jié)果及評價

4.1 圖像特征提取實驗

對一張圖像，用SURF算法和本文算法提取特征，提取結(jié)果對比如圖5所示。對圖像SURF特征提取時特征點數(shù)量為1 677個，耗時1.056秒，本文算法提取時特征點數(shù)量為1 965個，耗時僅0.652秒。由于本文算法使用了與高斯二階微分模板更接近的盒子濾波器，更多地保留了圖像的細節(jié)信息，檢測出的特征點更多，并且在描述子生成時只計算了一次Haar小波響應，這樣雖然檢測出的特征點更多，但是運行時間卻縮短了。為了證明這一點，從Corel標準圖像庫中隨機選擇10幅圖像，統(tǒng)計檢測出的特征點數(shù)量和提取時間，如表1所示。

圖5 特征提取對比

表1的數(shù)據(jù)表明，本文算法在提取圖像特征點數(shù)量增加的同時，平均提取時間縮短了48%左右。特別是本文方法提取的特征不僅效率大大提高，而且對圖像也更具代表性，在多幅圖像檢索任務中，更能體現(xiàn)出本文算法的優(yōu)勢。

4.2 圖像檢索實驗

使用Corel標準圖像庫對本文算法進行圖像檢索測試，Corel圖像庫中有10類圖像，分別為:AfricanPeople、Beach、Buildings、Buses、Dinosaurs、Elephants、Flowers、Horses、Mountains、Food，每個類別中都有100張圖像。如圖1中的步驟，檢索時用同樣的詞袋構建算法將待檢索圖像表示為視覺單詞出現(xiàn)頻率的向量，計算該向量與圖像庫中各個向量的歐氏距離，按距離從小(最相似)到大返回與待檢索圖像相似的L幅圖像。圖6是一個檢索示例。

圖6 檢索示例

在詞典大小K值的選擇方面，K值越大，詞典中包含視覺單詞數(shù)量越多，對圖像庫的代表性越強。測試L=10時本文算法在50、100、150、200這幾種詞典大小時每類的平均查準率，如圖7所示?？梢钥闯鲈贙=200時平均查準率反而下降了，并且生成詞典時K=150比K=100耗費的時間增加了將近一倍左右，所以綜合查準率和檢索效率，選擇K=100來進行檢索實驗。

圖7 不同詞典大小時檢索平均查準率

由于在檢索過程中一般關心的都是檢索返回結(jié)果中靠前的一些圖像，故本文選擇L=10、L=20兩個參數(shù)統(tǒng)計實驗結(jié)果。在每類圖像中隨機抽取20幅圖像進行檢索，統(tǒng)計每類平均的查準率，得到的結(jié)果如圖8所示。

圖8 不同算法檢索查準率比較

從圖8中可以看出，對于兩種算法來說，返回圖像數(shù)量為10張時每類的查準率都比返回數(shù)量為20張圖像的查準率要高；本文改進BoVW的檢索結(jié)果與原BoVW的檢索結(jié)果相比，在取兩種不同L值時查準率都有一定的提高，這是因為改進BoVW中的特征提取保留了圖像更多的漸變細節(jié)信息，且改進k-means一定程度上提高了詞袋聚類的穩(wěn)定性。在類別(5)Dinosaurs中兩種算法的檢索效果最好，查準率幾乎達到了100%，在類別(7)Flowers中查準率也達到了82.5%左右，然而因為這兩種類別圖像的漸變特征較少，本文特征提取算法并沒有體現(xiàn)出很大的優(yōu)勢。除了在類別(4)中L=10時，本文方法比原方法查準率略有降低，在其他所有類別中本文改進算法的檢索效果都要優(yōu)于原算法。計算十類圖像的平均查準率，在L=10時改進BoVW查準率比BoVW的查準率提高了2.2%左右，L=20時提高了4.1%左右。

5 結(jié) 語

為了提高圖像檢索的效率，從圖像檢索的關鍵技術入手，提出一種基于視覺詞袋模型的圖像檢索方法。針對SURF算法提取圖像特征點少、特征表達需重復計算Haar小波響應的問題，提出一種改進的局部特征提取方法，使用添加漸變信息的盒子濾波器構造尺度空間，并在特征表達時避免Haar小波響應的重復計算，同時保留了圖像更多的細節(jié)信息，特征提取速度提高48%左右；通過改進k-means算法對特征庫聚類構建加權的視覺詞典，以概率計算的方式選取初始聚類中心，降低了傳統(tǒng)k-means聚類效果對初始聚類中心選擇的敏感性。改進的詞袋比起改進前的詞袋對圖像庫更具代表性，圖像檢索實驗表明本算法構建詞袋效率較高，同時查準率也提高2%以上。

[1] 何云峰,周玲,于俊清,等.基于局部特征聚合的圖像檢索方法[J].計算機學報,2011,34(11):2224-2233.

[2] 賈平,徐寧,張葉.基于局部特征提取的目標自動識別[J].光學精密工程,2013,21(7):1898-1905.

[3]KharchenkoV,MukhinaM.Correlation-extremevisualnavigationofunmannedaircraftsystemsbasedonspeed-uprobustfeatures[J].Aviation,2014,18(2):80-85.

[4] 薛峰,顧靖,崔國影,等.基于SURF特征貢獻度矩陣的圖像ROI選取與檢索方法[J].計算機輔助設計與圖形學學報,2015,27(7):1271-1277.

[5] 丘文濤,趙建,劉杰.結(jié)合區(qū)域分割的SIFT圖像匹配方法[J].液晶與顯示,2012,27(6):827-831.

[6]LindebergT.ScaleInvariantFeatureTransform[J].Scholarpedia,2012,7(5):2012-2021.

[7]BayH,EssA,TuytelaarsT,etal.Speeded-UpRobustFeatures(SURF)[J].ComputerVisionandImageUnderstanding,2008,110(3):346-359.

[8]TolaE,LepetitV,FuaP.DAISY:AnEfficientDenseDescriptorAppliedtoWide-BaselineStereo[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2010,32(5):815-830.

[9] 羅楠,孫權森,陳強,等.結(jié)合SURF特征點與DAISY描述符的圖像匹配算法[J].計算機科學,2014,41(11):286-290,300.

[10]Fei-FeiL,FergusR,PeronaP.Learninggenerativevisualmodelsfromfewtrainingexamples:anincrementalBayesianapproachtestedon101objectcategories[J].ComputerVisionandImageUnderstanding,2007,106(1):59-70.

[11]AlfanindyaA,HashimN,EswaranC.ContentBasedImageRetrievalandClassificationusingspeeded-uprobustfeatures(SURF)andgroupedbag-of-visual-words(GBoVW)[C]//Technology,Informatics,Management,Engineering,andEnvironment(TIME-E),2013InternationalConferenceon.IEEE,2013:77-82.

[12]RochaBM,NogueiraEA,GuliatoD,etal.ImageretrievalviageneralizedI-divergenceinthebag-of-visual-wordsframework[C]//Electronics,CircuitsandSystems(ICECS),2014 21stIEEEInternationalConferenceon.IEEE,2014:734-737.

[13]HuangX,WangJ,ZhangM,etal.Gradual-SURF[C]//ImageandSignalProcessing(CISP),2011 4thInternationalCongresson.IEEE,2011:906-909.

[14] 張滿囤,王潔,黃向生,等.Gradual-SURF算子的角點提取[J].計算機工程與應用,2013,49(10):191-194,200.

[15] 周燕,吳學文,劉娜.基于改進的SURF算法的視頻總結(jié)方法[J].微型電腦應用,2015,31(10):65-68.

[16] 翟東海,魚江,高飛,等.最大距離法選取初始簇中心的K-means文本聚類算法的研究[J].計算機應用研究,2014,31(3):713-715,719.

[17]AgarwalS,YadavS,SinghK.K-meansversusk-means++clusteringtechnique[C]//EngineeringandSystems(SCES),2012StudentsConferenceon.IEEE,2012:1-6.

[18] 趙春暉,王瑩,MasahideKaneko.一種改進的k-means聚類視覺詞典構造方法[J].儀器儀表學報,2012,33(10):2380-2386.

AN IMAGE RETRIEVAL METHOD BASED ON BAG OF VISUAL WORDS MODEL

Jin Ming Wang Yousheng Bian Hang Wang Yuting

(SchoolofElectronicInformationandControlEngineering,BeijingUniversityofTechnology,Beijing100124,China)

In order to improve the efficiency of image retrieval, an image retrieval method based on BoVW (Bag of Visual Words) model is proposed. On the one hand, in image local feature extraction algorithm, we use box filter with gradient information to form scale space, to retain more image details information. On the other hand, only the Haar wavelet response in the circular neighborhood of the feature point is calculated in the feature expression, which avoids the repeated calculation of the Haar wavelet response and reduces the dimension while guarantee rotational invariance. At the same time, using improved k-means clustering method to construct a weighted visual dictionary, the k-means initial clustering center is selected based on probabilistic calculation method, which reduces the sensitivity of the traditional k-means clustering to the initial clustering center selection. The experimental results show that the proposed method is more efficient than the traditional method, feature extraction speed is increased by about 48% and the precision is improved by more than 2%.

Image retrieval Bag of visual words model Local feature extraction Feature clustering

2016-03-08。金銘，碩士，主研領域：圖像處理。汪友生，副教授。邊航，碩士。王雨婷，碩士。

TP391.9

A

10.3969/j.issn.1000-386x.2017.04.042