雙倍比特量化近似查詢索引算法研究

宋馥莉　閆培玲

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

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

中圖分類號：TP391.41 文獻標識碼：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]和目標檢測[3]等領域的核心工作是高維特征的最近鄰搜索。二進制碼在進行圖像檢索方面有以下兩方面優勢：一方面，海明距離的計算非常高效，只需要幾個機器指令即可完成[4];另一方面，二進制碼占用的存儲空間遠遠少于浮點型數據[5]。

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

2 研究現狀

2.1 二進制量化

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

2.2 二進制索引技術

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

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

3.1 雙倍比特量化

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

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

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

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

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

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

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

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

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

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

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

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

3.2 非對稱距離計算

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

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

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

4 實驗結果及分析

4.1 實驗設置

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

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

4.2 雙倍比特量化

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

結果表明，雙倍比特量化方法的查詢精度總是高于傳統二進映射算法，并且該效果與數據集、圖像特征和二進制映射方法的選擇無關。

4.3 非對稱距離

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

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

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

5 結論

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

參考文獻：

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

[2]吳純青，任沛閣，王小峰.基于語義的網絡大數據組織與搜索[J].計算機學報，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.