基于雙倍比特量化與分段哈希索引的軍事圖像過濾

李 雯 鄧 涵 許玉珍

1.國防科學技術大學信息通信學院,武漢430010 2.中國科學院信息工程研究所, 北京100049 3.北京強度環(huán)境研究所, 北京100076

高維特征的最近鄰查詢是圖像過濾[1]、計算機視覺[2]和目標檢測[3]等領域的核心工作。最近鄰搜索旨在大規(guī)模高維數(shù)據(jù)庫中為查詢數(shù)據(jù)找到與之相似的數(shù)據(jù)。在大規(guī)模數(shù)據(jù)庫中查找最近鄰時，通常把歐氏距離作為衡量高維數(shù)據(jù)之間是否相似的度量標準。然而卻造成嚴重的性能瓶頸[4]。對高維特征最近鄰查詢性能的影響主要包括2個方面：計算時間和內存占用；傳統(tǒng)浮點型特征需要大量的存儲空間，且歐氏距離計算復雜度高。二進制碼正好有效地解決這2大問題，一方面，海明距離的計算非常高效，只需要幾個機器指令即可完成[5]；另一方面，二進制碼占用的存儲空間遠遠少于浮點型數(shù)據(jù)。

二進制碼的顯著優(yōu)勢推動了二進制量化與索引技術的發(fā)展[5]。二進制量化技術把原始的浮點型特征轉換為二進制碼，并且保證相似的特征以很高的概率被映射為相似的二進制碼；同時為二進制碼設計相應的索引算法，以實現(xiàn)大規(guī)模數(shù)據(jù)環(huán)境下的快速最近鄰查詢[6]。二進制量化方法主要可以分為2類：基于隨機的量化和基于學習的量化[3]。隨機量化與處理的數(shù)據(jù)無關，它通過若干個隨機的哈希函數(shù)，把特征映射到超平面進行投影。這種映射方式需要維度足夠高才具有較好的近似查詢效果[7-8]；基于學習的量化是由訓練集求出區(qū)分性最佳的映射空間，然后再把特征映射到該空間。該方法在維度較低的情況下也能得到較好的近似查詢精度，但是它的量化方法極大減弱了原始特征之間的區(qū)分性，導致查詢精度的降低。

盡管量化后的二進制碼在匹配上十分高效，但線性查找仍然無法滿足大規(guī)模數(shù)據(jù)環(huán)境下的需求。因此，研究者提出針對二進制碼的索引技術。文獻[9]直接用生成的二進制碼作為鍵來構建哈希表，通過搜索一系列以查詢?yōu)橹行陌霃竭f增的海明球體，返回所有近似的結果。但是該方法在二進制碼維度較高時，效率十分低下。對于較長的二進制碼，文獻[10]提出多索引哈希(Multi-index Hashing, MIH)算法。MIH的基本思想是將較長的二進制碼劃分為若干子串，然后在各個子空間內分別建立哈希表進行搜索。由于空間維度降低，MIH可以極大地提高搜索速度。但是MIH不能有效處理多維二進制量化[4]。

針對上述問題，提出雙倍比特量化與分段哈希的近似查詢索引，如圖1所示，具體創(chuàng)新如下：

1)設計了一種雙倍比特量化方法。通過二進制映射技術把高維浮點型的特征投影為中間空間的高維向量，然后把中間空間的高維向量中的每一維數(shù)據(jù)量化為2個比特二進制碼，從而增加特征之間的區(qū)分性。雙倍比特量化方法可以作用于不同的二進制量化技術、不同類型以及不同維度的特征；

2)針對雙倍比特量化的二進制碼提出雙倍比特分段哈希索引。通過把雙倍比特二進制碼劃分為若干段子串，并對每一段子串分別建立哈希表。在查詢最近鄰時，同樣把查詢特征劃分為若干個子串，將每個子串在對應的哈希表中進行查詢；為了快速計算雙倍比特二進制碼之間的距離，提出加權的海明距離，以提高查詢速度。

