王 振，孫福振，張龍波，王 雷

山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博 255000

1 引言

傳統(tǒng)圖像近鄰檢索算法根據(jù)圖像的高維浮點(diǎn)特征描述子（如320 維的全局特征描述子GIST）之間的歐式距離衡量圖像之間的相似度，計(jì)算復(fù)雜度較高，無(wú)法實(shí)時(shí)響應(yīng)海量圖像的近鄰檢索請(qǐng)求。為了解決這一問題，人們提出利用哈希算法將高維浮點(diǎn)特征映射成緊湊二值編碼，并依據(jù)漢明距離檢索近鄰點(diǎn)，其可直接利用計(jì)算機(jī)硬件指令異或操作計(jì)算漢明距離，計(jì)算速率較快，并且按位存儲(chǔ)二值編碼，存儲(chǔ)空間利用率較高。

近年來，為了提升近鄰檢索性能，人們提出了不同種類的哈希算法。王妙等人[1]在神經(jīng)網(wǎng)絡(luò)層中加入了哈希層，可實(shí)現(xiàn)分級(jí)檢索策略，其先利用哈希碼得到粗檢索結(jié)果，然后再根據(jù)圖像高層語(yǔ)義特征之間的歐式距離進(jìn)行精檢索，從而避免了檢索復(fù)雜度高以及內(nèi)存不足的問題。朱命冬等人[2]將LSH 算法應(yīng)用到二元混合類型數(shù)據(jù)（圖像-文本數(shù)據(jù)）的近鄰檢索任務(wù)中，提出利用LSH 構(gòu)建能有效融合兩種數(shù)據(jù)類型的相似性的混合索引，并將其用于最近鄰查詢。為了克服語(yǔ)義信息未被充分利用的局限性，段文靜等人[3]提出在一個(gè)深度網(wǎng)絡(luò)框架內(nèi)同時(shí)利用成對(duì)標(biāo)簽信息和分類信息學(xué)習(xí)哈希編碼。為了適應(yīng)分布式存儲(chǔ)數(shù)據(jù)的近鄰檢索需求，基于乘積量化的分布式哈希學(xué)習(xí)方法SparkPQ提出在Spark分布式計(jì)算框架下利用分布式乘積量化算法學(xué)習(xí)分布式數(shù)據(jù)的哈希編碼[4]。

根據(jù)訓(xùn)練過程是否依賴于數(shù)據(jù)集，可將現(xiàn)有哈希算法大致分為數(shù)據(jù)獨(dú)立哈希與數(shù)據(jù)依賴哈希。數(shù)據(jù)獨(dú)立哈希，如局部敏感哈希[5]，隨機(jī)生成線性哈希函數(shù)，并根據(jù)數(shù)據(jù)點(diǎn)與線性哈希函數(shù)的映射符號(hào)生成二值編碼。由于局部敏感哈希的訓(xùn)練過程不依賴于訓(xùn)練數(shù)據(jù)集，為了獲取較優(yōu)的近鄰檢索性能，所生成的二值編碼應(yīng)足夠長(zhǎng)。之后，為了確保采用緊湊二值編碼也能獲得令人滿意的近鄰檢索結(jié)果，人們提出了數(shù)據(jù)依賴哈希，其利用機(jī)器學(xué)習(xí)機(jī)制，生成符合數(shù)據(jù)集分布特性的哈希函數(shù)。譜哈希[6]（Spectral Hashing，SH）和錨圖哈希[7]（Anchor Graph Hashing，AGH）建立了數(shù)據(jù)點(diǎn)之間的相似性圖，并通過分割譜圖生成數(shù)據(jù)點(diǎn)的二值編碼，但其要求數(shù)據(jù)集服從均勻分布。迭代量化[8]（Iterative Quantization，ITQ）哈希建立了超立方體，旨在將超立方體頂點(diǎn)附近的樣本映射為相同的編碼。類似的，K-均值哈希[9]也將編碼中心點(diǎn)附近的數(shù)據(jù)點(diǎn)映射為相同的二值編碼，但其要求編碼中心點(diǎn)能夠同時(shí)最小化量化誤差和相似性誤差，從而確保編碼中心點(diǎn)能夠適應(yīng)于數(shù)據(jù)集的分布特性。譜哈希[6]、錨圖哈希[7]、迭代量化哈希[8]和K-均值哈希[9]旨在將相似或相同的樣本映射為相近或相同的二值編碼，其適用于語(yǔ)義相似性檢索任務(wù)。

