夏立超,　蔣建國,　齊美彬

(合肥工業(yè)大學 計算機與信息學院,安徽 合肥　230009)

?

基于改進譜哈希的大規(guī)模圖像檢索

夏立超,蔣建國,齊美彬

(合肥工業(yè)大學 計算機與信息學院,安徽 合肥230009)

為了提高圖像檢索精度,文章在譜哈希的基礎上引入最小量化誤差的思想,提出了一種基于改進譜哈希的大規(guī)模圖像檢索算法,該算法避免了譜哈希中要求的數(shù)據(jù)服從均勻分布的假設,并且能夠保持數(shù)據(jù)在原始空間的相似性;引入Boosting算法來確定閾值,使得該算法具有更強的適應性和更廣泛的應用;在公開的圖像數(shù)據(jù)集上做了實驗,實驗結(jié)果表明該方法優(yōu)于譜哈希、局部敏感哈希和迭代量化等哈希算法。

哈希;經(jīng)驗誤差;拉普拉斯矩陣;Boosting算法

在大規(guī)模圖像數(shù)據(jù)檢索領域，近似最近鄰(approximate nearest neighbor,ANN)檢索是計算機視覺中最基本的問題[1-2]。對于近似最近鄰(ANN)檢索,有很多基于建立索引結(jié)構(gòu)的方法,例如KD樹(k-dimensional tree)和R樹等,但是當維度很高時,就會產(chǎn)生維數(shù)災難,使其檢索效率低于線性檢索[3]。為了解決這一問題,基于哈希的圖像檢索算法[4]成為近年來研究的熱點。哈希方法的準則是在原始空間中相似的圖像有相似的哈希碼,其原理是將高維數(shù)據(jù)映射至漢明空間,直接用漢明距離進行快速準確的檢索。為了進一步提高基于哈希的圖像檢索效率,近年來有研究者提出建立基于漢明空間索引結(jié)構(gòu)[5]的方法以提高檢索效率。

現(xiàn)有的哈希方法大致可以分為數(shù)據(jù)相關和數(shù)據(jù)無關2種方法。在數(shù)據(jù)相互獨立前提下的哈希方法中,哈希函數(shù)可通過輸入數(shù)據(jù)直接訓練而得到，局部敏感哈希(locality-sensitive hashing,LSH)[6]是其中經(jīng)典的方法,其改進方法有核化局部敏感哈希(kernelized locality-sensitive hashing,KLSH)[7]和拓撲局部敏感哈希[8]等，但這類方法都是基于隨機映射,有較大的隨機性,因此檢索準確率較低。近年來有許多基于數(shù)據(jù)分布特性的自學習的哈希方法被提出。譜哈希(spectral hashing,SH)的方法[9]創(chuàng)新性地利用譜圖分割最優(yōu)化問題,最終轉(zhuǎn)換為對應的圖的拉普拉斯矩陣[10-11]的特征向量求解問題,取得了較好的檢索效果。其改進算法有語義一致圖譜哈希[12],它是一類有監(jiān)督算法,利用圖像的標簽(先驗知識)構(gòu)建最優(yōu)的拉普拉斯矩陣,提高了檢索的精度。譜哈希前提是假設數(shù)據(jù)服從均勻分布,但實際中很難滿足,導致檢索準確率低下。迭代量化(Iterative Quantization,ITQ)的方法[13]和K均值笛卡爾哈希[14]均通過旋轉(zhuǎn)數(shù)據(jù)中心使得映射的量化誤差最小。球哈希(spherical hashing,SPH)[15]使用超球面分割原始數(shù)據(jù),從而得到相應的球哈希函數(shù),其優(yōu)勢在于哈希函數(shù)學習過程的算法復雜度較低,且提高了檢索準確率。還有許多基于監(jiān)督學習的哈希方法,例如監(jiān)督哈希[12,16]和半監(jiān)督哈希(semi-supervised hashing,SSH)[17]。

譜哈希算法為了得到數(shù)據(jù)集的哈希碼,需要用流形學習[18]的方法計算拉普拉斯矩陣的特征向量。本文引入迭代量化的經(jīng)驗誤差最小化得到哈希碼,但不是通過迭代取得最優(yōu)解,而是通過譜哈希的模型直接求解哈希函數(shù),訓練過程中不需要用到流形學習方法,從而擺脫譜哈希要求的數(shù)據(jù)服從均勻分布的假設,又能保持數(shù)據(jù)在原始空間的相似性。譜哈希算法假設原始數(shù)據(jù)在高維空間中服從均勻分布,以理論最優(yōu)值0為閾值,但是每個圖像數(shù)據(jù)集的數(shù)據(jù)分布都不盡相同,圖像本身的結(jié)構(gòu)化信息豐富,因此以0為閾值并不能適用于所有的哈希方法。本文引入機器學習中的Boosting算法[19],根據(jù)不同數(shù)據(jù)集本身的性質(zhì),計算出合適的閾值,使得本文算法對于不同的數(shù)據(jù)集都具有良好的適應性。