本文方法具有3個優(yōu)點：1)雙倍比特量化方法可以有效地降低量化損失，從而提高近似查詢精度；2)雙倍比特分段哈希索引充分利用二進制碼距離度量的特性，有效提高了查詢速度；3)方法簡單，易于實現(xiàn)。相比于目前已有的基于多倍比特量化的哈希量化索引方法，本文所述的方法只使用雙倍比特量化方法，在降低量化損失的同時又保證系統(tǒng)的效率，實現(xiàn)編碼比特數(shù)目和搜索效率之間更好的權衡，同時針對雙倍比特量化技術設計了加權海明距離的計算方法，便于在MIH系統(tǒng)的應用，與線性搜索相比，顯著提高了二進制碼的查詢速度。

在此基礎上，設計了大規(guī)模軍事圖像過濾系統(tǒng)。實驗表明，相比于Faster R-CNN+CNNH+MIH系統(tǒng)，可以使得大規(guī)模軍事圖像過濾精度提升5.4%。

圖1 雙倍比特量化與分段哈希索引示意圖

1 雙倍比特量化與分段哈希索引

1.1 雙倍比特量化

為了提高查詢效率并節(jié)省存儲空間，本文通過雙倍比特量化把浮點型特征映射為二進制碼。并提出一種新的加權海明距離計算方法，提高海明距離的計算效率。

傳統(tǒng)的量化方法只能粗略地把中間向量的每一維數(shù)據(jù)映射為2類(表示為0或者1)，導致中間向量的區(qū)分能力大幅降低[4]。為了緩解這個問題，把中間向量的每一維數(shù)據(jù)量化為2-bit的二進制碼，并在最近鄰查詢時為不同的距離賦予不同的權重，從而有效地提高了高維數(shù)據(jù)之間的區(qū)分性。雙倍比特量化方法的步驟如下：

1)特征映射。得到一個K維的特征x，首先用多維投影方法g(s)=[gk(s),k=1，…，K]′把x投影為中間向量g(x)。為了提高特征之間距離計算的有效性，對所有中間向量的每一維數(shù)據(jù)進行L1歸一化得到，其中，li(s)=N[gi(s)],i=1，…，K,N表示對數(shù)據(jù)歸一化；

2)數(shù)據(jù)劃分。首先根據(jù)中間向量每一維數(shù)據(jù)的正負符號把這些數(shù)據(jù)劃分為2類。然后，在每個維度上都計算出到這2類數(shù)據(jù)的中值，nmi和pmi分別表示第i維的正數(shù)數(shù)據(jù)以及負數(shù)數(shù)據(jù)的中值。根據(jù)每維數(shù)據(jù)的正負符號以及2個中值，把中間向量的每一維數(shù)據(jù)劃分為4類，如圖2所示。盡管這個劃分方法很簡單，該方法仍能應用于多種二進制映射方法上并得到很好的效果；

圖2 雙倍比特量化方法

3)二進制量化。對數(shù)據(jù)進行劃分后，為了標明不同的4類數(shù)據(jù)，提出了一種新穎的量化方法。如圖2所示，把中間向量的每一維數(shù)據(jù)量化為2-bit的二進制碼。對特征s中的第i維數(shù)據(jù)，雙倍比特量化定義為：

假設特征y為特征x的最近鄰，由于中間向量很好地保持了原始特征的相似性，則DBQi(x)和DBQi(y)以很大概率被映射為同一類數(shù)據(jù)。相反，如果x和y在原始空間的距離很遠，那DBQi(x)和DBQi(y)以很大概率被映射到間隔較大的2類數(shù)據(jù)中。因此，DBQ可以很自然地保持特征之間的相似性。雙倍比特量化的本質是為靠近查詢向量的特征賦予更高的權重。

1.2 雙倍比特分段哈希索引

MIH通過增加海明距離并檢測相應的哈希桶來獲得最近鄰。給定查詢q，可以通過q XOR mask來計算需要檢測的哈希桶的地址，其中，mask中的比特位的值為1的個數(shù)表示海明距離。例如，假設q = 00011011，而需要查詢的是與q的海明距離為3的二進制碼。于是得到其中一個mask，值為00000111，最后計算出q XOR mask = 00011100，可以驗證該結果與q的海明距離為3。

表1 每一維的加權海明距離

