盧艷君，徐望明

(武漢科技大學(xué)信息科學(xué)與工程學(xué)院，湖北 武漢，430081)

一種運(yùn)用隨機(jī)算法改進(jìn)的圖像檢索方法

盧艷君，徐望明

(武漢科技大學(xué)信息科學(xué)與工程學(xué)院，湖北 武漢，430081)

傳統(tǒng)基于局部特征表示的圖像檢索方法在圖像特征提取和特征相似性匹配時計(jì)算量較大，為此提出一種運(yùn)用隨機(jī)算法進(jìn)行改進(jìn)的圖像檢索方法。在圖像特征提取方面，通過隨機(jī)采樣獲得數(shù)量適當(dāng)?shù)南袼攸c(diǎn)作為特征點(diǎn)，用SIFT(scale invariant feature transform)算子對隨機(jī)特征點(diǎn)進(jìn)行描述以形成圖像的有效表示；在特征相似性匹配方面，采用基于隨機(jī)映射的LSH(locality sensitive hashing)算法為圖像特征庫建立索引，并用于對所查詢圖像的局部特征進(jìn)行高效的近似近鄰搜索。實(shí)驗(yàn)結(jié)果表明，該方法有效降低了圖像檢索的計(jì)算復(fù)雜度，提高了檢索效率。

圖像檢索；局部特征；隨機(jī)采樣；特征索引；SIFT特征；LSH算法

為了從海量數(shù)字圖像信息中獲取有價(jià)值的信息，基于內(nèi)容的圖像檢索(content-based image retrieval, CBIR)技術(shù)[1]近年來得到廣泛關(guān)注和應(yīng)用。CBIR是從所查詢圖像的視覺特征出發(fā)，在圖像庫中找出與其最為相似的圖像。CBIR系統(tǒng)中最關(guān)鍵的兩項(xiàng)技術(shù)是圖像特征提取和特征相似性匹配。

圖像特征提取技術(shù)是CBIR的基礎(chǔ)，用于解決圖像的有效特征表示問題。圖像特征有全局特征和局部特征之分，后者是近年來計(jì)算機(jī)視覺領(lǐng)域的研究熱點(diǎn)，人們相繼提出很多局部特征描述方法，其中SIFT(scale invariant feature transform)特征[2]的性能得到普遍認(rèn)可。標(biāo)準(zhǔn)SIFT特征是采用精心設(shè)計(jì)的算法檢測圖像特征點(diǎn)(也稱作“興趣點(diǎn)”或“關(guān)鍵點(diǎn)”)并進(jìn)行特征描述而得到，而通常從一幅圖像上提取的特征數(shù)量有限，且隨圖像灰度的變化其差異性較大，甚至在有些對比度過低的圖像中還可能檢測不到特征，另外一個不利因素是其特征點(diǎn)檢測算法的運(yùn)算復(fù)雜度一般較高；密集采樣(dense sampling)[3]的局部特征(如dense SIFT)按給定窗口尺寸和步長遍歷圖像子區(qū)域并進(jìn)行特征描述，雖然其對圖像內(nèi)容的描述覆蓋面較大，但也帶來特征數(shù)據(jù)量過多的問題。

特征相似性匹配技術(shù)是CBIR的核心，用于解決庫圖像特征的有效索引和所查詢圖像特征的高效近鄰搜索問題。一個有效的特征索引機(jī)制對于查詢特征的高效近鄰搜索而言是至關(guān)重要的。常規(guī)的基于特征空間搜索的索引算法如KD -Tree、R-Tree等僅能處理較低維度的特征數(shù)據(jù)，當(dāng)維度提高時這些算法的復(fù)雜度呈指數(shù)級上升，性能急劇下降，而線性掃描(即窮舉搜索)雖然不受特征維度的限制，但耗時較長。在圖像檢索的實(shí)際應(yīng)用中，為了提高檢索速度，一種可行的做法是以降低部分檢索準(zhǔn)確度為代價(jià)，由此，從“近鄰搜索”的概念出發(fā)，研究者提出了“近似近鄰搜索”的概念。LSH(locality sensitive hashing)算法就是建立在哈希索引基礎(chǔ)上的近似近鄰搜索算法[4-6]，它具有較低的復(fù)雜度，對高維數(shù)據(jù)空間中搜索查詢的支持性較好。