相對(duì)而言，近似近鄰檢索任務(wù)更加關(guān)注數(shù)據(jù)點(diǎn)之間的相對(duì)相似性。為此，人們提出了序列保持哈希[1，10-11]，要求在漢明空間內(nèi)保持?jǐn)?shù)據(jù)點(diǎn)之間的原歐式序列關(guān)系。最小損失哈希[10]定義了鉸鏈損失函數(shù)，懲罰漢明距離較大的相似數(shù)據(jù)點(diǎn)或漢明距離較小的非相似數(shù)據(jù)點(diǎn)。與最小損失哈希[10]類似，鉸鏈損失哈希[11]也利用三元組之間的相似性關(guān)系近似序列損失。三元損失哈希[12]要求相似數(shù)據(jù)點(diǎn)之間的漢明距離值應(yīng)遠(yuǎn)小于非相似數(shù)據(jù)點(diǎn)之間的漢明距離值。序列保持哈希[13]（Order Preserving Hashing，OPH）根據(jù)數(shù)據(jù)點(diǎn)與查詢數(shù)據(jù)點(diǎn)之間的距離，將其分成不同的類，并力求在漢明空間和歐式空間內(nèi)同時(shí)最小化類間與類內(nèi)誤差，從而可確保在漢明空間內(nèi)保持?jǐn)?shù)據(jù)點(diǎn)之間的原序列關(guān)系。為了進(jìn)一步增強(qiáng)序列保持性能，序列約束二值編碼[1]建立了基于四元組的序列保持約束條件，要求任意四元組在漢明空間和歐式空間內(nèi)具有相同的序列關(guān)系。

通常，上述語(yǔ)義哈希和序列保持哈希認(rèn)為所有比特位具有相同的權(quán)重值，且漢明距離為離散整數(shù)值，使得一些編碼不同的數(shù)據(jù)點(diǎn)與查詢數(shù)據(jù)點(diǎn)之間具有相同的漢明距離[4，13]。如編碼為“01”和“10”的數(shù)據(jù)點(diǎn)與編碼為“00”的數(shù)據(jù)點(diǎn)之間的漢明距離均為1，從而無(wú)法正確區(qū)分這些數(shù)據(jù)點(diǎn)在近鄰檢索中的排序。為了解決這一問題，人們提出比特位加權(quán)算法，根據(jù)比特位的重要程度為其賦予不同的權(quán)重值，并根據(jù)加權(quán)漢明距離進(jìn)一步區(qū)分漢明距離相同的數(shù)據(jù)點(diǎn)之間的相似度。QaRank 算法[14]根據(jù)數(shù)據(jù)點(diǎn)之間的加權(quán)漢明距離和歐式距離，將數(shù)據(jù)點(diǎn)分成不同的類別，并要求最小化類內(nèi)與類間誤差，且同時(shí)保持各個(gè)類之間的相對(duì)相似性關(guān)系。查詢敏感比特位權(quán)值算法[15]（QsRank）根據(jù)原始浮點(diǎn)數(shù)據(jù)以及近鄰半徑計(jì)算比特位權(quán)值，其能有效提升主成分分析哈希的近鄰檢索性能。加權(quán)漢明距離算法要求比特位權(quán)值應(yīng)符合訓(xùn)練數(shù)據(jù)集的分布特性，且對(duì)查詢數(shù)據(jù)點(diǎn)較敏感。與上述比特位權(quán)值算法不同，本文所提出的模糊序列感知哈希直接利用二值編碼本身的信息區(qū)分具有相同漢明距離的數(shù)據(jù)點(diǎn)對(duì)之間的相似度，如圖1所示。為了保證所生成的二值編碼能夠滿足近鄰檢索任務(wù)的需求，定義了類似于平均準(zhǔn)確率的序列保持約束條件，但仍會(huì)有編碼不同的樣本共享相同的漢明距離，且無(wú)法正確區(qū)分它們的序列關(guān)系，如近鄰檢索結(jié)果（e）所示。為了解決這一問題，在訓(xùn)練階段中引入首位區(qū)分規(guī)則，并學(xué)習(xí)滿足這一規(guī)則的哈希函數(shù)，從而可在近鄰檢索結(jié)果中利用此規(guī)則區(qū)分漢明距離相同但編碼不同的數(shù)據(jù)點(diǎn)對(duì)之間的相似度，使得近鄰檢索結(jié)果唯一，且性能較優(yōu)，如檢索結(jié)果（f）所示。

