基于詞匯樹(shù)方法的圖像檢索

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

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230039)

?

基于詞匯樹(shù)方法的圖像檢索

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

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230039)

目前SIFT特征提取算法具有較高的時(shí)間復(fù)雜度，不利于大規(guī)模圖像檢索，提出一種構(gòu)建詞匯樹(shù)的方法，來(lái)縮短用戶檢索圖像的時(shí)間。對(duì)圖像庫(kù)用SIFT特征提取算法提取特征點(diǎn)，用聚類方法對(duì)圖像庫(kù)中的特征點(diǎn)構(gòu)建一棵三層詞匯樹(shù)，并為每個(gè)結(jié)點(diǎn)賦合適的權(quán)值。接著計(jì)算圖像庫(kù)中每張圖片與詞匯樹(shù)的距離，這個(gè)距離稱為索引值，用來(lái)唯一表示每張圖片。在進(jìn)行圖像檢索時(shí)，只需計(jì)算待檢索圖片的索引值，通過(guò)索引值的匹配來(lái)檢索圖像，可以極大地縮短用戶檢索圖像的時(shí)間。

SIFT特征提?。籏-Means聚類算法；詞匯樹(shù)；索引值

0 引言

圖像檢索是計(jì)算機(jī)視覺(jué)的核心問(wèn)題，也是一個(gè)非常值得研究的問(wèn)題，它的關(guān)鍵在于構(gòu)建能夠適用于不同規(guī)模圖像庫(kù)[1-2]的方法，并且可以在有限的時(shí)間內(nèi)檢索到最準(zhǔn)確的圖像。對(duì)于傳統(tǒng)的SIFT特征提取算法[3]具有很好的魯棒性和抗干擾性，有著廣泛的應(yīng)用，但是由于SIFT 算子具有很高的維數(shù)(128維)，增強(qiáng)了其計(jì)算復(fù)雜性和時(shí)間復(fù)雜度，并且在大規(guī)模特征圖像庫(kù)[4]的檢索中存在存儲(chǔ)壓力。目前國(guó)內(nèi)外研究學(xué)者針對(duì)其高維數(shù)的缺點(diǎn)，進(jìn)行了改進(jìn)和嘗試，以求在保持SIFT算子良好特征的前提下，盡量降低其維數(shù)。

本文提出的構(gòu)建三層詞匯樹(shù)的方法在很大程度上是受傳統(tǒng)的詞匯樹(shù)構(gòu)建方法[5-6]的啟發(fā)，都是通過(guò)特征提取和聚類方法來(lái)構(gòu)建詞匯樹(shù)，主要區(qū)別在于詞匯樹(shù)[7-8]結(jié)點(diǎn)權(quán)重的確定方法以及每張圖片索引值的計(jì)算方法上有所不同。由于構(gòu)建詞匯樹(shù)的過(guò)程是通過(guò)線下完成的，不需要占用用戶的等待時(shí)間，從而提高檢索效率。同時(shí)，計(jì)算圖像庫(kù)中圖片的索引值，通過(guò)索引值來(lái)唯一表示圖像，就可以極大地減少圖像庫(kù)的存儲(chǔ)壓力。本文最重要的貢獻(xiàn)是建立了一個(gè)索引機(jī)制[9]，它可以實(shí)現(xiàn)非常高效的檢索。

1 構(gòu)建詞匯樹(shù)方法

1.1 SIFT特征提取

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

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

首先將高斯核函數(shù)G與輸入圖像卷積構(gòu)成高斯金字塔：

(1)

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

(2)

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

在高斯金字塔的基礎(chǔ)上，利用同一階的2個(gè)相鄰的2層的尺度空間函數(shù)之差得到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個(gè)步驟

(1)尺度空間極值點(diǎn)檢測(cè)

待檢測(cè)點(diǎn)在由圖1中26個(gè)圓點(diǎn)構(gòu)成的鄰域中進(jìn)行比較，如果該檢測(cè)點(diǎn)為最大值或最小值，則該點(diǎn)為候選關(guān)鍵點(diǎn)。圖中*表示待檢測(cè)點(diǎn)。

圖1 尺度空間極值點(diǎn)的確定

