李 雯 鄧 涵 許玉珍

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

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

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

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

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

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

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

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

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

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

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

1.1 雙倍比特量化

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

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

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

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

圖2 雙倍比特量化方法

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

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

1.2 雙倍比特分段哈希索引

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

表1 每一維的加權(quán)海明距離

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

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

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

address= query+IN-RN,

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

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

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

2 實(shí)驗(yàn)結(jié)果及分析

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

2.1 雙倍比特量化實(shí)驗(yàn)及結(jié)果分析

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

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

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

2.2 雙倍比特分段哈希索引實(shí)驗(yàn)及結(jié)果分析

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

圖3 通過(guò)LSH生成的64bit二進(jìn)制碼在分段哈希索引中進(jìn)行最近鄰查詢(xún)的平均運(yùn)行時(shí)間，并以線性查詢(xún)?yōu)榛鶞?zhǔn)，其中設(shè)置最近鄰數(shù)量分別為1,10和100

圖4 通過(guò)LSH生成的128bit二進(jìn)制碼在分段哈希索引中進(jìn)行最近鄰查詢(xún)的平均運(yùn)行時(shí)間，并以線性查詢(xún)?yōu)榛鶞?zhǔn)，其中設(shè)置最近鄰數(shù)量分別為1，10和100

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

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

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

圖5 圖像過(guò)濾系統(tǒng)架構(gòu)

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

表3 2種圖像過(guò)濾系統(tǒng)精度對(duì)比(度量標(biāo)準(zhǔn)是mAP)

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

3 結(jié)論

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