圖1 模糊序列感知哈希算法流程圖

本文的創(chuàng)新點(diǎn)如下：

（1）提出首位區(qū)分規(guī)則，依據(jù)二值編碼本身信息區(qū)分模糊序列，與傳統(tǒng)比特位權(quán)值算法相比，在近鄰檢索過程中無(wú)需額外計(jì)算比特位權(quán)值與加權(quán)漢明距離，降低了近鄰檢索過程的復(fù)雜度。

（2）建立了類似于平均準(zhǔn)確率的目標(biāo)函數(shù)，其屬于序列保持約束條件，可確保所生成的二值編碼能夠滿足近鄰檢索任務(wù)需求。

（3）提出了二值編碼、漢明距離和判斷函數(shù)的連續(xù)化松弛策略，從而可直接采用批量梯度下降算法優(yōu)化目標(biāo)函數(shù)。

2 模糊序列感知哈希

2.1 首位區(qū)分規(guī)則

基于哈希的圖像近鄰檢索算法[3，8]主要包含兩個(gè)步驟，其先生成圖像的浮點(diǎn)特征（如全局特征描述子GIST），再利用哈希函數(shù)H(x)={h1(x),h2(x),…,hM(x)}將浮點(diǎn)特征映射成M位二值編碼B={b1,b2,…,bM}。從而，可根據(jù)浮點(diǎn)特征對(duì)應(yīng)的二值編碼之間的漢明距離檢索圖像近鄰。hm(x)表示第m位哈希函數(shù)，其常被定義為線性函數(shù)hm(x)=wTm x，wm為哈希函數(shù)hm(x)的系數(shù)。bm(x)表示第m位比特編碼，其值由數(shù)據(jù)點(diǎn)x與線性哈希函數(shù)hm(x) 的映射符號(hào)決定，即bm(x)=sgn(hm(x))。

通常，認(rèn)為所有比特位的重要程度是相同的[1，9]，且漢明距離為離散整數(shù)值，導(dǎo)致一些編碼不同的數(shù)據(jù)點(diǎn)與查詢數(shù)據(jù)點(diǎn)之間具有相同的漢明距離，從而無(wú)法準(zhǔn)確區(qū)分它們?cè)诮彊z索結(jié)果中的排序[15-16]，并且不同序列的近鄰檢索性能差異較大。如圖2所示，數(shù)據(jù)點(diǎn)被映射為3 bit 的二值編碼，樣本a 的編碼為“000”，樣本b、c、d 的編碼分別為“011”“101”“110”。在歐式空間內(nèi)樣本 b 為樣本a 的真正近鄰點(diǎn)，但在漢明空間內(nèi)檢索樣本a 的近鄰點(diǎn)時(shí)，樣本b、c、d 與樣本a 之間的漢明距離均為2，它們?cè)跐h明空間內(nèi)的排序是隨機(jī)的，將產(chǎn)生多種不同的近鄰檢索結(jié)果，并且根據(jù)近鄰檢索性能評(píng)價(jià)指標(biāo)，只存在一種最優(yōu)的近鄰檢索結(jié)果。

圖2 模糊序列導(dǎo)致多種不同近鄰檢索結(jié)果

