大规模图像特征检索中查询结果的自适应过滤  

Adaptively Filtering Query Results for Large Scale Image Feature Retrieval

作　　者：艾列富[1,2] 于俊清[1] 管涛[1] 何云峰[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074 [2]安庆师范学院计算机与信息学院,安徽安庆246133

出　　处：《计算机学报》2015年第1期122-132,共11页Chinese Journal of Computers

基　　金：国家自然科学基金(61173114;61202300;61272202);武汉市应用基础研究计划项目基金(2014010101010027)资助~~

摘　　要：针对大规模图像的快速检索问题,提出了面向倒排索引结构的检索方法中查询结果的自适应过滤方法:全面过滤和不完全过滤.目的是在不影响查询精度的前提下,提高查询效率.根据查询特征所在的空间位置,全面过滤通过构造以查询特征点为球心的超球体并自适应地计算半径,只对位于超球体内部的查询结果进行排序,从而减少需要排序的查询结果数量,提高查询效率.在此基础上,为了降低过滤查询结果的时间开销,不完全过滤将倒排列表划分为若个子倒排列表并将对应的聚类中心用于过滤查询结果.为了验证所提出方法的有效性,以一种典型检索方法:基于残差量化的检索方法为应用实例,分别将全面过滤和不完全过滤与该检索方法相结合.此外,为了提高特征量化效率,将一种欧式距离下限定理与残差量化相结合并用于过滤特征量化过程中非近邻聚类中心.通过在公开数据集进行实验,实验结果表明在保证具有相同平均查全率的前提下,全面过滤和不完全过滤都能明显减少基于残差量化的检索方法的查询时间,不完全过滤比全面过滤具有更快的检索速度.此外,非近邻聚类中心过滤可以有效提高残差量化的特征量化效率.Aiming at the problem of rapid retrieval in large scale image,two methods：exhaustive filtration and non-exhaustive filtration are proposed to filter query results for inverted indexing structure-based retrieval methods.The objective is to improve query efficiency without influencing accuracy.Exhaustive filtration constructs a hyper-sphere whose center is the query feature,and the corresponding radius is calculated adaptively.Only the features that lie in the hyper-sphere are used to sort,then the number of features need to be sorted is reduced and the query efficiency is increased.Based on this,to reduce the time costs on filtering query results,non-exhaustive filtration partitions the inverted list into several sub-inverted lists,where the corresponding centroids are used to filter query results.To demonstrate the effectiveness of proposed methods,a typical method：residual vector quantization-based（RVQ）retrieval is used as an application example,which is combined with exhaustive filtration and non-exhaustive filtration respectively.Besides,to improve the efficiency on quantizing feature vectors,RVQ is combined with a theorem of lower bound of Euclidean distance which is used to filter non-nearest centroids in vectorquantization process.The experimental results on public datasets show that both exhaustive filtration and non-exhaustive can noticeably reduce the query time of RVQ-based retrieval in the condition of same average recall rate. Moreover,non-exhaustive filtration is faster than exhaustive filtration.Besides,RVQ can be efficiently improved by filtering non-nearest centroids.

关 键 词：大规模图像特征 查询结果 自适应过滤 超球体 距离下限 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]