基于詞匯樹方法的圖像檢索

曹健健，唐 悅，劉芮辰，王志青

(安徽大學 計算機科學與技術學院，安徽 合肥 230039)

?

基于詞匯樹方法的圖像檢索

曹健健，唐 悅，劉芮辰，王志青

(安徽大學 計算機科學與技術學院，安徽 合肥 230039)

目前SIFT特征提取算法具有較高的時間復雜度，不利于大規模圖像檢索，提出一種構建詞匯樹的方法，來縮短用戶檢索圖像的時間。對圖像庫用SIFT特征提取算法提取特征點，用聚類方法對圖像庫中的特征點構建一棵三層詞匯樹，并為每個結點賦合適的權值。接著計算圖像庫中每張圖片與詞匯樹的距離，這個距離稱為索引值，用來唯一表示每張圖片。在進行圖像檢索時，只需計算待檢索圖片的索引值，通過索引值的匹配來檢索圖像，可以極大地縮短用戶檢索圖像的時間。

SIFT特征提取；K-Means聚類算法；詞匯樹；索引值

0 引言

圖像檢索是計算機視覺的核心問題，也是一個非常值得研究的問題，它的關鍵在于構建能夠適用于不同規模圖像庫[1-2]的方法，并且可以在有限的時間內檢索到最準確的圖像。對于傳統的SIFT特征提取算法[3]具有很好的魯棒性和抗干擾性，有著廣泛的應用，但是由于SIFT 算子具有很高的維數(128維)，增強了其計算復雜性和時間復雜度，并且在大規模特征圖像庫[4]的檢索中存在存儲壓力。目前國內外研究學者針對其高維數的缺點，進行了改進和嘗試，以求在保持SIFT算子良好特征的前提下，盡量降低其維數。

本文提出的構建三層詞匯樹的方法在很大程度上是受傳統的詞匯樹構建方法[5-6]的啟發，都是通過特征提取和聚類方法來構建詞匯樹，主要區別在于詞匯樹[7-8]結點權重的確定方法以及每張圖片索引值的計算方法上有所不同。由于構建詞匯樹的過程是通過線下完成的，不需要占用用戶的等待時間，從而提高檢索效率。同時，計算圖像庫中圖片的索引值，通過索引值來唯一表示圖像，就可以極大地減少圖像庫的存儲壓力。本文最重要的貢獻是建立了一個索引機制[9]，它可以實現非常高效的檢索。

1 構建詞匯樹方法

1.1 SIFT特征提取

尺度不變特征變換[3](Scale Invariant Feature Transform，SIFT)是David Lowe提出的提取圖像局部特征[10-11]的算法，SIFT已被證實在同類描述子中具有最強的健壯性,對平移、旋轉、亮度變化和噪聲等有良好的不變性。SIFT算法實現過程如下。

1.1.1 構建高斯差分(DoG)尺度空間

首先將高斯核函數G與輸入圖像卷積構成高斯金字塔：

(1)

L(x,y,σ)=G(x,y,σ)*I(x,y),

(2)

式中，I(x,y)為圖像I上的點，L為尺度空間，σ 為尺度空間因子。

在高斯金字塔的基礎上，利用同一階的2個相鄰的2層的尺度空間函數之差得到DoG金子塔：

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*I(x,y)=

L(x,y,kσ)-L(x,y,σ) 。

(3)

1.1.2 特征提取的4個步驟

(1)尺度空間極值點檢測

待檢測點在由圖1中26個圓點構成的鄰域中進行比較，如果該檢測點為最大值或最小值，則該點為候選關鍵點。圖中*表示待檢測點。

圖1 尺度空間極值點的確定

(2)對粗特征點的過濾和精確定位

首先，剔除低對比度點，特征點的像素必須是與周圍的點有明顯的差異；其次，去除邊緣點，有助于提高抗噪聲能力。

(3)為特征點分配方向值

利用關鍵點鄰域像素的梯度方向分布為每個關鍵點指定主方向，公式如下：

(4)