(2)對(duì)粗特征點(diǎn)的過(guò)濾和精確定位

首先，剔除低對(duì)比度點(diǎn)，特征點(diǎn)的像素必須是與周?chē)狞c(diǎn)有明顯的差異；其次，去除邊緣點(diǎn)，有助于提高抗噪聲能力。

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

利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布為每個(gè)關(guān)鍵點(diǎn)指定主方向，公式如下：

(4)

(5)

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

(4)生成SIFT特征向量

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

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

1.2 K-Means聚類算法

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

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

(6)

式中，E為數(shù)據(jù)庫(kù)中所有對(duì)象的平方誤差的總和，p是空間中的點(diǎn)，mi是簇Ci的平均值。

1.3 構(gòu)建詞匯樹(shù)具體步驟

詞匯樹(shù)[7-8]用來(lái)唯一地表示一個(gè)圖像庫(kù)，它是基于對(duì)圖像庫(kù)中的所有特征點(diǎn)進(jìn)行聚類構(gòu)造出來(lái)，并根據(jù)特征點(diǎn)的密集程度[7]為每個(gè)聚類中心分配不同的權(quán)重。

詞匯樹(shù)的具體構(gòu)造步驟如下：

① 利用SIFT特征提取方法將圖像庫(kù)中的圖片進(jìn)行特征提取,并保存每張圖片的特征點(diǎn)；對(duì)圖像庫(kù)中的所有特征點(diǎn)[2-3]利用K-Means聚類算法構(gòu)建最底層的葉子結(jié)點(diǎn)(64個(gè))，根據(jù)每個(gè)結(jié)點(diǎn)上特征點(diǎn)的個(gè)數(shù)分配不同的權(quán)重；

② 對(duì)底層的葉子結(jié)點(diǎn)利用K-Means聚類算法構(gòu)建中層葉子結(jié)點(diǎn)(16個(gè))，結(jié)點(diǎn)權(quán)重的分配方法與上述相同；

③ 對(duì)中層葉子結(jié)點(diǎn)再次聚類，這樣就構(gòu)建出一個(gè)三層的詞匯樹(shù)并且每個(gè)結(jié)點(diǎn)都有相應(yīng)的權(quán)重。權(quán)重的分配方法如下：

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

(7)

式中，Wi,j為詞匯樹(shù)第i層第j個(gè)結(jié)點(diǎn)的權(quán)重，maxi為結(jié)點(diǎn)中包含最多特征點(diǎn)的個(gè)數(shù)，nri,j為第i層第j個(gè)結(jié)點(diǎn)上特征點(diǎn)的個(gè)數(shù)。圖3為建立的詞匯樹(shù)模型。

圖3 詞匯樹(shù)模型

2 基于詞匯樹(shù)的圖像檢索算法

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

索引值的計(jì)算方法如下：首先，計(jì)算圖片的每個(gè)特征點(diǎn)到詞匯樹(shù)的各個(gè)結(jié)點(diǎn)之間的距離；距離計(jì)算公式：

(8)

式中，di,k為圖片的第i個(gè)特征點(diǎn)與詞匯樹(shù)的第k個(gè)結(jié)點(diǎn)之間的距離，xi為圖片的第i個(gè)特征點(diǎn)，yk為詞匯樹(shù)的第k個(gè)結(jié)點(diǎn)。接著，找出距離最短的下標(biāo)k，則該特征點(diǎn)屬于詞匯樹(shù)的第k個(gè)結(jié)點(diǎn)；統(tǒng)計(jì)圖片所有特征點(diǎn)屬于詞匯樹(shù)各個(gè)結(jié)點(diǎn)的數(shù)目num1*m，可以得到一個(gè)矩陣；將該矩陣與詞匯樹(shù)的權(quán)重矩陣weightn*1相乘，就可以得到該圖片相對(duì)于詞匯樹(shù)的索引值。

3 有效性分析

3.1 實(shí)驗(yàn)中的圖像庫(kù)

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

3.2 實(shí)驗(yàn)數(shù)據(jù)