為了解決上述模糊排序問題，可利用比特位權(quán)值算法[15-16]根據(jù)比特位的重要程度或區(qū)分度，賦予每個(gè)比特位相應(yīng)的權(quán)重值，從而可根據(jù)加權(quán)漢明距離進(jìn)一步區(qū)分漢明距離相同的數(shù)據(jù)點(diǎn)之間的近鄰排序。然而，比特位權(quán)值算法需要額外學(xué)習(xí)比特位權(quán)值函數(shù)，并且在檢索過程中需要計(jì)算加權(quán)漢明距離，增加了訓(xùn)練和檢索過程的計(jì)算復(fù)雜度。

在本文中，提出直接借助二值編碼自身的信息區(qū)分模糊排序。在近鄰檢索結(jié)果中，若有多個(gè)數(shù)據(jù)點(diǎn)與查詢數(shù)據(jù)點(diǎn)具有相同的漢明距離，則依次比較這些樣本點(diǎn)與查詢數(shù)據(jù)點(diǎn)的編碼，并優(yōu)先返回最先出現(xiàn)不同值的樣本。若有多個(gè)樣本同時(shí)出現(xiàn)不同值，則繼續(xù)依次比較剩余位，直至能夠正確區(qū)分所有樣本的近鄰排序。例如，對(duì)于圖2 中的模糊序列，可定義比較順序?yàn)閺挠抑磷螅瑯颖綽、c與樣本a在第1位具有不同的編碼，二者在近鄰檢索結(jié)果中的排序應(yīng)在樣本d 之前。但此時(shí)仍無(wú)法正確區(qū)分樣本b、c 之間的排序，則繼續(xù)依次向后比較，樣本b 與樣本a 在第2 位具有不同的編碼，因此優(yōu)先返回樣本b。最終，可得到樣本a 的近鄰檢索結(jié)果為b、c、d。綜上，首位區(qū)分規(guī)則能夠區(qū)分漢明距離相同但編碼不同的樣本在近鄰檢索結(jié)果中的序列。

基于首位區(qū)分規(guī)則的比特位權(quán)值算法與傳統(tǒng)加權(quán)算法均賦予比特位不同的權(quán)重值，并根據(jù)加權(quán)漢明距離檢索近鄰點(diǎn)。傳統(tǒng)加權(quán)算法在近鄰檢索過程中需要考慮所有比特位的值，其近鄰檢索復(fù)雜度為O(M)，M為數(shù)據(jù)點(diǎn)被映射為二值編碼的長(zhǎng)度。相對(duì)而言，當(dāng)首次出現(xiàn)值不相同的比特位時(shí)，基于首位區(qū)分規(guī)則的近鄰檢索算法便可有效區(qū)分?jǐn)?shù)據(jù)點(diǎn)在近鄰檢索結(jié)果中的相對(duì)排序，其近鄰檢索時(shí)間復(fù)雜度僅為O(lbM)。

首位區(qū)分規(guī)則要求，若數(shù)據(jù)點(diǎn)的第1 至m-1 位的比特值相同，則第m位具有優(yōu)先決定權(quán)，即第m位的權(quán)重值應(yīng)大于之后所有比特位的權(quán)重值之和，其形式化定義如公式（1）所示：

bit_weight(m)表示第m位比特位的權(quán)重值。為了保證比特位權(quán)重值能夠滿足公式（1）所定義的約束條件，比特位的權(quán)重值應(yīng)呈指數(shù)冪增長(zhǎng)。每個(gè)比特位的最大取值為1，為了保證計(jì)算加權(quán)漢明距離時(shí)在任意比特位上均不產(chǎn)生溢出，需將指數(shù)冪的底數(shù)設(shè)定為大于2的數(shù)值。在本文中，利用梯度下降算法優(yōu)化目標(biāo)函數(shù)，為了方便計(jì)算加權(quán)漢明距離的導(dǎo)數(shù)，冪指數(shù)的底數(shù)取值為10。綜上，可預(yù)先定義第m位比特位的權(quán)重值為eM-m，并采用公式（2）定義基于首位區(qū)分規(guī)則的加權(quán)漢明距離。

接下來，要解決的問題是如何保證采用首位區(qū)分規(guī)則能夠得到較優(yōu)的近鄰檢索結(jié)果。

