低空間復雜度的LSH算法及其在圖像檢索中的應用*

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

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

1 引言

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

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

2 圖像的特征提取

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

3 LSH算法

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

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

(1)

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

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

3.1 算法描述

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

哈希函數定義為：

(2)

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

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

(3)

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

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

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

3.2 算法分析

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

4 LSH算法的改進

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

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

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

(4)

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

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

5 實驗仿真與結果

5.1 數據集的建立

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

5.2 評價測度

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

(5)

其中符號#表示樣本的數量，#TP與#FN的和是數據庫中所有相關樣本的數量。如果系統對查詢結果做了排序，然后從第一幅圖像開始依次對這個排序表進行檢查，可以計算出若干組對應的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范數距離測度。圖2給出了順序搜索算法、I-LSH算法和LSH算法[4]的比較結果，為了比較算法的性能，LSH算法和I-LSH參數取值均為l=5,k=3,w=0.1。 可以看出,在空間復雜度相同的情況下，改進后的算法I-LSH的性能比標準LSH要好很多，而且十分接近窮盡搜索的結果。窮盡搜索是LSH算法的極限情況(一個哈希表只包含一個哈希桶)，所以窮盡搜索的結果可以被看作理想的參照基準。由圖2可以看到，當l的值較低時，LSH算法還表現出隨意性。在圖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算法，該算法不需要有標記的樣本，僅僅利用數據的分布信息構造投影方向，使生成的哈希函數更適合目標數據庫。實驗結果表明，改進的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 索引的自動參數調整方法[J]. 華中科技大學學報, 2006, 34(11):38-40.

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

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

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