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

王秀美，丁利杰，高新波

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

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

王秀美，丁利杰，高新波

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

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

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

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

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

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

1 線性嵌入哈希

假設(shè)給定一個(gè)包含n個(gè)d維數(shù)據(jù)點(diǎn)的數(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）獲得，那么整個(gè)訓(xùn)練數(shù)據(jù)的編碼過程為Y= sgn（WX）.

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

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

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

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

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

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

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

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

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

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

第3步 模型訓(xùn)練過程.步驟如下:

FOR i=1 to N

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

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

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

END FOR

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

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

2.1LabelMe實(shí)驗(yàn)結(jié)果

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

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

2.2ClFAR10實(shí)驗(yàn)結(jié)果

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

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

3 結(jié)束語

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

［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.機(jī)器學(xué)習(xí)實(shí)戰(zhàn)［M］.李銳，李鵬，曲亞東，譯.北京:人民郵電出版社，2013:184-199.

［9］伍忠東，高新波，謝維信.基于核方法的模糊聚類方法［J］.西安電子科技大學(xué)學(xué)報(bào)，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ò)出版時(shí)間：2015-04-14

國家杰出青年科學(xué)基金資助項(xiàng)目（61125204）；國家自然科學(xué)基金重點(diǎn)資助項(xiàng)目（61432014）；國家自然科學(xué)基金資助項(xiàng)目（6147230）；國家自然科學(xué)基金青年基金資助項(xiàng)目（61100158）

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

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