增強型殘差量化的圖像視覺特征不完全檢索方法

艾列富，劉　奎，吳　健

(安慶師范學院　a.計算機與信息學院,b.安徽省智能感知與計算重點實驗室， 安徽 安慶　246133)

?

增強型殘差量化的圖像視覺特征不完全檢索方法

艾列富a,b，劉奎a,b，吳健a,b

(安慶師范學院a.計算機與信息學院,b.安徽省智能感知與計算重點實驗室， 安徽 安慶246133)

摘要:針對圖像視覺特征的快速檢索問題，提出了一種增強型殘差量化的不完全檢索方法。建立在增強型殘差量化的基礎上，提出利用多層低復雜度的碼書構建包含較大規(guī)模倒排列表的多維倒排索引結構，使得只需根據圖像視覺特征的量化編碼就可以將其快速地插入到倒排索引結構中。此外，結合倒排索引結構，設計了一種不完全檢索方法和圖像視覺特征之間近似距離的計算方法。通過在公開數據集進行實驗和性能對比，所提出不完全檢索方法較典型的三種不完全檢索方法具有更好的檢索精度和檢索效率。

關鍵詞：圖像視覺特征；增強型殘差量化；不完全檢索

在互聯網+時代，以圖像為代表的多媒體信息呈現指數性增長趨勢。面對海量的圖像庫，作為圖像搜索服務提供方，只有對圖像進行有效地組織和管理，才能為人們提供快速和準確的獲取所需圖片的檢索服務。因此，如何在保證具有較高檢索精度的情況下快速檢索到相似圖像至關重要。在圖像檢索過程中，圖像內容在計算機中通常是以圖像視覺特征來表達，因而，圖像視覺特征的檢索是圖像檢索的關鍵之一。

目前圖像視覺特征的檢索方法主要分為基于樹、基于哈希以及基于倒排索引的檢索方法三類。

以K-D樹[1-2]為代表的樹形檢索方法在低維特征空間上具有較好的檢索效果，但其檢索效率會隨著維度的增加而不斷降低，最終退化到線性檢索。

以E2LSH[3]為代表的位置敏感哈希方法通過一組哈希函數，將相似的圖像特征映射到哈希表中相同桶或者鄰近桶。通常，相比稀疏特征，E2LSH對致密特征向量具有更好的檢索效果。然而，E2LSH對檢索結果的排序是依據查詢特征與所有查詢結果之間歐式距離。為了保證檢索速度，圖像的原始視覺特征需要存儲在計算機內存，因而，在一定程度上影響了E2LSH處理的圖像庫規(guī)模。同E2LSH相對的是哈希編碼方法，如：譜哈希(Spectral Hasing)[4]、球形哈希(Spherical Hashing)[5]以及k-means哈希(k-means Hashing)[6]等，利用哈希函數將相似的特征映射為相同或者漢明距離相近的二進制編碼。相比原始特征，存儲二進制編碼可以大幅度降低內存空間需求。哈希編碼方法使用漢明對檢索結果進行排序。漢明距離雖然較歐式距離具有更快的排序速度，但其區(qū)分能力受限于所采用的二進制編碼長度。

相比上述的兩類檢索方法，從文本檢索領域引入的基于倒排索引的圖像檢索方法[7]近年來得到更廣泛的研究與應用。倒排索引結構中倒排列表由視覺單詞標識，每個索引列表相當于一個聚類，對應的聚類中心即為該倒排列表的視覺單詞。圖像的視覺特征根據歐氏距離被插入到最近的視覺單詞對應的倒排列表。目前已有關于有損壓縮方法以及特征量化方法研究用于對圖像特征進行編碼，目的是降低倒排索引中圖像視覺特征的存儲空間需求。這些方法主要有漢明嵌入[8-9]、非對稱漢明嵌入[10]、miniBOF[11]、積量化[12-13]、殘差量化[14]以及轉換編碼[15]等。傳統(tǒng)倒排索引結構中倒排列表數即為需要訓練的聚類中心數。倒排列表的數量越多，雖然對數據集的劃分粒度越細，但是花費在訓練聚類中心的開銷就會越大。文獻[16]利用積量化將特征向量分為兩段，通過分別在各子向量空間上訓練k個聚類中心，構建包含k2個索引列表的倒排索引結構。

