曹玉東，劉艷洋，孫福明，賈 旭

(遼寧工業(yè)大學電子與信息工程學院，遼寧 錦州 121001)

1 引言

為了提高圖像檢索速度，最好的辦法就是建立索引。眾多研究者已經給出了大量的索引方法，例如TBBF[1]、iDistanc[2]和R-tree[3]等都能在一定程度上克服維數(shù)災難，較好地解決了高維數(shù)據搜索問題。BBF保持kd-tree的二叉平衡樹索引結構不變，在數(shù)據搜索的回溯查詢階段，引入一個優(yōu)先查找隊列，極大地提高了kd-tree的查找性能。iDistance索引方法認為如果兩個高維向量相似，那么它們到某個參考點的距離也相似?；谠撍枷?，iDistance把特征集合聚類，每個分類被看作是一個以質心為中心的超球體，給定查詢點及其查詢半徑，通過三角不等式確定在各個類中的查詢范圍。R-tree把一個多維對象只分到一個子空間中，構成一棵平衡樹，隨后R-tree的變種也相繼出現(xiàn)，但是當特征維數(shù)高于10時，R-tree就會因為重疊超矩形空間和死區(qū)的大量存在而導致性能嚴重下降，甚至不如順序搜索(即將查詢點逐一同數(shù)據庫中所有的元素做比較，也稱為線性搜索或窮盡搜索)。前面提到的其它索引算法也不同程度地存在此問題。 局部敏感哈希LSH(Locality Sensitive Hashing)索引[4]則完全從另外一個角度建立索引結構，先將數(shù)據庫中的高維數(shù)據點投影到某個特征空間；然后從哈希函數(shù)簇中隨機選擇k個不同的哈希函數(shù)，將每個數(shù)據點映射為一個k維矢量， 相似的數(shù)據點可能會被量化為同一個k維矢量，這樣的數(shù)據點會散列到同一個哈希桶中，查詢時對輸入的數(shù)據點做相同的散列，窮舉搜索與查詢點發(fā)生沖突的桶，將會以較大的概率得到查詢點的近鄰。為避免邊界的影響，增加找到真實近鄰的概率，可以重復以上操作幾次。實驗數(shù)據表明，LSH算法無論是在匹配速度還是匹配精度上，都具有明顯的優(yōu)勢[5]?，F(xiàn)在LSH算法已經成功地應用到圖像檢索[6]、音頻檢索[7]和文本檢索[8]等領域。

國內一些研究人員也提出了一些改進的LSH算法，如文獻[9]利用數(shù)據集的統(tǒng)計特性運用迭代的方法從隨機生成的若干哈希函數(shù)中選擇出更合適的哈希函數(shù)，從而提高了LSH算法的性能，但其離線訓練時間明顯增加。文獻[10]提出了多次隨機子向量量化哈希算法，根據隨機抽取的特征子向量構建哈希函數(shù)，但是其實驗僅僅在包含大約一萬幅圖像的數(shù)據庫上進行。計算技術的進步導致海量數(shù)據出現(xiàn)在因特網上，本文旨在降低標準LSH算法的空間復雜度，使用較少數(shù)量的哈希表構造高維數(shù)據的索引結構，同時不降低算法的性能，這對大規(guī)模的高維數(shù)據搜索任務是有意義的。

2 圖像的特征提取

表達圖像的原始數(shù)據往往是龐大和無序的，通常只考慮了存儲和傳輸?shù)囊?，為了挖掘隱藏在圖像原始數(shù)據中的規(guī)律性特征和本質性特征，需要在圖像的內容層次設計圖像特征的表達方法，常見的圖像特征表示方法可以分為兩種，一是基于特征袋(Bag of Features)表示[11]，另一個是使用全局描述算子表示。特征袋表示法一般用若干局部特征構成的集合來表示圖像，適合使用倒排文檔索引組織數(shù)據；圖像的全局特征通常是一個高維矢量。本文使用Gist特征[12](全局描述算子的一種)表示圖像。文獻[13]指出圖像的Gist特征已經在圖像檢索應用中取得了很好的效果。Gist特征描述了一系列感知維度，包括自然度(Naturalness)、開放度(Openness)、粗糙度(Roughness)、擴展度(Expansion)和光滑度(Ruggedness)。這些感知維度代表了場景的空間結構，可以通過譜變換和粗略的局部定位信息估計出來。令圖像通過一組Gabor濾波器(在三個尺度上的方向數(shù)分別是2、4、4)，將圖像分成2×2個無重疊的窗口，在每個窗口中提取出方向柱狀圖，這樣每幅圖像用(2+4+4)×4=40維的Gist特征來表示。

3 LSH算法

