張勝杰,查宇飛,李運強,李寰宇,楊源

(1.空軍工程大學航空航天工程學院,710038,西安;2.空軍工程大學空管領航學院,710051,西安)

?

一種利用局部結構信息的加權哈希圖像檢索算法

張勝杰1,查宇飛1,李運強1,李寰宇2,楊源2

(1.空軍工程大學航空航天工程學院,710038,西安;2.空軍工程大學空管領航學院,710051,西安)

針對圖像檢索領域中現(xiàn)有哈希算法僅考慮數據的全局信息,同時平等地對待每一維投影數據,導致得到的哈希碼不能很好地保持原始數據的相似性的問題,提出利用圖像數據局部結構信息的加權哈希(WLSH)算法。該算法同時考慮原始圖像空間的局部結構信息和投影數據的各維方差,首先利用數據之間的相似性構建關系矩陣,進而獲得原始圖像數據的局部結構信息;然后通過迭代量化的方法尋找最優(yōu)的正交旋轉矩陣,使得投影以后的量化誤差最小;最后通過權重矩陣平衡各維方差,保證每一維的單位編碼信息相同,從而實現(xiàn)對原始數據最優(yōu)的保距映射。在圖像庫上的實驗結果表明,WLSH算法應用于圖像檢索時在查準率和查全率上比主成分分析-迭代量化方法分別提高了3%和2%。

投影函數;局部結構信息;迭代量化;平衡各維方差;圖像檢索

目前,最近鄰搜索已經被廣泛地應用于數據壓縮、模式識別、文檔檢索等領域。進入大數據時代,如何快速地進行圖像檢索成為亟待解決的問題。哈希學習[1]通過學到數據的二進制哈希碼表示,使得哈希碼盡可能地保持原空間中的近鄰關系,節(jié)省了存儲空間,提高了查詢速度,在大數據的最近鄰搜索中被廣泛應用。

數據獨立哈希算法包括局部敏感哈希(locality sensitive Hashing,LSH)算法[2]以及它的拓展算法[3-4],通過隨機生成一個投影矩陣作為哈希函數,使得相似的樣本以較高的概率映射到同一個哈希桶中,但這些算法需要較長的哈希碼才能取得理想的精度。數據依賴哈希算法[5-8]從原始數據中學習出哈希函數,只需較短的哈希碼就能取得理想的精度。譜哈希(spectral Hashing, SH)算法[5]將編碼過程視為圖分割過程,對高維數據進行譜分析,通過放松約束條件將問題轉化成拉普拉斯特征圖的降維問題從而求得哈希函數。數據依賴的多索引哈希算法[6]采用自適應投影的方法使得哈希表中的元素下標接近于均勻分布,進而提升查詢速度。線性嵌入哈希算法[7]利用相關性預測函數保持高維數據與其編碼之間的鄰近關系,構建線性哈希映射矩陣,獲得緊致的哈希編碼,提高了圖像與編碼間的相關性,實現(xiàn)了高精度的圖像檢索?；诠５哪夸浰饕惴╗8]將Hash表與B+樹結合從而高效地索引目錄的子索引節(jié)點。另外,主成分分析哈希(principal component analysis hashing,PCAH)算法[9]通過主成分分析(PCA)學得投影矩陣。投影之后的各維度方差各不相同,但其將每一維度編碼成相同的碼長,從而降低了檢索性能。迭代量化(iterative quantization,ITQ)哈希算法通過學習一個最優(yōu)的正交旋轉矩陣平衡各維方差,進而減小量化誤差,但其不能保證平衡之后的各維方差完全相等。監(jiān)督哈希算法[10-11]利用數據的類標信息可以取得很好的檢索性能,但是類標信息有限且很難獲得。半監(jiān)督哈希算法[12]利用少量的標注樣本和大量的未標注樣本學習得到哈希函數。非監(jiān)督哈希算法[9,13]不需要數據的類標信息,但存在諸多限制條件而使性能受到一定影響。

