一種相似性保持的線性嵌入哈希方法

王秀美，丁利杰，高新波

（西安電子科技大學電子工程學院，陜西西安 710071）

一種相似性保持的線性嵌入哈希方法

王秀美，丁利杰，高新波

（西安電子科技大學電子工程學院，陜西西安 710071）

在圖像檢索技術中，針對高維特性海量的圖像數據檢索速度慢、數據存儲容量大及圖像和其哈希編碼之間相關性差的缺點，將相關性預測函數引入到哈希算法中，提出了一種相似性保持的線性嵌入哈希方法.該方法利用相關性預測函數保持高維數據與其編碼之間的鄰近關系，使邊界損失代價最小化，構建線性哈希映射矩陣，獲得緊致的哈希編碼，提高了圖像與編碼間的相關性，實現了高精度的圖像檢索.通過與現存經典的哈希算法相對比，實驗結果驗證了線性嵌入哈希方法在查全率和查準率上的有效性.

相似最近鄰搜索；哈希；相關性預測函數；查準率；查全率

近年來，隨著互聯網、云計算、移動設備和物聯網的迅猛發展，全球數據量進入ZB時代，并且每年仍以指數級形式增長.如何高效收集、存儲、分析處理、可視化展示并利用大數據獲得效益成為現今的熱點研究問題.在大數據處理檢索技術中，相似最近鄰搜索技術［1］被廣泛應用，如基于內容的圖像檢索、目標識別以及分類等.

一些經典的哈希方法已經被提出用于相似最近鄰搜索和圖像查詢.最早提出的較為經典的哈希算法是局部敏感哈希算法（Locality-Sensitive Hashing，LSH）［3］，該方法是對圖像數據進行隨機映射來構建隨機哈希函數，可以使得相似的圖像數據映射后的編碼有較高的幾率落在同一哈希桶中.但是這種方法需要長編碼來保持數據的相似性.之后一系列基于學習的哈希方法被提出來，如基于圖構建獲得哈希函數的方法——有譜哈希（Spectral Hashing，SH）［2］，它是通過無向圖構建獲得圖像數據之間相似度關系，最終通過譜圖理論求解相似度矩陣特征值與特征函數問題獲得哈希函數.另外，基于主成分分析方法的哈希算法［4］和迭代量化哈希算法（ITerative Quantization，ITQ）［5］是通過學習，不斷地減少量化誤差得到哈希函數.最近，積量化方法被應用到哈希中.如文獻［6］提出一種將高維空間數據分解到低維空間，通過最小化與空間分解和碼書相關的量化失真，獲得有效的哈希編碼.文獻［7］使用K均值［8-9］量化分離的特征空間獲得每個簇的標識索引，通過計算索引的漢明距離來估計原始空間的歐式距離.積量化用于哈希雖然能夠得到有效的檢索性能，但是優化過程困難.為了保持輸入數據之間的局部結構，文獻［10］提出了一種非參數流形學習的非線性嵌入方法，通過數據流形間的幾何結構獲得緊致的哈希代碼.為了利用類標信息或數據間的相似度提高檢索精度，人們提出了基于核函數的哈希方法（Supervised Hashing with Kernels，KSH）［11］.基于核的哈希方法是利用在優化代碼內積和漢明距離的等值性來優化哈希函數.為了處理監督信息不足的問題，半監督學習技術被引入到哈希算法中，半監督哈希算法（Semi-Supervised Hashing，SSH）［12］通過最小化有標簽數據和無標簽數據的經驗損失正則項優化哈希函數.

一方面，監督信息是非常有限的；另一方面，監督信息的獲取需要大量的人力物力.因此，無監督哈希方法越來越受到人們的重視.但一些現存的無監督哈希方法都是在一定的限制條件下優化目標函數，限制條件勢必使得哈希方法的普及性和性能受到影響.如基于圖構建的無監督哈希方法［2］是假設數據分布或近鄰結構已知條件下獲得目標函數的近似結果.另外，很多無監督哈希方法不適應長哈希碼情況，如基于主成分分析方法的哈希算法（Principal Component Analysis Hashing，PCAH）和迭代量化哈希算法的查準率和查全率隨著哈希碼長度增加而變化不明顯.針對以上的問題，筆者提出一種線性無監督哈希方法，該算法在實現中沒有過多條件限制.而且它是基于線性嵌入模型，通過該模型能夠獲得圖像數據與其對應哈希碼的相關性表征，展示圖像數據與哈希碼之間的內在聯系.用這種相關性聯系去學習哈希函數，能使得該算法性能隨著哈希碼位數提高而變優.