本文利用前期研究工作中提出的增強型殘差量化(Enhanced Residual Vector Quantization,ERVQ)方法[17]，首先，提出一種多維倒排索引結構，然后，在此基礎上，設計一種不完全檢索方法并同目前幾種典型的不完全檢索方法進行試驗比較和分析，以驗證本文所提出方法的有效性。

1相關前期工作

ERVQ[17]是一個由多層低復雜度的碼書構成的量化器。除了第一層，ERVQ的其他層量化器的輸入都是上一層量化器的量化誤差；對應地，除了最后一層，每次量化器的量化誤差輸出作為下一層量化器的輸入數據,目的是通過多次對特征的量化誤差向量進行量化，減少量化誤差。每層量化器都對應一個碼書，而這些量化器串聯起來就形成ERVQ。ERVQ分為訓練和特征量化兩個過程。

1.1ERVQ的訓練過程

ERVQ的訓練劃分為初始碼書訓練和碼書優(yōu)化兩個階段。初始碼書采用RVQ[14]方法訓練得到。在碼書優(yōu)化階段， ERVQ逐次對每層碼書進行優(yōu)化。具體地，ERVQ的優(yōu)化條件是將待優(yōu)化層之外的碼書當作已知碼書，將該待優(yōu)化層作為最后一層未知碼書來重新訓練。

ERVQ通過計算訓練特征向量與其對應于已知層的量化結果之間的殘差向量，使得待優(yōu)化層的訓練樣本就包含了特征量化的總體量化誤差；在此基礎上，利用k-means聚類方法重新訓練碼書并代替代舊的碼書。根據新生成的碼書，還需更新訓練樣本集量化結果和對應編碼。

同樣的優(yōu)化過程被用于下一層碼書的優(yōu)化。循環(huán)如此過程，直至迭代優(yōu)化過程收斂為止。

1.2ERVQ的量化過程

圖1是2層RVQ對一個特征向量x進行量化和編碼的示意圖，其過程是從第一層到最后一層依次順序進行的。

(1)

然后利用公式(2)計算x在第一層的量化誤差ε1，

(2)

對于圖1中的兩層ERVQ，特征x的量化過程到此結束。如果ERVQ的層數L>2，則需要繼續(xù)計算x的第二層量化誤差ε2并作為第三層量化器的輸入并循環(huán)至第L層為止。

圖1　ERVQ的特征量化示意圖

2基于ERVQ的不完全檢索方法

2.1多維倒排索引的構建

基于ERVQ，設計一種多維倒排索引結構，利用較少數量的聚類中心構造具有較大規(guī)模倒排列表的索引結構。

利用ERVQ的前M層碼書，假定每層碼書有k個聚類中心。如果對這M個碼書進行笛卡爾組合，那么可以構建最多包含kM個倒排列表的索引結構LIST = list(index1 ,…,,indexM )。倒排列表的索引關鍵字為(index1,…,indexM)，其中indexi表示第i層碼字的ID。

對于同等規(guī)模的倒排索引結構(kM個倒排列表)，標準倒排索引方法將圖像特征向量x插入倒排索引需要計算x到kM個聚類中心的距離，其時間復雜度為O(d×kM)；而基于ERVQ的多維倒排索引將圖像特征向量x插入倒排索引的計算量只發(fā)生在計算x的前M層量化標識，其時間復雜度為O(d×k×M)。

圖2　基于ERVQ的多維倒排索引的示意圖

2.2不完全檢索方法

給定查詢特征向量q，其檢索過程如下，

Step1: 利用公式(3)計算q與kM個聚類中心的近似歐式距離；

(3)