2.2 序列保持約束

語(yǔ)義相似性保持哈希[7-8]強(qiáng)調(diào)將相似數(shù)據(jù)點(diǎn)映射為相同或相近的二值編碼，其適應(yīng)于語(yǔ)義相似性檢索任務(wù)。相對(duì)而言，近鄰檢索任務(wù)更強(qiáng)調(diào)數(shù)據(jù)點(diǎn)之間的相對(duì)相似性關(guān)系。因此，為了在漢明空間內(nèi)得到較優(yōu)的近鄰檢索性能，需建立序列保持約束目標(biāo)。類似的，三元損失哈希[12]、鉸鏈損失哈希[11]和最小損失哈希[10]定義了基于三元組的序列保持約束，序列約束哈希[1]學(xué)習(xí)滿足基于四元組的序列保持約束條件的二值編碼。

在本文中，為了進(jìn)一步增強(qiáng)序列保持性能，定義了類似于近鄰檢索性能評(píng)價(jià)指標(biāo)平均準(zhǔn)確率（Average Precision，AP）的約束條件AP*，其要求在漢明空間內(nèi)每一個(gè)截?cái)鄈處得到的查詢樣本xq的近鄰點(diǎn)與原歐式空間內(nèi)的近鄰檢索結(jié)果是一致的，如公式（3）所示：

X為訓(xùn)練數(shù)據(jù)集，Nk(xq)為歐式空間內(nèi)查詢數(shù)據(jù)點(diǎn)xq的k近鄰集合，xj表示第j(j≤k)個(gè)近鄰數(shù)據(jù)點(diǎn)。I(·) 為判斷函數(shù)，要求(xq,xj) 之間的漢明距離應(yīng)小于(xq,xk)之間的漢明距離，若條件滿足，返回1，否則，返回0。在公式（3）中，采用2.1 節(jié)中定義的首位區(qū)分規(guī)則計(jì)算漢明序列公式（3）強(qiáng)調(diào)，返回不同數(shù)量 (k)的近鄰樣本，均具有較優(yōu)的檢索準(zhǔn)確率，其屬于序列保持約束條件，可保證得到較優(yōu)的近鄰檢索性能。

在本文中，采用批量梯度下降算法學(xué)習(xí)哈希函數(shù)。故而，將目標(biāo)函數(shù)定義為公式（4）所示：

2.3 松弛優(yōu)化

公式（4）所定義的目標(biāo)函數(shù)中含有二值編碼、漢明距離和判斷函數(shù)，其均為離散整數(shù)值，若直接采用批量梯度下降算法優(yōu)化原目標(biāo)函數(shù)，其為NP難問題。因此，需要對(duì)二值編碼、漢明距離以及判斷函數(shù)做連續(xù)化松弛處理。

對(duì)于二值編碼過程，可采用tanh（·）函數(shù)近似替代其中的符號(hào)函數(shù)，如公式（5）所示：

結(jié)合公式（5），可采用公式（6）重新定義基于首位區(qū)分規(guī)則的漢明距離：

在本文中，利用公式（7）近似替代原目標(biāo)函數(shù)中的判斷函數(shù)I(?)：

函數(shù)G(?)的定義如公式（8）所示：

在訓(xùn)練階段，分別利用公式（5）、（6）和（7）替代原有的二值編碼、漢明距離和判斷函數(shù)。采用批量梯度下降算法學(xué)習(xí)哈希函數(shù)hm時(shí)，目標(biāo)函數(shù)關(guān)于哈希函數(shù)系數(shù)wm的偏導(dǎo)數(shù)，如公式（9）所示：

數(shù)據(jù)點(diǎn)之間的漢明距離關(guān)于wm的偏導(dǎo)數(shù)如公式（11）所示：

在訓(xùn)練過程中，采用公式（12）更新哈希函數(shù)的系數(shù)，參數(shù)λ為更新速率。