在綜合分析標(biāo)準(zhǔn)SIFT和密集采樣這兩種特征提取方式優(yōu)缺點(diǎn)的基礎(chǔ)上，本文提出一種運(yùn)用隨機(jī)算法改進(jìn)的圖像檢索方法，即通過合理設(shè)置采樣點(diǎn)數(shù)和相關(guān)參數(shù)對圖像進(jìn)行隨機(jī)采樣(random sampling)[7]，將采樣點(diǎn)作為特征點(diǎn)，進(jìn)而利用SIFT特征描述算法對隨機(jī)特征點(diǎn)進(jìn)行描述，從而形成圖像的特征集表示形式；同時，在建立特征索引和進(jìn)行近鄰搜索時均采用LSH算法，以提高檢索效率。

1 改進(jìn)的圖像檢索系統(tǒng)工作原理

本文運(yùn)用隨機(jī)算法改進(jìn)的圖像檢索系統(tǒng)如圖1所示，系統(tǒng)可分為離線過程和在線過程兩部分。①離線過程，即對于圖像庫中的每幅圖像，系統(tǒng)事先離線運(yùn)用特征提取算法，經(jīng)特征檢測、特征描述兩步得到圖像特征向量，形成相應(yīng)的圖像特征庫，然后在此基礎(chǔ)上建立特征索引以方便對查詢特征的快速搜索；②在線過程，即對于用戶提交的查詢圖像，系統(tǒng)運(yùn)用相同的特征提取算法實(shí)時獲取圖像特征向量，然后通過適當(dāng)?shù)南嗨菩运阉魉惴◤奶卣鲙熘胁檎宜胁樵儓D像特征的近鄰特征，并通過對庫圖像投票的方式計(jì)算查詢圖像與庫圖像之間的相似度，按相似度從大到小的順序返回最相似的一組庫圖像作為圖像檢索結(jié)果。

為了評估圖像檢索性能，可根據(jù)返回的檢索結(jié)果和庫中真實(shí)結(jié)果做統(tǒng)計(jì)分析，計(jì)算出查準(zhǔn)率、查全率及檢索效率等評價(jià)指標(biāo)。其中，查全率是檢索出的相關(guān)圖像與圖像庫中相關(guān)圖像的比值，查準(zhǔn)率是檢索出的相關(guān)圖像與檢索出的圖像總量的比值。

Fig.1 Improved image retrieval system using random algorithms

2 關(guān)鍵算法描述

2.1 隨機(jī)采樣SIFT

圖像特征提取包括特征檢測和特征描述兩個部分。標(biāo)準(zhǔn)SIFT算法獲取圖像特征向量大致有4個步驟[1]：檢測尺度空間極值點(diǎn)作為候選特征點(diǎn)；篩選并精確定位特征點(diǎn)的位置和尺度；為特征點(diǎn)分配主方向；生成特征描述向量。其中，前兩步屬于特征檢測部分，后兩步屬于特征描述部分。

本文縮減了標(biāo)準(zhǔn)SIFT算法在特征檢測階段的大量計(jì)算，通過隨機(jī)采樣圖像像素點(diǎn)作為特征點(diǎn)并進(jìn)行SIFT特征描述從而得到圖像特征向量，不涉及尺度空間理論和極值點(diǎn)檢測及篩選過程，因此該方法能有效降低計(jì)算復(fù)雜度，提高計(jì)算效率。

隨機(jī)特征點(diǎn)采樣完成后，對其進(jìn)行描述。特征描述的目的在于準(zhǔn)確表達(dá)局部圖像信息并使這種信息具有可靠的表征性。本文直接對隨機(jī)采樣的特征點(diǎn)進(jìn)行SIFT特征描述，因此最終得到的特征向量相對于標(biāo)準(zhǔn)SIFT算法而言只包含位置和方向信息。SIFT特征向量計(jì)算步驟如下：

(1)取特征點(diǎn)周圍4×4的鄰域，利用此鄰域內(nèi)像素點(diǎn)的梯度來統(tǒng)計(jì)方向直方圖，即以每10°方向?yàn)橐粋€柱，柱所代表的方向?yàn)橄袼攸c(diǎn)梯度方向，柱的長度代表梯度幅值。對方向直方圖進(jìn)行兩次平滑后的主峰值即為特征點(diǎn)的主方向。利用特征點(diǎn)鄰域像素的梯度方向分布特性，可以為每個特征點(diǎn)指定方向，從而使描述子對圖像旋轉(zhuǎn)具有不變性。設(shè)特征點(diǎn)(x,y)處的灰度值為g(x,y)，圖像梯度方向?yàn)棣?x,y)、幅值為M(x,y)，計(jì)算公式如下：

