基于視覺詞典和位置敏感哈希的圖像檢索方法

孫曉峰 ，彭天強(qiáng)

(1.河南工程學(xué)院 國際教育學(xué)院,河南 鄭州 451191; 2.河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191)

?

基于視覺詞典和位置敏感哈希的圖像檢索方法

孫曉峰1，彭天強(qiáng)2

(1.河南工程學(xué)院 國際教育學(xué)院,河南 鄭州 451191; 2.河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191)

當(dāng)前視覺詞袋(Bag of Visual Word，BoVW)模型中的視覺詞典均由k-means及其改進(jìn)算法在原始局部特征描述子上聚類生成，但隨著圖像數(shù)據(jù)的迅速增長，在原始局部特征空間中進(jìn)行聚類存在著運(yùn)行時間較長和占用內(nèi)存較大的問題.針對著這些問題，提出了一種基于視覺詞典和位置敏感哈希的圖像檢索方法.首先，選擇合適的生成二進(jìn)制哈希碼的哈希算法，將局部特征點(diǎn)保持相似性地映射為二進(jìn)制哈希碼.然后，在二進(jìn)制哈希碼上進(jìn)行k-means，生成視覺詞為二進(jìn)制碼的視覺詞典.最后，用視覺單詞的詞頻向量表示圖像內(nèi)容，根據(jù)詞頻向量對圖像進(jìn)行檢索.在SIFT-1M和Caltech-256數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本方法可以縮短視覺詞典生成的時間，占用更少的存儲空間，與傳統(tǒng)的基于k-means的視覺詞典算法相比，圖像檢索性能基本不變.

二進(jìn)制哈希碼；視覺詞袋模型；局部特征；二進(jìn)制視覺詞典；圖像檢索

隨著大數(shù)據(jù)時代的到來，互聯(lián)網(wǎng)圖像資源迅猛增長，如何對大規(guī)模圖像資源進(jìn)行快速有效檢索的問題亟待解決.圖像檢索技術(shù)由早期的基于文本的圖像檢索(Text-based Image Retrieval，TBIR)逐漸發(fā)展為基于內(nèi)容的圖像檢索(Content-based Image Retrieval，CBIR)，CBIR通過提取圖像的視覺底層特征來實(shí)現(xiàn)圖像內(nèi)容的表達(dá).視覺底層特征包括基于梯度的圖像局部特征描述子，如SIFT[1](Scale-Invariant Feature Transform)、HOG[2](Histogram of Orientated Gradients)等.局部特征能夠表征圖像的底層視覺特征，被大量用于圖像內(nèi)容的分析.在基于局部特征的圖像檢索中，視覺詞袋法(BoVW)[3]是主流的圖像內(nèi)容表示方法.BoVW的主要流程：①局部特征提取，一般提取SIFT特征；②視覺詞典生成，采用聚類算法對局部特征進(jìn)行聚類得出；③量化，將單幅圖像的各局部特征量化為視覺單詞；④創(chuàng)建直方圖，根據(jù)視覺詞典創(chuàng)建各圖像視覺單詞頻向量,得到的詞頻向量用于表示圖像，作為圖像的特征進(jìn)行圖像的檢索和識別等.

在上述視覺詞袋法的流程中，關(guān)鍵在于第二步——視覺詞典的生成，而第二步一般采用k-means聚類算法及其相關(guān)的改進(jìn)算法[4]直接對圖像的局部特征進(jìn)行聚類，聚類得出中心構(gòu)成視覺詞典.k-means聚類算法需要對數(shù)據(jù)集中所有局部特征點(diǎn)進(jìn)行多次迭代運(yùn)算，而且每次迭代都需要將特征點(diǎn)分配到與之最近的聚類中心.在數(shù)據(jù)集規(guī)模較大時，聚類時間和內(nèi)存消耗會急劇增加(其時間復(fù)雜度為O(nk)，k是聚類數(shù)目，n為特征點(diǎn)數(shù)目).為了加快視覺詞典的構(gòu)建速度，Mu等[5]提出了基于位置敏感哈希[6](Locality Sensitive Hashing，LSH)構(gòu)建視覺詞典，該算法不需要聚類，利用LSH生成視覺詞典.類似地，趙永威等[7]采用精確歐式位置敏感哈希(Exact Euclidean Locality Sensitive Hashing，E2LSH)對局部特征點(diǎn)進(jìn)行聚類，生成多個視覺詞典并加以融合.以上兩種方法雖然避免了使用聚類方法生成視覺詞典，但是采用了隨機(jī)的哈希方法生成視覺詞典，導(dǎo)致生成的視覺詞典隨機(jī)性太強(qiáng)，需要生成多個視覺詞典組并加以融合才能達(dá)到不錯的效果.