(5)

式中，m為(x,y)處的模值，θ表示方向，L為所在的空間尺度函數。采用梯度方向直方圖法，以梯度模m作為權重，選擇主峰值作為特征點的主方向，局部峰值作為輔助方向。

(4)生成SIFT特征向量

首先將坐標軸旋轉為關鍵點的方向，以關鍵點為中心取8*8的窗口，每個小格代表所在尺度空間的一個像素。圖中心點為關鍵點。圖中圓圈代表高斯加權的范圍(越靠近關鍵點的像素梯度方向信息貢獻越大)。在4*4的小塊上計算8個方向的梯度方向，繪制其累加值，最后將特征向量長度歸一化。

圖2 圖像梯度及特征向量生成

1.2 K-Means聚類算法

聚類[12]就是按照某個特定標準把一個數據集分割成不同的類或簇，使得聚類后同一類的數據盡可能聚集[13]到一起，不同數據盡量分離。K-Means聚類算法以k為參數，把n個對象分成k個簇，使簇內具有較高的相似度，而簇間的相似度較低。

k-means算法的處理過程如下：首先，隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心；對剩余的每個對象，根據其與各簇中心的距離，將它賦給最近的簇；然后重新計算每個簇的平均值。這個過程不斷重復，直到準則函數收斂。通常，采用平方誤差準則，其定義如下：

(6)

式中，E為數據庫中所有對象的平方誤差的總和，p是空間中的點，mi是簇Ci的平均值。

1.3 構建詞匯樹具體步驟

詞匯樹[7-8]用來唯一地表示一個圖像庫，它是基于對圖像庫中的所有特征點進行聚類構造出來，并根據特征點的密集程度[7]為每個聚類中心分配不同的權重。

詞匯樹的具體構造步驟如下：

① 利用SIFT特征提取方法將圖像庫中的圖片進行特征提取,并保存每張圖片的特征點；對圖像庫中的所有特征點[2-3]利用K-Means聚類算法構建最底層的葉子結點(64個)，根據每個結點上特征點的個數分配不同的權重；

② 對底層的葉子結點利用K-Means聚類算法構建中層葉子結點(16個)，結點權重的分配方法與上述相同；

③ 對中層葉子結點再次聚類，這樣就構建出一個三層的詞匯樹并且每個結點都有相應的權重。權重的分配方法如下：

Wi,j=(maxi-nri,j)/maxii=1,2,3，

(7)

式中，Wi,j為詞匯樹第i層第j個結點的權重，maxi為結點中包含最多特征點的個數，nri,j為第i層第j個結點上特征點的個數。圖3為建立的詞匯樹模型。

圖3 詞匯樹模型

2 基于詞匯樹的圖像檢索算法

通過對大型圖像庫[4-6]的特征點進行訓練，利用K-Means聚類算法構建出詞匯樹[7-8]，接下來就是利用構建出的三層詞匯樹對圖像進行檢索。具體做法如下：首先可以先計算出圖像庫中每張圖片的特征點相對于詞匯樹各個結點(聚類中心)之間的距離，這個距離作為每張圖片的索引值[8-9]，稱之為圖片索引。這樣圖像庫中每張圖片就具有唯一的一個索引值，計算索引值可以通過線下處理。用戶在進行圖像檢索過程中只需將待檢索圖片的索引值計算出來，與圖像庫中每個圖片的索引值進行比較[14]和排序[15]，將排序后的圖片再進行篩選，選出最接近待檢索圖片索引值的圖片，即為檢索到的圖片。

索引值的計算方法如下：首先，計算圖片的每個特征點到詞匯樹的各個結點之間的距離；距離計算公式：

(8)

式中，di,k為圖片的第i個特征點與詞匯樹的第k個結點之間的距離，xi為圖片的第i個特征點，yk為詞匯樹的第k個結點。接著，找出距離最短的下標k，則該特征點屬于詞匯樹的第k個結點；統計圖片所有特征點屬于詞匯樹各個結點的數目num1*m，可以得到一個矩陣；將該矩陣與詞匯樹的權重矩陣weightn*1相乘，就可以得到該圖片相對于詞匯樹的索引值。