(1)

M(x,y)=[(g(x+1,y)-g(x-1,y))2+

(2)

(2)為保證特征向量的旋轉(zhuǎn)不變性，將特征點(diǎn)周圍16×16鄰域旋轉(zhuǎn)為特征點(diǎn)的主方向。設(shè)旋轉(zhuǎn)前采樣點(diǎn)坐標(biāo)為(x,y)，則可計(jì)算旋轉(zhuǎn)后的采樣點(diǎn)坐標(biāo)(x′,y′)：

(3)

式中：θ為步驟(1)中計(jì)算得到的特征點(diǎn)梯度方向θ(x,y)。

(3)在特征點(diǎn)周圍16×16鄰域窗口中，對各像素點(diǎn)根據(jù)坐標(biāo)按加權(quán)平均歸入4×4的位置網(wǎng)格，每個網(wǎng)格構(gòu)成一個種子點(diǎn)。

(4)利用式(1)、式(2)統(tǒng)計(jì)各個網(wǎng)格的方向直方圖，此時每個網(wǎng)格區(qū)域直方圖將00～360°劃分為8個方向區(qū)間，每個區(qū)間范圍為45°，即每個種子點(diǎn)有8個方向區(qū)間的梯度強(qiáng)度信息，最終獲得128維的SIFT特征描述向量。進(jìn)一步對其進(jìn)行歸一化處理，以去除光照變化的影響。

由于本文中采樣點(diǎn)的位置是隨機(jī)的，一些采樣點(diǎn)經(jīng)特征描述后得到的128維向量表征圖像特征的能力較弱，甚至可能影響檢索的準(zhǔn)確率，因此，需對特征描述后得到的向量進(jìn)行篩選，具體方法為：

假設(shè)特征點(diǎn)D經(jīng)特征描述后所得向量(a0,a1,…,a127)中元素值為0的元素個數(shù)為n(n∈[0,128])，若n>K(K∈N+)，則舍去該點(diǎn)D。K值可根據(jù)所查詢的圖像，通過多次實(shí)驗(yàn)比較獲得。

2.2 LSH算法

LSH算法的基本思想是：對于數(shù)據(jù)點(diǎn)集，利用一組具有一定約束條件的哈希函數(shù)建立多個哈希表，使得在某種相似度量條件下相似點(diǎn)發(fā)生沖突的概率相對較大，而不相似點(diǎn)發(fā)生沖突的概率相對較小[4-5]。引入LSH函數(shù)族定義：

LSH函數(shù)實(shí)際上是一種隨機(jī)映射，本文將LSH算法應(yīng)用于CBIR系統(tǒng)中，將圖像局部特征映射為Hamming空間的點(diǎn)，對這些點(diǎn)進(jìn)行哈希處理，使Hamming距離越近的點(diǎn)發(fā)生沖突的概率越大。在CBIR系統(tǒng)中，LSH算法用于進(jìn)行圖像特征相似性匹配，具體包括建立庫圖像的特征索引以及搜索查詢圖像特征的近似近鄰。

應(yīng)用LSH算法為圖像特征庫建立索引的步驟為：

(1)將圖像高維特征向量p=(x1,x2,…,xd)映射到Hamming空間中，轉(zhuǎn)化為二進(jìn)制串p'=Uc(x1)Uc(x2)…Uc(xd)。其中，Uc(xi)(i∈[1,d])表示xi個1后跟c-xi個0組成的二進(jìn)制串，c為特征向量p中任意元素xi的最大值。

(2)從字符串p'中隨機(jī)選k位(k∈(0,c×d))組成哈希函數(shù)族gj(p)(j∈(0,l],l∈N+))，這樣l個函數(shù)：g1(p)、g2(p)、…、gl(p)，每個函數(shù)對應(yīng)一個哈希表。此過程計(jì)算復(fù)雜度低，體現(xiàn)了LSH算法的隨機(jī)性。

(3)利用步驟(2)中的哈希函數(shù)，將特征向量映射到相應(yīng)的哈希表中。

應(yīng)用LSH算法對查詢圖像特征進(jìn)行近似近鄰搜索的步驟為：

(1)對于查詢圖像中特征q1、q2、…、qk，同樣將特征向量按索引建立過程中的步驟(1)映射到Hamming空間中，轉(zhuǎn)換為二進(jìn)制字符串，并通過與索引建立過程中相同的l個哈希函數(shù)g1(p)、g2(p)、…、gl(p)分別映射到相應(yīng)的哈希表中。

(2)提取gi(qj)(i∈(0,l],j∈(0,k])相似域中的所有哈希表項(xiàng)，保留與查詢圖像特征向量距離在閾值范圍內(nèi)的表項(xiàng)，由特征庫索引查找對應(yīng)特征作為候選的近鄰特征。

(3)對于得到的候選近鄰特征集，按其與查詢特征之間的Hamming距離由小到大排序，返回前K個特征作為查詢圖像特征的近鄰特征，它們是后續(xù)對庫圖像進(jìn)行投票和排序從而得出圖像檢索結(jié)果的依據(jù)。

這里，LSH算法將原始特征空間中距離問題轉(zhuǎn)換成了Hamming空間中的距離度量問題，提高了空間使用率，大規(guī)模數(shù)據(jù)的索引、查詢操作轉(zhuǎn)化為一組哈希函數(shù)的操作，在一個相對很小的數(shù)據(jù)集上的數(shù)據(jù)檢索大大縮短了相似搜索時間。因此，LSH算法具有較好的時間效率，而且在高維數(shù)據(jù)空間仍能保持良好的性能[8]。

3 圖像檢索實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)環(huán)境為Intel(R)Core(TM)i5CPU3.20 GHz，操作系統(tǒng)為Windows XP，系統(tǒng)開發(fā)平臺為配置了開源計(jì)算機(jī)視覺庫OpenCV2.4.9的Microsoft Visual Studio 2012。所用圖像庫是著名的ZuBuD圖像庫[9]，它包含201棟建筑物圖像，每個建筑物各有5幅不同季節(jié)和天氣條件下不同角度的圖像，共1005幅，格式為png，分辨率為640×480。本實(shí)驗(yàn)的目標(biāo)在于從圖像庫中查找與給定查詢圖像屬于同一建筑物的圖像。經(jīng)多次實(shí)驗(yàn)觀察，對于本文所用圖像，在對特征描述后得到的向量進(jìn)行篩選時，取K=64時檢索效果較好。