1 線性嵌入哈希

假設給定一個包含n個d維數據點的數據集X=［x1，x2，…，xn］∈Rd×n，yi∈｛1，-1｝c，i=1，2，…，n，表示高維圖像數據xi所對應的哈希碼，設哈希映射函數H（x）=｛hk（x）｝ck=1，并且獲得哈希碼表Y=［y1，y2，…，yn］∈｛1，-1｝c×n，能夠保存數據的相似度信息，其中c為哈希碼的長度.哈希函數通過閾值化得到，即對于每一位哈希碼，哈希編碼函數被定義為

其中，wk是超平面參數的列向量，W∈Rc×n，W是列向量wk組成的矩陣.閾值化編碼一般是通過符號函數y（x）=sgn（v）（如果v＞0，那么，y=1；否則，y=-1）獲得，那么整個訓練數據的編碼過程為Y= sgn（WX）.

為了表征圖像數據與編碼的相關性關系，受文獻［13］啟發，提出相關性預測函數模型，即

該函數返回一個可以估計圖像數據x與編碼b1之間相關性的值.假設圖像數據x與編碼串b1之間的相關性高于圖像數據x與編碼串b2之間的相關性，那么得到的相關性預測函數值f（x，b1）＞f（x，b2）.

線性嵌入哈希算法沒有任何監督信息，為獲得預設的哈希編碼，首先運用K均值聚類，得到k個聚類中心C=［c1，c2，…，ck］T∈Rk×d，然后，把初始的模型參數矩陣與聚類中心的乘積φi（C，W）=CW進行閾值化處理得到預設編碼B=［b1，b2，…，bk］T∈Rk×c.預設編碼列bi∈｛1，-1｝c，i=1，2，…，k的第i編碼行的第j個元素bij為1時，對應的φij必為正數；反之，bij為-1時，對應的φij必為負數.從而可得某一圖像數據x和其相關的預設編碼b1所對應的相關性預測函數的返回值高，圖像數據x和其不相關的預設編碼b2之間的相關性預測函數的返回值小.進而保證在原始空間中相近的圖像數據點映射到漢明空間后所對應的漢明距離接近.

對于通過式（2）去學習最優的權重W，為了保證相關對（x，b1）的相關性大于不相關對（x，b2）的相關性，即要使得x W（b1）T＞x W（b2）T，引入邊界損失函數，即

其中，γ≥0是測試函數邊界，Bx表示圖像數據x的相關預設編碼集.分析上式可知，只有滿足條件x Wbj＞γ+x Wbk時，才能使得某一圖像數據x與它的相關預設編碼和不相關預設編碼之間的邊界損失為0，進而保證最終邊界損失函數達到最小.在邊界損失函數達到最小時，同時保證了相關對（x，bj）之間的相關性高于不相關對（x，bk）之間的相關性.運用梯度下降算法去優化邊界損失函數，在每次迭代中，隨機選擇一個圖像數據相關對，然后對此圖像數據不相關點去做一次梯度分析.在訓練線性嵌入模型時，選擇最小化訓練誤差的固定學習步長為λ，用N（0，1）高斯分布初始化訓練模型參數W.

線性嵌入哈希算法步驟如下:

輸入:一個訓練樣本集X=｛xi∈Rd｝in=1，哈希編碼位數為c，聚類數目k.

初始化:模型參數W（用均值為0、方差為1的高斯分布），損失函數邊界γ，隨機梯度下降學習步長λ，循環迭代次數N.

第1步 K均值聚類.對訓練樣本數據集進行K均值聚類，得到樣本數據集的k個聚類中心，并存儲每個簇中各樣本對應類別標號.

第二，基準站。基準站的作用是完成了數據的接收、處理和生成這些流程，對于后續工作起到推進的作用。與此同時，還能減少工作人員獲取到控制點時的處理難度，基準站可以直接記錄點位數據，避免了人工操作可能出現的失誤。另外，在實際應用中，人們可以利用偽距差分技術導航位點數據，且極為精準，一般誤差不超過五米。[1]同時，測繪更新的時效性也給人們的出行定位帶來了便利，工作人員可以在一定的時間范圍內將測得的數據信息上傳，經過整合處理后生成三維坐標，相比于傳統的測繪技術耗時少且流程簡單。

第2步 線性映射得到預設碼表.對所得到的k個聚類中心線性映射到低維的漢明空間，得到聚類中心所對應的預設碼表，并且把預設碼表中的每一個碼行作為所對應類中各樣本的正項預設編碼，其他碼行則作為這個類中各樣本的負項預設編碼.

