基于動態(tài)閾值哈希的大規(guī)模遙感影像快速內(nèi)容檢索方法

強永剛，肖志峰，陳歡歡，閆麗陽

(1. 中國科學技術大學計算機科學與技術學院，安徽 合肥 230027； 2. 武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢 430079)

隨著對地觀測技術的快速發(fā)展及高分辨率成像傳感器的廣泛使用，每天獲取的遙感影像數(shù)量呈現(xiàn)指數(shù)級增長的趨勢，使得大規(guī)模遙感影像數(shù)據(jù)庫的有效管理和檢索面臨著巨大挑戰(zhàn)?；趦?nèi)容的遙感影像檢索通過搜索并返回與查詢影像相關的影像，為大規(guī)模遙感影像檢索任務提供了可能的有效解決途徑，近年來受到眾多研究者的關注[1- 3]?；趦?nèi)容的大規(guī)模遙感影像檢索任務中，影像特征的長度及相似性度量方法將對檢索效率產(chǎn)生重要影響，尤其是在面對超大規(guī)模影像數(shù)據(jù)庫檢索任務的情景下[4- 7]。因此，如何通過構建高效的特征索引結構實現(xiàn)快速檢索是大規(guī)模影像檢索必須面對的問題[8]。針對以上問題，本文提出動態(tài)閾值哈希索引方法，該方法根據(jù)特征向量的空間分布情況動態(tài)生成向量的哈希編碼，對高維的遙感影像特征向量進行低維編碼，大大降低了檢索計算量，可顯著提高大規(guī)模遙感影像庫的檢索準確率和效率，可有效應用于大規(guī)模遙感影像檢索。

1 動態(tài)閾值哈希索引方法

由于遙感影像數(shù)據(jù)量巨大，常規(guī)特征提取方法往往提出了高維影像特征向量，此時進行特征向量的相似性度量需要消耗大量的時間，因此需要考慮建立高效的索引結構加快影像檢索的速度。本文基于局部敏感哈希(local sensitive hashing,LSH)算法的基本思想，提出一種動態(tài)閾值哈希索引方法，為海量影像的相似性度量和快速檢索提供思路，并將其應用于大規(guī)模遙感影像內(nèi)容檢索，減少影像檢索所需的時間。

1.1 局部敏感哈希原理

LSH算法是一種常見的用于處理高維特征向量索引問題的方法[9]，其基本思想為：將原始數(shù)據(jù)空間中的相鄰數(shù)據(jù)點通過某種哈希變換后，得到相同哈希結果的概率很大，而對于原始空間中不相鄰的數(shù)據(jù)點，得到相同哈希結果的概率很小。局部敏感哈希的具體方案依賴于所使用的局部敏感哈希函數(shù)[10]，對于位于Rd空間中的任意兩個向量p和q，如果存在函數(shù)族H，滿足以下條件，則稱H是(R,cR,p1,p2)敏感的。

(1) 如果‖p-q‖≤R，則PrH[h(p)=h(q)]≥p1。

(2) 如果‖p-q‖≥cR，則PrH[h(p)=h(q)]≤p2。

其中，PrH[h(p)-h(q)]表示p和q哈希結果相同的概率，c是一個不大于1的正數(shù)。

在對原始數(shù)據(jù)哈希映射之后，可以用所得二進制編碼之間的海明距離代替原空間中的距離計算方法計算特征向量之間的距離，在大大提高運算速度的基礎上，得到較為準確的近似最近鄰結果。

1.2 動態(tài)閾值哈希算法

基于深度卷積神經(jīng)網(wǎng)絡的遙感影像內(nèi)容檢索中[11- 13]，采用余弦相似度比較兩個特征向量之間的相似性。特征向量在比較距離之前進行了L2范數(shù)歸一化處理后所有的特征向量的長度為1。對于這種海量特征數(shù)據(jù)，可以采用一種按照各維度上數(shù)值的正負號進行哈希的方法劃分原始數(shù)據(jù)空間，其實質(zhì)是根據(jù)特征點分布在多維空間中的不同象限進行哈希分塊。若原始特征向量為F，其長度為D，特征經(jīng)過哈希所得的二進制編碼為C，則C中第位的值為

