基于雙倍比特量化分類索引技術(shù)的圖像檢索研究

魯明 宋馥莉 劉平勝 蘭勇

摘 要：本文對(duì)圖像數(shù)據(jù)進(jìn)行雙倍比特量化分類，增強(qiáng)了每個(gè)維度數(shù)據(jù)的差異程度。為了最大限度地提升量化后的查詢精度，其間采用量化后比對(duì)結(jié)果和量化前的查詢數(shù)據(jù)進(jìn)行非等距計(jì)算，提高索引的查詢精度。試驗(yàn)證明，最近鄰查詢的準(zhǔn)確率較傳統(tǒng)二進(jìn)制映射中的雙倍比特量化大大提高了性能。

關(guān)鍵詞：二進(jìn)制量化;雙倍比特量化;加權(quán)距離度量

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1003-5168（2021）03-0015-04

Research on Image Retrieval Based on Double Bit

Quantitative Classification Index Technology

LU Ming1 SONG Fuli1 LIU Pingsheng2 LAN Yong3

（1. The Open University of Henan，Zhengzhou Henan 450008;2. Zhongshan Torch Polytechnic，Zhongshan Guangdong 528436;3. Tianjin University of Finance and Economics Pearl River College ， Tianjin 301800）

Abstract： In this paper， the double-bit quantization classification of image data had enhanced the degree of difference in data in each dimension. In the meantime， in order to maximize the query accuracy after quantification， the comparison result after quantization and the query data before quantification were used to perform non-equal distance calculations to improve the query accuracy of the index. Experiments showed that the accuracy of nearest neighbor query greatly improved the performance compared to the double-bit quantization in traditional binary mapping.

Keywords： binary quantization;double bit quantization;weighted distance metric

視覺圖像檢測(cè)[1]和圖像檢索[2-3]的核心工作存在相似性，二者都需要在高維數(shù)據(jù)庫(kù)中檢索和匹配相似的特征數(shù)據(jù)。它的目的是在大型高維數(shù)據(jù)庫(kù)中搜索相似的數(shù)據(jù)來(lái)查詢數(shù)據(jù)。最近鄰算法作為大型多維度數(shù)據(jù)庫(kù)的常用算法，其性能和效率問(wèn)題愈發(fā)顯現(xiàn)[4]。

1 概述

針對(duì)最近鄰算法圖像檢索效率低的問(wèn)題，本文在高維圖像檢索過(guò)程中引入了二進(jìn)制編碼形式。二進(jìn)制代碼是執(zhí)行效率最高的一種編碼形式，可以應(yīng)用于圖像數(shù)據(jù)的二進(jìn)制量化和索引技術(shù)[5]中。二進(jìn)制量化是將圖像數(shù)據(jù)存儲(chǔ)格式中原始浮點(diǎn)相似的特征數(shù)據(jù)轉(zhuǎn)化映射為近似的二進(jìn)制碼，然后針對(duì)生成的二進(jìn)制代碼設(shè)計(jì)出高效快捷的圖像檢索算法，以適應(yīng)大規(guī)模數(shù)據(jù)環(huán)境[6]下的圖像檢索需求。如圖1所示，本文提出了一種雙倍比特量化的索引查詢技術(shù)，具體創(chuàng)新主要有兩點(diǎn)。

1.1 雙倍比特量化的方法

將浮點(diǎn)高維特征空間投影到高維向量二元映射，屬性間的區(qū)別在于添加了中間高維向量空間，每一維的數(shù)據(jù)有兩位的二進(jìn)制代碼。雙倍比特量化可以應(yīng)用于不同的二進(jìn)制量化技術(shù)、不同的類型和不同的尺寸特征。

1.2 非對(duì)稱距離查詢算法