3 有效性分析

3.1 實驗中的圖像庫

本次實驗采用的圖像庫中含有170張圖片，每張圖片的大小約為500*500像素，圖片可以分為50組，圖片的主題為人行走時的狀態。圖片記錄了不同人物在不同的背景下行走時的姿態，由于人物行走時的姿態具有很大的相似性，檢索中的特征點相似程度[16]比較高，所以對于實驗的算法要求就比較高，對實驗方法的驗證具有很好的有效性。

3.2 實驗數據

在構建詞匯樹的過程中，會產生一些非常重要的數據，這些數據對于成功構建詞匯樹至關重要，對于圖像檢索的準確性具有很大的影響，本次實驗數據如表1所示。對于大規模圖像庫，所提取特征點的個數更多，所建立的詞匯樹模型的層次也可以適當的增加。表中，centers1、centers2、centers3為3次聚類的聚類中心；centers 表示聚類中心；k1、k2、k3 為各級聚類的個數；tezheng向量用來存儲每張照片特征點；cid表示每個數據屬于哪一類，nr表示每一類的個數。

表1 構建詞匯樹的參數和圖像庫的索引值

3.3 數據分析

3.3.1 SIFT算法的時間復雜度分析

實驗中統計了每張圖片用SIFT特征提取算法提取的特征點的個數以及所用的時間，從中抽取若干數據進行分析，統計特征點個數與提取時間的關系，如圖4所示。可以發現圖片提取的特征點與提取時間基本成線性增加，從而驗證了SIFT算法具有較高的時間復雜度O(N)。

圖4 圖像特征點個數與提取時間的關系

3.3.2 基于詞匯樹的檢索過程

① 輸入待檢索圖像，如圖5所示。

圖5 待檢索的圖像

② 檢索圖像過程，如圖6所示。

圖6 圖像檢索程序的過程

③ 檢索結果如圖7和圖8所示。

圖7 檢索到第1張圖片(最相似)

圖8 檢索到第2張圖片

3.3.3 實驗結果分析

在本次實驗之前，同樣進行了傳統SIFT特征特征提取，利用特征點的高斯距離來進行檢索圖像，但是由于SIFT算法具有較高的時間復雜度，提取過程就非常耗時，同時距離匹配的計算也十分耗時，容易出現超出內存的現象，實驗的結果不是很理想。對于本文提出的利用詞匯樹檢索圖像的方法，從實驗的結果來看，檢索一張圖片的時間大約是1 min，并且檢索的結果也十分準確。

4 結束語

利用傳統的SIFT算法進行圖像檢索，需要計算圖像庫中每張圖片的特征點與待檢索圖像特征點之間的距離，再進行排序檢索，此算法耗時嚴重。而構建詞匯樹的方法，可以將圖像庫的建樹以及每張圖片索引值的計算通過線下處理完成，用戶只需要計算待檢索圖像的索引值，根據索引值進行檢索，算法的時間復雜度大大減少，可以很快速檢索到用戶所需的圖片。

[1] Lowe D.Object Recognition from Local Scale-Invariant Features[C]∥International Conference On Computer Vision,Corfu,Greece,1999:1150-1157.

[2] Lowe D.Distinctive Image Features from Scale Invariant Keypoints[C]∥ Computer Science Department University of British Columbia ,Vancouver B C,Canada,2004:91-110.

[3] Vedaldi A. An Implementation of SIFT Detector and Descriptor[D]. Los Angeles :University of California,2010 .

[4] Zhou W,Lu Y,Li H,et al. Scalar Quantization for Large Scale Image Search[C]∥Conference Proceedings of the 20th ACM International Conference on Multimedia,Japan,2012:169-178.

[5] Cai Y,Tong W,Yang L,et al.Constrained Keypoint Quantization: Towards Better Bag-of-words Model for Large-scale Multimedia Retrieval[C]∥ACM International Conference on Multimedia Retrieval,Hong Kong,China,2012:1-8.