以上傳統(tǒng)的哈希算法均存在2點不足:一是僅考慮數據的全局信息;二是平等地對待每一維的投影數據,導致得到的哈希碼不能很好地保持原始數據的相似性。針對這2點問題,本文同時考慮原空間的局部結構信息和投影數據的各維方差,提出了加權局部結構哈希(WLSH)算法。該算法首先利用數據之間的相似性構建關系矩陣,挖掘原始數據的局部結構信息,繼而創(chuàng)建局部結構變換矩陣,對原始樣本數據進行線性變換得到一種局部結構數據。然后,將該數據作為訓練樣本進行主成分分析得到投影函數,通過迭代量化尋找最優(yōu)的正交旋轉矩陣,使得量化誤差最小;最后通過權重矩陣平衡各維方差,保證每一維的單位編碼信息相同,從而實現(xiàn)對原始數據最優(yōu)的保距映射。

1 加權局部結構哈希

選取n個樣本構成樣本集合X={x1,x2,…,xn},xi∈Rm,m為樣本的維度。學習哈希函數的目的就是為了得到哈希碼,即h:X→Y∈{1,-1}n×k,哈希函數表示為h(xi)=sgn[f(xi)],f(xi)為投影函數,Y為哈希碼矩陣形式,k為哈希函數的個數,sgn(·)表示符號函數。

1.1 局部結構數據

為了保持原始數據空間與漢明空間數據結構的一致性,譜哈希(SH)算法[5]挖掘數據內部的譜性質,通過約束經哈希映射后的二進制編碼中某一位(bit)結果為-1或1的概率相等以及二進制哈希碼的每一位不相關,從而建立目標函數如下

(1)

(2)

式中:N(x,s)表示樣本x在U中最近的s個錨點,本文設置s=5。

通過相似矩陣Z,可以計算對稱關系矩陣A=ZZT,進而可求得A的標準化形式

(3)

式中:Q=D-1/2Z∈Rn×d。這里,定義Q為局部結構變換矩陣,該矩陣是由錨點圖相似矩陣z(x)變換得到,包含了豐富的局部結構信息。下面將引出由該矩陣變換所得的局部結構數據。

(4)

(5)

主成分分析是一種非常經典有效的降維算法,雖然在變換過程中存在一定程度上的信息損失,但其絕大部分能量能被保留在前k個最大的特征值對應的維度上。哈希算法目的是通過盡可能少的維度去保留盡可能多的能量,從而實現(xiàn)快速圖像檢索,雖然PCA變換存在一定程度的信息丟失,但并不影響對圖像進行快速檢索。

圖1 局部結構特征提取和變換示意圖

圖1是局部結構特征提出和變換示意圖。圖1表示對原始數據X進行局部結構特征提取得到對稱關系矩陣A,然后由學習得到的局部結構變換矩陣Q對原始數據進行線性組合得到局部結構數據。

1.2 迭代量化方法

迭代量化方法[9]通過旋轉主成分方向使得各主成分方向的方差盡量保持平衡。隨機生成兩組滿足高斯分布的數據集,并將這兩組數據集分別進行無旋轉、隨機旋轉、最優(yōu)旋轉的操作,最終得到如圖2所示的可以形象表達迭代量化方法的示意圖。圖中點代表訓練樣本,線代表主成分方向。當對這些訓練樣本進行二值量化,由圖2a可知,同一類樣本被不同的哈希編碼序列表示了出來,即相似的樣本落在了不同的哈希桶中。圖2b對主成分方向進行了一次隨機旋轉,使得同一類樣本盡能多地落在相同的哈希桶中。圖2c是通過迭代量化方法得到的投影向量及哈希碼編碼序列,可以看出,相似的訓練樣本落在了相同的哈希桶中。

為了尋找到最優(yōu)的正交旋轉矩陣R,目標函數可表示為

(6)

式中:V=XH*表示訓練樣本經主成分分析后的投影數據;H*為投影函數;Y代表哈希碼矩陣;‖·‖F(xiàn)表示F范數。

(a)無旋轉 (b)隨機旋轉 (c)最優(yōu)旋轉圖2 迭代量化方法示意圖

1.3 加權平衡方法

迭代量化方法[9]通過不斷迭代降低量化誤差,從而使得每維方差趨于相等,然而,這種方式并不能獲得相等的方差。本文采用CIFAR-10數據庫[16]分別在隨機正交旋轉(PCA-RR)、10次和50次迭代3種情況下對投影數據進行單位化方差與投影數據的比特數關系實驗,結果如圖3所示。

圖3 3種情況下單位化方差與投影數據比特數的關系

同樣,經過迭代量化后同樣滿足方差大小與信息量大小的一致性。在哈希碼編碼序列上,方差越大的維包含的信息量越大,則需分配的權重值也應更大,因此可以求得每一位哈希碼對應的權值為