對(duì)于每次查詢，可以在漢明最近鄰的空間選擇雙倍比特量化舉措，繼而在漢明最近鄰候選集空間通過(guò)浮點(diǎn)計(jì)算非對(duì)稱距離，對(duì)查詢函數(shù)（中間數(shù)據(jù)）和二進(jìn)制碼特征庫(kù)進(jìn)行重新排序，從而提高查詢精度指標(biāo)。

本文使用的要領(lǐng)具有三個(gè)顯著優(yōu)勢(shì)。一是雙倍比特量化方法能夠高效降低量化耗損，提高查詢精度;二是雙倍比特量化和非對(duì)稱距離算法可以應(yīng)用于現(xiàn)有的二進(jìn)制量化和索引方法;三是雙倍比特量化易于實(shí)現(xiàn)?；鶞?zhǔn)數(shù)據(jù)集試驗(yàn)表明，雙倍比特量化方法可以使最近鄰查詢精度提升15%～25%。

2 研究現(xiàn)狀

2.1 二進(jìn)制量化

目前，研究者提出了很多著名的二進(jìn)制映射方法，其主要分為兩類，即基于隨機(jī)的映射和基于學(xué)習(xí)的映射?；陔S機(jī)的映射主要有局部敏感哈希（LSH）和位置敏感聚類（Locality Sensitive Clustering， LSC）。LSH使用內(nèi)積來(lái)比較兩個(gè)向量的相似程度，通過(guò)多元正態(tài)分布取得多個(gè)哈希函數(shù)，并將其稀疏之特質(zhì)映射到超平面。隨機(jī)映射與處理數(shù)據(jù)無(wú)關(guān)，處理速度快，但只有在維度足夠高時(shí)才有好的檢索效果?；趯W(xué)習(xí)的二進(jìn)制映射技術(shù)在維度低的情況下能滿足查詢精度的要求，但試驗(yàn)效率較低，而且中間向量的每一維數(shù)據(jù)在傳統(tǒng)的量化方法下只能被簡(jiǎn)要地映射為兩類（為0或者1），這樣的量化方法不能很好地保持原始特征之間的相似關(guān)系。位置敏感聚類方法主要包括三部分：第一，生成位置敏感哈希函數(shù);第二，桶標(biāo)記的產(chǎn)生，即利用位置敏感哈希函數(shù)對(duì)每個(gè)點(diǎn)進(jìn)行映射得出桶標(biāo)記;第三，桶標(biāo)記的合并。由于桶標(biāo)記的個(gè)數(shù)多于實(shí)際的類數(shù)目，需要選擇合適的合并區(qū)間對(duì)桶標(biāo)記進(jìn)行合并，合并后的桶標(biāo)記對(duì)可用來(lái)對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分組，得出最終的類標(biāo)簽。

4.1 試驗(yàn)設(shè)置

試驗(yàn)在BIGANN SIFT 1M和Caltech101兩個(gè)數(shù)據(jù)集上開展，如表2所示。試驗(yàn)的硬件環(huán)境是Intel Xeon E5-2620*2（7.2 GT/s，2.00 GHz，15M cache，6cores），內(nèi)存為64 GB。

4.2 雙倍比特量化分類索引

下面使用多種二進(jìn)制映射方法來(lái)驗(yàn)證本文所提二進(jìn)制映射的優(yōu)化方法，包括局部敏感哈希（LSH）、主成分分析（PCA）和迭代量化（PCA-ITQ）。

每個(gè)試驗(yàn)包括1 000個(gè)查詢，以查詢的平均準(zhǔn)確率和平均召回率當(dāng)作性能指標(biāo)來(lái)明確雙位量化。試驗(yàn)在兩個(gè)數(shù)據(jù)集（BIGANN SIFT 1M和Caltech101）比照使用差異二進(jìn)制映射方式。為了獲得雙倍二進(jìn)制碼，訓(xùn)練集中的高維特征被映射為中間數(shù)據(jù)，并根據(jù)每個(gè)維度的正負(fù)符號(hào)獲得中值。繼而，以與訓(xùn)練集相同的方式將特征庫(kù)中的特征和查詢特征變換為中間數(shù)據(jù)，通過(guò)雙倍比特量化將數(shù)據(jù)轉(zhuǎn)化為二進(jìn)制碼。最后，計(jì)算并查詢二進(jìn)制碼與每個(gè)二進(jìn)制碼的加權(quán)海明距離。在兩個(gè)數(shù)據(jù)集上，使用原始二進(jìn)制映射算法和雙倍比特量化方法比較結(jié)果如表3和表4顯示。