為了進(jìn)行對比分析，離線過程中，對圖像庫所有圖像采用標(biāo)準(zhǔn)SIFT或隨機(jī)采樣SIFT進(jìn)行特征提取，將所有特征數(shù)據(jù)存入特定文件夾作為圖像特征庫，不建立索引或采用LSH算法對特征庫建立索引；在線過程中，從圖像庫中選取100幅圖像作為查詢圖像，同樣采用標(biāo)準(zhǔn)SIFT或隨機(jī)采樣SIFT實(shí)時提取特征后，將查詢特征與特征庫特征通過線性掃描法或LSH算法實(shí)現(xiàn)近鄰搜索，從而根據(jù)搜索到的近鄰特征對庫圖像進(jìn)行投票、排序并得出最終檢索結(jié)果。

在進(jìn)行圖像特征提取實(shí)驗(yàn)時，統(tǒng)計(jì)了對單幅圖像特征提取的平均數(shù)量和平均時間，以比較標(biāo)準(zhǔn)SIFT算法和本文采用的隨機(jī)采樣SIFT算法。實(shí)驗(yàn)結(jié)果如表1所示。

表1 單幅圖像特征提取的平均數(shù)量和時間

Table 1 Average number and time of feature extraction from one image

由表1不難看出，隨機(jī)采樣SIFT算法提取的特征數(shù)量雖然是標(biāo)準(zhǔn)SIFT算法的近4倍，但所需的提取時間卻不到標(biāo)準(zhǔn)SIFT算法的1/3，因此，隨機(jī)采樣SIFT算法明顯比標(biāo)準(zhǔn)SIFT算法的特征提取效率高。

采用不同的特征提取方法(標(biāo)準(zhǔn)SIFT、隨機(jī)采樣SIFT)和特征相似性匹配方法(線性掃描法、LSH算法)進(jìn)行圖像檢索的實(shí)驗(yàn)結(jié)果對比如表2所示。

