艾列富，刘　奎，吴　健

(安庆师范学院　a.计算机与信息学院,b.安徽省智能感知与计算重点实验室， 安徽 安庆　246133)



增强型残差量化的图像视觉特征不完全检索方法

艾列富a,b，刘奎a,b，吴健a,b

(安庆师范学院a.计算机与信息学院,b.安徽省智能感知与计算重点实验室， 安徽 安庆246133)

摘要:针对图像视觉特征的快速检索问题，提出了一种增强型残差量化的不完全检索方法。建立在增强型残差量化的基础上，提出利用多层低复杂度的码书构建包含较大规模倒排列表的多维倒排索引结构，使得只需根据图像视觉特征的量化编码就可以将其快速地插入到倒排索引结构中。此外，结合倒排索引结构，设计了一种不完全检索方法和图像视觉特征之间近似距离的计算方法。通过在公开数据集进行实验和性能对比，所提出不完全检索方法较典型的三种不完全检索方法具有更好的检索精度和检索效率。

关键词：图像视觉特征；增强型残差量化；不完全检索

在互联网+时代，以图像为代表的多媒体信息呈现指数性增长趋势。面对海量的图像库，作为图像搜索服务提供方，只有对图像进行有效地组织和管理，才能为人们提供快速和准确的获取所需图片的检索服务。因此，如何在保证具有较高检索精度的情况下快速检索到相似图像至关重要。在图像检索过程中，图像内容在计算机中通常是以图像视觉特征来表达，因而，图像视觉特征的检索是图像检索的关键之一。

目前图像视觉特征的检索方法主要分为基于树、基于哈希以及基于倒排索引的检索方法三类。

以K-D树[1-2]为代表的树形检索方法在低维特征空间上具有较好的检索效果，但其检索效率会随着维度的增加而不断降低，最终退化到线性检索。

以E2LSH[3]为代表的位置敏感哈希方法通过一组哈希函数，将相似的图像特征映射到哈希表中相同桶或者邻近桶。通常，相比稀疏特征，E2LSH对致密特征向量具有更好的检索效果。然而，E2LSH对检索结果的排序是依据查询特征与所有查询结果之间欧式距离。为了保证检索速度，图像的原始视觉特征需要存储在计算机内存，因而，在一定程度上影响了E2LSH处理的图像库规模。同E2LSH相对的是哈希编码方法，如：谱哈希(Spectral Hasing)[4]、球形哈希(Spherical Hashing)[5]以及k-means哈希(k-means Hashing)[6]等，利用哈希函数将相似的特征映射为相同或者汉明距离相近的二进制编码。相比原始特征，存储二进制编码可以大幅度降低内存空间需求。哈希编码方法使用汉明对检索结果进行排序。汉明距离虽然较欧式距离具有更快的排序速度，但其区分能力受限于所采用的二进制编码长度。

相比上述的两类检索方法，从文本检索领域引入的基于倒排索引的图像检索方法[7]近年来得到更广泛的研究与应用。倒排索引结构中倒排列表由视觉单词标识，每个索引列表相当于一个聚类，对应的聚类中心即为该倒排列表的视觉单词。图像的视觉特征根据欧氏距离被插入到最近的视觉单词对应的倒排列表。目前已有关于有损压缩方法以及特征量化方法研究用于对图像特征进行编码，目的是降低倒排索引中图像视觉特征的存储空间需求。这些方法主要有汉明嵌入[8-9]、非对称汉明嵌入[10]、miniBOF[11]、积量化[12-13]、残差量化[14]以及转换编码[15]等。传统倒排索引结构中倒排列表数即为需要训练的聚类中心数。倒排列表的数量越多，虽然对数据集的划分粒度越细，但是花费在训练聚类中心的开销就会越大。文献[16]利用积量化将特征向量分为两段，通过分别在各子向量空间上训练k个聚类中心，构建包含k2个索引列表的倒排索引结构。