1　算法原理

1.1相關定義與假設

訓練集{(xi∈R1×d),i=1,2,…,n}由n幅圖像組成,其中xi為第i幅圖像對應的d維特征向量;X∈Rn×d為n幅圖像組成的訓練全集矩陣。{(yi∈{-1,1}1×k),i=1,2,…,n}為n幅圖像經(jīng)過哈希函數(shù)轉(zhuǎn)換到漢明空間后對應的哈希編碼,其中yi為第i幅圖像對應的k維編碼向量,Y∈{-1,1}n×k為n幅圖像對應的哈希編碼矩陣。本文的目標就是要學習得到一系列哈希函數(shù)如下:

(1)

第i個哈希函數(shù)定義為:

(2)

其中,ωi∈Rd×1為哈希函數(shù)的變換矩陣,bi∈R為哈希函數(shù)的偏移量。定義W∈Rd×k和B∈R1×k分別為:

(3)

相似圖像間的平均漢明距離為:

(4)

其中,D∈Rn×n為訓練集的相似度矩陣,本文用高斯核函數(shù)計算訓練集的相似度矩陣為:

(5)

其中,ε=1。

根據(jù)譜哈希的思想,為了保持歐式空間的相似性,需最小化(4)式,即

其中,L為拉普拉斯矩陣,且有:

(7)

譜哈希算法還需要保證映射的擴展性,即當有新的數(shù)據(jù)時,不需要重新訓練,而直接進行編碼。譜哈希通過假設數(shù)據(jù)服從多維均勻分布,用流形學習方法求拉普拉斯矩陣L的特征向量,再閾值化得到哈希碼。譜哈希引入拉普拉斯矩陣L并且放松Y(i,j)∈{-1,1}的編碼條件,于是(6)式的求解就轉(zhuǎn)換為拉普拉斯特征圖的降維。為了解決訓練集外圖像索引編碼問題,將特征向量轉(zhuǎn)換為特征方程,通過有權(quán)重的拉普拉斯-貝特拉米算子的特征方程來解決。

本文引入量化誤差最小化,避免模型求解過擬合問題,同時可直接求解哈希函數(shù),即W和B。最小化式變換如下:

(8)

其中,Ω(hl)為哈希函數(shù)hl的歸一化函數(shù);α為原始空間相似度和經(jīng)驗誤差間的權(quán)重;β為哈希函數(shù)歸一化權(quán)重。根據(jù)譜哈希算法原理,(8)式在約束條件下是一個NP-hard解問題,需放寬約束條件才能求解,故將(8)式變換為:

(9)

其中,I1∈Rn×1為一個元素全為1的列向量。

1.2模型求解

分別對(9)式中的W和B求偏導,令偏導數(shù)為0,求得W和B分別為:

W=(XTLcX+βId)-1XTLcY,

(10)

其中,Id∈Rd×d為一個單位陣;Lc=In-I1I1T/n,In∈Rn×n為一個單位陣。把(10)式帶入 (9)式中,化簡目標函數(shù)可得:

min tr(YTLY)+tr(YTMY)，

(11)

其中

M=Lc-LcX(XTLcX+βId)-1XTLc

(12)

(11)式形如譜哈希(9)式,L*=L+M相當于譜哈希中的拉普拉斯矩陣,通過對矩陣L*求特征值和特征向量,即可求出W和B。

1.3Boosting算法確定閾值

譜哈希算法以理論最優(yōu)值0為閾值,將特征映射矩陣二值化為二元漢明編碼矩陣。本文在譜哈希的基礎上引入量化誤差最小化,再采用Boosting算法,通過訓練獲得相應的閾值,使得本文算法具有更好的適應性。

Boosting算法是一種有監(jiān)督的分類算法,其核心思想是通過學習訓練得到一組弱分類器,由弱分類器組合獲得需要的強分類器。本文在改進譜哈希算法基礎上引入相似度敏感編碼Boosting(Boosting similarity sensitive coding)算法[20],對每個數(shù)據(jù)集分別計算得到相應的閾值。