針對以上問題，提出了一種基于視覺詞典和位置敏感哈希的圖像檢索方法，基本思想是利用保持相似性的二進(jìn)制哈希碼代替原空間的特征進(jìn)行聚類算法生成視覺詞典，即將原始特征變換到Hamming空間中，在Hamming空間再做一次聚類操作，生成視覺詞典.這樣，既利用了二進(jìn)制哈希碼在計(jì)算速度和存儲空間上的優(yōu)越性，又找到了一種原特征點(diǎn)與二進(jìn)制視覺詞之間的變換方法，降低了視覺詞典的隨機(jī)性.

1　位置敏感哈希

位置敏感哈希按照其應(yīng)用可以分為兩類[8]：一類是以一個有效的方式對原始數(shù)據(jù)進(jìn)行排序以加快搜索速度，這種類型的哈希算法稱為二進(jìn)制哈希(Original LSH)；另一類是將高維數(shù)據(jù)嵌入Hamming空間，進(jìn)行按位操作以找到相似的對象，這種類型的哈希算法稱為“Binary Hashing” .二進(jìn)制哈?？梢詾槊恳粋€對象產(chǎn)生二進(jìn)制編碼，通過二進(jìn)制碼的Hamming距離來度量兩個對象的相似性和距離，Hamming距離還可以保持原始對象間的歐氏距離.

二進(jìn)制哈希方法可以分為無監(jiān)督的哈希算法、半監(jiān)督的哈希算法和監(jiān)督的哈希算法.無監(jiān)督的哈希方法不考慮數(shù)據(jù)的標(biāo)簽信息，包括Isotropic Hashing[9](PCAH)、譜哈希[10](Spetral Hashing，SH)、PCA-ITQ[11]等；半監(jiān)督的哈希方法考慮部分相似性信息，包括半監(jiān)督哈希方法[12](Semi-Supervised Hashing，SSH) ；監(jiān)督的哈希方法利用數(shù)據(jù)集的標(biāo)簽信息或者相似性點(diǎn)對信息作為監(jiān)督信息，包括BRE[13](Binary Reconstructive Embedding)、監(jiān)督的核哈希[14](Kernel-Based Supervised Hashing，KSH)等.這些二進(jìn)制哈希算法的目標(biāo)均是尋找能夠較好地保持特征在原空間中的相似性信息且能夠生成緊致二進(jìn)制碼的哈希函數(shù).由于半監(jiān)督和監(jiān)督的哈希方法需要數(shù)據(jù)的類別標(biāo)簽信息，適用性具有一定的限制，所以考慮使用無監(jiān)督的哈希方法，而在無監(jiān)督的哈希方法中PCA-ITQ的性能最優(yōu).所以，本研究利用PCA-ITQ方法學(xué)習(xí)哈希函數(shù).

2　基于視覺詞典和哈希方法的圖像檢索

2.1多索引哈希技術(shù)

多索引哈希技術(shù)[15](Multi-Index Hashing，MIH)通過為二進(jìn)制碼建立索引結(jié)構(gòu)，在Hamming空間中可以快速進(jìn)行精確的r鄰域搜索.它的基本思想是將維度為q的二進(jìn)制哈希碼h劃分成m個不相交的子串h(1)，…，h(m)，分別為每個子集建立哈希結(jié)構(gòu).搜索與Hamming距離小于r的近鄰域g，g需要滿足在m中的某個子串中，h和g之間的Hamming距離不超過r′，其中r′=?r/m?.將在高維Hamming空間中r鄰域的搜索問題轉(zhuǎn)化為在較低維度空間中進(jìn)行半徑更小的r′鄰域問題，在較低維空間中進(jìn)行較小半徑的鄰域搜索，速度更快.