當(dāng)8-點(diǎn)關(guān)聯(lián)一個(gè)3-面時(shí),類似于對(duì)7度點(diǎn)的討論,我們可以得出類似最壞情形，即在最壞情況下是8-點(diǎn)關(guān)聯(lián)著(3,3,8)-面,三面及面上的點(diǎn)最多從8-點(diǎn)拿走的權(quán)值為同理,對(duì)于9+-點(diǎn)也滿足同樣的結(jié)果，分別稱之為最壞3-面8-點(diǎn)情形和最壞3-面9+-點(diǎn)情形。

綜上，模糊序列感知哈希的偽代碼如算法1所示。

算法1模糊序列感知哈希

輸入：數(shù)據(jù)集X；編碼長(zhǎng)度：M

輸出：哈希函數(shù)的系數(shù)：W={w1,w2,…,wM}

1.隨機(jī)初始化W={w1,w2,…,wM}

2.將數(shù)據(jù)集X分成多個(gè)子集{X1,X2,…,Xn}

3.Fori=1:n

5.WhilexqinXi

6.采用首位決策規(guī)則計(jì)算xq在漢明空間的近鄰序列

7.利用公式（9）計(jì)算目標(biāo)函數(shù)對(duì)wm的偏導(dǎo)數(shù)

8.利用公式（12）更新wm的值

9.Until Convergence

10.End

11.End

在算法1中，采用隨機(jī)批量梯度下降算法迭代更新線性哈希函數(shù)。全部訓(xùn)練數(shù)據(jù)被分成n個(gè)子集，且每個(gè)子集中含有L個(gè)數(shù)據(jù)點(diǎn)。在每次迭代更新中，力求最小化數(shù)據(jù)點(diǎn)在歐式空間與漢明距離內(nèi)的序列誤差。本算法在線下預(yù)先計(jì)算數(shù)據(jù)點(diǎn)之間的歐式序列關(guān)系，線上訓(xùn)練時(shí)只需計(jì)算每個(gè)子集中數(shù)據(jù)點(diǎn)的基于首位區(qū)分規(guī)則的漢明近鄰序列，每個(gè)子集中含有L個(gè)數(shù)據(jù)點(diǎn)，其時(shí)間復(fù)雜度為O(LlbM)。在每個(gè)批次中，共需進(jìn)行L次更新，學(xué)習(xí)M個(gè)線性哈希函數(shù)，且全部數(shù)據(jù)被分為n個(gè)子集。綜上，算法1的訓(xùn)練時(shí)間復(fù)雜度為O(M?n?L2?lbM)。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

在本文中，分別在三種圖像數(shù)據(jù)集上設(shè)置了近鄰檢索對(duì)比實(shí)驗(yàn)，三種數(shù)據(jù)集分別為NUS-WIDE[17]、22K LabelME[18]和ImageNet 100。在近鄰檢索實(shí)驗(yàn)中，每種數(shù)據(jù)集均被分為三部分，訓(xùn)練數(shù)據(jù)集、待查詢數(shù)據(jù)集和測(cè)試數(shù)據(jù)集。

NUS-WIDE數(shù)據(jù)集[17]包含27萬(wàn)Flickr圖像，從中分別隨機(jī)選取19 萬(wàn)幅和5 萬(wàn)幅圖像作為待查詢數(shù)據(jù)集和測(cè)試數(shù)據(jù)集，并且訓(xùn)練數(shù)據(jù)集包含5 萬(wàn)幅圖像。22K LabelMe數(shù)據(jù)集[18]為不含標(biāo)簽的圖像集，共包含2.2萬(wàn)幅圖像，從中隨機(jī)選取2 萬(wàn)幅圖像作為待查詢數(shù)據(jù)集，其余2 000幅圖像作為測(cè)試集，并從中隨機(jī)選取5 000幅圖像作為訓(xùn)練數(shù)據(jù)集。ImageNet 100 是ImageNet 圖像集的子集，共包含100 類圖像，隨機(jī)選取13 萬(wàn)幅圖像作為待查詢數(shù)據(jù)集，3萬(wàn)幅圖像作為訓(xùn)練數(shù)據(jù)集，1萬(wàn)幅圖像作為測(cè)試數(shù)據(jù)集。