第3步 模型訓練過程.步驟如下:

FOR i=1 to N

（1）在訓練樣本集中隨機選擇一個樣本圖像數據x，對于樣本數據x，找到它所對應的類別標號，并通過類別標號，選擇它對應的正項b1∈Bx；

（2）通過式（2），計算樣本圖像數據x與其對應的正項b1之間的相關性預測數f（x，b1）；

（4）如果f（x，b1）＜f（x，b2）+γ，那么運用隨機梯度下降方法進行一次梯度步驟最小化邊界損失函數: max（0，γ+f（x，b2）-f（x，b1）），去優化模型參數W，然后，繼續跳到步驟（1），進行迭代循環.

END FOR

第4步 閾值化編碼.模型訓練后得到最優的模型參數W，然后通過式（1），將訓練樣本進行閾值化得到哈希編碼codec（xi）←［h1（xi），…，hc（xi）］.

輸出:n個哈希編碼H=｛codec（xi）｝in=1.

2 實驗結果與分析

測試提出的線性嵌入哈希（Linear Embedded Hashing，LEH）算法對相似最近鄰查詢的有效性，在Label Me和CIFAR10兩個圖像數據庫上進行評估.CIFAR10數據庫是8千萬個小圖像的子集，它包含60 000個32×32彩色圖像，總共分為10類，每類有6 000個圖像樣本.Label Me數據庫是多標簽數據庫，包含22 000個圖像，在數據庫中，每個圖像都是由一個512維的GIST特征矢量所代表.

對比線性嵌入哈希算法，使用了現今比較成熟的無監督哈希方法.它們分別是譜哈希方法、平移不變核局部敏感哈希方法［14］、迭代量化、基于主成分分析的哈希方法.

實驗過程中，從CIFAR10、Label Me兩個數據集中選擇5 000個數據點，并把每個數據集分為兩部分，4 000數據點作為訓練集，另外1 000數據點作為測試集.畫出數據點檢索的查準率-查全率曲線和平均準確率曲線（MAP）等分別去評估圖像檢索性能.其中，查準率為在某具體漢明距離中查詢到的與查詢點相關的圖像數據個數和此漢明距離中所有的圖像數據點個數之比.查全率為在某具體漢明距離中查詢到的與查詢點相關的圖像數據個數和整個數據集中與查詢點相關的全部圖像數據個數之比.

2.1LabelMe實驗結果

在Label Me數據集上得到的實驗結果曲線如圖1所示，圖1（a）和圖1（b）為Label Me數據庫下各哈希函數在哈希碼為32位、64位下查準率-查全率曲線.從圖中可知，線性嵌入哈希方法（LEH）的查準率-查全率比迭代量化（ITQ）增加將近18%.并且譜哈希（SH）、迭代量化（ITQ）、PCAH這3種哈希方法查準率-查全率隨哈希編碼長度變化不明顯.平移不變核局部敏感哈希方法（SKLSH）的查準率-查全率隨著哈希編碼長度變長而變的更優，但仍低于迭代量化（ITQ）.圖1（c）為平均準確率曲線，從圖中可知，一定的哈希碼長度范圍，線性嵌入哈希方法（LEH）的平均準確率（MAP）優于其他哈希方法的，并且平均準確率隨位數的增加而增加.

圖1　Label Me結果曲線

2.2ClFAR10實驗結果

圖2為CIFAR10數據庫下各哈希函數分別在48位、64位下查準率-查全率曲線和平均準確率曲線.由圖2可看到，線性嵌入哈希方法在各哈希代碼長度下的查準率-查全率優于其他所有的哈希方法.在高于一定的哈希碼位數下，平均準確率（MAP）優于其他哈希方法的，并且平均準確率隨位數的增加而增加.另外，對于譜哈希、迭代量化、PCAH這3種哈希方法性能隨哈希編碼長度變化性不明顯.平移不變核局部敏感哈希方法和線性嵌入哈希方法的性能隨著哈希編碼長度變長而變的更優.但是平移不變核局部敏感哈希方法在代碼很長時性能仍舊低于迭代量化，所以，這種方法如果要達到好的精確度必須增加哈希代碼長度，增加代碼長度會造成存儲空間的增大與查全率的下降.對于線性嵌入哈希方法，在較短的哈希碼長度下，已經達到比較好地效果.

圖2　CIFAR10結果曲線圖

3 結束語