假設有k個哈希函數(shù),圖像訓練集矩陣經(jīng)過哈希函數(shù)計算獲得閾值的編碼矩陣每列需要確定1個閾值,且可作為1個弱分類器,則共有k個弱分類器。通過訓練獲得最優(yōu)的k個弱分類器,即k個閾值。引入Boosting算法是為了計算每個哈希函數(shù)的閾值,因此不需要將弱分類器組合成強分類器。

為了得到錯誤率最低的弱分類器,本文將哈希映射的結(jié)果進行適當?shù)念A處理。假設有n個圖像數(shù)據(jù),2個為1組,則總共有n2種組合。以圖像間近鄰與否對每個組合添加標簽f,如果圖像間相似則為正例且f記為1,否則為反例且f記為0。f計算式為:

(13)

考慮由哈希函數(shù)得到的編碼矩陣的第j列,即第j個弱分類器,其編碼表達式為:

(14)

其中,z(i,j)為編碼矩陣第i行第j列的值,即第i個圖像的第j個哈希值；Tj為閾值。那么根據(jù)以上編碼過程,可能產(chǎn)生以下2種不正確的分類。

(1) xa和xb相似,但是通過編碼計算后,在第j列上相應的z(a,j)和z(b,j)被二值化成不同的值,例如z(a,j)=1和z(b,j)=0。

(2) xa和xb不相似,但是通過編碼計算后,在第j列上相應的z(a,j)和z(b,j)被二值化成相同的值,例如z(a,j)=z(b,j)=0。

本文的目標是利用Boosting算法,訓練獲得合適的閾值Tj,使得不正確的分類數(shù)盡量小。

1.4Boosting確定閾值基本流程

Boosting算法實際將每列的所有值作為可能的閾值,并計算錯誤率,最終選擇錯誤率最低的數(shù)作為閾值。并且在哈希編碼矩陣的每列上重復該操作,以獲得編碼矩陣所有列的閾值。確定閾值步驟如下,其中eps為可定義的最小正數(shù)。

(1) 根據(jù)哈希函數(shù)H(x)得到編碼矩陣,即所有圖像的哈希值z(a,j)、z(b,j),還有近鄰數(shù)據(jù)f(xa,xb)。

(2) 初始化集合A=?,錯誤分類的數(shù)目Tn=0。

(3) 對于每個三元組z(a,j)、z(b,j)、f(xa,xb),若z(a,j)>z(b,j),則lab=1;如果z(a,j)

(4) 根據(jù)集合A中的元素的第1項z(:,j)值,升序排列A的2N2個元素。

(5)Sp為相似圖像的所有l(wèi)值之和,Sn為非相似圖像的所有l(wèi)值之和,cb為動態(tài)變化的閾值。令Sp=Sn=0,cb=Tn,Tj=min(z(:,j))-eps。

(6) 對于k=1∶2N2,(z,l,f)=A[k],若f=1,則Sp=Sp-1;若f=-1,則Sn=Sn-1;令c=Tn-Sn+Sp,若c

利用上述算法計算哈希編碼矩陣每列對應的閾值,對圖像的哈希碼進行二值化,得到最終的哈希碼Y。

1.5編碼過程

對于包含n幅圖像的訓練集矩陣X∈Rn×d,訓練集包含數(shù)據(jù)較多,若全部參與編碼,數(shù)據(jù)量太大,計算機無法實現(xiàn),故一般隨機采樣一些數(shù)據(jù),組成X*∈Rm×d,利用求出的哈希函數(shù)再對X所有數(shù)據(jù)進行編碼。編碼過程如下:

(1) 固定α、β,根據(jù)(11)式求出L*=L+M。

(2) 求L*的特征值和特征向量,取k個最小的特征值對應的特征向量。將k個特征向量按列組成W。

(3) 通過(10)式求出B。

(4) 用W和B對訓練集矩陣X和測試集矩陣T進行哈希編碼,并根據(jù)測試集矩陣T的歐氏距離k近鄰數(shù)據(jù)求出平均準確率，即均值平均精度(mean average precision,MAP)。

(5) 重復步驟(2)～步驟(4),取MAP最高的一組確定α、β。

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

2.1實驗數(shù)據(jù)及特征表達

本文實驗在2個數(shù)據(jù)集上完成,查詢集包含1 000個圖像，數(shù)據(jù)集其他參數(shù)見表1所列。

表1　實驗數(shù)據(jù)集

注:括號中數(shù)字為維度大小。