試驗(yàn)結(jié)果表明，傳統(tǒng)二進(jìn)制映射的性能有了很大的提高。在使用原始二進(jìn)制映射算法時(shí)，數(shù)據(jù)集BIGANN 1M SIFT的結(jié)果（百分比）如表3所示。二進(jìn)制代碼分別是32位、64位、128位和256位。二值投影算法分別為ITQ、RR、SH、LSH和PCA。T@1表示top-1的準(zhǔn)確率，B@10表示top-10的召回率。SB代表單位量化，DB代表雙倍比特量化。

在使用雙倍比特量化方法時(shí)，數(shù)據(jù)集Caltech GIST datasets的結(jié)果（百分比）如表4所示。二進(jìn)制代碼分別為64位、128位、256位和320位。二進(jìn)制投影算法分別是ITQ、RR、SH、LSH和PCA。T@1表示top-1的準(zhǔn)確率，B@10表示top-10的召回率。SB代表單位量化，DB代表雙位量化。

每個(gè)試驗(yàn)有1 000個(gè)查詢。本研究只對(duì)結(jié)果進(jìn)行了重新排序，召回率仍舊保持固定不變，所以本試驗(yàn)以準(zhǔn)確率作為檢測(cè)指標(biāo)。在兩個(gè)有差別的數(shù)據(jù)集（BIGANN SIFT 1M和Caltech101）中，本文使用不同的二值映射方式，結(jié)果發(fā)現(xiàn)，使用不對(duì)稱距離進(jìn)行重新排序的結(jié)果優(yōu)于直接獲取的成果。

5 結(jié)論

在大規(guī)模數(shù)據(jù)環(huán)境下進(jìn)行快速最近鄰查詢時(shí)，需要量化普通二進(jìn)制數(shù)據(jù)，但是查詢信息的原始特征信息弱化會(huì)導(dǎo)致查詢精度降低。研究者充分利用二進(jìn)制運(yùn)算規(guī)則簡(jiǎn)單、適于邏輯運(yùn)算的特點(diǎn)，提出了一種雙倍比特量化分類索引方法，解決了該問(wèn)題。本文對(duì)量化分類后的二進(jìn)制數(shù)據(jù)和查詢信息未量化前的數(shù)據(jù)進(jìn)行距離計(jì)算，大大提高了查詢的精度和準(zhǔn)確性。大數(shù)據(jù)集試驗(yàn)證明，該方法可以提升15%～25%的最近鄰查詢精度。

參考文獻(xiàn)：

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

[2]RUBLEE E，RABAUD V，KONOLIGE K，et al.ORB：an efficient alternative to SIFT or SURF[C]//International Conference on Computer Vision.2012.

[3]ZITNICK C L.Binary Coherent Edge Descriptors[C]//European Conference on Computer Vision，2010.

[4]馬艷萍，姬光榮，鄒海林，等.數(shù)據(jù)依賴的多索引哈希算法[J].西安電子科技大學(xué)學(xué)報(bào)，2015（4）：159-164.

[5]李雯，鄧涵，許玉珍.基于雙倍比特量化與分段哈希索引的軍事圖像過(guò)濾[J].航天控制，2019（4）：59-65.

[6]宋馥莉，閆培玲.雙倍比特量化近似查詢索引算法研究[J].河南科技，2019（25）：28-31.