Step2: 選擇距離最近的w(w≥1)聚類中心，將對應的倒排列表中特征都作為初始查詢結果；

Step3: 利用公式(3)計算q與初始查詢結果之間的距離；

Step4: 排序返回knn個檢索結果。

3實驗

3.1實驗數據集和環(huán)境

公開的sift和gist數據集上[12]作為實驗數據用于評估所提方法在近鄰搜索方面的性能。sift是局部特征，描述的是圖像中偏遠的方向梯度的投票直方圖。gist是全局特征，描述圖像的整體梯度統(tǒng)計信息。

sift和gist數據集各包括三個子集：訓練集、數據庫和查詢集。訓練集用于訓練倒排索引所需的聚類中心以及向量編碼的量化器，數據庫集和查詢集用于評估近鄰搜索性能。數據庫集有假期圖形庫和FLICKER圖像庫合成，查詢數據集提取自假日圖像庫。sift和gist數據集的具體信息如表1所示。

表1　數據集信息

所有實驗都是在一臺Intel Core i5-5200U 2.2GHZ CPU,4G內存的PC，MATLAB 2011環(huán)境下完成的。

3.2不完全檢索的精度及比較

檢索性能采用平均召回率Recall@R來衡量檢索性能。Recall@R是指為每個查詢返回R個最終結果，其中包含最近鄰特征的查詢特征在查詢特征集中的比例。Recall@R的值越大，說明檢索精度越高。

本節(jié)分別用IVFERVQ、IVFRVQ和IVFPQ表示基于多維倒排索引、基于RVQ[14]和基于PQ[12]的不完全檢索方法。此外，本文還比較IVFERVQ同IVFPQ的結構化版本IVFS-PQ和基于海明嵌入(Hamming Embedding,HE)[9]的檢索性能進行對比。

圖3　sift特征集上檢索性能比較

在圖3和4的實驗中，對sift和gist特征集均采用64bits對其進行編碼。IVFPQ、IVFPQ和HE都構建包coarseK個倒排列表；IVFERVQ和IVFRVQ利用圖像特征的前M層編碼插入索引結構。其中，圖中的參數L表示RVQ和ERVQ的碼書層數，k為每層碼書設定的聚類中心數。IVFPQ和IVFS-PQ均采用引用文獻中的參數設置。

從圖中可以看出，所有不完全檢索方法的Recall值均隨著w值的增長而變大并趨向于一個穩(wěn)定值。此外，在同等參數條件(相同w值)下，IVFERVQ的最近鄰檢索的平均查全率指標要優(yōu)于IVFRVQ、IVFPQ、IVFS-PQ和HE。

3.3不完全檢索的效率及比較

表2和3對比了以上各種不完全檢索方法在sift和gist特征集上的查詢效率。在表2的實驗結果中，IVFERVQ的檢索速度在M=1時要高于IVFRVQ和IVFPQ，并且平均召回率也更好；當M=2時，IVFERVQ的平均查詢時間要多余IVFRVQ，但具有更高的平均召回率。

表2　sift特征集上檢索效率對比

表3　gist特征集上檢索效率對比

4結論

面向圖像視覺特征，本文對基于ERVQ的不完全檢索方法進行了研究。在前期研究工作的基礎上，提出了基于ERVQ的多維倒排索引的構建方法，同時，設計了相應的不完全檢索方法以及查詢特征與數據庫特征之間歐氏距離的計算方法。通過實驗將本文所提出的不完全檢索方法同目前典型的3種基于倒排索引的不完全檢索方法進行對比，實驗結果證明，本文所提出的不完全檢索方法較其他方法具有更好的平均召回率和檢索效率。

參考文獻：

[1] Beis J S,Lowe D G.Shape Indexing Using Approximate Nearest-neighbour Search in High-dimensional Spaces[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR),1997:1000-1006.

