一種運用隨機算法改進的圖像檢索方法

盧艷君，徐望明

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

一種運用隨機算法改進的圖像檢索方法

盧艷君，徐望明

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

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

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

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

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

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

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

1 改進的圖像檢索系統工作原理

本文運用隨機算法改進的圖像檢索系統如圖1所示，系統可分為離線過程和在線過程兩部分。①離線過程，即對于圖像庫中的每幅圖像，系統事先離線運用特征提取算法，經特征檢測、特征描述兩步得到圖像特征向量，形成相應的圖像特征庫，然后在此基礎上建立特征索引以方便對查詢特征的快速搜索；②在線過程，即對于用戶提交的查詢圖像，系統運用相同的特征提取算法實時獲取圖像特征向量，然后通過適當的相似性搜索算法從特征庫中查找所有查詢圖像特征的近鄰特征，并通過對庫圖像投票的方式計算查詢圖像與庫圖像之間的相似度，按相似度從大到小的順序返回最相似的一組庫圖像作為圖像檢索結果。

為了評估圖像檢索性能，可根據返回的檢索結果和庫中真實結果做統計分析，計算出查準率、查全率及檢索效率等評價指標。其中，查全率是檢索出的相關圖像與圖像庫中相關圖像的比值，查準率是檢索出的相關圖像與檢索出的圖像總量的比值。

Fig.1 Improved image retrieval system using random algorithms

2 關鍵算法描述

2.1 隨機采樣SIFT

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

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

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

(1)取特征點周圍4×4的鄰域，利用此鄰域內像素點的梯度來統計方向直方圖，即以每10°方向為一個柱，柱所代表的方向為像素點梯度方向，柱的長度代表梯度幅值。對方向直方圖進行兩次平滑后的主峰值即為特征點的主方向。利用特征點鄰域像素的梯度方向分布特性，可以為每個特征點指定方向，從而使描述子對圖像旋轉具有不變性。設特征點(x,y)處的灰度值為g(x,y)，圖像梯度方向為θ(x,y)、幅值為M(x,y)，計算公式如下：

(1)

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

(2)

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

(3)

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

(3)在特征點周圍16×16鄰域窗口中，對各像素點根據坐標按加權平均歸入4×4的位置網格，每個網格構成一個種子點。

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

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

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

2.2 LSH算法

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

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

應用LSH算法為圖像特征庫建立索引的步驟為：

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

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

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

應用LSH算法對查詢圖像特征進行近似近鄰搜索的步驟為：

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

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

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

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

3 圖像檢索實驗及結果分析

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

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

在進行圖像特征提取實驗時，統計了對單幅圖像特征提取的平均數量和平均時間，以比較標準SIFT算法和本文采用的隨機采樣SIFT算法。實驗結果如表1所示。

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

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

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

采用不同的特征提取方法(標準SIFT、隨機采樣SIFT)和特征相似性匹配方法(線性掃描法、LSH算法)進行圖像檢索的實驗結果對比如表2所示。

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

4 結語

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

[1] 韋立梅, 蘇兵. 基于內容的圖像檢索技術綜述[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] 於慧, 謝萍, 李世進, 等. 基于多特征LSH索引的快速遙感圖像檢索[J]. 山西大學學報:自然科學版, 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] 趙啟濰, 張樂, 祝貝利, 等.面向高維數據的LSH算法及應用[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.

[責任編輯 尚 晶]

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

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

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

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

TP391.4

A

1674-3644(2015)01-0072-05