筆者提出了一種相似性保持的線性嵌入哈希方法，并對其基本思想、實現步驟進行了敘述和分析.在不同數據集上的實驗結果顯示，線性嵌入哈希方法的性能隨著哈希碼的長度增加而變優.在哈希碼高于一定長度，線性嵌入哈希方法的性能優于現存的經典的無監督哈希算法的性能.但是該方法在較短的哈希碼長度內，其性能達不到理想的效果，這是由于初始化過程中預設編碼無法充分表征原始圖像數據間的相似性關系所致.該方法對于大代碼長度圖像檢索問題是有效的，并提供了一種解決相似最近鄰搜索問題的實用而有效的方案.

［1］INDYK P，MOTWANI R.Approximate Nearest Neighbors:Towards Removing The Curse Of Dimensionality［C］// Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing.New York:ACM，1998:604-613.

［2］WEISS Y，TORRALBA A，FERGUS R.Spectral Hashing［C］//Proceedings of the Conference on Advances in Neural Information Processing Systems.New York:NIPS，2009:1753-1760.

［3］DATAR M，IMMORLICA N，INDYK P，et al.Locality-sensitive Hashing Scheme Based on p-stable Distributions ［C］//Proceedings of the Twentieth Annual Symposium On Computational Geometry.New York:ACM，2004:253-262.

［4］WANG X J，ZHANG L，JING F，et al.Annosearch:Image Auto-annotation by Search［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2006: 1483-1490.

［5］GONG Y，LAZEBNIK S.Iterative Quantization:a Procrustean Approach to Learning Binary Codes［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2011:817-824.

［6］GE T，HE K，KE Q，et al.Optimized Product Quantization for Approximate Nearest Neighbor Search［C］// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2013:2946-2953.

［7］HE K，WEN F，SUN J.K-means Hashing:an Affinity-preserving Quantization Method for Learning Binary Compact Codes［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2013:2938-2945.

［8］HARRINGTON P.機器學習實戰［M］.李銳，李鵬，曲亞東，譯.北京:人民郵電出版社，2013:184-199.

［9］伍忠東，高新波，謝維信.基于核方法的模糊聚類方法［J］.西安電子科技大學學報，2004，31（4）:533-537. WU Zhongdong，GAO Xinbo，XIE Weixin.A Study of a New Fuzzy Clustering Algorithm Based on the Kernel Method ［J］.Journal of Xidian University，2004，31（4）:533-537.

［10］SHEN F，SHEN C，SHI Q，et al.Inductive Hashing on Manifolds［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2013:1562-1569.

［11］WANG J，KUMAR S，CHANG S F.Semi-supervised Hashing for Large-scale Search［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（12）:2393-2406.

［12］LIU W，WANG J，JI R，et al.Supervised Hashing with Kernels［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2012:2074-2081.

［13］WESTON J，WEISS R，YEE H.Affinity Weighted Embedding［C］//Proceedings of the International Conference on Machine Learning.Washington:International Machine Learning Society，2014:2958-2966.

［14］RAGINSKY M，LAZEBNIK S.Locality-sensitive Binary Codes from Shift-invariant Kernels［C］//Proceedings of the Conference on Advances in Neural Information Processing Systems.New York:NIPS，2009:1509-1517.

（編輯:王 瑞）

Linear embedding Hashing method in preserving similarity

WANG Xiumei，DING Lijie，GAO Xinbo
（School of Electronic Engineering，Xidian Univ.，Xi’an 710071，China）

In order to implement quick and effective search，save the storage space and improve the poor performance of affinity relationshaps between high dimensional data and its codes in image retrieval，a new linear embedding hashing is proposed by introducing the preserving similarity.First，the whole data set is clustered into several classes，and then the similarity predicted function is used to maintain affinity relationships between high dimensional data and its codes so as to establish the objective function.By minimizing the margin loss function，the optimal embedded matrix can be obtained.Compared with the existing classic hashing algorithm，experimental results show that the performance of the linear embedding hash algorithm is superior to the other binary encoding strategy on precision and recall.

approximate nearest neighbor search；hashing；similarity predicted function；precision；recall

TP391

A

1001-2400（2016）01-0094-05

10.3969/j.issn.1001-2400.2016.01.017

2014-09-26 網絡出版時間：2015-04-14

國家杰出青年科學基金資助項目（61125204）；國家自然科學基金重點資助項目（61432014）；國家自然科學基金資助項目（6147230）；國家自然科學基金青年基金資助項目（61100158）

王秀美（1978-），女，副教授，博士，E-mail:wangxm@xidian.edu.cn.

網絡出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.014.html