LSH算法的基本思想就是用隨機的哈希函數(shù)值保證相似的數(shù)據點以很高的概率發(fā)生沖突而能夠被檢測到[4]。哈希函數(shù)是單向的散列函數(shù)，它將目標的表示映射為更簡單的形式，在LSH算法中，哈希函數(shù)滿足:

Prh∈H[h(u)=h(v)]=sim(u,v)

(1)

其中，H是哈希函數(shù)簇，哈希函數(shù)h從H中均勻地選取，把一個向量映射為一個數(shù)，u和v是兩個高維的數(shù)據點，sim(u,v)∈[0,1]是相似度函數(shù)。

給定一個查詢點，LSH算法能夠在遠小于窮舉搜索的時間內搜索到近似近鄰。尤其在數(shù)據庫的規(guī)模很大的時候，其優(yōu)勢十分明顯。

3.1 算法描述

標準LSH索引高維數(shù)據的過程如下所述，使用哈希函數(shù)把數(shù)據庫中的矢量點投影到隨機的方向矢量ai上。ai的每個元素服從p-穩(wěn)定分布(當p=2時是標準高斯分布)。

哈希函數(shù)定義為：

(2)

其中，w是投影的量化寬度;b的取值服從[0,w]的均勻分布,參數(shù)b增強了哈希函數(shù)的隨機性，可能有利于消除哈希桶邊界的影響。內積ai·p就是數(shù)據點p在ai上的投影。經過取整操作，哈希函數(shù)的值被量化為一個整數(shù)。單個哈希函數(shù)的區(qū)分性較弱，因此需要構建第二級哈希函數(shù)，它也被稱為局部敏感哈希函數(shù)LSH，其形式為：

gj(p)={hj,1(p),…,hj,k(p)},j=1,…,l

(3)

其中，k的值遠遠小于數(shù)據點的維數(shù)，由k個整數(shù)構成的矢量也被稱為哈希碼，它可以看作是數(shù)據點p的降維表示。每一個gi對應一個哈希表，高維數(shù)據點經過gi映射為k維哈希碼，具有相同哈希碼值的數(shù)據點將被散列到同一個桶中[14],每個哈希表都包含若干個桶。如圖1所示，通過投影和量化操作，數(shù)據點p被索引到哈希表中的某一個桶內，每個哈希表都包含了數(shù)據庫中所有的點。使用多個哈希表的目的是為了增加找到真正近鄰的概率，消除哈希桶邊界的影響。余下的操作就是如何實現(xiàn)哈希表的壓縮存儲，同時盡量減少不相似的數(shù)據點發(fā)生沖突，詳細的描述可以查閱文獻[15]。

Figure 1 Indexing data in LSH algorithm[16]圖1 LSH算法索引數(shù)據的過程[16]

在查詢階段，查詢數(shù)據點q以同樣的方式被散列到l個哈希表中。在每個哈希表中和查詢點q位于同一個桶內的數(shù)據點可能是近鄰而被返回，所有的返回數(shù)據點構成一個短列表(short-list)，short-list包含的數(shù)據量遠遠小于數(shù)據庫中所有元素的數(shù)量，順序搜索short-list中的數(shù)據點，得到查詢數(shù)據的近鄰。

3.2 算法分析

LSH算法[4]沒有考慮數(shù)據的分布結構，哈希函數(shù)是基于p-穩(wěn)態(tài)分布隨機生成的，所以為了提高算法的性能，就必須提高哈希表的數(shù)量l和第二級哈希函數(shù)的長度k。參數(shù)l越大，找到近鄰的可能性就越大，但是查詢時間會變長，內存的使用量也會增加。參數(shù)k越大，二級哈希函數(shù)的值越能準確地反映公式(1)中相似度的值，當然如果k取較小的值，散列操作會變得更快。

4 LSH算法的改進

空間復雜度可以用哈希表的個數(shù)來表示，或者用內存總的使用情況來衡量[8]。改進后的算法I-LSH可以使用較少的哈希表就能達到較好的查詢效果，性能和順序搜索相當，將I-LSH用于副本圖像檢索任務。在不降低或不顯著降低算法性能的前提下，減少哈希表的數(shù)量能有效地降低算法的空間復雜度。設計合理的哈希函數(shù)能實現(xiàn)這個目標，實質就是確定哈希函數(shù)的投影方向ai。

借鑒模式識別中主成份分析PCA(Principal Component Analysis)的思想，將哈希函數(shù)投影方向的生成過程歸納如下：

(1)從數(shù)據庫中均勻、隨機選出m個數(shù)據點，構造為集合{p1,p2,…,pm}，計算該集合的協(xié)方差矩陣:

(4)

(2) 排序該協(xié)方差矩陣∑的特征值，對應的特征向量為v1,v2,…,vn。

