宋馥莉　閆培玲

摘 要：本文提出雙倍比特量化與非對稱距離的近似查詢索引。首先，設(shè)計了一種雙倍比特量化方法，通過把特征的每一維數(shù)據(jù)量化為兩個比特二進制碼，增加特征之間的區(qū)分性。然后，研究了非對稱距離算法，通過計算浮點型查詢特征與特征庫中二進制碼的距離，對海明空間下的最近鄰進行重排序，以提高索引的查詢精度?；鶞?zhǔn)數(shù)據(jù)集上的實驗表明，雙倍比特量化與非對稱距離的方法使最近鄰查詢精度提高15%～25%。

關(guān)鍵詞：二進制量化;近似查詢索引;雙倍比特量化

中圖分類號：TP391.41 文獻標(biāo)識碼：A 文章編號：1003-5168（2019）25-0028-04

Research on Approximate Query Index Algorithms with

Double Bit Quantization

SONG Fuli1 YAN Peiling2

（1.Henan Radio & Television University，Zhengzhou Henan 450000;

2.Henan University of Chinese Medicine，Zhengzhou Henan 450046）

Abstract： In this paper， we proposed an approximate query index based on double bit quantization and asymmetric distance. First of all， a double bit quantization method was designed to increase the distinction between features by quantizing each one-dimensional data into two bit binary codes. Then， the asymmetric distance algorithm was studied. By calculating the distance between the floating-point query feature and the binary code in the feature library， the nearest neighbor in Hamming space was reordered to improve the query accuracy of the index. Experiments on the benchmark data set show that the accuracy of nearest neighbor query is improved by 15%～25% by using the method of double bit quantization and asymmetric distance.

Keywords： binary embedding;nearest neighbor search;double-bit quantization

1 研究背景

圖像檢索[1]?、計算機視覺?[2]和目標(biāo)檢測[3]等領(lǐng)域的核心工作是高維特征的最近鄰搜索。二進制碼在進行圖像檢索方面有以下兩方面優(yōu)勢：一方面，海明距離的計算非常高效，只需要幾個機器指令即可完成[4];另一方面，二進制碼占用的存儲空間遠遠少于浮點型數(shù)據(jù)[5]。

本文設(shè)計了一種雙倍比特量化方法，研究了非對稱距離算法對海明空間的最近鄰進行重排序，提出了雙倍比特量化與非對稱距離的近似查詢索引方法，可以使索引的查詢精度提高15%～25%。

2 研究現(xiàn)狀

2.1 二進制量化

基于隨機的映射和基于學(xué)習(xí)的映射是目前已提出的較著名的兩類二進制映射技術(shù)，其中通用的是基于學(xué)習(xí)的映射。比如，主成分分析映射（Principal Component Analysis Embedding，PCAE）[6]通過正交變換將一組可能存在相關(guān)性的變量轉(zhuǎn)換為一組線性不相關(guān)的變量，轉(zhuǎn)換后的這組變量叫主成分并作為原始特征的映射結(jié)果;譜哈希（Spectral Hashing，SH）[7]通過優(yōu)化稀疏特征的權(quán)重差異來得到最優(yōu)的二進制碼，可將其看作是對PCAE每一維度都賦予不同權(quán)重的改進算法;迭代量化主成分分析嵌入（Principal Component Analysis Embedding Iterative Quantization，PCAE-ITQ）通過對數(shù)據(jù)進行旋轉(zhuǎn)使編碼和降維的誤差最小化。

2.2 二進制索引技術(shù)

當(dāng)前，高維索引領(lǐng)域的研究熱點是基于二進制碼的索引技術(shù)。局部敏感哈希方法在二進制特征的快速匹配上有一定效果。Rublee等人對ORB特征建立基于LSH的索引，Zitnick等人使用Min-hash技術(shù)對二進制特征建立索引。二進制特征之間的海明距離是度量距離，因此基于度量空間的索引可以應(yīng)用于二進制特征的匹配。Muja等人提出建立多棵層次聚類樹HCT來查詢匹配二進制特征。HCT索引中采用256位的二進制碼，并對特征庫進行聚類。Norouzi等人[8]提出了多索引哈希技術(shù)（Multi-Index Hashing，MIH），對二進制特征的不相連子串建立多個哈希表，在海明空間下執(zhí)行精確最近鄰查找。