然而，當執(zhí)行最近鄰搜索時，XOR操作并不適合于雙倍比特二進制碼。因此，提出了一種雙倍比特分段哈希索引，可以將雙倍比特二進制碼應用于基于MIH的索引而不改變MIH的結構。如表1所示，在每個維度中有4種二進制碼，即00，01，10和11。它們分別對應于十進制中的0，1，2和3。其中，最大值為3(二進制為11)，最小值為0(二進制為00)。因此，每種維度可達的距離范圍是不一樣的。例如，00可以通過加1，2和3變?yōu)?1，10和11；對于10，可以對其加1以及減1或2。由于不同的距離相當于不同的權重，所以值的增加或減小被認為是加權海明距離(weighted Hamming distance, WHD)。因此，進行最近鄰查詢時，在計算加權海明距離的過程中，每種維度都有不同的情況，而不是簡單的0/1位翻轉。所以，分別討論不同的情況，具體步驟如下：

1)調整mask大小。mask中的1的數(shù)量等于加權海明距離。并且，mask某一維度中1的數(shù)量表示對應維度的加權海明距離。假設C1是二進制碼中00和11的數(shù)量，而C2是二進制碼中10和01的數(shù)量。由于11和00的加權海明距離的范圍是0～3，01和10的加權海明距離的范圍是0～2，所以mask的長度被設置為3×C1+2×C2，其中C1+C2=b/2；

3)檢測哈希桶。經(jīng)過前面的步驟，要檢測的哈希桶的地址為：

address= query+IN-RN,

舉個例子，給定查詢 01001011，它是 4 維的 8 位二進制碼， mask 的長度設置為 10-bit。假設加權海明距離是 4，則掩碼應該包含4個 1。假設其中1個 mask是 0010110100。對于第1維(從右到左)， mask 的相應維度不包含任何 1，因此IN或RN沒有任何變化；對于第2維 00， mask(共 3-bit)有2個值為 1 的位，因此IN=IN| 00100000；對于第3維 10，對應的 mask 有1個值為 1 的位，則RN=RN| 00000100；對于第4維 11，存在1個比特值為 1，因此RN=RN|00000001。于是得到IN= 00100000，RN= 00000101。代入公式可得：需要檢測的哈希桶的地址是 01100110，其與 q 的加權海明距離為 4。

后續(xù)的查詢操作與原始MIH算法[10]一致。

雙倍比特分段哈希索引考慮了加權海明距離的所有情況，并且每種情況只出現(xiàn)1次。為了使雙倍比特二進制碼適用于MIH，本文考慮mask和二進制碼的不同組合而不是單個mask，以獲得要檢測哈希桶的地址。從實驗結果來看，與線性查詢相比，雙倍比特分段哈希索引可以顯著提高查詢速度。

2 實驗結果及分析

本節(jié)驗證本文算法的有效性。第2.1小節(jié)使用多種二進制映射方法驗證雙倍比特量化的有效性；第2.2小節(jié)驗證雙倍比特分段哈希索引的有效性；第2.3小節(jié)驗證本文方法在大規(guī)模軍事圖像過濾上的性能。

2.1 雙倍比特量化實驗及結果分析

表2顯示在BIGANN 1M GIST數(shù)據(jù)集[11]上，使用原始二進制映射算法和雙倍比特量化方法的比較結果。實驗包括了1000個查詢，這1000個查詢的平均準確率和平均召回率用作判斷雙倍比特量化的性能指標。結果表明，雙倍比特量化方法的查詢精度總是高于傳統(tǒng)二進映射算法。當采用SH時，可以觀察到128bit的二進制碼的準確率提高了42.3%。實驗結果表明，雙倍比特量化為傳統(tǒng)的二進制映射獲得了極大的性能提升。

表2 在數(shù)據(jù)集BIGANN 1M GIST的結果(%)

表2顯示了二進制碼分別為64bit, 128bit, 256bit和512bit，二進制投影算法分別為ITQ，RR，SH，LSH。P@1表示表示top-1的準確率，R@10表示top-10的召回率。SB表示單比特量化，DB表示雙比特量化。

2.2 雙倍比特分段哈希索引實驗及結果分析

