改進(jìn)哈希編碼加權(quán)排序的圖像檢索算法*

郭呈呈， 于鳳芹， 陳 瑩

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

0 引 言

為了提高局部敏感哈希[1,2](locality sensitive Hashing,LSH)編碼效率，提出了許多生成緊湊哈希編碼的方法[3～7]，但由于哈希編碼是離散的且受編碼長(zhǎng)度的限制，因此,在檢索時(shí)查詢圖像與許多圖像數(shù)據(jù)間的漢明距離是相同的，難以根據(jù)距離排序來(lái)判斷這些圖像與查詢圖像間的相似性。為了解決該問(wèn)題，可以對(duì)各個(gè)哈希比特位進(jìn)行加權(quán)處理，Zhang X等人[8]沒(méi)有將查詢數(shù)據(jù)壓縮到二值哈希編碼，從而減少了信息的損失。Jiang Y G等人[9]根據(jù)預(yù)定義的類別標(biāo)簽，為不同類別圖像學(xué)習(xí)不同的比特位權(quán)重，但算法受類別標(biāo)簽數(shù)量限制，適用性較差。Zhang L等人[10]提出了加權(quán)漢明距離排序(weighted Hamming distance ranking, WHRank)算法，但該方法十分依賴數(shù)據(jù)分布假設(shè)。Liu X L等人[11，12]提出了哈希編碼加權(quán)排序(query-adaptive Hash code ranking,QRank)算法，克服了上述加權(quán)方法適用性差的問(wèn)題，然而由于QRank在計(jì)算比特位權(quán)重時(shí)利用隨機(jī)采樣的方法選取采樣子集，導(dǎo)致數(shù)據(jù)分布特性丟失，權(quán)重分配不符合實(shí)際情況，檢索精度下降。

針對(duì)上述問(wèn)題，本文提出了一種改進(jìn)的哈希編碼加權(quán)排序圖像檢索算法，與現(xiàn)有的比特位加權(quán)算法相比，本文主要有兩點(diǎn)改進(jìn)：1)利用數(shù)據(jù)依賴差異[13]的思想對(duì)圖像數(shù)據(jù)集采樣，得到一個(gè)保留數(shù)據(jù)分布特性的采樣子集，利用該采樣子集計(jì)算各個(gè)比特位權(quán)重，提高檢索精度；2)提出了一種由粗到細(xì)的圖像最近鄰檢索策略:采用哈希方法將圖像特征映射成二值哈希編碼;計(jì)算哈希比特位權(quán)重，對(duì)哈希編碼進(jìn)行加權(quán)漢明距離排序，返回一個(gè)查詢圖像的候選最近鄰集合;對(duì)候選最近鄰集合中的圖像數(shù)據(jù)進(jìn)行主成分分析(principal component analysis,PCA)映射，計(jì)算每幅候選圖像的排序得分，根據(jù)得分重新排序來(lái)進(jìn)一步提高檢索精度，完成查詢圖像的最近鄰檢索。

1 改進(jìn)哈希編碼排序圖像檢索的基本原理

1.1 數(shù)據(jù)依賴差異的基本原理

基本思想是兩個(gè)數(shù)據(jù)在樣本密集區(qū)域的差異性較大，在樣本稀疏區(qū)域的差異性較小，也就是數(shù)據(jù)依賴差異與數(shù)據(jù)的分布有關(guān)。定義一個(gè)能同時(shí)覆蓋樣本數(shù)據(jù)x和y的最小區(qū)域

(1)

式中 1(·)為指示函數(shù),D為樣本數(shù)據(jù),H∈H(D)為一個(gè)分割模型，將空間分割成若干個(gè)不重疊且非空的區(qū)域。

1)構(gòu)造一個(gè)包含t個(gè)隨機(jī)樹(shù)的隨機(jī)森林作為分割結(jié)構(gòu)R，每個(gè)隨機(jī)樹(shù)都根據(jù)數(shù)據(jù)集D的一個(gè)子集構(gòu)建得到，通過(guò)遍歷樹(shù)的方式記錄數(shù)據(jù)的分布信息；

2)找到包含數(shù)據(jù)x,y的所有t個(gè)分割R(x,y|Hi)，計(jì)算數(shù)據(jù)依賴差異

(2)

3)利用數(shù)據(jù)依賴差異代替基本的歐氏距離度量對(duì)數(shù)據(jù)集進(jìn)行聚類，根據(jù)每個(gè)類別數(shù)據(jù)的數(shù)量占總數(shù)的比重，對(duì)其進(jìn)行采樣，共取ns個(gè)數(shù)據(jù)作為采樣子集。

1.2 由粗到細(xì)的圖像最近鄰檢索算法

1.2.1 生成短哈希編碼

采用哈希方法生成較短的哈希碼，假設(shè)給定一個(gè)包含n個(gè)d維數(shù)據(jù)點(diǎn)的數(shù)據(jù)集X={xi∈Rd,i=1,…,n)和m個(gè)哈希函數(shù)H(·)={h1(·),…,hm(·)}，每個(gè)樣本數(shù)據(jù)xi均被第k個(gè)哈希函數(shù)編碼成哈希比特yik=hk(xi)∈{-1,1}，其中哈希編碼函數(shù)定義為

