一種基于隨機游走模型的融合視覺單詞共現性的軟分配詞袋技術

張晉

（四川大學計算機學院，成都 610065）

一種基于隨機游走模型的融合視覺單詞共現性的軟分配詞袋技術

張晉

（四川大學計算機學院，成都 610065）

提取局部興趣點并通過詞袋技術表征圖片，是進行圖片檢索的一種經典方案。在傳統的詞袋技術中，每一個局部興趣點的分配都是相互獨立的，而沒有考慮相鄰局部興趣點分配的相互影響。這樣可能會導致某些局部興趣點不可靠的分配，從而降低圖片檢索的精確度。通過統計視覺單詞的共現性，可以學習到一些有價值的先驗知識；同時利用隨機游走模型，將視覺單詞的共現性融合到傳統的軟分配詞袋技術中，從整體上減少局部興趣點不可靠的分配，進而提升圖片檢索的精確度。

局部興趣點；視覺單詞；詞袋技術；共現性；隨機游走模型

0 引言

如何高效準確地實現以圖搜圖，是近年來學術界和工業界的一個熱點研究問問題。一個經典的技術方案是：使用SIFT算子提取并描述圖片中的局部興趣點，通過聚類算法學習一個包含一定數量視覺單詞的詞典，計算圖片中局部興趣點在該詞典上的詞頻分布，用于表征該圖片。其中，詞頻分布的計算就涉及到軟分配詞袋技術，其大致思想如下：一個局部興趣點分配給詞典中和該局部興趣點距離最近的K個單詞，而不僅僅是分配給和該點距離最近的1個單詞，這樣可以減少分配中可能存在的誤差。

在傳統的軟分配詞袋技術中，相鄰局部興趣點的分配是相互獨立的，而沒有考慮相鄰局部興趣點分配結果的相互影響，可能會導致不可靠的分配進而降低檢索模型的精確度。事實上，詞典中單詞之間往往存在一些統計規律，如兩個單詞共同出現的頻率。本文利用隨機游走模型，通過考慮相鄰局部興趣點的分配結果的相互影響，將上述統計規律融合到傳統的軟分配方案中去，借以減少不可靠的分配進而提升圖片檢索的精確度。

1 統計視覺單詞之間的共現性

1.1 什么是視覺單詞的共現性

在討論具體融合方法之前，我們會詳細說明什么是視覺單詞之間的共現性，以及如何統計視覺單詞之間的共現性。

在文本中，“中華”“人民”以及“共和國”3個詞頻繁出現。我們相信，如果文本中當前的2個單詞依次是“中華”和“人民”，那么下一個詞是“共和國”的概率一定遠大于是“蛋糕”或“屏幕”的概率。視覺單詞之間同樣存在類似的共現性規律。在字典學習過程中，訓練集中每一個局部興趣點都會被標記為某個視覺單詞：如果在單詞a一定范圍內，單詞b頻繁地出現，那么單詞a和單詞b就具有比較高的共現性；反之同理。

1.2 統計視覺單詞之間的共現性

給定一個訓練圖片集，我們使用SIFT算子提取并描述圖片中的局部興趣點，這樣就得到了一個規模龐大的局部興趣點集合。我們使用K-means算法對該集合進行聚類，形成了K個單詞的視覺詞典。這樣訓練集中每一張圖片的每一個局部興趣點就可以被標記為某個視覺單詞。我們這樣定義2個視覺單詞共同出現：對于某個單詞a，如果單詞b出現在以a為圓心以某個閾值d為半徑的范圍內，我們就說單詞a和單詞b共同出現。以此為基礎，我們使用互信息來描述視覺單詞兩兩之間的共現性，計算公式如下[1]：

其中w1和w2表示2個視覺單詞，p（w1）和p（w2）分別表示w1和w2出現的頻率，p（w1，w2）表示w1和w2共同出現的頻率，I（w1，w2）表示w1和w2之間的互信息。

1.3 對共現性進行假設檢驗

事實上，有相當比例的視覺單詞之間是偶然共現的，我們需要剔除掉這些偶然的共現性，以減少后續處理的誤差積累。我們使用四格表卡方檢驗剔除偶然的共現性，并將那些顯著共現的視覺單詞組合的互信息，存入一個互信息矩陣I中。實驗發現，經過卡方檢驗該矩陣的稀疏度可以降到不足10%。