3 雙倍比特量化與非對稱距離

3.1 雙倍比特量化

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

為了準(zhǔn)確地描述二進制映射技術(shù)的流程，筆者引入一組符號加以說明。[s]表示一個在Ω空間下的[K]維圖像特征，[hk]表示一種二進制嵌入方法，即[hk：Ω→{0，1}]。由[K]個這樣的二進制映射方法構(gòu)成集合[H={hk，? k=1…K}]。二進制映射技術(shù)可以利用以下公式進行處理：

[hks=qkgks]? ? ? ? ? ? ? ? ? ? ? ? ? （1）

其中，[gks：Ω→R]（R為中間空間）是投影函數(shù);[qks：R→0，1]是量化函數(shù)。

為了解決傳統(tǒng)量化方法只能粗略地把中間向量的每一維數(shù)據(jù)映射為兩類（表示為0或者1），導(dǎo)致中間向量的區(qū)分能力大幅降低[9]的問題，本文提出利用加權(quán)海明距離來進行計算。

為了在線計算中間數(shù)據(jù)[r]與[q]之間的加權(quán)海明距離，筆者需要把每一維數(shù)據(jù)之間的距離相加。用[dkDBQkr，DBQkq]代表[r]與[q]第[k]維數(shù)據(jù)間的加權(quán)海明距離，具體表示如表1所示。

海明距離是指序列相同位置上數(shù)據(jù)不同的個數(shù)，而這里采用加權(quán)海明距離，即相同位置不同的數(shù)據(jù)表示為1，相同位置相同的數(shù)據(jù)表示為0，左一位對應(yīng)的值乘以2的0次方，左二位對應(yīng)的值為2的1次方，其距離為如表1所示。

根據(jù)海明距離的定義得到變量[r]與[q]間的海明距離：

[dWH（r，q）=kβr，qk]? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

相比于查詢特征與數(shù)據(jù)庫中大量的特征之間距離計算，[β]計算的時間復(fù)雜度可以忽略不計。針對計算機內(nèi)存對數(shù)據(jù)的存儲是以字節(jié)為單位的，雙倍比特二進制碼之間的加權(quán)海明距離計算可通過對維度分組來進行。為了簡潔地說明，本文假設(shè)k為4個倍數(shù)。所以，該計算方法可以表示：

[dWH（r，q）=k=0k/4-1j=1j=4βr，q4k+j]? ? ? ? ? ? ? ? ? ? ? （3）

由于二進制子串[[DBQ4kr，? DBQ4k+1（r）]，[DBQ4k+2][r，DBQ4k+3r]]正好為1個字節(jié)，每個[j=1j=4βr，q4k+j]都只有256種可能的值。雙倍比特量化方法可以使查詢精度與查詢速度都得到顯著提高，如實驗部分所述。

3.2 非對稱距離計算

本文設(shè)計并實現(xiàn)了非對稱距離算法，當(dāng)獲得一個查詢特征后，筆者首先使用雙倍比特量化的方法得到其在海明空間下的最近鄰，并把這些最近鄰作為候選集，最后使用非對稱距離算法來對候選集進行重排序，以提高查詢精度[10]。

大多數(shù)的二進制映射方法不僅要把特征庫的特征轉(zhuǎn)換為二進制碼，同樣也要把查詢特征轉(zhuǎn)化為二進制碼。然而，筆者并不需要把查詢特征也轉(zhuǎn)換為二進制碼，因為一個單獨的未量化特征占用的空間可以忽略不計。非對稱算法用于計算二進制碼與未壓縮的原始向量之間的距離，由于兩種數(shù)據(jù)存在于不同的空間，所以我們把兩者之間的距離稱為非對稱距離。非對稱距離最大的好處就是它可以利用未壓縮查詢向量的優(yōu)勢以取得更好的查詢精度。

由于雙倍比特二進制特征之間的空間關(guān)系存在四種情況而非傳統(tǒng)的兩種，通過改進的非對稱距離算法，特征之間的區(qū)分能力被進一步加強了。

4 實驗結(jié)果及分析

4.1 實驗設(shè)置

實驗在BIGANN SIFT 1M數(shù)據(jù)集上開展，數(shù)據(jù)集描述如表2所示。其中，BIGANN數(shù)據(jù)集中的數(shù)據(jù)是高維特征：SIFT為128維，可供本文直接使用;而Caltech101數(shù)據(jù)為圖像集。