2.2基于二進(jìn)制哈希碼的k-means算法

Gong等[16]提出了一種基于二進(jìn)制哈希碼的聚類算法，用于大量圖像的分類.它的主要流程為首先利用深度學(xué)習(xí)算法為每張圖像提取特征，然后利用保持相似性的哈希算法將高維的深度特征映射為二進(jìn)制哈希碼，并用二進(jìn)制編碼作為圖像的特征表示進(jìn)行聚類.

基于二進(jìn)制哈希碼的k-means算法的目標(biāo)函數(shù)為

(1)

該目標(biāo)函數(shù)類似于k-means算法的目標(biāo)函數(shù)，只是聚類中心和樣本均為離散的二進(jìn)制值，該優(yōu)化可以利用EM算法來求解.首先，需要將每個二進(jìn)制哈希碼分配到與之最近的聚類中心，對當(dāng)前二進(jìn)制編碼的情形可以通過多索引哈希技術(shù)(MIH)加快該處理過程.然后，更新二進(jìn)制聚類中心，可以通過求解問題(1)的最優(yōu)解得到其計(jì)算公式.

僅考慮某個聚類中心，問題(1)優(yōu)化問題可轉(zhuǎn)化為

(2)

由于式(4)中第一項(xiàng)和第二項(xiàng)均為常數(shù)值，問題(4)的最小化問題可以轉(zhuǎn)化為等價的最大值問題：

(3)

問題(3)有解析形式的最優(yōu)解且其最優(yōu)解為

(4)

2.3基于二進(jìn)制視覺詞典的圖像檢索

圖1　基于二進(jìn)制視覺詞典的圖像檢索流程Fig.1　The flow chart of image retrieval for binary-based visual vocabulary

基于二進(jìn)制視覺詞典的圖像檢索流程見圖1.基于二進(jìn)制視覺詞典的圖像檢索分為視覺詞典生成和圖像檢索兩個階段，與傳統(tǒng)的BoVW圖像檢索方法的區(qū)別在于，視覺詞典是二進(jìn)制哈希碼及局部特征點(diǎn)需要變換到漢明空間轉(zhuǎn)化為二進(jìn)制哈希碼.二進(jìn)制視覺詞典的生成過程如下：

(1)提取圖像集中各圖像的SIFT特征；

(2)從SIFT特征點(diǎn)集中選擇樣本點(diǎn)，訓(xùn)練生成PCA-ITQ哈希方法所需參數(shù)；

(3)根據(jù)(2)得到的參數(shù)，利用PCA-ITQ算法將SIFT特征集轉(zhuǎn)化為二進(jìn)制哈希碼；

(4)根據(jù)2.2中基于二進(jìn)制哈希碼的聚類算法，將二進(jìn)制哈希碼聚成k類(k為事先指定的視覺詞典的單詞數(shù)目)；

最后,得到的k個聚類中心構(gòu)成了二進(jìn)制視覺詞典.

利用上述(2)中的參數(shù)將圖像集各圖像局部特征點(diǎn)轉(zhuǎn)化為二進(jìn)制哈希碼，然后根據(jù)二進(jìn)制視覺詞典統(tǒng)計(jì)圖像集各圖像二進(jìn)制哈希碼的詞頻生成圖像集的詞頻向量組.

圖像檢索過程，主要包括：①提取查詢圖像的SIFT特征；②利用PCA-ITQ哈希算法將SIFT特征點(diǎn)轉(zhuǎn)化為二進(jìn)制哈希碼；③根據(jù)視覺詞典統(tǒng)計(jì)二進(jìn)制哈希碼的詞頻，生成查詢圖像的詞頻向量組；④計(jì)算查詢圖像詞頻向量和圖像集詞頻向量的相似度；⑤進(jìn)行相似度排序，確定相似圖像.

3　實(shí)驗(yàn)與性能評價

3.1實(shí)驗(yàn)