(7)

2 模型構建及其優(yōu)化

2.1 模型構建

(8)

2.2 模型優(yōu)化

這一小節(jié)將對模型進行優(yōu)化。為了解決上述問題,運用固定一個變量,求解另一變量的方式對模型進行優(yōu)化求解。

2.2.1 固定W計算H對每一維哈希碼的權重進行初始化,將各維權重設為等值,并且約束權重之和等于1,則初始化權重矩陣表示為W=k-1E,其中k是哈希碼的長度,E是單位矩陣。將初始化權重矩陣代入式(8),則目標函數變?yōu)?/p>

s.t.HTH=I

(9)

然后,應用投影函數H*,得到投影數據V=XH*,選擇符號函數sgn()作為編碼函數,即可求得哈希碼Y=sgn(XH*)。

然而,主成分分析得到的投影數據各主成分方向的方差(或信息量)通常各不相等,迭代量化算法通過旋轉主成分方向使得旋轉后各方向的方差盡量保持平衡。該方法的目標是通過尋求最優(yōu)正交矩陣R,最小化量化誤差

s.t.RTR=I

(10)

采用迭代量化方法去逼近量化誤差最小值,其交替進行的步驟如下。

(1)初始化R為隨機正交矩陣。

(2)固定R,更新Y=sgn(XH*R)。

(3)固定Y,更新R。目標函數變?yōu)?/p>

(11)

(4)當量化誤差足夠小時,所得到的正交矩陣R和哈希碼Y即為所求,實驗表明當迭代次數在40～60時,算法趨于平穩(wěn),本文選擇迭代50次。最終可以求得最優(yōu)正交旋轉矩陣R及H=H*R。

2.2.2 固定H求解W在上一小節(jié)中,固定W,通過優(yōu)化目標函數式(8),解得了投影函數H。圖3表明,迭代量化方法求得的方差并不完全相等,還存在差異性,為了進一步平衡各維方差差異,提出了加權平衡的方法。本小節(jié)將利用已經求得的投影函數H,求解每位哈希碼上分配的權重W。首先,求解每位哈希碼的方差vt=var(yt);然后結合公式(7),即可求得權值

(12)

總結WLSH算法流程如下。

輸入 原始樣本數據X={x1,x2,…,xn},xi∈Rm,哈希碼維度k,迭代次數t,構建錨點圖的參數[14]。

初始化W=k-1E。

(2)運用局部結構數據,計算投影函數

(3)fori=1:t;

(4) 固定R,更新Y

Y=sgn(XH);

(5) 固定Y,更新R

(6) end for;

(7)用式(12)計算權重矩陣W。

輸出 投影函數H=H*R,權重矩陣W。

2.3 時間復雜度分析

分別對本文算法的訓練和測試時間復雜度進行分析。

對于任意一個測試樣本,生成哈希碼的測試時間復雜度為O(mk),相對于一些非線性哈希算法如SH和KLSH,測試時間復雜度有所降低。雖然本文算法的訓練時間相對于一些算法有所增加,但是測試時間很快,能夠滿足現(xiàn)實需要。

3 實驗結果及分析

3.1 數據集與實驗設置

實驗選用2個比較常用的數據庫CIFAR-10[16]和MNIST[12]來驗證本文算法的有效性。

CIFAR-10含有60 000個樣本,每個樣本維度為320,該數據庫包含飛機、汽車、鳥、貓、鹿、狗、青蛙、馬、輪船和卡車10個分類,每類數據集有6 000個樣本。MNIST是數字手寫識別數據庫,該數據庫中包含70 000個維度為784的數據樣本。本文隨機選取5 000個樣本作為訓練集和1 000個樣本作為測試集。數據庫具體信息如表1。

所有實驗均在3.06 GHz、6 GB內存的64 bit計算機環(huán)境下通過MATLAB 2013a軟件平臺仿真實現(xiàn)。

表1 2種數據庫的具體信息

3.2 對比算法及評價標準

3.3 實驗結果分析

圖4為在數據庫CIFAR-10和MNIST上,返回500幅檢索圖像時加權平衡算法WPCAH、WPCA-RR、WPCA-ITQ和基準算法PCAH、PCA-RR、PCA-ITQ的查準率隨比特數變化的關系。由圖4可以看出,對基準算法PCAH進行加權平衡,效果提升顯著,而對迭代量化算法(ITQ)進行加權平衡效果提升不太明顯,因為迭代量化過程也有平衡方差的作用。

