王秀美，丁利杰，高新波

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

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

王秀美，丁利杰，高新波

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

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

相似最近鄰搜索；哈希；相關(guān)性預測函數(shù)；查準率；查全率

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

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

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

1 線性嵌入哈希

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

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

為了表征圖像數(shù)據(jù)與編碼的相關(guān)性關(guān)系，受文獻［13］啟發(fā)，提出相關(guān)性預測函數(shù)模型，即

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

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

對于通過式（2）去學習最優(yōu)的權(quán)重W，為了保證相關(guān)對（x，b1）的相關(guān)性大于不相關(guān)對（x，b2）的相關(guān)性，即要使得x W（b1）T＞x W（b2）T，引入邊界損失函數(shù)，即

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

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

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

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

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

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

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

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

FOR i=1 to N

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

（2）通過式（2），計算樣本圖像數(shù)據(jù)x與其對應(yīng)的正項b1之間的相關(guān)性預測數(shù)f（x，b1）；

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

END FOR

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

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

2 實驗結(jié)果與分析

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

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

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

2.1LabelMe實驗結(jié)果

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

圖1　Label Me結(jié)果曲線

2.2ClFAR10實驗結(jié)果

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

圖2　CIFAR10結(jié)果曲線圖

3 結(jié)束語

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

［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，F(xiàn)ERGUS 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.機器學習實戰(zhàn)［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 網(wǎng)絡(luò)出版時間：2015-04-14

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

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

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.014.html