hk(x)=thr(wkx)

(3)

式中wk為超平面參數(shù)的列向量。二值編碼通過(guò)符號(hào)函數(shù)y(x)=sgn(f)(如果f>0，那么y=1；否則，y=-1)獲得，數(shù)據(jù)的編碼過(guò)程為Y=sgn(WX)。

1.2.2 改進(jìn)的加權(quán)漢明距離排序方法

對(duì)于一個(gè)查詢數(shù)據(jù)q，若一個(gè)哈希函數(shù)可以較好的保存其最近鄰集NN(q)，則該函數(shù)對(duì)應(yīng)的哈希比特位在加權(quán)漢明距離中應(yīng)體現(xiàn)出更重要的作用，應(yīng)賦予其更大的權(quán)重?；诠：瘮?shù)的近鄰保存能力，可以根據(jù)譜嵌入損失[4]定義權(quán)重

(4)

1)找到查詢的最近鄰集NN(q)。針對(duì)文獻(xiàn)[12]利用隨機(jī)采樣的方法，獲取的數(shù)據(jù)不穩(wěn)定，不能保留數(shù)據(jù)的分布特性，本文利用數(shù)據(jù)依賴差異的思想來(lái)獲取符合數(shù)據(jù)分布特性的采樣子集。

2)計(jì)算相似性s(p,q)。為了度量查詢與數(shù)據(jù)集間的全局相似性，采用錨圖[14]的方法來(lái)近似數(shù)據(jù)的鄰居結(jié)構(gòu)，利用K-means對(duì)數(shù)據(jù)進(jìn)行聚類，取c個(gè)聚類中心作為錨點(diǎn)，基于數(shù)據(jù)和錨點(diǎn)間的近鄰關(guān)系，可以用區(qū)分力更強(qiáng)的非線性特征z(x)表示樣本數(shù)據(jù)x，最終兩個(gè)數(shù)據(jù)間的相似性為

s(p,q)=exp(-‖z(p)-z(q)‖2/σ2)

(5)

式中σ為z(p)和z(q)間的最大距離。

此外，通過(guò)計(jì)算兩個(gè)哈希函數(shù)的互信息判斷獨(dú)立性。

綜合考慮以上兩點(diǎn)，計(jì)算哈希比特位權(quán)重需要同時(shí)最大化哈希函數(shù)的近鄰保存能力和獨(dú)立性，這個(gè)問(wèn)題可以看作一個(gè)二次規(guī)劃問(wèn)題求解。

1.2.3 計(jì)算排序得分

計(jì)算排序得分時(shí)將查詢數(shù)據(jù)的近鄰半徑ε和原始特征作為輸入，在哈希編碼空間對(duì)查詢的ε近鄰進(jìn)行統(tǒng)計(jì)特性的建模分，并利用PCA對(duì)候選最近鄰集數(shù)據(jù)進(jìn)行降維壓縮，利用PCA方法一方面可以將數(shù)據(jù)特征信息盡可能的壓縮，減少編碼長(zhǎng)度，提高計(jì)算效率，另一方面PCA映射是正交的且能夠保存L2距離，因此,查詢數(shù)據(jù)的ε近鄰在經(jīng)過(guò)PCA映射后仍保留其近鄰關(guān)系。

為了計(jì)算方便，可以將排序得分近似為

(6)

式中q為查詢圖像,h為哈希編碼,k為編碼長(zhǎng)度,ωj為排序得分的單個(gè)比特輸出

(7)

式中yj為pj(yj)生成的隨機(jī)數(shù)。本文假設(shè)pj(yi)為均勻分布。式中只要有任意一個(gè)ωj(qj,hj,ε)為0，最終的排序得分即為0，哈希編碼為h的數(shù)據(jù)則不會(huì)返回，可大幅提高計(jì)算效率。

2 算法流程

本文算法流程如圖1所示。

圖1 改進(jìn)哈希編碼加權(quán)排序的圖像檢索算法流程

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

3.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

仿真實(shí)驗(yàn)采用圖像哈希檢索常用的手寫(xiě)數(shù)字?jǐn)?shù)據(jù)庫(kù)MNIST[15]和自然圖像數(shù)據(jù)庫(kù)CIFAR—10，本文隨機(jī)選取數(shù)據(jù)庫(kù)中的1 000幅作為測(cè)試用的查詢圖像，其余的作為數(shù)據(jù)集輸入。實(shí)驗(yàn)硬件環(huán)境為Intel Core i5—6200U處理器、8 GB內(nèi)存，軟件環(huán)境為Windows10，編程環(huán)境采用MATLAB R2016a。