在本文中，分別采用召回率（recall）和平均均勻準(zhǔn)確率（mAP）評(píng)價(jià)近鄰檢索性能。召回率的定義如公式（13）所示，其表示檢索到的正樣本的數(shù)量占所有正樣本數(shù)量的比重，#（檢索到的正樣本）表示檢索到的正樣本的數(shù)量，#（正樣本）表示數(shù)據(jù)集中所有正樣本的數(shù)量。然而，召回率無(wú)法衡量正樣本的返回速率。為此，將進(jìn)一步采用平均均勻準(zhǔn)確率衡量近鄰檢索性能，其定義如公式（14）所示，|Q|表示查詢樣本的數(shù)量，Kn表示第n個(gè)樣本的真實(shí)近鄰點(diǎn)的數(shù)量，rank(j)表示第j個(gè)正樣本在查詢結(jié)果中的排序，由此可知，正樣本返回速率越快，其值越大。

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

在近鄰檢索對(duì)比實(shí)驗(yàn)中，先提取NUS-WIDE[17]、22K LabelMe[18]、ImageNet100 圖像集的 GIST 特征描述子，然后采用不同種類的哈希算法分別將圖像的GIST特征映射為32位、64位二值編碼，并根據(jù)漢明距離檢索近鄰點(diǎn)，其實(shí)驗(yàn)結(jié)果如圖3～5 和表1～3 所示。在召回率曲線圖中，橫坐標(biāo)為返回的近鄰點(diǎn)數(shù)量，縱坐標(biāo)為召回率，M表示二值編碼長(zhǎng)度，NN表示在原歐式空間內(nèi)真正近鄰點(diǎn)的數(shù)量。

圖3 在22K LabelMe數(shù)據(jù)集上的近鄰檢索性能召回率曲線

圖4 在NUS-WIDE數(shù)據(jù)集上的近鄰檢索性能召回率曲線

圖5 在ImageNet 100數(shù)據(jù)集上的近鄰檢索性能召回率曲線

表1 在22K LabelMe數(shù)據(jù)集上的平均均勻準(zhǔn)確率值 %

表2 在NUS-WIDE數(shù)據(jù)集上的平均均勻準(zhǔn)確率值%

表3 在ImageNet 100數(shù)據(jù)集上的平均均勻準(zhǔn)確率值 %