哈希后的二進制編碼長度仍為D，共有2D種哈希結果。對于二維特征向量，在平面中的劃分如圖1所示。

這種劃分方式有效地保持了向量之間的相似程度，余弦相似度大的向量被劃分到同一子空間的概率足夠大，而余弦相似度小的向量被劃分到同一子空間的概率很小，對于原始空間中更相似的特征向量，其對應的二進制編碼之間的海明距離更小。但若直接比較各維度上數(shù)值與0的大小，則可能喪失對實際數(shù)據(jù)的理解。實際數(shù)據(jù)在每一個維度上并不一定是以0作為中位數(shù)的分布，特別是當原始數(shù)據(jù)中某一維度上的取值全為正時，所有數(shù)據(jù)的哈希結果中對應的二進制位將全部被標記為1，無法產(chǎn)生理想的哈希效果。因此，可先通過訓練數(shù)據(jù)計算數(shù)據(jù)在這一維度上的中位數(shù)，代替原設計中的0，用于后續(xù)哈希計算，本文將這種方法稱為動態(tài)閾值哈希方法(dynamic threshold hashing,DTH)。若訓練數(shù)據(jù)中的特征向量總條數(shù)為M，則當處理到第i維時，首先計算所有訓練數(shù)據(jù)在第i維的中位數(shù)Ti

然后對于每條特征向量，根據(jù)Fi與Ti的大小關系確定哈希所得的二進制編碼C中第i位的值

圖2給出了分別使用0作為固定閾值進行哈希(如圖2(a)所示)和使用動態(tài)閾值進行哈希(如圖2(b)所示)的效果,可以明顯看出，使用動態(tài)閾值進行哈希能夠使數(shù)據(jù)劃分更加均勻。

實際應用中，二進制編碼的位數(shù)應該盡量短小，以保證存儲大規(guī)模的影像數(shù)據(jù)。因此，需要編碼的二進制位數(shù)N通常遠小于原始特征數(shù)據(jù)的維數(shù)，最基本的解決辦法是從原始數(shù)據(jù)中隨機抽取N個維度進行處理，但這種方法很難保證原始數(shù)據(jù)在所選取的維度上具有良好的區(qū)分能力。對原始高維特征數(shù)據(jù)進行降維處理[14]，然后再利用DTH方法對降維后的數(shù)據(jù)進行處理是一種可行的方案。

DTH作為一種動態(tài)哈希手段，可以對其他通過降維的特征進行動態(tài)哈希處理。若對原始數(shù)據(jù)進行主成分分析，將原始特征數(shù)據(jù)降維到N維，然后再使用動態(tài)閾值哈希方法對降維后的N維數(shù)據(jù)進行處理，這種哈希方法記為PCA- DTH。若求取原始數(shù)據(jù)在每一維度上的標準差，然后選擇標準差最大的前N個維度，在這些維度上進行動態(tài)閾值哈希處理，這種利用最大標準差(max standard deviation,MSD)進行數(shù)據(jù)預處理的動態(tài)閾值哈希方法記為MSD- DTH。