為驗(yàn)證本方法的有效性，在SIFT-1M[17]、Caltech-256[18]圖像集上對本方法進(jìn)行了評估.SIFT-1M包含1 000 000個128維的局部特征點(diǎn)；Caltech-256圖像集是目標(biāo)分類任務(wù)中常用數(shù)據(jù)集，包含256個類別共計(jì)30 608張圖像，其中每個類別中至少包含80張圖像.

實(shí)驗(yàn)用單機(jī)的硬件配置為3.4 GHz的雙核CPU、16 G的內(nèi)存.圖像檢索性能指標(biāo)采用MAP(Mean Average Precision)，它表示所有圖像查準(zhǔn)率的平均值.其中,查準(zhǔn)率定義如下：

(5)

3.2實(shí)驗(yàn)性能分析

為驗(yàn)證基于二進(jìn)制哈希碼的聚類算法(Bk-means)的有效性，在SIFT-1M數(shù)據(jù)集上與傳統(tǒng)的k-means算法進(jìn)行比較.首先,在SIFT-1M數(shù)據(jù)集中隨機(jī)選出10 000個樣本，訓(xùn)練生成PCA-ITQ算法所需參數(shù)；其次，利用PCA-ITQ算法將SIFT-1M數(shù)據(jù)集轉(zhuǎn)化為64 bit的二進(jìn)制哈希碼；然后，利用2.2中基于二進(jìn)制哈希碼的聚類算法進(jìn)行聚類，測試它聚類所用的時間.在SIFT-1M數(shù)據(jù)集上測試在設(shè)置不同的聚類個數(shù)的情況下，Bk-means算法和k-means算法的所用時間,實(shí)驗(yàn)結(jié)果如表1所示.

為驗(yàn)證基于二進(jìn)制視覺詞典的檢索方法在圖像檢索中的有效性，在Caltech-256圖像集上進(jìn)行了實(shí)驗(yàn).在特征點(diǎn)個數(shù)N不同的情況下，測試基于Bk-means的視覺詞典生成算法和基于k-means的視覺詞典生成算法，在視覺詞典生成時間和檢索結(jié)果MAP上作比較,結(jié)果見表2.

表1　在數(shù)據(jù)集SIFT-1M上聚類時間對比

表2　不同特征點(diǎn)個數(shù)的圖像檢索MAP值和視覺詞典生成時間對比

從表2中可以看出，在不同的特征點(diǎn)N的情況下，基于傳統(tǒng)k-means算法生成視覺詞典所用時間是基于二進(jìn)制哈希碼生成視覺詞典所用時間的2倍.隨著N的增加，基于傳統(tǒng)k-means的視覺生成算法所用時間增加速度快于基于Bk-means的視覺詞典生成算法.

4　結(jié)語

提出了一種基于視覺詞典和局部敏感哈希的圖像檢索方法.首先，為了充分利用二進(jìn)制哈希碼在存儲和計(jì)算速度上的優(yōu)越性，選擇無監(jiān)督的PCA-ITQ算法將原始空間中的局部特征點(diǎn)保持相似性地映射為二進(jìn)制哈希碼.然后，在二進(jìn)制哈希碼上進(jìn)行k-means，生成視覺詞為二進(jìn)制碼的視覺詞典.最后，用二進(jìn)制視覺單詞的詞頻向量表示圖像，根據(jù)詞頻向量對圖像進(jìn)行檢索，實(shí)驗(yàn)結(jié)果有效地驗(yàn)證了本方法的圖像檢索精度損失不大，但是在運(yùn)行時間和存儲空間上有較大的優(yōu)勢.

[1]DAVID G，LOWE.Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision,2004,60(2): 91-110.

[2]DALAL N,TRIGGS B.Histograms of oriented gradients for human detection[C]∥Computer Vision and Pattern Recognition,San Diego,CA：IEEE，2005:886-893.

[3]SIVIC J,ZISSERMAN A.Video Google:a text retrieval approach to object matching in videos[C]∥Proceedings of 9th IEEE International Conference on Computer Vision,Nice：IEEE，2003:1470-1477.

[4]FRANK M,ERIC N,FREDERIC J.Randomized clustering forests for image classification[J].Pattern Analysis and Machine Intelligence,IEEE Transaction on Pattern Analysis and Machine Intelligence,2008,30(9):1632-1646.