在BIGANN SIFT1G[11]數(shù)據(jù)集上驗證雙倍比特分段哈希索引，使用多個查詢的平均查詢速度度量索引的查詢速度。每個實驗進行10000次查詢，每個查詢的平均運行時間作為雙倍比特分段哈希索引的判別指標。當二進制維度為64時，將二進制碼劃分為4段，而128bit的二進制碼被分成8段。結果表明，與線性查詢相比，雙倍比特分段哈希索引的查詢效率顯著提升。圖3和4顯示了不同k-NN問題和2個不同二進制碼長度(64bit和128bit)的線性查詢和雙倍比特分段哈希索引的查詢速度。雖然二進制代碼的線性查詢速度已經(jīng)足夠快[9]，但雙倍比特分段哈希索引執(zhí)行速度仍然比線性查詢提高了若干倍。例如，當二進制碼為128維并且最近鄰個數(shù)為100時，雙倍比特分段哈希索引的速度大約比線性查詢提高了5倍(圖3)。1NN和10NN的性能更令人印象深刻。而使用64位LSH二進制碼，雙倍比特分段哈希索引執(zhí)行1NN搜索任務的速度比線性搜索快30倍。

圖3 通過LSH生成的64bit二進制碼在分段哈希索引中進行最近鄰查詢的平均運行時間，并以線性查詢?yōu)榛鶞剩渲性O置最近鄰數(shù)量分別為1,10和100

圖4 通過LSH生成的128bit二進制碼在分段哈希索引中進行最近鄰查詢的平均運行時間，并以線性查詢?yōu)榛鶞剩渲性O置最近鄰數(shù)量分別為1，10和100

把特征的每一維數(shù)據(jù)量化為2個bit二進制碼，因此在二進制特征存儲層面會使得存儲空間翻倍。由于二進制碼每1位只占1個比特位，因此增加的存儲空間有限。

2.3 基于雙倍比特量化和分段哈希索引的軍事圖像過濾性能

為了驗證本文方法在軍事圖像過濾上的有效性，基于上述方法設計了圖像過濾系統(tǒng)。圖像過濾系統(tǒng)框架如圖5所示，運行于Linux平臺，采用C++和Python混合編碼實現(xiàn)。本文分別構建含10類軍事標識(槍支、刀具、飛機、軍艦、軍章、軍銜、基地、旗幟、設備和獎章)的訓練集和測試集。其中訓練集有2萬幅圖像，每類標識有2000幅圖像；樣例集有2000幅圖像，每類標識有200幅圖像。從網(wǎng)絡上采集10000幅含有各類軍事標識的圖像作為測試集，模擬網(wǎng)絡圖像過濾。實驗的硬件環(huán)境是：Intel Xeon E5-2620*2(2.00 GHz, 7.2GT/s, 15M cache, 6cores)，K80GPU，64G內存。

圖5 圖像過濾系統(tǒng)架構

基于Faster R-CNN+CNNH+MIH框架[11]的圖像過濾系統(tǒng)主要分為3個部分：①采用了何凱明等人提出的Faster R-CNN的目標檢測算法，進行目標的定位；②顏水成等人在2014年提出的CNNH算法，此算法提取目標特征，并且將浮點數(shù)特征量化為二進制碼；③2011年Norouzi等人提出的哈希索引算法，采用分段檢索的方法進行二進制碼的快速最近鄰查詢。表3對比了本文系統(tǒng)與基于Faster R-CNN+CNNH+MIH框架的圖像過濾系統(tǒng)對軍事圖像的過濾精度，可以看出本文系統(tǒng)具有更高的過濾精度，相比于Faster R-CNN+CNNH+MIH系統(tǒng)，可以使得過濾精度提升5.4%。圖6顯式地展示了本文系統(tǒng)對軍事圖像的過濾效果。

表3 2種圖像過濾系統(tǒng)精度對比(度量標準是mAP)

圖6 圖像過濾系統(tǒng)架構軍事圖像過濾展示(左側為庫圖像，右側為系統(tǒng)發(fā)現(xiàn)的與其內容相似的網(wǎng)絡圖像)

3 結論

為充分利用二進制碼占用存儲空間少且易于進行距離度量的優(yōu)勢，研究者提出二進制量化方法以實現(xiàn)大規(guī)模數(shù)據(jù)環(huán)境下的快速最近鄰查詢。但是，二進制量化損失原始特征的信息量，導致查詢精度的降低。針對這一問題，提出雙倍比特量化與分段哈希的近似查詢索引；把特征的每一維數(shù)據(jù)量化為2個比特二進制碼以增加特征之間的區(qū)分性；對二進制碼分段并建立哈希索引提高查詢速度。據(jù)此，本文設計了大規(guī)模軍事圖像過濾系統(tǒng)。實驗表明，相比于Faster R-CNN+CNNH+MIH系統(tǒng)，本文方法可以使軍事圖像過濾精度提升5.4%。