新的哈希函數(shù)增加了對數(shù)據的區(qū)分性，能使數(shù)據點更均勻地分布到哈希桶中，落入同一個桶中的數(shù)據點的相似性大大增加了。在計算能力容許的前提下，應選擇較大的m值，這樣得到的哈希函數(shù)會更適合索引當前數(shù)據集。

5 實驗仿真與結果

5.1 數(shù)據集的建立

實驗采用了文獻[17]提供的一個圖像評價集，它包括兩個真實圖像集和一個人為編輯過的圖像集(Dark Knight, The Lord of The Rings, Flickr)。在Flickr數(shù)據集中，通過12種不同的方法編輯每一幅原始圖像得到12幅近似圖像，這12種編輯方法是圖像模糊、亮度變化、存儲格式改變、顏色變化、顏色增強、對比度變化、壓縮、剪切、在圖像中增加標識(Adding Logo)、分辨率改變、縮放和以上多種方法的聯(lián)合使用。文獻[16]給出了更詳細的描述。同時又搜集了若干的網絡圖像，通過隨機采樣構建大小不同的“迷惑圖像”集混合到評價集中，實驗分別在六個規(guī)模不同的數(shù)據集上進行，使用40維的Gist表示每一幅圖像，最小的數(shù)據集包含四千幅圖像，最大的數(shù)據集包含七萬幅圖像。

5.2 評價測度

圖像檢索任務的評價測度很多，常見的評價測度包括查準率Precision、查全率Recall、均值平均精度mAP(mean Average Precision)等。給定一幅查詢圖像，系統(tǒng)返回的結果可以被標記為如下四種類型：正確的正樣本TP(True Positive)、錯誤的正樣本FP(False Positive)、正確的負樣本TN(True Negative)、錯誤的負樣本FN(Flase Negative)。TP的含義是系統(tǒng)將返回結果判定為相關圖像，實際也如此；FP的含義是系統(tǒng)將返回結果判定為相關圖像，實際上返回結果與查詢圖像卻是不相關的；TN的含義是系統(tǒng)將返回結果判定為不相關的圖像，實際上返回結果與查詢圖像也確實是不相關的；FN的含義是系統(tǒng)將返回結果判定為不相關圖像，實際上返回結果與查詢圖像卻是相關的。Precision和Recall的計算公式定義為：

(5)

其中符號#表示樣本的數(shù)量，#TP與#FN的和是數(shù)據庫中所有相關樣本的數(shù)量。如果系統(tǒng)對查詢結果做了排序，然后從第一幅圖像開始依次對這個排序表進行檢查，可以計算出若干組對應的Precision和Recall的值，進而繪制查準率/查全率曲線(P-R curve)。

Figure 3 Comparison of query results exhaustive search, LSH and I-LSH圖3 窮盡搜索、LSH和I-LSH方法的查詢結果比較

作為圖像檢索的評價測度，mAP已經被廣泛使用[13,18]。輸入一幅查詢圖像，可以計算和繪制它的精度-召回率曲線(Precision-Recall Curve)，精度-召回率曲線下的面積值被定義為平均精度AP(Average Precision)。給定一組查詢，可以獲得一組平均精度，它們的平均值就被稱為mAP。

5.3 實驗結果和分析

實驗中對short-list的排序使用了2范數(shù)距離測度。圖2給出了順序搜索算法、I-LSH算法和LSH算法[4]的比較結果，為了比較算法的性能，LSH算法和I-LSH參數(shù)取值均為l=5,k=3,w=0.1。 可以看出,在空間復雜度相同的情況下，改進后的算法I-LSH的性能比標準LSH要好很多，而且十分接近窮盡搜索的結果。窮盡搜索是LSH算法的極限情況(一個哈希表只包含一個哈希桶)，所以窮盡搜索的結果可以被看作理想的參照基準。由圖2可以看到，當l的值較低時，LSH算法還表現(xiàn)出隨意性。在圖3中第1行是隨機選擇的一幅查詢圖像，第2行是窮盡搜算法返回的相關圖像，第3行是LSH算法返回的相關圖像，第4行是I-LSH算法返回的相關圖像。圖4～圖6是三種算法對應的查準率-查全率曲線圖。

Figure 2 Comparison of mAP among exhaustive search, LSH and I-LSH圖2 窮盡搜索、LSH和I-LSH方法的mAP性能比較

Figure 4 Curve of Precision-Recall of LSH圖4 LSH算法的查準率-查全率曲線圖

Figure 5 Curve of Precision-Recall of I-LSH圖5 I-LSH算法的查準率-查全率曲線圖

Figure 6 Curve of Precision-Recall of exhaustive search圖6 窮盡搜索算法的查準率-查全率曲線圖

6 結束語

