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

夏立超,　蔣建國(guó),　齊美彬

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

?

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

夏立超,蔣建國(guó),齊美彬

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

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

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

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

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

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

1　算法原理

1.1相關(guān)定義與假設(shè)

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

其中,ε=1。

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

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

(7)

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

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

(8)

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

(9)

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

1.2模型求解

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

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

(10)

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

min tr(YTLY)+tr(YTMY)，

(11)

其中

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

(12)

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

1.3Boosting算法確定閾值

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

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

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

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

(13)

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

(14)

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

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

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

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

1.4Boosting確定閾值基本流程

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

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

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

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

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

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

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

利用上述算法計(jì)算哈希編碼矩陣每列對(duì)應(yīng)的閾值,對(duì)圖像的哈希碼進(jìn)行二值化,得到最終的哈希碼Y。

1.5編碼過(guò)程

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

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

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

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

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

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

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

2.1實(shí)驗(yàn)數(shù)據(jù)及特征表達(dá)

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

表1　實(shí)驗(yàn)數(shù)據(jù)集

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

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

2.2評(píng)價(jià)指標(biāo)

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

假設(shè)對(duì)于每幅圖像xi,在圖像庫(kù)中有mi個(gè)相似圖像。對(duì)于n幅圖像的MAP計(jì)算公式為:

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

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

2.3實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

圖3　查詢圖例

圖4　檢索實(shí)例1

圖5　　檢索實(shí)例2

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

3　結(jié)　　論

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

[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矩陣和非負(fù)矩陣的圖像分類[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),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.

(責(zé)任編輯張淑艷)

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61371155;61174170)

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

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

10.3969/j.issn.1003-5060.2016.08.009

TN919.81

A

1003-5060(2016)08-1049-06

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