模糊序列感知哈希

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

山東理工大學 計算機科學與技術學院，山東 淄博 255000

1 引言

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

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

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

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

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

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

本文的創新點如下：

（1）提出首位區分規則，依據二值編碼本身信息區分模糊序列，與傳統比特位權值算法相比，在近鄰檢索過程中無需額外計算比特位權值與加權漢明距離，降低了近鄰檢索過程的復雜度。

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

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

2 模糊序列感知哈希

2.1 首位區分規則

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

通常，認為所有比特位的重要程度是相同的[1，9]，且漢明距離為離散整數值，導致一些編碼不同的數據點與查詢數據點之間具有相同的漢明距離，從而無法準確區分它們在近鄰檢索結果中的排序[15-16]，并且不同序列的近鄰檢索性能差異較大。如圖2所示，數據點被映射為3 bit 的二值編碼，樣本a 的編碼為“000”，樣本b、c、d 的編碼分別為“011”“101”“110”。在歐式空間內樣本 b 為樣本a 的真正近鄰點，但在漢明空間內檢索樣本a 的近鄰點時，樣本b、c、d 與樣本a 之間的漢明距離均為2，它們在漢明空間內的排序是隨機的，將產生多種不同的近鄰檢索結果，并且根據近鄰檢索性能評價指標，只存在一種最優的近鄰檢索結果。

圖2 模糊序列導致多種不同近鄰檢索結果

為了解決上述模糊排序問題，可利用比特位權值算法[15-16]根據比特位的重要程度或區分度，賦予每個比特位相應的權重值，從而可根據加權漢明距離進一步區分漢明距離相同的數據點之間的近鄰排序。然而，比特位權值算法需要額外學習比特位權值函數，并且在檢索過程中需要計算加權漢明距離，增加了訓練和檢索過程的計算復雜度。

在本文中，提出直接借助二值編碼自身的信息區分模糊排序。在近鄰檢索結果中，若有多個數據點與查詢數據點具有相同的漢明距離，則依次比較這些樣本點與查詢數據點的編碼，并優先返回最先出現不同值的樣本。若有多個樣本同時出現不同值，則繼續依次比較剩余位，直至能夠正確區分所有樣本的近鄰排序。例如，對于圖2 中的模糊序列，可定義比較順序為從右至左，樣本b、c與樣本a在第1位具有不同的編碼，二者在近鄰檢索結果中的排序應在樣本d 之前。但此時仍無法正確區分樣本b、c 之間的排序，則繼續依次向后比較，樣本b 與樣本a 在第2 位具有不同的編碼，因此優先返回樣本b。最終，可得到樣本a 的近鄰檢索結果為b、c、d。綜上，首位區分規則能夠區分漢明距離相同但編碼不同的樣本在近鄰檢索結果中的序列。

基于首位區分規則的比特位權值算法與傳統加權算法均賦予比特位不同的權重值，并根據加權漢明距離檢索近鄰點。傳統加權算法在近鄰檢索過程中需要考慮所有比特位的值，其近鄰檢索復雜度為O(M)，M為數據點被映射為二值編碼的長度。相對而言，當首次出現值不相同的比特位時，基于首位區分規則的近鄰檢索算法便可有效區分數據點在近鄰檢索結果中的相對排序，其近鄰檢索時間復雜度僅為O(lbM)。

首位區分規則要求，若數據點的第1 至m-1 位的比特值相同，則第m位具有優先決定權，即第m位的權重值應大于之后所有比特位的權重值之和，其形式化定義如公式（1）所示：

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

接下來，要解決的問題是如何保證采用首位區分規則能夠得到較優的近鄰檢索結果。

2.2 序列保持約束

語義相似性保持哈希[7-8]強調將相似數據點映射為相同或相近的二值編碼，其適應于語義相似性檢索任務。相對而言，近鄰檢索任務更強調數據點之間的相對相似性關系。因此，為了在漢明空間內得到較優的近鄰檢索性能，需建立序列保持約束目標。類似的，三元損失哈希[12]、鉸鏈損失哈希[11]和最小損失哈希[10]定義了基于三元組的序列保持約束，序列約束哈希[1]學習滿足基于四元組的序列保持約束條件的二值編碼。

在本文中，為了進一步增強序列保持性能，定義了類似于近鄰檢索性能評價指標平均準確率（Average Precision，AP）的約束條件AP*，其要求在漢明空間內每一個截斷k處得到的查詢樣本xq的近鄰點與原歐式空間內的近鄰檢索結果是一致的，如公式（3）所示：

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

在本文中，采用批量梯度下降算法學習哈希函數。故而，將目標函數定義為公式（4）所示：

2.3 松弛優化

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

對于二值編碼過程，可采用tanh（·）函數近似替代其中的符號函數，如公式（5）所示：

結合公式（5），可采用公式（6）重新定義基于首位區分規則的漢明距離：

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

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

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

數據點之間的漢明距離關于wm的偏導數如公式（11）所示：

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

當8-點關聯一個3-面時,類似于對7度點的討論,我們可以得出類似最壞情形，即在最壞情況下是8-點關聯著(3,3,8)-面,三面及面上的點最多從8-點拿走的權值為同理,對于9+-點也滿足同樣的結果，分別稱之為最壞3-面8-點情形和最壞3-面9+-點情形。

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

算法1模糊序列感知哈希

輸入：數據集X；編碼長度：M

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

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

2.將數據集X分成多個子集{X1,X2,…,Xn}

3.Fori=1:n

5.WhilexqinXi

6.采用首位決策規則計算xq在漢明空間的近鄰序列

7.利用公式（9）計算目標函數對wm的偏導數

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

9.Until Convergence

10.End

11.End

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

3 實驗

3.1 實驗設置

在本文中，分別在三種圖像數據集上設置了近鄰檢索對比實驗，三種數據集分別為NUS-WIDE[17]、22K LabelME[18]和ImageNet 100。在近鄰檢索實驗中，每種數據集均被分為三部分，訓練數據集、待查詢數據集和測試數據集。

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

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

3.2 實驗結果與分析

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

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

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

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

表1 在22K LabelMe數據集上的平均均勻準確率值 %

表2 在NUS-WIDE數據集上的平均均勻準確率值%

表3 在ImageNet 100數據集上的平均均勻準確率值 %

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

4 結束語

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