[6] Zheng L,Wang S,Liu Z,et al.Lp-norm IDF for Large Scale Image Search[C]∥IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Springer,2013:1626-1633.

[7] Jégou H,Douze M,Schmid C.On the Burstiness of Visual Elements[C]∥IEEE Conference on Computer Vision and Pattern Recognition,Miami,2009:1169-1176.

[8] Wang X,Yang M,Cour T,et al.Contextual Weighting for Vocabulary Tree Based Image Retrieval[C]∥IEEE Intetnational Conference on Computer Vision,Barcelona,2011:209-216.

[9] Zhang X,Li Z,Zhang L,et al. Efcient Indexing for Large Scale Visual Search[C]∥IEEE Intetnational Conference on Computer Vision,USA,2009:761-768.

[10]Zhou W,Lu Y,Li H,et al.Spatial Coding for Large Scale Partial-duplicate Web Image Retrieval[J].Journal of Computer Science & Technology,2014,29(5):837-848.

[11]Ke Y,Sukthankar R. PCA-SIFT: A More Distinctive Representation for Local Image Descriptors[C]∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Washington,2004:506-513.

[12]汪海波，張海臣，段雪麗．基于MATLAB的自組織競爭神經網絡聚類研究[J]．邢臺職業技術學院學報，2005，22(1)：45-47．

[13]Yuan X T,Yan S.Visual Classification with Multi-task Joint Sparse Representation[C]∥In Proc. IEEE Conf. Comput. Vis. Pattern Recognit,2010:3493-3500.

[14]Sivic J,Zisserman A.Video Google: A Text Retrieval Approach to Object Matching in Videos[C]∥In Proc. 9th Int. Conf. Com-put. Vis.,Nice,France,2003:1470-1477.

[15]Fagin R,Kumar R,Sivakumar D.Efficient Similarity Search and Classification Via Rank Aggregation[C]∥In Proc. ACM SIGMOD Int. Conf. Manage. Data,San Diego,CA,USA,2003:301-312.

[16]Jaccard P.The Distribution of the Flora in the Alpine Zone[J].New Phytologist,1912,11(2):37-50.

Image Retrieval Based on Vocabulary Tree Approach

CAO Jian-jian,TANG Yue,LIU Rui-chen,WANG Zhi-qing

(School of Computer Science and Technology,Anhui University,Hefei Anhui 230039,China)

The SIFT feature extraction algorithm has higher time complexity,which is disadvantageous to large-scale image retrieval. In view of this problem,this paper puts forward a new method of constructing vocabulary tree in order to shorten the user time of image retrieval. In this method,firstly the feature points are extracted from image library by using SIFT feature extraction algorithm,these points are clustered by clustering method,a three-layer vocabulary tree is constructed,and the appropriate weights are assigned to all nodes After constructing a complete vocabulary tree for the image library,the distance between the vocabulary tree and each image in image library is calculated,and this distance is called as index value and used to represent each image uniquely. In image retrieval,only the index values of images to be retrieved are necessary to calculate,and the image retrieval is performed by matching the index value of the image library. This method can greatly shorten the user time of image retrieval.

SIFT feature extraction; k-means clustering algorithm; vocabulary tree; index value

2017-05-18

安徽大學大學生創新項目(J10118515624)

曹健健(1996—)，男，本科生，主要研究方向：基于內容的圖像檢索。唐悅(1996—)，女，本科生，主要研究方向：模式識別。

10. 3969/j.issn. 1003-3114. 2017.05.17

曹健健，唐悅，劉芮辰，等.基于詞匯樹方法的圖像檢索[J].無線電通信技術,2017,43(5):77-81.

[CAO Jianjian,TANG Yue,LIU Ruichen,et al. Image Retrieval Based on Vocabulary Tree Approach[J].Radio Communications Technology,2017,43(5):77-81.]

TP391

A

1003-3114(2017)05-77-5