郭呈呈， 于鳳芹， 陳 瑩

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

0 引 言

為了提高局部敏感哈希[1,2](locality sensitive Hashing,LSH)編碼效率，提出了許多生成緊湊哈希編碼的方法[3～7]，但由于哈希編碼是離散的且受編碼長度的限制，因此,在檢索時查詢圖像與許多圖像數(shù)據(jù)間的漢明距離是相同的，難以根據(jù)距離排序來判斷這些圖像與查詢圖像間的相似性。為了解決該問題，可以對各個哈希比特位進行加權(quán)處理，Zhang X等人[8]沒有將查詢數(shù)據(jù)壓縮到二值哈希編碼，從而減少了信息的損失。Jiang Y G等人[9]根據(jù)預(yù)定義的類別標簽，為不同類別圖像學習不同的比特位權(quán)重，但算法受類別標簽數(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)方法適用性差的問題，然而由于QRank在計算比特位權(quán)重時利用隨機采樣的方法選取采樣子集，導致數(shù)據(jù)分布特性丟失，權(quán)重分配不符合實際情況，檢索精度下降。

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

1 改進哈希編碼排序圖像檢索的基本原理

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

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

(1)

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

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

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

(2)

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

1.2 由粗到細的圖像最近鄰檢索算法

1.2.1 生成短哈希編碼

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

hk(x)=thr(wkx)

(3)

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

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

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

(4)

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

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

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

(5)

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

此外，通過計算兩個哈希函數(shù)的互信息判斷獨立性。

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

1.2.3 計算排序得分

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

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

(6)

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

(7)

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

2 算法流程

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

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

3 仿真實驗與結(jié)果分析

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

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

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

3.2 結(jié)果分析

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

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

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

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

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

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

4 結(jié) 論

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