GIST-1M數(shù)據(jù)集[21]已包含圖像的GIST特征[22],對CIFAR-10數(shù)據(jù)集[23]每幅圖像計算8個方向和4個尺度的灰度GIST特征,生成320維特征的數(shù)據(jù)集。

2.2評價指標

對圖像的編碼過程是線下進行的,即先對圖像特征數(shù)據(jù)進行編碼,將圖像數(shù)據(jù)的哈希碼保存入庫。當有查詢圖像時,直接對查詢圖像進行編碼,并與圖像庫中的哈希碼進行碼間異或運算。通常所說的哈希算法提高效率是指提高查找效率,而圖像哈希是通過訓練獲得更好的哈希函數(shù),其訓練過程也是線下操作,不影響圖像的檢索效率,所以哈希算法的算法復雜度并不作為算法評價的重要指標,而且相關研究[6-7,9,13-15]也未對算法復雜度進行比較分析,因此本文不對哈希算法的算法復雜度進行分析和比較,只將MAP作為評價指標。MAP是信息檢索中常用性能指標,現(xiàn)已被廣泛應用于各種圖像檢索算法[6-7,9,13-15]的性能評價。

假設對于每幅圖像xi,在圖像庫中有mi個相似圖像。對于n幅圖像的MAP計算公式為:

其中,R為第j個相似圖像在返回結(jié)果中的Rank,Rank為排序后的序號。

采用LSH、ITQ、SH、SPH 4種方法作為對比,這4種方法在GIST-1M和CIFAR-10數(shù)據(jù)集上計算3次MAP取平均,本文算法由于較復雜且計算量較大,所以只做1次運算。

2.3實驗結(jié)果及分析

在GIST-1M和CIFAR-10數(shù)據(jù)集中隨機選取1 000個數(shù)據(jù)作為測試集,余下的數(shù)據(jù)作為訓練集。用歐氏距離計算出測試集每個數(shù)據(jù)的k近鄰(KNN)作為基準,計算檢索MAP。其中GIST-1M數(shù)據(jù)集上k取1 000(1 000-NN),CIFAR-10數(shù)據(jù)集上k取100(100-NN)。每種方法在GIST-1M數(shù)據(jù)集上都取碼長32～512 bit,在CIFAR-10數(shù)據(jù)集上取碼長16～256 bit,并計算MAP。

實驗結(jié)果如圖1、圖2所示,本文方法在2個數(shù)據(jù)集上的準確率見表2所列。

從圖1和圖2可以看出,本文算法略優(yōu)于球哈希(SPH)算法。其中迭代量化(ITQ)算法的檢索平均精度隨著碼長的增加大致呈線性增長,本文算法、球哈希(SPH)和迭代量化(ITQ)在碼長較低時檢索平均精度相近,而位置敏感哈希(LSH)和譜哈希(SH)效果明顯差于其他算法。本文算法效果最好,譜哈希(SH)最差。

圖1　GIST-1M數(shù)據(jù)集的實驗結(jié)果

圖2　CIFAR-10數(shù)據(jù)集的實驗結(jié)果

表2　本文方法在2個數(shù)據(jù)集上的準確率 %

2.4圖像檢索結(jié)果示例

查詢圖像實例1、實例2如圖3所示,對應檢索實例如圖4、圖5所示。檢索實例均為在CIFAR數(shù)據(jù)集上以128 bit檢索的結(jié)果,每幅圖上合成了用相應算法檢索出的前100幅相似圖像。

圖3　查詢圖例

圖4　檢索實例1

圖5　　檢索實例2

圖4a、圖5a為歐式空間用特征間的歐式距離查詢的結(jié)果;圖4b、圖5b為本文算法的檢索結(jié)果;括號內(nèi)為對應的查準率?？梢钥闯霰疚乃惴▋?yōu)于其他算法。

3　結(jié)　　論

本文引入量化誤差最小化的思想改進譜哈希,擺脫了譜哈希對訓練數(shù)據(jù)的限制,并引入Boosting算法確定閾值,提高了圖像檢索的精度。實驗結(jié)果表明本文方法優(yōu)于其他哈希算法。下一步將研究圖像哈希算法,進一步提高檢索的準確率。

[1]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.

[2]XU H,WANG J,LI Z,et al.Complementary hashing for approximate nearest neighbor search[C]//2011 IEEE International Conference on Computer Vision (ICCV).[S.l.]:IEEE,2011:1631-1638.

