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

宋馥莉　閆培玲

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

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

中圖分類(lèi)號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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]?、計(jì)算機(jī)視覺(jué)?[2]和目標(biāo)檢測(cè)[3]等領(lǐng)域的核心工作是高維特征的最近鄰搜索。二進(jìn)制碼在進(jìn)行圖像檢索方面有以下兩方面優(yōu)勢(shì)：一方面，海明距離的計(jì)算非常高效，只需要幾個(gè)機(jī)器指令即可完成[4];另一方面，二進(jìn)制碼占用的存儲(chǔ)空間遠(yuǎn)遠(yuǎn)少于浮點(diǎn)型數(shù)據(jù)[5]。

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

2 研究現(xiàn)狀

2.1 二進(jìn)制量化

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

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

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

3 雙倍比特量化與非對(duì)稱距離

3.1 雙倍比特量化

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

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

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

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

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

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

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

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

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

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

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

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

3.2 非對(duì)稱距離計(jì)算

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

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

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

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

4.1 實(shí)驗(yàn)設(shè)置

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

在雙倍比特量化的實(shí)驗(yàn)中，使用準(zhǔn)確率與召回率來(lái)評(píng)估該方法的性能;非對(duì)稱距離算法通過(guò)準(zhǔn)確率進(jìn)行驗(yàn)證。

4.2 雙倍比特量化

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

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

4.3 非對(duì)稱距離

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

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

[2]吳純青，任沛閣，王小峰.基于語(yǔ)義的網(wǎng)絡(luò)大數(shù)據(jù)組織與搜索[J].計(jì)算機(jī)學(xué)報(bào)，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.