為了驗(yàn)證所提算法的有效性，選擇文獻(xiàn)[2]提出的基本的哈希編碼方法，即LSH，以及兩種哈希編碼加權(quán)排序方法，文獻(xiàn)[10]的WhRank算法和文獻(xiàn)[12]的QRank算法進(jìn)行對(duì)比實(shí)驗(yàn)，同時(shí)為了驗(yàn)證本文算法的適用性，對(duì)比了文獻(xiàn)[3]PCA哈希(PCAH)和文獻(xiàn)[5]遞歸量化哈希(ITQ)，共進(jìn)行了3組仿真實(shí)驗(yàn)，并對(duì)結(jié)果進(jìn)行比較分析。本文采用精度(precision)，召回率(recall)和平均準(zhǔn)確率(mean average precision,MAP)作為算法的評(píng)價(jià)指標(biāo)。精度為返回的前K個(gè)結(jié)果中最近鄰所占的比率；召回率為前K個(gè)結(jié)果中最近鄰占所有最近鄰的比率,K值相同的條件下精度和召回率越高，檢索性能越好;平均準(zhǔn)確率的大小對(duì)應(yīng)著precision-recall曲線下區(qū)域面積的大小，MAP值越大，檢索性能越好。由于查詢圖像是隨機(jī)選取的，因此每個(gè)實(shí)驗(yàn)重復(fù)3次，每次選取5 000幅圖像作為訓(xùn)練數(shù)據(jù)，1 000幅圖像作為測(cè)試數(shù)據(jù)，取結(jié)果的平均值作為最終結(jié)果。數(shù)據(jù)庫(kù)中與查詢圖像標(biāo)簽相同的圖像即為查詢圖像的真實(shí)近鄰。

3.2 結(jié)果分析

圖2為CIFAR—10數(shù)據(jù)庫(kù)上查詢圖像返回的部分檢索結(jié)果，根據(jù)圖2(a)可以看出，經(jīng)過(guò)加權(quán)排序粗檢索后得到的候選最近鄰集合中雖然大部分檢索結(jié)果是正確的，但仍有錯(cuò)誤的匹配，影響檢索質(zhì)量，經(jīng)過(guò)圖2(b)計(jì)算排序得分的細(xì)檢索后，去除了大部分的錯(cuò)誤匹配，提高了檢索精度。

圖2 飛機(jī)查詢圖像的部分檢索結(jié)果

表1中具體列出了MNIST數(shù)據(jù)庫(kù)中編碼長(zhǎng)度分別為48 bit和96 bit時(shí)幾種算法的MAP，相比于基本的LSH圖像檢索算法，本文算法在檢索精度上有明顯的提升，并且本文算法的MAP也優(yōu)于WHRank和QRank兩種哈希比特位加權(quán)排序算法，在編碼長(zhǎng)度為96 bit時(shí)，本文算法的MAP分別提高11.61 %，8.42 %和1.86 %。

表1 MNIST數(shù)據(jù)庫(kù)上二種編碼長(zhǎng)度下各算法的MAP

圖3為MNIST數(shù)據(jù)庫(kù)上各算法的性能對(duì)比，圖3(c)給出了編碼長(zhǎng)度為48 bit時(shí)的檢索精度曲線，可以看出，通過(guò)對(duì)哈希編碼進(jìn)行加權(quán)排序，提升了基本哈希方法的搜索性能，對(duì)于每種哈希方法，使用本文的加權(quán)排序算法后檢索精度平均提升了約14 %，對(duì)于LSH算法，精度提升的更多(約19 %)。圖3(d)給出了增加編碼長(zhǎng)度的檢索精度曲線，可以看出，本文算法提升了基本哈希方法的檢索精度，與其他加權(quán)排序方法相比，檢索精度更高。對(duì)比圖3(c)、圖3(d)可以發(fā)現(xiàn)，LSH和PCAH哈希算法在編碼長(zhǎng)度為96 bit時(shí)的檢索精度仍然要低于編碼長(zhǎng)度為48 bit時(shí)使用本文排序算法的檢索精度，說(shuō)明了本文算法能夠用更短的哈希編碼達(dá)到更高的檢索精度，有效提升編碼效率，節(jié)省存儲(chǔ)空間。圖3(a)、圖3(b)給出了在數(shù)據(jù)集MNIST上編碼長(zhǎng)度分別為48 bit和96 bit的召回率曲線，可以發(fā)現(xiàn)，本文算法有效地提升了召回率，且在性能上優(yōu)于其他2種排序算法，較QRank算法在召回率上提升了約7.47 %。

圖3 MNIST數(shù)據(jù)庫(kù)上二種編碼長(zhǎng)度下各算法的性能對(duì)比

4 結(jié) 論

提出了一種由粗到細(xì)的檢索策略查找查詢圖像的最近鄰，仿真實(shí)驗(yàn)結(jié)果表明：本文算法的檢索性能優(yōu)于其他算法，但在計(jì)算排序得分時(shí)依賴基于PCA的哈希編碼技術(shù)，因此，編碼長(zhǎng)度不能超過(guò)輸入特征的維數(shù)，對(duì)此，需要進(jìn)一步研究更優(yōu)的量化方案。