本文利用前期研究工作中提出的增强型残差量化(Enhanced Residual Vector Quantization,ERVQ)方法[17]，首先，提出一种多维倒排索引结构，然后，在此基础上，设计一种不完全检索方法并同目前几种典型的不完全检索方法进行试验比较和分析，以验证本文所提出方法的有效性。

1相关前期工作

ERVQ[17]是一个由多层低复杂度的码书构成的量化器。除了第一层，ERVQ的其他层量化器的输入都是上一层量化器的量化误差；对应地，除了最后一层，每次量化器的量化误差输出作为下一层量化器的输入数据,目的是通过多次对特征的量化误差向量进行量化，减少量化误差。每层量化器都对应一个码书，而这些量化器串联起来就形成ERVQ。ERVQ分为训练和特征量化两个过程。

1.1ERVQ的训练过程

ERVQ的训练划分为初始码书训练和码书优化两个阶段。初始码书采用RVQ[14]方法训练得到。在码书优化阶段， ERVQ逐次对每层码书进行优化。具体地，ERVQ的优化条件是将待优化层之外的码书当作已知码书，将该待优化层作为最后一层未知码书来重新训练。

ERVQ通过计算训练特征向量与其对应于已知层的量化结果之间的残差向量，使得待优化层的训练样本就包含了特征量化的总体量化误差；在此基础上，利用k-means聚类方法重新训练码书并代替代旧的码书。根据新生成的码书，还需更新训练样本集量化结果和对应编码。

同样的优化过程被用于下一层码书的优化。循环如此过程，直至迭代优化过程收敛为止。

1.2ERVQ的量化过程

图1是2层RVQ对一个特征向量x进行量化和编码的示意图，其过程是从第一层到最后一层依次顺序进行的。

(1)

然后利用公式(2)计算x在第一层的量化误差ε1，

(2)

对于图1中的两层ERVQ，特征x的量化过程到此结束。如果ERVQ的层数L>2，则需要继续计算x的第二层量化误差ε2并作为第三层量化器的输入并循环至第L层为止。

图1　ERVQ的特征量化示意图

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

2.1多维倒排索引的构建

基于ERVQ，设计一种多维倒排索引结构，利用较少数量的聚类中心构造具有较大规模倒排列表的索引结构。

利用ERVQ的前M层码书，假定每层码书有k个聚类中心。如果对这M个码书进行笛卡尔组合，那么可以构建最多包含kM个倒排列表的索引结构LIST = list(index1 ,…,,indexM )。倒排列表的索引关键字为(index1,…,indexM)，其中indexi表示第i层码字的ID。

对于同等规模的倒排索引结构(kM个倒排列表)，标准倒排索引方法将图像特征向量x插入倒排索引需要计算x到kM个聚类中心的距离，其时间复杂度为O(d×kM)；而基于ERVQ的多维倒排索引将图像特征向量x插入倒排索引的计算量只发生在计算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实验数据集和环境

公开的sift和gist数据集上[12]作为实验数据用于评估所提方法在近邻搜索方面的性能。sift是局部特征，描述的是图像中偏远的方向梯度的投票直方图。gist是全局特征，描述图像的整体梯度统计信息。

sift和gist数据集各包括三个子集：训练集、数据库和查询集。训练集用于训练倒排索引所需的聚类中心以及向量编码的量化器，数据库集和查询集用于评估近邻搜索性能。数据库集有假期图形库和FLICKER图像库合成，查询数据集提取自假日图像库。sift和gist数据集的具体信息如表1所示。

表1　数据集信息

所有实验都是在一台Intel Core i5-5200U 2.2GHZ CPU,4G内存的PC，MATLAB 2011环境下完成的。

3.2不完全检索的精度及比较

检索性能采用平均召回率Recall@R来衡量检索性能。Recall@R是指为每个查询返回R个最终结果，其中包含最近邻特征的查询特征在查询特征集中的比例。Recall@R的值越大，说明检索精度越高。

本节分别用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值)下，IVFERVQ的最近邻检索的平均查全率指标要优于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)、安徽省高校科研创新平台团队项目资助。

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