2 融合視覺單詞共現性的軟分配詞袋技術

在統計獲得視覺單詞之間的共現性信息之后，我們需要將這些共現性信息融合進局部興趣點的分配過程中去，期望經過融合之后的局部興趣點分配結果和視覺單詞之間的共現性相一致。那么怎樣進行融合呢？一個可能的方法是使用隨機游走模型（Random Walk Model）：對于互信息矩陣I中對應數值比較大的單詞組合，在原始分配方案中出現的可能性得到提高；對于互信息矩陣I中對應數值比較小的單詞組合，在原始分配方案中出現的可能性得到減小。

給定一張圖片，我們使用SIFT算子提取并描述圖片中的局部興趣點。假設局部興趣點集合為L，對于一個局部興趣點p∈L，可以得到一個K維向量Local（p），其中[2]：

其中，wi（p）表示視覺詞典中距局部興趣點p第i近的單詞，D表示一種距離尺度，K表示向量的維度。我們計算每一個局部興趣點的Local向量。

接下來是一個迭代的處理過程，每一輪我們從2個方面出發，校正每一個局部興趣點的概率向量：該點原始的Local向量；與該點相鄰的局部興趣點對該點概率向量的推測。該迭代過程的公式化表示如下[3]：

①對于每一個局部興趣點x，令p（0）（x）=Local（x）

②對于每一個局部興趣點x，計算一組轉移概率矩陣Rxy：

其中y表示與x相鄰的一個局部興趣點，如1.2中所述如果y出現在以x為圓心以d為半徑的范圍里，就可以認為y與x相鄰。

重復該過程直到收斂：

其中N（x）表示與局部興趣點x相鄰的局部興趣點集合。當前輪點p的概率向量由Local（x）和Social（x）加權平均獲得，權值α一般取0.85。

最終的p（x）就是融合共現性信息的軟分配向量了，我們使用這些向量計算出圖片最終的特征向量，進而進行圖片檢索。

3 實驗結果及結論

我們在四川大學校園建筑圖片集上分別計算了原始的軟分配方法和融合共現性的軟分配方法進行圖片檢索的MAP值和召回率，結果對照如圖1所示。

實驗證明，融合視覺單詞共現性的軟分配詞袋技術在MAP上有約1.4%的提高，確實能夠在一定程度上減少局部興趣點不可靠的分配，進而提升圖片檢索的精確度。

[1] Xiao-Yong Wei,Zhen-Qun Yang,Chong-Wah Ngo,Wei Zhang.Visual Typo Correction by Collocative Optimization-A Case Study on Merchandize Images,IEEE Transactions on Image Processing，2014，23（2）：527～540

[2] J'egou,H.,Douze,M.,and Schmid,C.Improving Bag-of-Features for Large Scale Image Search.International Journal of Computer Vision，2010，87（3）：316～336

[3] Xiao-Yong Wei,Zhen-Qun Yang.Mining In-Class Social Networks for Large-Scale Pedagogical Analysis.ACM Multimedia 2012（MM'12）,Nara,Japan,October 29-November 2,2012

Bag of Features with Co-occurrence Fusing Visual Words Mutual Information Based on Random Walk Model

ZHANG Jin
（School of Computer Science，Sichuan University，Chengdu 610065）

A classic scheme to retrieve image is to extract local interesting points and use bag of features to represent an image.In traditional bag of features method,every local interesting point’s assignment is mutually independent,the scheme does not consider the interaction between two adjacent local interesting points’assignment.So this can incur unreliable assignment for some local interesting points,and low the overall accuracy of image retrieve.Considers that learn some valuable priori knowledge by counting the co-occurring times between visual words;then fuses the co-occurrence information between visual words into the original soft-assigned bag of features based on random walk model,in order to avoid unreliable assignment of local interesting points and improve overall accuracy of image retrieve.

Local Interesting Point;Visual Word;Bag of Features;Mutual Information;Random Walk Model

圖1

1007-1423（2015）02-0015-03

10.3969/j.issn.1007-1423.2015.02.004

張晉（1989-），男，山東曲阜人，碩士研究生，研究方向為有機器學習、多媒體計算

2014-11-13

2014-12-18