為了進一步提升其性能，可以考慮將這種基于動態(tài)閾值進行哈希的思想應用到性能優(yōu)良的迭代量化方法(ITQ)中。ITQ算法的基本思想是首先對原始特征數(shù)據(jù)進行降維處理，然后通過期望最大化(expectation maximization,EM)算法求取使得新數(shù)據(jù)具有最小量化誤差的旋轉矩陣，通過該旋轉矩陣對降維后數(shù)據(jù)進行旋轉后，能夠取得更穩(wěn)定的哈希效果。本文基于動態(tài)閾值哈希索引方法的思想對其進行改進，首先對ITQ算法中PCA降維后的特征數(shù)據(jù)進行中位數(shù)置0，也即計算降維后數(shù)據(jù)在每一維上的中位數(shù)，然后對每一維度上的數(shù)據(jù)進行相應的中位數(shù)大小的偏移，使偏移后的數(shù)據(jù)在每一維度上的中位數(shù)都為0，這時，新的數(shù)據(jù)是以0為中位數(shù)的分布，最后對偏移后的數(shù)據(jù)進行ITQ的迭代操作，求取最佳旋轉矩陣。本文將這種哈希方法記為PCA- DTH- ITQ，相應的，基于MSD- DTH實現(xiàn)的ITQ算法稱之為MSD- DTH- ITQ。圖3通過將PCA- DTH- ITQ哈希方法與PCA- ITQ哈希方法進行對比，描述了該哈希方法的思路，其中圖3(b)為PCA- ITQ哈希方法對圖3(a)中的特征數(shù)據(jù)旋轉后的結果，圖3(c)通過數(shù)據(jù)偏移將圖3(a)中的特征數(shù)據(jù)的中位數(shù)置為0，圖3(d)為PCA- DTH- ITQ哈希方法對圖3(c)中的特征數(shù)據(jù)旋轉后的結果。

2 試驗分析

2.1 試驗數(shù)據(jù)及環(huán)境

通過已有的數(shù)據(jù)集對檢索性能進行評價是必不可少的關鍵步驟。自然圖像檢索中已經(jīng)存在大量公開的數(shù)據(jù)集，但由于遙感影像自身的特點，公開的遙感影像數(shù)據(jù)集很少，因此，為了有效評價基于深度神經(jīng)網(wǎng)絡模型所提取的遙感影像特征在遙感影像內(nèi)容檢索中的性能，在進行具體的試驗前需要手動制作合適的遙感影像數(shù)據(jù)集。本文從天地圖第14級遙感影像中選擇了14 129幅大小為768×768像素的遙感影像，它由相鄰的9張256像素大小的遙感影像瓦片按照3×3的排列方式拼接而成。將其分為10個類別，各影像類別的名稱及具體數(shù)量見表1，具體如圖4所示。

影像類別影像數(shù)量影像類別影像數(shù)量裸地1685海岸1126耕地1682島嶼742云層1153居民區(qū)1024林地2183湖泊398半林地1917河流2219

2.2 性能分析

為了驗證本文所提出的動態(tài)閾值哈希索引方法對大規(guī)模影像高維特征的索引效果，基于遙感影像數(shù)據(jù)集，將動態(tài)閾值哈希索引方法的檢索效果與其他局部敏感哈希方法進行比較。試驗中采用基于ImageNet訓練所得的VGG- F模型提取影像的深度特征[13]，并將其降維到512維，從數(shù)據(jù)庫中隨機選擇2000張作為測試圖像。

對于局部敏感哈希算法及其相關的近似最近鄰搜索算法，存在兩種常見的算法評價方案。

(1) 以真實的最近鄰搜索的結果為真值。對于所有特征向量，計算各自與其第N個最近鄰之間的距離，并將這些距離的平均值作為一個距離閾值。對于每一條待測試的特征向量，可通過此距離閾值確定哪些特征向量與之相關或不相關，與之距離小于等于該閾值則相關，反之則不相關。在進行哈希查找近似最近鄰時，以此作為判斷返回結果是否與查詢向量相關的依據(jù)[15]。實際上，該方法是以線性搜索的結果為標準進行算法評價，在本文試驗中，N取值為500，在該評價方案中，以召回率- 精度(recall- precision)曲線和平均檢索精度mAP作為具體的評價指標。

(2) 以具有相同類別標簽的數(shù)據(jù)為真值。對于具有類別標簽的數(shù)據(jù)集，可以直接使用原始特征數(shù)據(jù)的類別標簽作為評價算法性能的依據(jù)。在進行哈希查找近似最近鄰時，根據(jù)返回結果的類別標簽是否與查詢向量一致作為判斷其是否相關的依據(jù)[16]。該評價方案中，本文將檢索返回的圖像數(shù)量為500時的檢索精度作為具體的評價指標。