(a)CIFAR-10數據庫

(b)MNIST數據庫圖4 2個數據庫上6種對比算法的查準率與比特數關系

圖5顯示了本文算法和比較算法在數據庫CIFAR-10上哈希碼分別為16、32、64和128 bit時的檢索效果。由圖5可以看出：本文算法在哈希碼為16、64和128 bit時,查準率明顯高于其他哈希算法;在32 bit時,其他算法有逼近本文算法的趨勢。

圖6表示在數據庫MNIST上,哈希碼為64和128 bit時查準率和查全率隨檢索樣本數的關系。在數據庫MNIST上,由于SKLSH算法的不具有可比性,因此未選用該算法作為對比算法。由圖6可以看出,本文算法在64 bit和128 bit時查準率和查全率都明顯高于其他哈希算法。

(a)16 bit (b)32 bit

(c)64 bit (d)128 bit圖5 數據庫CIFAR-10上5種算法在不同比特數下的 查準率與返回檢索樣本數的關系

(a)64 bit (b)128 bit

(c)64 bit (d)128 bit圖6 數據庫MNIST上5種算法在不同比特數下的 查準率和查全率與返回檢索樣本數的關系

圖7表示了在圖像庫CIFAR-10和MNIST上,當返回500幅檢索圖像時的查準率隨比特數變化的關系。圖7同樣反映了圖5和圖6的問題:當哈希碼在32 bit時,其他算法有逼近本文算法的趨勢;在32 bit之后,查準率隨著比特數增加呈不斷上升趨勢。

(a)CIFAR-10數據庫

(b)MNIST數據庫圖7 2種數據庫上8種對比算法的查準率與比特數關系

4 結 論

本文提出了一種加權局部結構哈希算法——WLSH,相比于以往哈希算法,該算法同時考慮了原空間的局部結構信息和投影數據的各維方差大小,最大程度的減少了信息損失。在2個大的數據庫上進行圖像檢索,實驗結果表明,該算法在所有比特數上的查準率和查全率都高于其他相關算法。

但是,該方法在取得優(yōu)異性能的同時也存在著一定的問題和不足,主要體現(xiàn)在兩個方面:一是算法中參數過多,在一定程度上增加了算法的復雜性,降低了實時性;二是對數據進行主成分分析過程本身會造成一定的信息損失。這些問題都有待通過進一步的研究來解決和完善。

[1] 李武軍, 周志華. 大數據哈希學習: 現(xiàn)狀與趨勢 [J]. 科學通報, 2015, 60(5/6): 485-490. LI Wujun, ZHOU Zhihua. Learning to Hash for big data: current status and future trends [J]. Chin Sci Bull, 2015, 60(5/6): 485-490.

[2] GIONIS A, INDYK P, MOTWANI R. Similarity search in high dimensions via Hashing [C]∥International Conference on Very Large Data Bases. New York, USA: ACM, 2000: 518-529.