由表2可見，在特征提取方法相同時，線性掃描法相比LSH算法在檢索準(zhǔn)確率上只提高4.5個百分點(diǎn)左右，然而LSH算法比線性掃描法的檢索時間卻減少了53.3%以上。在進(jìn)行圖像檢索時，本文采用的“隨機(jī)采樣SIFT+LSH算法”組合相比傳統(tǒng)的“標(biāo)準(zhǔn)SIFT+線性掃描法”組合在平均查準(zhǔn)率上只降低了7.1個百分點(diǎn)，但平均檢索時間明顯減少，前者的查詢效率接近后者的3.8倍。在對計(jì)算效率要求苛刻的圖像檢索實(shí)際應(yīng)用中，這種以犧牲較少準(zhǔn)確率為代價(jià)換取更高效率的做法是可取的。

4 結(jié)語

本文針對傳統(tǒng)基于局部特征表示的圖像檢索方法存在的不足，提出了一種運(yùn)用隨機(jī)算法改進(jìn)的圖像檢索新方法，即采用隨機(jī)采樣SIFT算法提取圖像局部特征，采用LSH算法實(shí)現(xiàn)圖像特征的相似性匹配，包括建立庫圖像特征索引和完成查詢圖像特征的近似近鄰搜索。隨機(jī)算法的合理運(yùn)用明顯降低了圖像檢索中特征提取和特征相似性匹配的計(jì)算復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，相比于傳統(tǒng)的基于局部特征表示的圖像檢索方法，本文方法有效減少了計(jì)算量，縮短了檢索時間，特征提取和圖像檢索的效率大為提高。

[1] 韋立梅, 蘇兵. 基于內(nèi)容的圖像檢索技術(shù)綜述[J]. 電腦與電信, 2012 (10): 69-70.

[2]LoweDG.Distinctiveimagefeaturesfromscale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[3] Li Fei-Fei, Pietro Perona. A Bayesian hierarchical model for learning natural scene categories[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE, Los Alamitos, CA, 2005, Vol 2: 524-531.

[4] Datar M, Indyk P, Immorlica N, et al. Locality-sensitive hashing scheme based on p-stable distributions[C]//Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG’04). New York, Jun 9-11, 2004: 253-262.

[5] Slaney M, Casey M. Locality-sensitive hashing for finding nearest neighbors[J]. IEEE Signal Processing Magazine, 2008,25(2):128-131.

[6] 於慧, 謝萍, 李世進(jìn), 等. 基于多特征LSH索引的快速遙感圖像檢索[J]. 山西大學(xué)學(xué)報(bào):自然科學(xué)版, 2013, 36(3):350-360.

[7] Nowak E, Jurie F, Triggs B. Sampling strategies for bag-of-features image classification[C]//Proceedings of 9th European Conference on Computer Vision. Graz, Austria, May 7-13, 2006: 490-503.

[8] 趙啟濰, 張樂, 祝貝利, 等.面向高維數(shù)據(jù)的LSH算法及應(yīng)用[J]. 福建電腦, 2012, 28(4): 13-14.

[9] Shao H, Svoboda T，Van Gool L. ZuBuD-Zurich buildings database for image based recognition[R]. Technical Report No.260, Zurich: Swiss Federal Institute of Technology, 2003.

[責(zé)任編輯 尚 晶]

An improved image retrieval method using random algorithms

LuYanjun,XuWangming

(College of Information Science and Engineering, Wuhan University of Science and Technology, Wuhan 430081, China)

An image retrieval method using random algorithms is proposed to improve the traditional local feature representation method which often needs a large amount of calculation during image feature extraction and similarity matching. For image feature extracting,the method adopts random sampling to obtain an appropriate number of image pixels as the feature points, then represents these random feature points with SIFT descriptors in order to form an effective image representation. For feature similarity matching, it applies a random mapping LSH algorithm to indexing the feature database and conducting the efficient approximate nearest neighbor query of image local features. Experimental results show that the proposed method can efficiently reduce the computation complexity and improve the image retrieval efficiency.

image retrieval; local feature; random sampling; feature indexing; scale invariant feature transform; locality sensitive hashing

2014-09-01

國家自然科學(xué)基金資助項(xiàng)目(61105058);武漢科技大學(xué)大學(xué)生科技創(chuàng)新基金研究項(xiàng)目(12ZRA109).

盧艷君(1988-),女,武漢科技大學(xué)碩士生. E-mail:1060146221@qq.com

徐望明(1979-),男,武漢科技大學(xué)高級工程師,博士. E-mail: xuwangming@wust.edu.cn

TP391.4

A

1674-3644(2015)01-0072-05