[2] Anan C S,Hartley R.Optimised KD-trees for Fast Image Descriptor Matching[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2008:1-8.

[3] Datar M,Immorlica N,Indyk P,et al.Locality-sensitive Hashing Scheme Based on P-stable Distributions[C]//Proceedings of the 20th Annual Symposium on Computational Geometry,2004:253-262.

[4] Yair W,Antonio T,Rob F.Spectral Hashing[C]//NIPS,2008:1-8.

[5] Heo J P,Lee Y,He J,et al.Spherical Hashing[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2012:2957-2964.

[6] He K,Wen F,Sun J K.K-means Hashing: an Affinity-preserving Quantization Method for Learning Binary Compact Codes[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2013:1-8.

[7] Josef S,Andrew Z.Video Google: a Text Retrieval Approach to Object Matching in Video[C]//Proceedings of IEEE International Conference on Computer Vision (ICCV),2003:1470-1477.

[8] Herve J,Matthijs D,Cordelia S.Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search[C]//Proceedings of ECCV,2008:304-317.

[9] Herve J,Matthijs D,Cordelia S.Improving Bag-of-feature for Large Scale Image Search[J].International Journal of Computer Vision,2010,87(3):316-336.

[10] Mihir J,Herve J,Patrick G.Asymmetric Hamming Embedding: Taking the Best of Our Bits for Large Scale Image Search[C]//Proceedings of the 19th ACM International Conference on Multimedia,2011:1441-1444.

[11] Herve J,Matthijs D,Cordelia S.Packing bag-of-features[C]//Proceedings of the IEEE 12th Conference on Computer Vision (ICCV),2009:2357-2364.

[12] Herve J,Matthijs D,Cordelia S.Product Quantization for Nearest Neighbor Search[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(1):117-128.

[13] Ge T,He K,Ke Q,et al.Optimized Product Quantization for Approximate Nearest Neighbor Search[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2013:1-8.

[14] Chen Y,Guan T,Wang C.Approximate Nearest Neighbor Search by Residual Vector Quantization[J].Sensors,2010,10:11259-11273

[15] Jonathan B.Transform Coding for Fast Approximate Nearest Neighbor Search in High Dimensions[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2010:1815-1822.

[16] Babenko A,Lempitsky V.The Inverted Multi-Index[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2012:3069-3076.

[17] Ai Liefu, Yu Junqing, He Yunfeng,et al.Optimized Residual Vector Quantization for Efficient Approximate Nearest Neighbor Search[J].Multimedia Systems,2015 (已在線出版)

[責任編輯：張永軍]

Enhanced Residual Vector Quantization-based Non-exhaustive Retrieval for Image Visual Features

AI Lie-fua,b, LIU Kuia,b, WU Jiana,b

(a.Department of Computer and Information, b.The University Key Laboratory of Intelligent Perception and Computing of Anhui Province, Anqing Normal University, Anqing, Anhui 246133, China)

Abstract:A non-exhaustive retrieval method based on enhanced residual vector quantization is proposed for rapid retrieval among image visual features.Built on enhanced residual vector quantization,a multi-inverted index composed of large number of inverted lists is presented,which is constructed by several codebooks of low complexity.Then,a visual feature can be quickly inserted into the index according to its quantization codes.By combining with the multi-inverted index,a non-exhaustive retrieval method is designed,also,the method of computing the approximate distance between image visual features is shown.The experimental results on public datasets show that the proposed non-exhaustive retrieval method outperform 3 existing typical methods over retrieval accuracy and efficiency.

Key words:image visual feature; enhanced residual vector quantization; non-exhaustive retrieval

中圖分類號：TP301.6

文獻標識碼：A

文章編號：1673-162X(2016)01-0046-06

作者簡介：艾列富(1985—)，男，安徽安慶人，安慶師范學院計算機與信息學院講師，博士。

基金項目：安徽省自然科學基金項目(1608085MF144, 1608085QF131)、安徽省教育廳自然科學研究項目(AQKJ2015B006)、安徽省高校科研創(chuàng)新平臺團隊項目資助。

收稿日期：2015-11-10修回日期：2015-12-23