[3] KULIS B, JAIN P, GRAUMAN K. Fast similarity search for learned metrics [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(12): 2143-2157.

[4] 趙永威, 李弼程, 彭天強, 等. 一種基于隨機化視覺詞典組和查詢擴展的目標檢索方法 [J]. 電子與信息學報, 2012, 34(5): 1154-1161. ZHAO Yongwei, LI Bicheng, PENG Tianqiang, et al. An object retrieval method based on randomized visual dictionaries and query expansion [J]. Journal of Electronics & Information Technology, 2012, 34(5): 1154-1161.

[5] WEISS Y, TORRALBA A, FERGUS R. Spectral hashing [C]∥ Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. Cambridge, MA, USA: MIT, 2008: 1753-1760.

[6] 馬艷萍, 姬光榮, 鄒海林, 等. 數據依賴的多索引哈希算法 [J]. 西安電子科技大學學報, 2015, 42(4): 159-164. MA Yanping, JI Guangrong, ZOU Hailin, et al. Data-oriented multi-index Hashing [J]. Journal of Xidian University, 2015, 42(4): 159-164.

[7] 王秀美, 丁利杰, 高新波. 一種相似度保持的線性嵌入哈希方法 [J]. 西安電子科技大學學報, 2016, 43(1): 94-98. WANG Xiumei, DING Lijie, GAO Xinbo. Linear embedding Hashing method in preserving similarity [J]. Journal of Xidian University, 2016, 43(1): 94-98.

[8] 劉賢焯, 王勁林, 朱明, 等. Hash表與B+樹相結合的高效目錄索引結構 [J]. 西安交通大學學報, 2013, 47(4): 105-111. LIU Xianzhuo, WANG Jinlin, ZHU Ming, et al. Effective directory index framework taking advantages of Hash table and B+tree [J]. Journal of Xi’an Jiaotong University, 2013, 47(4): 105-111.

[9] GONG Y C, LAZEBNIK S. Iterative quantization: a procrustean approach to learning binary codes for large scale image retrieval [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(12): 2916-2929.

[10]LIN G S, SHEN C H, SHI Q F, et al. Fast supervised Hashing with decision trees for high-dimensional data [C]∥ Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE Computer Society, 2014: 1971-1978.

[11]WANG Q F, SHEN B, WANG S M, et al. Binary codes embedding for fast image tagging with incomplete labels [C]∥ 13th European Conference on Computer Vision. Berlin, Germany: Springer-Verlag, 2014: 425-439.

[12]WANG J, KUMAR S, CHANG S F. Semi-supervised Hashing for scalable image retrieval [C]∥ IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE, 2010: 3424-3431.

[13]XIA Y, HE K M, KOHLI P, et al. Sparse projections for high-dimensional binary codes [C]∥Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE, 2015: 3332-3339.

[14]LIU W, WANG J, KUMAR S, et al. Hashing with graphs [C]∥Proceedings of the 28th International Conference on Machine Learning. New York, USA: Association for Computing Machinery, 2011: 1-8.

[15]SCHONEMANN P. A generalized solution of the orthogonal Procrustes problem [J]. Psychometrika, 1966, 31(1): 1-10.

[16]LENG Cong, CHENG Jian, YUAN Ting, et al. Learning binary codes with Bagging PCA [C]∥Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Berlin, Germany: Springer Verlag, 2014: 177-192.

[17]LIU X L, HE J F, DENG C, et al. Collaborative Hashing [C]∥Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE Computer Society, 2014: 2147-2154.

[18]RAGINSKY M, LAZEBNIK S. Locality-sensitive binary codes from shift-invariant kernels [C]∥23rd Annual Conference on Neural Information Processing Systems. Red Hook, NY, USA: Curran Associates Inc., 2009: 1509-1517.

[19]JEGOU H, DOUZE M, SCHMID C, et al. Aggregating local descriptors into a compact image representation [C]∥Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE Computer Society, 2010: 3304-3311.

(編輯 劉楊)

A Weighted Hashing Algorithm Based on Local Structured Information for Image Retrieval

ZHANG Shengjie1,ZHA Yufei1,LI Yunqiang1,LI Huanyu2,YANG Yuan2

(1. School of Aeronautics and Astronautics Engineering, Air Force Engineering University, Xi’an 710038, China;2. School of Air Control and Navigation, Air Force Engineering University, Xi’an 710051, China)

A weighted local structured Hashing (WLSH) method is proposed to address the problem in the field of image retrieval that most existing Hashing methods only consider the global information and treat each projected dimension equivalently, which leads to a problem that the binary codes cannot efficiently preserve the data similarity. The proposed method considers local structure information of original image data and the variance of each projected dimension simultaneously. An affinity weight matrix is built to describe the relationship between data points and to acquire local structure information of the original image data. Then, an iterative quantization is used to find an optimal orthogonal transformation matrix and to minimize the quantization error. Finally, a weighted matrix is used to balance the variances and to guarantee equivalent information of each Hashing bits, thus the data similarity is effectively preserve. Experimental results based on some large scale datasets show that the precision and recall of the WLSH algorithm are improved by 3% and 2% over principal component analysis-iterative quantization, respectively.

projection functions; local structure information; iterative quantization; balance the variance; image retrieval

2016-01-18。

張勝杰(1994—),男,碩士生;査宇飛(通信作者),男,副教授,碩士生導師。

國家自然科學基金資助項目(61472442);陜西省青年科技新星計劃資助項目(2015KJXX-46)。

時間:2016-07-23

http:∥www.cnki.net/kcms/detail/61.1069.T.20160723.1817.002.html

10.7652/xjtuxb201610012

TP391

A

0253-987X(2016)10-0078-08