局部敏感哈希[5]（LSH）隨機(jī)生成線性映射函數(shù)，訓(xùn)練過程不依賴于數(shù)據(jù)集，近鄰檢索性能不能隨著編碼長(zhǎng)度的增加而顯著提升，且本文所采用的均是緊湊二值編碼，故而局部敏感哈希[5]的近鄰檢索性能相對(duì)較弱。錨圖哈希[7]（AGH）采用K均值算法學(xué)習(xí)數(shù)據(jù)集的錨點(diǎn)，并通過分割錨點(diǎn)之間的相似性譜圖生成數(shù)據(jù)集的二值編碼，以確保相似數(shù)據(jù)點(diǎn)被映射為相同編碼，其近鄰檢索性能優(yōu)于局部敏感哈希算法。錨圖哈希要求數(shù)據(jù)集服從于均勻分布，而本文所采用的真實(shí)數(shù)據(jù)集并不符合均勻分布，故而錨圖哈希的近鄰檢索性能仍相對(duì)較弱。迭代量化（ITQ）哈希[8]、K均值哈希[9]（KMH）、鉸鏈哈希[11]（RSH）、序列約束哈希[1]（OCH）以及模糊序列感知哈希（ARPH）不再要求訓(xùn)練數(shù)據(jù)滿足特定的分布特性，近鄰檢索性能優(yōu)于錨圖哈希。迭代量化哈希[8]將相似或相近的數(shù)據(jù)點(diǎn)映射至同一個(gè)正立方體頂點(diǎn)，并賦予相同的二值編碼。在迭代量化哈希算法中，正立方體的頂點(diǎn)是固定的，對(duì)數(shù)據(jù)集分布特性的自適應(yīng)能力較弱。相對(duì)而言，K均值哈希[9]（KMH）學(xué)習(xí)能夠同時(shí)最小化相似性誤差和量化誤差的頂點(diǎn)，使得編碼中心點(diǎn)與數(shù)據(jù)集的分布特性相符，故K均值哈希的近鄰檢索性能要優(yōu)于迭代量化哈希。K均值哈希[9]、迭代量化哈希[8]、錨圖哈希[7]以及局部敏感哈希[5]只關(guān)注數(shù)據(jù)點(diǎn)之間的相似性保持問題，而近鄰檢索算法更重視數(shù)據(jù)點(diǎn)之間的相對(duì)相似性。鉸鏈損失哈希[11]建立了基于三元組之間的相對(duì)相似性保持約束條件，序列約束保持哈希[1]建立了基于四元組之間的相對(duì)相似性保持約束條件。模糊序列感知哈希建立了類似于均勻準(zhǔn)確率的目標(biāo)，要求在每一個(gè)截?cái)鄈處，在漢明空間與歐式空間內(nèi)得到的近鄰檢索結(jié)果是相同的，其屬于序列保持約束。從而可知，鉸鏈損失哈希[11]、序列約束保持哈希[1]以及模糊序列感知哈希關(guān)注如何保持?jǐn)?shù)據(jù)點(diǎn)之間的序列關(guān)系，更適應(yīng)于近鄰檢索任務(wù)，性能相對(duì)較優(yōu)。但是，鉸鏈損失哈希與序列約束保持哈希未關(guān)注近鄰檢索中的模糊序列問題，對(duì)于與查詢數(shù)據(jù)點(diǎn)具有相同漢明距離的數(shù)據(jù)點(diǎn)，采用隨機(jī)排序的規(guī)則，使得算法性能的穩(wěn)定性較差。模糊序列感知哈希定義了首位區(qū)分規(guī)則，并學(xué)習(xí)滿足這一規(guī)則的序列保持二值編碼，從而可有效區(qū)分近鄰檢索中的模糊序列，算法性能較穩(wěn)定。在三種大型圖像數(shù)據(jù)集上的近鄰檢索實(shí)驗(yàn)也證明了，模糊序列感知哈希具有較優(yōu)的近鄰檢索性能。

4 結(jié)束語(yǔ)

基于哈希的圖像近鄰檢索算法將圖像高維浮點(diǎn)描述子映射成二值編碼，并在漢明空間內(nèi)檢索圖像近鄰，其具有響應(yīng)速率快、存儲(chǔ)空間小的優(yōu)勢(shì)，已經(jīng)得到廣泛應(yīng)用。一般哈希算法認(rèn)為所有比特位具有相同的權(quán)重值，且漢明距離為離散整數(shù)值，從而使得編碼不同的數(shù)據(jù)點(diǎn)與同一查詢數(shù)據(jù)點(diǎn)具有相同的漢明距離，這將導(dǎo)致序列模糊問題。為了解決這一問題，本文提出了首位區(qū)分規(guī)則，優(yōu)先返回最早出現(xiàn)不同比特值的數(shù)據(jù)點(diǎn)，并在訓(xùn)練過程中學(xué)習(xí)滿足首位區(qū)分規(guī)則的哈希函數(shù)，從而可直接根據(jù)二值編碼本身的信息區(qū)分模糊序列。與比特位權(quán)值算法相比，無(wú)需額外計(jì)算比特位權(quán)值與加權(quán)漢明距離，查詢復(fù)雜度相對(duì)較低。學(xué)習(xí)哈希函數(shù)時(shí)，定義了類似于均勻準(zhǔn)確率的約束目標(biāo)，其屬于序列保持約束條件，可確保在漢明空間內(nèi)得到較優(yōu)的近鄰檢索性能。在訓(xùn)練過程中，對(duì)符號(hào)函數(shù)、判斷函數(shù)以及漢明距離均做了松弛連續(xù)化處理，從而可利用隨機(jī)梯度下降算法學(xué)習(xí)滿足目標(biāo)約束條件的哈希函數(shù)。在三種圖像數(shù)據(jù)集上的近鄰檢索對(duì)比實(shí)驗(yàn)也證明了，本文所提哈希算法具有較優(yōu)的近鄰檢索性能。