試驗中將以上4種動態(tài)閾值哈希索引方法(MSD- DTH、PCA- DTH、MSD- DTH- ITQ、PCA- DTH- ITQ)與其他多種流行的哈希算法進行了比較，主要有隨機超平面散列法(RHH)、密度敏感哈希(DSH)、譜哈希(SH)和迭代量化方法(PCA- ITQ)[17- 18]，分別用以真實的最近鄰搜索的結果為真值的評價方案和以具有相同類別標簽的數(shù)據(jù)為真值的評價方案進行算法性能評估。圖5給出了兩種算法評價方案中各種不同哈希索引方法的檢索性能。其中，圖5(a)基于以真實的最近鄰搜索結果為真值的評價方案，給出了哈希編碼位數(shù)與平均檢索精度之間的關系；圖5(b)基于以具有相同類別標簽的數(shù)據(jù)為真值的評價方案，給出了返回的影像數(shù)量為500時，哈希編碼位數(shù)與檢索精度之間的關系。圖6給出了第1種評價方案下，召回率與精度的關系。圖7給出了第2種評價方案下，檢索時返回的影像數(shù)量與檢索精度的關系。

根據(jù)對各種不同哈希算法的性能分析結果，可以得出以下幾個結論：

(1) 若單獨使用本文所提出的較為簡單的MSD- DTH和PCA- DTH算法，其性能表現(xiàn)一般，這和筆者的預期是一致的。但若將DTH算法的思想應用到ITQ算法中，由此產(chǎn)生的MSD- DTH- ITQ和PCA- DTH- ITQ算法性能優(yōu)良，特別是在哈希編碼的位數(shù)較小時，它們能夠取得最優(yōu)的檢索效果。

(2) 主成分分析是進行特征選擇和降維的最常用方法，大量研究表明該方法具有十分優(yōu)良的特性。但根據(jù)本試驗結果，MSD- DTH的性能優(yōu)于PCA- DTH，MSD- DTH- ITQ的性能優(yōu)于PCA- DTH- ITQ。表明在某些應用中，使用標準差最大化的簡單策略進行特征選擇和降維，其性能并不亞于甚至優(yōu)于主成分分析法。

(3) 圖5(b)是以具有相同類別標簽的數(shù)據(jù)為真值的評價方案，圖中表明了返回的影像數(shù)量為500時，哈希編碼位數(shù)與檢索精度之間的關系。當哈希編碼的位數(shù)大于32時，MSD- DTH- ITQ和PCA- DTH- ITQ的檢索精度優(yōu)于線性搜索(linear- search)，PCA- ITQ算法在哈希編碼的位數(shù)大于64時也具有這種性質(zhì)。結果表明基于ITQ系列索引方法所得的近似最近鄰結果相對線性搜索所得的最近鄰結果，更加貼近遙感影像數(shù)據(jù)的真實類別標簽。

當哈希編碼位數(shù)為64時，在遙感影像數(shù)據(jù)集上使用以具有相同類別標簽的數(shù)據(jù)為真值的評價方案進行遙感影像檢索，所得的各哈希方法的前30個檢索結果如圖8所示，其中，帶×號的圖像是不相關影像。

通過以上試驗，表明了本文所提出的動態(tài)閾值哈希索引方法的有效性和先進性，對于大規(guī)模數(shù)據(jù)的快速查詢與檢索，基于動態(tài)閾值的哈希索引方法具有較大的應用潛力。

3 結 語

遙感影像高維特征造成的“維度災難”是遙感影像內(nèi)容檢索研究面臨的重要問題，造成檢索響應時間的大大增加。為了解決這一問題，本文將遙感影像內(nèi)容檢索的特征最近鄰搜索問題轉化為近似最近鄰問題，提出了動態(tài)閾值哈希索引方法，在影像檢索的精度損失非常小的情況下，顯著提升了檢索的速度，對大規(guī)模遙感影像內(nèi)容檢索研究具有較好的促進作用。