[5]MU Y D,SUN J,TONY X,et al.Randomized locality sensitive vocabularies for bag-of-features model[C]∥European Conference on Computer Vision,Heraklion Crete：FORTH,2010:748-761.

[6]DATAR M,IMMORLICA N,INDYK P,et al.Locality sensitive hashing scheme based on p-stable distributions[C]∥Proceedings of the ACM Symposium on Computational Geometry,New York：ACM,2004:253-262.

[7]趙永威,李弼程,彭天強(qiáng),等.一種基于隨機(jī)化視覺詞典組合查詢擴(kuò)展的目標(biāo)檢索方法[J].電子與信息學(xué)報,2012,34(5):1154-1161.

[8]ZHANG L,ZHANG Y D,ZHANG D M,et al.Distribution-Aware Locality Sensitive Hashing[M].Berlin:Springer-Verlag Berlin Heidelberg,2013:395-406.

[9]KONG W H,LI W J.Isotropic hashing[C]∥Advances in neural information processing systems,Lake Tahoe：NIPS Foundation,2012:1646-1654.

[10]YAIR W,ANTONIO T，ROB F.Spectral Hashing[C]∥I Advances in neural information processing systems,Vomcouver,BC：NIPS Foundation,2009:1753-1760.

[11]MU Y D,LAZEBNIK S,GORDO A,et al.Iterative quantization:a procrustean approach to learning binary codes for large-scale image retrieval[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2012,35(12):2916-2929.

[12]WANG J,KUMAR S,CHANG S F.Semi-Supervised hashing for large scale search[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2012,34(12):2393-2406.

[13]KULIS B,DARRELL T.Learning to hash with binary reconstructive embeddings[C]∥Advances in neural information processing systems,Vomcouver,BC：NIPS Foundation,2009:1042-1052.

[14]LIU W,WANG J,JI R R,et al.Supervised hashing with kernels[C]∥Computer Vision and Pattern Recognition,Rhode Island：IEEE,2012:2074-2081.

[15]NOROUZI M,PUNJANI A,FLEET D J.Fast search in hamming space with multi-index hashing[C]∥Computer Vision and Pattern Recognition,Rhode Island：IEEE,2012:3108-3115.

[16]GONG Y,PAWLOWSKI M,YANG F,et al.Web scale photo hash clustering on a single machine[C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,Boston：IEEE,2015:19-27.

[17]JEGOU H,DOUZE M,SCHMID C.Product quantization for nearest neighbor search[J].Pattern Analysis and Machine Intelligence,2011,33(1):117-128.

[18]FERGUS F F L 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.

Image retrieval based on visual vocabulary and locality sensitive hashing

SUN Xiaofeng1, PENG Tianqiang2

(1.Department of International Education,Henan University of Engineering,Zhengzhou 451191,China;2.CollegeofComputer,HenanUniversityofEngineering,Zhengzhou451191,China)

Currently, visual vocabulary in the bag of visual word(BoVW) model is often generated either by the k-means algorithm or its improved algorithms based on original local features, but with the increasing amount of image data, clustering in the original local feature space have the problem of long running time and large memory occupation. For these problems, we propose an image retrieval method based on visual vocabulary and locality sensitive hashing. Firstly, we select an appropriate binary hashing algorithm, which map the similar local feature points onto similar binary hash codes. Second, we play k-means on the binary hash codes and generate the visual vocabulary with binary visual word. Finally, the image is represented with the word frequency vector of visual words, and image retrieval is achieved based on the word frequency vector. Experimental results on SIFT-1M and Caltech-256 data sets show that the proposed method can reduce the visual vocabulary generation time and take up less storage space. Compared with the traditional image retrieval based on k-means, the image retrieval performance is almost the same.

binary hashing code; bag of visual word model; local feature; binary visual vocabulary; image retrieval

2016-04-18

國家自然科學(xué)基金(61301232)

孫曉峰(1981-)，女，黑龍江哈爾濱人，講師，研究方向?yàn)閳D像檢索.

TN391.4

A

1674-330X(2016)03-0064-05