在構(gòu)建詞匯樹(shù)的過(guò)程中，會(huì)產(chǎn)生一些非常重要的數(shù)據(jù)，這些數(shù)據(jù)對(duì)于成功構(gòu)建詞匯樹(shù)至關(guān)重要，對(duì)于圖像檢索的準(zhǔn)確性具有很大的影響，本次實(shí)驗(yàn)數(shù)據(jù)如表1所示。對(duì)于大規(guī)模圖像庫(kù)，所提取特征點(diǎn)的個(gè)數(shù)更多，所建立的詞匯樹(shù)模型的層次也可以適當(dāng)?shù)脑黾?。表中，centers1、centers2、centers3為3次聚類的聚類中心；centers 表示聚類中心；k1、k2、k3 為各級(jí)聚類的個(gè)數(shù)；tezheng向量用來(lái)存儲(chǔ)每張照片特征點(diǎn)；cid表示每個(gè)數(shù)據(jù)屬于哪一類，nr表示每一類的個(gè)數(shù)。

表1 構(gòu)建詞匯樹(shù)的參數(shù)和圖像庫(kù)的索引值

3.3 數(shù)據(jù)分析

3.3.1 SIFT算法的時(shí)間復(fù)雜度分析

實(shí)驗(yàn)中統(tǒng)計(jì)了每張圖片用SIFT特征提取算法提取的特征點(diǎn)的個(gè)數(shù)以及所用的時(shí)間，從中抽取若干數(shù)據(jù)進(jìn)行分析，統(tǒng)計(jì)特征點(diǎn)個(gè)數(shù)與提取時(shí)間的關(guān)系，如圖4所示。可以發(fā)現(xiàn)圖片提取的特征點(diǎn)與提取時(shí)間基本成線性增加，從而驗(yàn)證了SIFT算法具有較高的時(shí)間復(fù)雜度O(N)。

圖4 圖像特征點(diǎn)個(gè)數(shù)與提取時(shí)間的關(guān)系

3.3.2 基于詞匯樹(shù)的檢索過(guò)程

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

圖5 待檢索的圖像

② 檢索圖像過(guò)程，如圖6所示。

圖6 圖像檢索程序的過(guò)程

③ 檢索結(jié)果如圖7和圖8所示。

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

圖8 檢索到第2張圖片

3.3.3 實(shí)驗(yàn)結(jié)果分析

在本次實(shí)驗(yàn)之前，同樣進(jìn)行了傳統(tǒng)SIFT特征特征提取，利用特征點(diǎn)的高斯距離來(lái)進(jìn)行檢索圖像，但是由于SIFT算法具有較高的時(shí)間復(fù)雜度，提取過(guò)程就非常耗時(shí)，同時(shí)距離匹配的計(jì)算也十分耗時(shí)，容易出現(xiàn)超出內(nèi)存的現(xiàn)象，實(shí)驗(yàn)的結(jié)果不是很理想。對(duì)于本文提出的利用詞匯樹(shù)檢索圖像的方法，從實(shí)驗(yàn)的結(jié)果來(lái)看，檢索一張圖片的時(shí)間大約是1 min，并且檢索的結(jié)果也十分準(zhǔn)確。

4 結(jié)束語(yǔ)

利用傳統(tǒng)的SIFT算法進(jìn)行圖像檢索，需要計(jì)算圖像庫(kù)中每張圖片的特征點(diǎn)與待檢索圖像特征點(diǎn)之間的距離，再進(jìn)行排序檢索，此算法耗時(shí)嚴(yán)重。而構(gòu)建詞匯樹(shù)的方法，可以將圖像庫(kù)的建樹(shù)以及每張圖片索引值的計(jì)算通過(guò)線下處理完成，用戶只需要計(jì)算待檢索圖像的索引值，根據(jù)索引值進(jìn)行檢索，算法的時(shí)間復(fù)雜度大大減少，可以很快速檢索到用戶所需的圖片。

[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ìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)聚類研究[J]．邢臺(tái)職業(yè)技術(shù)學(xué)院學(xué)報(bào)，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

安徽大學(xué)大學(xué)生創(chuàng)新項(xiàng)目(J10118515624)

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

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

曹健健，唐悅，劉芮辰，等.基于詞匯樹(shù)方法的圖像檢索[J].無(wú)線電通信技術(shù),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