在雙倍比特量化的實驗中，使用準(zhǔn)確率與召回率來評估該方法的性能;非對稱距離算法通過準(zhǔn)確率進行驗證。

4.2 雙倍比特量化

每個實驗包括了1 000個查詢，這1 000個查詢的平均準(zhǔn)確率作為判斷雙倍比特量化的性能指標(biāo)。實驗在一個數(shù)據(jù)集中（BIGANN SIFT 1M）對比使用不同二進制映射方法。根據(jù)每個維度的正負(fù)符號獲得中值，計算查詢二進制碼與每個二進制碼的加權(quán)海明距離。

結(jié)果表明，雙倍比特量化方法的查詢精度總是高于傳統(tǒng)二進映射算法，并且該效果與數(shù)據(jù)集、圖像特征和二進制映射方法的選擇無關(guān)。

4.3 非對稱距離

實驗采用1 000個查詢。由于筆者只對結(jié)果重新排序，召回率保持不變，所以該實驗只使用準(zhǔn)確率作為檢測指標(biāo)。數(shù)據(jù)集（BIGANN SIFT 1M）的二進制映射方法的實驗效果中，使用非對稱距離進行重排序的結(jié)果優(yōu)于直接獲得的結(jié)果。

圖1表示在不同數(shù)據(jù)集中不同二進制映射方法使用非對稱距離前后的準(zhǔn)確率。即使雙倍比特量化已經(jīng)顯著提高了精度，非對稱距離仍進一步提高了最近鄰查詢準(zhǔn)確率。在BIGANN SIFT1M和GIST特征數(shù)據(jù)集中，性能也很出色：如圖1（b）所示，查詢準(zhǔn)確率平均提高了58.3%。

筆者注意到，當(dāng)比特數(shù)較小時非對稱距離的效果并不明顯。由于二進制碼是由雙倍比特量化產(chǎn)生的，每兩個比特僅表示一個維度。然而，非對稱距離是由每個維度計算得到的。因此，當(dāng)位數(shù)較小時，非對稱距離的優(yōu)勢將受到限制。

5 結(jié)論

本文提出雙倍比特量化與非對稱距離的近似查詢索引，把特征的每一維數(shù)據(jù)量化為兩個比特二進制碼以增加特征之間的區(qū)分性，計算浮點型查詢特征與特征庫中二進制碼的距離，對海明空間下的最近鄰進行重排序，提高索引的查詢精度。在大規(guī)模數(shù)據(jù)集上的實驗表明，本文提出的方法使最近鄰查詢精度提高15%～25%。

參考文獻：

[1]賈佳，唐勝，謝洪濤，等.移動視覺搜索綜述[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2017（6）：1007-1021.

[2]吳純青，任沛閣，王小峰.基于語義的網(wǎng)絡(luò)大數(shù)據(jù)組織與搜索[J].計算機學(xué)報，2015（1）：1-17.

[3]Lei Z， Zhang Y， Tang J， et al. Topology preserving hashing for similarity search[C]// Acm International Conference on Multimedia. 2013.

[4]Wang J， Shen H T， Song J， et al. Hashing for Similarity Search： A Survey[J]. Computer Science，2014（1408）：1-29.

[5]Yan C C ， Xie H ， Zhang B ， et al. Fast approximate matching of binary codes with distinctive bits[J]. Frontiers of Computer Science （print），2015（5）：741-750.

[6]Benzrihem N， Zelnikmanor L. Approximate nearest neighbor fields in video[J]. Computer Science，2015（8）：5233-5242.

[7]Weiss Y， Torralba A， Fergus R. Spectral hashing[C]//International Conference on Neural Information Processing Systems.2008.

[8]Norouzi M， Punjani A， Fleet D J. Fast Exact Search in Hamming Space With Multi-Index Hashing[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，2013（6）：1107-1119.

[9]M. Raginsky，S. Lazebnik. Locality-Sensitive Binary Codes from Shift-Invariant Kernels[EB/OL].（2013-08-13）[2019-07-20]. http：//www.doc88.com/p-3922945380458.html.

[10]Gordo A， Perronnin F. Asymmetric distances for binary embeddings[C]//Computer Vision & Pattern Recognition.2011.