本文改進了LSH算法，該算法不需要有標記的樣本，僅僅利用數(shù)據的分布信息構造投影方向，使生成的哈希函數(shù)更適合目標數(shù)據庫。實驗結果表明，改進的LSH算法有效地降低了內存的使用量，性能也相當接近窮盡搜索算法。

[1] Lowe D G. Distinctive image features from scale invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2):91-110.

[2] Jagadish H V, Ooi Beng Chin, Tan Kian-Lee, et al. iDistance:An adaptive B+-tree based indexing method for nearest neighbor search[J]. ACM Transactions on Data Base Systems, 2005, 30(2):364-397.

[3] Guttman A. R-Trees：A dynamic index structure for spatial searching[C]∥Proc of ACM SIGMOD International Conference on Management of Data, 1984:47-57.

[4] Datar M, Immorlica N, Indyk P. Locality sensitive hashing scheme based onp-stable distributions[C]∥Proc of Symposium on Computational Geometry, 2004:253-262.

[5] He Zhou-can, Wang Qing, Yang Heng. An extended local sensitivity Hash algorithm for feature correspondence and image matching[J]. Journal of Sichuan University, 2010, 47(2):269-274.(in Chinese)

[6] Kullis B, Grauman K. Kernelized locality sensitive Hashing for scalable image search[C]∥Proc of ICCV, 2009:2130-2137.

[7] Ryynanen M, Klapur A. Query by humming of midi and audio using locality sensitive hashing[C]∥Proc of ICASSP, 2008:1.

[8] Cai Heng, Li Zhou-jun, Sun Jian, et al. Fast image retrieval based on LSH indexing[J]. Computer Science， 2009, 36 (8):201-204.(in Chinese)

[9] Lu Yan-sheng, Rao Qi. A self-tuning method of LSH index[J]. Journal of Huazhong University of Science and Technology, 2006, 34(11):38-40.(in Chinese)

[10] Yang Heng, Wang Qing, He Zhou-can. Multiple randomized sub-vectors quantization hashing for high-dimensional image feature matching[J]. Journal of Computer-Aided Design & Computer Graphics, 2010, 22(3):409-502.(in Chinese)

[11] Cao Y D, Zhang H G, Guo J. Matching image with multiple local features[C]∥Proc of ICPR,2010:519-522.

[12] Oliva A,Torralba A.Modeling the shape of the scene:A holistic representation of the spatial envelope[J]. International Journal of Computer Vision, 2001, 42(3)：145-175.

[13] Douze M, Jegou H, Sandhawalia H. Evaluation of GIST descriptors for web-scale image search[C]∥Proc of CIVR, 2009,DOI:10.1111511646396.1646421.

[14] Ma Ru-lin, Jiang Hua, Zhang Qing-xia. An improved fast searching method of hash table[J]. Computer Engineering & Science, 2008, 30(9)：66-68.(in Chinese)

[15] Shakhnarovich G,Darrell T,Indyk P.Nearest-neighbor methods in learning and vision:Theory and practice[M]. Cambridge:MIT Press, 2006.

[16] Cao Yu-dong, Liu Fu-ying, Cai Xi-biao. Research on high dimension image data indexing technology based on locality sensitive hashing algorithm[J]. Journal of Liaoning University of Technology, 2013, 33(1)：1-4.(in Chinese)

[17] Kim H, Chang H W, Lee J. BASIL:Effective near-duplicate image detection using gene sequence alignment[C]∥Proc of ECIR, 2010:229-240.

[18] Philbin J, Chum O, Isard M, et al. Object retrieval with large vocabularies and fast spatial matching[C]∥Proc of CVPR, 2007,DOI:10.1109/CVPR.2007.383172.

附中文參考文獻：

[5] 何周燦, 王慶, 楊恒. 一種面向快速圖像匹配的擴展LSH算法[J]. 四川大學學報, 2010, 47(2):269-274.

[8] 蔡衡, 李舟軍, 孫健，等. 基于LSH的中文文本快速檢索[J]. 計算機科學, 2009, 36 (8):201-204.

[9] 盧炎生, 饒祺. 一種LSH 索引的自動參數(shù)調整方法[J]. 華中科技大學學報, 2006, 34(11):38-40.

[10] 楊恒, 王慶, 何周燦. 面向高維圖像特征匹配的多次隨機子向量量化哈希算法[J]. 計算機輔助設計與圖形學學報, 2010, 22(3):409-502.

[14] 馬如林, 蔣華, 張慶霞. 一種哈希表快速查找的改進方法[J]. 計算機工程與科學, 2008, 30(9):66-68.

[16] 曹玉東, 劉福英, 蔡希彪. 基于局部敏感哈希算法的圖像高維數(shù)據索引技術的研究[J]. 遼寧工業(yè)大學學報, 2013, 33(1)：1-4.