Deep Supervised Hashing for Fast Image Retrieval
Abstract
在本文中，我們提出了一種新的哈希方法來學習緊湊的二進制碼，以便在大規模資料集上高效地檢索圖像。而複雜的圖像外觀變化仍然對可靠的檢索構成巨大的挑戰,根據在不同的視覺任務上學習魯棒圖像表征的卷積神經網絡(CNN)的最新進展 ,本文提出了一種新的深度監督哈希(Deep Supervised Hashing，DSH)方法，為大規模資料集學習緊湊的similarity-preserving二進制編碼。具體來說，我們設計了一種CNN架構，它以圖像對(相似/不相似)作為訓練輸入，并鼓勵每個圖像的輸出近似離散值(例如+1/-1)。為此，我們精心設計了一個損失函數，通過對來自輸入圖像對的監督資訊進行編碼，同時對實值輸出進行正則化，以逼近所需的離散值，進而最大限度地提高輸出空間的可辨識性。在圖像檢索中，新出現的查詢圖像通過輸入網絡進行編碼，然後将網絡輸出量化成二進制編碼表征，可以很容易地對其進行編碼。在兩個大規模資料集CIFAR-10和NUS-WIDE上進行的大量實驗表明，與目前的研究相比，我們的方法具有良好的性能。
1. Introduction
近年來，網際網路上每天都有數十萬張圖檔被上傳到網上，根據不同使用者的要求尋找相關圖檔變得極為困難。例如，基于内容的圖像檢索檢索,即得到與給定查詢圖像相似的圖像，其中“相似”可能指視覺上相似或語義上相似。假設資料庫中的圖像和查詢圖像都用實值特征表示，尋找相關圖像的最簡單方法是根據資料庫圖像在特征空間中與查詢圖像的距離對資料庫圖像進行排序，并傳回最接近的圖像。然而，對于擁有數百萬幅圖像的資料庫，即使是在資料庫中進行線性搜尋，也會耗費大量的時間和記憶體。
為了解決實值特征效率低的問題，提出了一種哈希方法，将圖像映射到緊湊的二進制編碼中，可以近似地保留原始空間中的資料結構[27,9,17]。由于圖像采用二進制編碼而不是實值特征表示，大大減少了搜尋的時間和記憶體開銷。然而，現有的大多數哈希方法的檢索性能在很大程度上依賴于所使用的特征，這些特征基本上是無監督提取的，是以更适合于處理視覺相似度搜尋，而不是語義相似度搜尋。另一方面，近年來在圖像分類[12,25,8]、目标檢測[26]、人臉識别[24]等許多視覺任務[18,2]的研究進展顯示出CNN神經網絡令人印象深刻的學習能力。在這些不同的任務中，網絡神經網絡可以被看作是一個特征提取器，該特征提取器由專門為單個任務設計的目标函數指導。網絡神經網絡在各種任務中的成功應用表明，盡管圖像存在顯著的外觀變化，但網絡神經網絡學習到的特征能夠很好地捕捉圖像的底層語義結構。
受CNN特性的魯棒性啟發，我們提出了一個利用CNN結構的二進制編碼學習架構，名為深度監督哈希(Deep Supervised Hashing，DSH)。在我們的方法中，我們首先設計了一個CNN模型，它将圖像對以及表示兩幅圖像是否相似的标簽作為訓練輸入，并生成二進制編碼作為輸出，如圖1所示。在實際操作中，我們線上生成圖像對，以便在訓練階段使用更多的圖像對。損失函數的設計目的是将相似圖像的網絡輸出拉到一起，将不同圖像的輸出推開，使學習的hamming空間能夠很好地逼近圖像的語義結構。為了避免對hamming空間的不可微損失函數進行優化，将網絡輸出放寬為實值，同時使用正則化器使實值輸出逼近期望的離散值。在這個架構下，圖像可以很容易地編碼，首先通過網絡傳播，然後量化網絡輸出的二進制編碼表征。
本文的其餘部分組織如下:第2節讨論與我們的方法相關的工作。第3節較長的描述了DSH。第4節在兩個大資料集上廣泛地評價了提出的方法。第5節作結束語。
2. Related Works
許多哈希方法[4,28,13,27,6,20,17,22,16,23,15,29,31,14]由于其較低的時間和空間複雜度，已經被提出來提高近似最近鄰搜尋的性能。在早期，研究人員主要關注于資料無關的哈希方法，如稱為局部性敏感哈希(Locality Sensitive Hashing，LSH)[4]的一組方法。LSH方法使用随機投影産生哈希位。理論上證明了随着碼長的增加，兩個二進制碼之間的hamming距離在特征空間中漸近于對應的距離。然而，LSH方法通常需要很長的編碼才能達到令人滿意的性能，這就需要大量的記憶體。
為了産生更緊湊的二進制碼，提出了依賴資料的哈希方法。這些方法嘗試從訓練集學習保持相似的哈希函數。這些方法可以進一步分為無監督方法和有監督(半監督)方法。無監督方法隻利用無标記的訓練資料來學習哈希函數。例如，光譜哈希(Spectral Hashing, SH)[28]使圖像對的權重漢明距離最小化，其中權值定義為圖像對的相似度度量;疊代量化(Iterative Quantization，ITQ)[6]試圖最小化投影圖像描述符的量化誤差，以緩解實值特征空間與二值漢明空間的差異造成的資訊損失。
為了處理更複雜的語義相似度，提出了利用标簽資訊如類别标簽的監督方法。CCA-ITQ[6]是ITQ的擴充，它使用标簽資訊為圖像描述符找到更好的投影;可預測的判别二進制碼(Predictable Discriminative Binary Code, DBC)[22]尋找能分割具有大邊際的類别的超平面作為哈希函數;最小損失哈希(Minimal Loss Hashing，MLH)[20]優化了hinge-like損失的上界，以學習哈希函數。另一方面，半監督哈希(Semi-Supervised Hashing，SSH)[27]利用大量的未标記資料來規範化哈希函數。上述方法使用線性投影作為哈希函數，很難處理線性不可分的資料。為了克服這一局限性，提出了帶核的監督哈希(Supervised Hashing with Kernels，KSH)[17]和二進制重構嵌入(Binary Reconstructive Embedding，BRE)[13]哈希函數，在核空間中學習保持相似的哈希函數 ; 深度哈希(Deep Hashing，DH)[3]利用非線性深度網絡産生二進制編碼。大多數哈希方法在優化時将二進制碼放寬為實數，并将模型輸出量化以生成二進制碼。但是，不能保證最優實值編碼在量化後仍然是最優的。是以提出了離散圖哈希(Discrete Graph Hashing，DGH)[16]和監督離散哈希(Supervised Discrete Hashing，SDH)[23]等方法直接對二進制碼進行優化，克服了松弛法的缺點，提高了檢索性能。
雖然上述的哈希方法在一定程度上取得了成功，但它們都使用了手工制作的特征，無法捕獲真實資料中巨大的外觀變化下的語義資訊，進而限制了學習的二進制編碼的檢索精度。為了解決這個問題，最近，幾種基于CNN的哈希方法[31,14,29,15,30]被提出來，使用前景良好的CNN學習圖像表征和二進制編碼。[31, 14, 30]強制網絡學習保留triplets圖像語義關系的類二進制輸出;[29]訓練一個CNN來拟合由pairwise相似度矩陣計算出的二進制編碼;[15]以類二進制隐藏層作為圖像分類任務的特征訓練模型。這些方法将圖像特征提取與二進制編碼學習相結合，大大提高了檢索精度。然而，這些方法在訓練目标上仍然存在一些缺陷，這限制了它們的實際檢索性能，我們将在實驗中詳細說明。此外，他們用來近似量化步驟的非線性激活以可能減慢網絡訓練[12]為代價進行操作。
3. Approach
我們的目标是學習圖像的緊湊二進制編碼，這樣:(a)相似的圖像應該被編碼到漢明空間相似的二進制編碼，反之亦然;(b)二進制編碼可以有效地計算。
盡管已有許多哈希方法被提出來學習保持相似性的二進制編碼，但它們都受到手工特征或線性投影的限制。強大的非線性模型被稱為CNNs，它促進了最近計算機視覺社群在各種任務上的成功。為此，我們提出使用如圖1所示的CNN去同時學習可辨識的圖像表征和緊湊的二進制編碼，可以突破手工特征和線性模型的局限性。我們的方法首先使用圖像對和相應的相似度标簽來訓練CNN。在這裡，損失函數被精心設計來學習保持相似的類二值圖像表征。然後對CNN輸出進行量化，生成新的圖像的二進制編碼。
3.1. Loss Function
讓
表示RGB空間，我們的目标是學習一個從
映射到k-bits二進制編碼的：
，使相似的(無論是在視覺上相似的還是在語義上相似的)圖像被編碼成相似的二進制編碼。為了達到這一目的，相似圖像的編碼應該盡可能的接近，不同圖像的編碼應該遠離。基于這個目标，loss函數自然被設計成将相似圖像的編碼拉到一起，将不同圖像的編碼推開。
具體地說,一副圖像I1、I2∈Ω,對應的二進制網絡輸出為 b1, b2∈{+ 1−1}k, 如果他們是相似的，我們定義y = 0,否則和y = 1。對兩幅圖像的損失定義為:
其中Dh(.,.)表示兩個二進制向量之間的hamming距離，m > 0是一個邊際門檻值參數。第一項懲罰映射到不同的二進制編碼的相似圖像,第二項在映射到相近二進制編碼的不相似圖像的hamming距離低于邊際門檻值m時進行懲罰。這裡值得注意的是,為了避免崩潰,我們的損失函數采取了類似[7]的contrastive損失,隻有那些距離在一個半徑内的不相似圖像對有資格貢獻自己的損失函數（其實就是差距過大的不相似圖像對訓練網絡沒什麼用）。
假設這裡有N對随機從訓練圖像
中采樣的訓練圖像對，我們的目标是最小化總體的損失函數：
3.2. Relaxation
直接優化等式(2)可能更好，但由于bi,j的二值限制要求對網絡輸出進行門檻值化(如用signum函數)，使得用反向傳播算法訓練網絡變得棘手，是以不可行。最近的一些研究[23,16]提出了直接優化二進制編碼的方法，但是由于記憶體的限制，CNN模型隻能通過小批量進行訓練，當批量大小相對于整個訓練集非常小時，生成的二進制編碼的最優性存在問題。
另一方面，如果完全忽略二進制限制，則會由于歐幾裡得空間和漢明空間的差異而導緻二進制編碼效果次優，而不是最優。一個常用的松弛方案是利用sigmoid或tanh函數來逼近門檻值化過程（即+1，-1）。然而，使用這種非線性函數将不可避免地減慢甚至抑制網絡[12]的收斂。為了克服這種限制，在本研究中，我們提出在實值網絡輸出上加一個正則化器，以接近期望的離散值(+1/-1)。其中，我們将Eqn.(1)中的漢明距離替換為歐幾裡得距離，并附加一個正則化器來替換二進制限制，則等式(1)改寫為:
其中下标r為松弛損失函數，1為值全1的向量，||·||1為向量的L1範數，|·|為基于元素的絕對值運算，α為控制正則化器強度的權重參數。
這裡我們使用L2範數來度量網絡輸出之間的距離，因為低階範數産生的子梯度将不同距離的圖像對平等對待，沒有利用到不同距離大小所涉及的資訊。雖然高階範數也是可行的，但同時會産生更多的計算量。對于正則化器，我們選擇了L1範數而不是高階範數，因為它的計算量小得多，有利于加快訓練過程。
通過将等式(3)代入等式(2)，我們将重新定義的總損失函數改寫為:
針對此目标函數，采用小批量梯度下降法的反向傳播算法對網絡進行訓練。為此,等式(4)關于bi, j,∀i, j的梯度需要計算。由于目标函數中的max運算和絕對值運算在某些點上不可微，是以我們改用子梯度，并将這些點上的子梯度定義為1。等式(4)前兩項的子梯度和第三項(即正則化器)的子梯度分别改寫為:
這是基于元素的。通過在mini-batch上計算子梯度，可以以标準方式完成其餘的反向傳播。
Discussion: 在這樣的架構下，用sign(b)很容易得到圖像的二進制編碼。注意，與現有的基于CNN的哈希方法[29,15,14,31,30]不同，我們的方法沒有使用飽和非線性，例如tanh或sigmoid來近似量化步驟，因為這些非線性可能會減慢訓練過程[12]。第4.2節中的實驗将驗證該歸一化器相對于飽和非線性的優勢。
3.3. Implementation details
Network parameters: 我們的DSH方法是用Caffe[10]實作的。網絡結構如圖1所示，它由三個卷積池層和兩個全連接配接的層組成。卷積層分别使用32、32和64個步長為1的5×5的filter, pooling使用步長為2的3×3的window。第一個全連接配接層有500個節點，第二個全連接配接層有k個節點，其中k為二進制編碼的長度。所有卷積層和第一個全連接配接層後均配置ReLU[19]。
權重層使用“Xavier”初始化[5]進行初始化。在訓練期間，batch size被設定為200，momentum為0.9，權重衰減為0.004。初始學習率設定為10-3，每20,000次疊代(共150,000次疊代)後降低40%。等式(4)中的邊際m被啟發式地設定為m = 2k，以鼓勵不同圖像的編碼差異不小于k/2 bits。
Training methodology: 一種直覺的訓練網絡的方法是使用Siamese結構[7]和離線生成圖像對。然而，在這樣的方案下，處理n幅圖像隻能産生n/2個有效圖像對，存儲這些圖像對會占用很大的空間。為了更好地利用計算資源和存儲空間，我們建議利用每個小批進行中的所有唯一圖像對線上生成圖像對。為了跨batches覆寫這些圖像對，在每次疊代時從整個訓練集中随機選取訓練圖像。這樣，我們的方法減少了存儲整個成對相似矩陣的需要，是以可擴充到大規模資料集。
此外，為了學習對應于不同編碼長度的模型，如果一個人選擇從頭開始訓練每個模型，這将是種嚴重的浪費，因為前面的層可以被這些模型共享。此外，随着代碼長度的增加，模型在輸出層會包含更多的參數，進而容易發生過拟合。為了克服這種限制，我們建議先訓練一個輸出層節點較少的網絡，然後對其進行微調，得到具有所需編碼長度的目标模型。
4. Experiments
省略
5. Conclusion
我們将DSH的檢索性能歸功于三個方面:第一，利用非線性特征學習和哈希編碼的耦合來提取特定任務的圖像表征;其次，所提出的用于減小實值網絡輸出空間與期望漢明空間誤差的正則化器;第三，線上生成了密集的成對監督來很好地描述期望的漢明空間。在效率方面，實驗表明，該方法比傳統的散列方法編碼新圖像的速度更快。由于我們目前的架構是相對通用的，更複雜的網絡結構也可以很容易地利用。此外，本研究中對“網絡內建”的初步研究證明，這是一種很有前途的方法，值得我們進一步研究，以提高檢索性能。