[3]BEYER K,GOLDSTEIN J,RAMAKRISHNAN R,et al.When is “nearest neighbor” meaningful?[M]//Database Theory: ICDT’99.Berlin:Springer,1999:217-235.

[4]TORRALBA A,FERGUS R,WEISS Y.Small codes and large image databases for recognition[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.[S.l.]:IEEE,2008:1-8.

[5]NOROUZI M,PUNJANI A,FLEET D J.Fast exact search in hamming space with multi-index hashing[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(6):1107-1119.

[6]ANDONI A,INDYK P.Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions[C]//47th Annual IEEE Symposium on Foundations of Computer Science.[S.l.]:IEEE,2006:459-468.

[7]KULIS B,GRAUMAN K.Kernelized locality-sensitive hashing[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(6):1092-1104.

[8]PANIGRAHY R.Entropy based nearest neighbor search in high dimensions[C]//Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm.[S.l.]:Society for Industrial and Applied Mathematics,2006:1186-1195.

[9]WEISS Y,TORRALBA A,FERGUS R.Spectral hashing[M]//Advances in Neural Information Processing Systems.[S.l.:s.n.],2009:1753-1760.

[10]XIE B,WANG M,TAO D.Toward the optimization of normalized graph Laplacian[J].IEEE Transactions on Neural Networks,2011,22(4):660-666.

[11]蔣云志,王年,汪斌,等.基于圖的Laplace矩陣和非負矩陣的圖像分類[J].合肥工業(yè)大學學報(自然科學版),2011,34(9):1330-1334.

[12]LI P,WANG M,CHENG J,et al.Spectral hashing with semantically consistent graph for image indexing[J].IEEE Transactions on Multimedia,2013,15(1):141-152.

[13]GONG Y,LAZEBNIK S.Iterative quantization: a procrustean approach to learning binary codes[C]//2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR).[S.l.]:IEEE,2011:817-824.

[14]NOROUZI M,FLEET D J.Cartesian k-means[C]//2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR).[S.l.]:IEEE,2013:3017-3024.

[15]HEO J P,LEE Y,HE J,et al.Spherical hashing[C]//2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR).[S.l.]:IEEE,2012:2957-2964.

[16]LIU W,WANG J,JI R,et al.Supervised hashing with kernels[C]//2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR).[S.l.]:IEEE,2012:2074-2081.

[17]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.

[18]CHENG J,LENG C,LI P,et al.Semi-supervised multi-graph hashing for scalable similarity search[J].Computer Vision & Image Understanding,2014,124:12-21.

[19]NADLER B,LAFON S,COIFMAN R R,et al.Diffusion maps,spectral clustering and reaction coordinates of dynamical systems[J].Applied and Computational Harmonic Analysis,2006,21(1):113-127.

[20]SHAKHNAROVICH G,VIOLA P,DARRELL T.Fast pose estimation with parameter-sensitive hashing[C]//Proceedings of the Ninth IEEE International Conference on Computer Vision (ICCV),Vol 2.Washington D C,USA:IEEE Computer Society,2003:750-757.

[21]JEGOU H,DOUZE M,SCHMID C.Product quantization for nearest neighbor search[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(1):117-128.

[22]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.

[23]KRIZHEVSKY A.Learning multiple layers of features from tiny images[R].Toronto:University of Toronto,2009.

(責任編輯張淑艷)

A large-scale image retrieval method based on improved spectral hashing

XIA Lichao,JIANG Jianguo,QI Meibin

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

In this paper, a large-scale image retrieval method based on improved spectral hashing is proposed by introducing the quantization error minimization to improve the image retrieval accuracy. The algorithm gets rid of the assumption that data is uniformly distributed required by the spectral hashing,and can keep the data similarity in the original space.Boosting algorithm is used to determine the threshold so that the algorithm can be more adaptive and more widely used. The algorithm is evaluated on the public datasets, and the experimental results show that the proposed method is better than spectral hashing(SH), locality-sensitive hashing(LSH) and iterative quantization hashing algorithm.

hashing; empirical error; Laplacian matrix; Boosting algorithm

2015-04-21；

2015-05-05

國家自然科學基金資助項目(61371155;61174170)

夏立超(1990-),男,安徽廬江人,合肥工業(yè)大學碩士生;

蔣建國(1955-),男,安徽寧國人,合肥工業(yè)大學教授,博士生導師;

10.3969/j.issn.1003-5060.2016.08.009

TN919.81

A

1003-5060(2016)08-1049-06

齊美彬(1969-),男,安徽東至人,博士,合肥工業(yè)大學教授,碩士生導師.