论文部分内容阅读
摘要：文章提出了一種适用于大规模数据集的图像检索算法，目的是在有干扰的情况下，准确地找出目标图片。本文采用局部特征算子作为衡量标准，又创造性地在每个视觉词袋后[1]建立图像索引，形成以特征算子为基元的带权视觉词典结构，在保证检索精度的前提下尽可能的提高检索速度，更好的满足了大规模数据对效率的要求。实验证明，该算法具对存在一定干扰的图像效果显著，鲁棒性强，达到了国际一流水准。
关键词：图像检索；局部特征算子；带权视觉词典；干扰图像
中图分类号：TP391.41 文献标识码：A文章编号：1007-9599 (2011) 20-0000-01
Interference Image Quick Search Algorithm
Yin Changqing,Mao Wei
(School of Software Engineering,Tongji University,Shanghai200092,China)
Abstract:This paper presents a large-scale data sets for image retrieval algorithm,the aim is the case of interference,and accurately identify the target picture.In this paper,the local operator as a measure of standard features,but the visual creativity of each word in the bag[1]to establish an image index,to form a characteristic element of the operator-based visual dictionary with the right structure to ensure the accuracy of the premise to make retrieval possible to improve the retrieval speed,and better meet the requirements of large-scale data on the efficiency.Experiments show that the algorithm with the image of the interference effect of certain significant,robust,reaching a world-class standards.
Keywords:Image retrieval;Local feature operator;Dictionary with the right visual;Interference image
一、引言
图像检索指的是根据用户提交的查询条件，在图像数据库中搜索并找出相符合的图片或图片集。根据目的不同，可以分为精确匹配检索和模糊相似检索；根据衡量标准不同，又可以分为立足于文本，立足于图像内容以及文本和内容相结合三种形式。其中基于内容的检索方式在近几年来发展迅速，是图像检索中一个十分热门的研究方向。本文中要讨论的正是基于内容的图像精确匹配检索算法。
二、本文算法
在选择特征描述符之前，我们首先使用FAST-9算法得到图像的关键点，之后部分采用SIFT方法得到特征描述符。这样每个关键点就可以产生一个128维的特征向量。由于图像特征描述符的数量庞大，直接建立索引的开销不菲，特别是针对大规模图像，可行性低。所以我们提出了一种带权的视觉词典模型，对所有图像的特征描述符进行聚类，得到一定数量的视觉单词。每个视觉单词由2部分组成，前一部分是128维的特征描述符，后一部分是由一系列图像序号组成的索引列表。考虑到检索效率，下一步用这些视觉单词的key部分建立kd-tree。我们就把这样一个由一棵128维的key搜索树和叶子节点所对应的value值所组成的数据结构称为带权视觉词典。
在得到目标图像之后，我们首先提取图像的关键点生成相应的特征描述符。再把这些特征描述符分别带入视觉词典进行检索，找到相对应的key值（基于kd-tree的近似最近邻搜索[2]），同时也就得到了这个key值所对应的value向量。之后把所有的关键点采集到的value值进行加权，即可以得到图像权重列表，并且很容易的就可以从中找出Wmax。按照上述模型，目标图像I总能找到一张和他最接近临时检索结果I’。假设目标图像有T个特征点，图像库的大小为M，临时检索结果的权重为Wmax，这里我们需要引入一个百分比阈值Per，如果 ，那我们就认为这个Wmax对应的I’为最后的检索结果；否则目标图像不存在于图库中。
三、实验结果和分析
本文选取Corel图像库进行测试。把所有的9907张图像全部作为样本进行训练，建立相应的带权视觉词典。之后取出有不同关键点数量的80张图片作为目标图片，和传统的视觉词袋法[1]进行对比测试。本文算法的平均耗时在600ms左右，而传统的视觉词袋算法则需要大约2s的时间，而且算法的平均耗时随着关键点数目的增多有着显著的上升趋势。显然，在图像数量庞大的情况下，传统的时间词袋方法已经很难达到实际应用的需求。
我们再次从图像库中随机选出200张图片，把他们均匀分为4类。对其中3类进行边缘切割、旋转变换和加上干扰像素。把处理过的图片作为目标图片进行检索，测试系统应对各种不同干扰的能力。这里比较了本文算法和传统基于全局特征的算法。对于没有任何干扰的图像，它们都有很高的正确率。但是在切割干扰和像素值干扰测试上，基于颜色特征算法和基于纹理特征算法的正确率都有了明显的下降，其中当图像存在像素干扰时，基于颜色算法的正确率甚至不足10%。从实验中不难发现，本文算法的正确率虽然也有小幅下降，但是它的抗干扰能力明显强于其他两种算法。
eBay每天都会新增成千上万的商品，有些图像是禁止用户上传的。这里我们有一个黑名单图像库，共计有11579张图片，以它为样本建立视觉词典。此外还有一个记录2011年第一季度eBay美国站点新上传图片的图像库（314293张），我们称它为待测图库。现在的任务是在待测图库中找出那些违规图片。可以想象，在实际上传图片的过程中，卖家很可能会对商品打上自己的水印，或者是对图片进行一定的处理，这样会造成图像的干扰很大。实验结果表明，基于颜色特征的算法找出的违规图片数量最少；基于纹理特征找出的图片数量要高于基于颜色特征的算法；而通过本文算法找到的违规图片最多，数量上要远远高于前两者。显而易见本文算法在查全率上要更胜一筹。
四、结论
本文的算法以关键点为基元，建立带权数据词典，通过所得权重大小来检索图像，打破了常规检索算法以图像为基元建立直方图的检索模式。实验结果表明，本算法在检索速度上要明显优于传统的视觉词袋法，同时在应对目标图像干扰时，本算法表现出很好的抗噪能力，鲁棒性强。
参考文献：
[1]G.Csurka,C.Bray,C.Dance,and L.Fan.Visual categorization with bags of keypoints[C].In Proc of ECCV Workshop on Statistical Learning in Computer Vision,Prague,Czech Republic,2004.
[2]Muja M,Lowe D.Fast approximate nearest neighbours with automatic algorithm configuration[C].4th International Conference on Computer Vision Theory and Applications.France,Springer Verlag,2009,331-340.
关键词：图像检索；局部特征算子；带权视觉词典；干扰图像
中图分类号：TP391.41 文献标识码：A文章编号：1007-9599 (2011) 20-0000-01
Interference Image Quick Search Algorithm
Yin Changqing,Mao Wei
(School of Software Engineering,Tongji University,Shanghai200092,China)
Abstract:This paper presents a large-scale data sets for image retrieval algorithm,the aim is the case of interference,and accurately identify the target picture.In this paper,the local operator as a measure of standard features,but the visual creativity of each word in the bag[1]to establish an image index,to form a characteristic element of the operator-based visual dictionary with the right structure to ensure the accuracy of the premise to make retrieval possible to improve the retrieval speed,and better meet the requirements of large-scale data on the efficiency.Experiments show that the algorithm with the image of the interference effect of certain significant,robust,reaching a world-class standards.
Keywords:Image retrieval;Local feature operator;Dictionary with the right visual;Interference image
一、引言
图像检索指的是根据用户提交的查询条件，在图像数据库中搜索并找出相符合的图片或图片集。根据目的不同，可以分为精确匹配检索和模糊相似检索；根据衡量标准不同，又可以分为立足于文本，立足于图像内容以及文本和内容相结合三种形式。其中基于内容的检索方式在近几年来发展迅速，是图像检索中一个十分热门的研究方向。本文中要讨论的正是基于内容的图像精确匹配检索算法。
二、本文算法
在选择特征描述符之前，我们首先使用FAST-9算法得到图像的关键点，之后部分采用SIFT方法得到特征描述符。这样每个关键点就可以产生一个128维的特征向量。由于图像特征描述符的数量庞大，直接建立索引的开销不菲，特别是针对大规模图像，可行性低。所以我们提出了一种带权的视觉词典模型，对所有图像的特征描述符进行聚类，得到一定数量的视觉单词。每个视觉单词由2部分组成，前一部分是128维的特征描述符，后一部分是由一系列图像序号组成的索引列表。考虑到检索效率，下一步用这些视觉单词的key部分建立kd-tree。我们就把这样一个由一棵128维的key搜索树和叶子节点所对应的value值所组成的数据结构称为带权视觉词典。
在得到目标图像之后，我们首先提取图像的关键点生成相应的特征描述符。再把这些特征描述符分别带入视觉词典进行检索，找到相对应的key值（基于kd-tree的近似最近邻搜索[2]），同时也就得到了这个key值所对应的value向量。之后把所有的关键点采集到的value值进行加权，即可以得到图像权重列表，并且很容易的就可以从中找出Wmax。按照上述模型，目标图像I总能找到一张和他最接近临时检索结果I’。假设目标图像有T个特征点，图像库的大小为M，临时检索结果的权重为Wmax，这里我们需要引入一个百分比阈值Per，如果 ，那我们就认为这个Wmax对应的I’为最后的检索结果；否则目标图像不存在于图库中。
三、实验结果和分析
本文选取Corel图像库进行测试。把所有的9907张图像全部作为样本进行训练，建立相应的带权视觉词典。之后取出有不同关键点数量的80张图片作为目标图片，和传统的视觉词袋法[1]进行对比测试。本文算法的平均耗时在600ms左右，而传统的视觉词袋算法则需要大约2s的时间，而且算法的平均耗时随着关键点数目的增多有着显著的上升趋势。显然，在图像数量庞大的情况下，传统的时间词袋方法已经很难达到实际应用的需求。
我们再次从图像库中随机选出200张图片，把他们均匀分为4类。对其中3类进行边缘切割、旋转变换和加上干扰像素。把处理过的图片作为目标图片进行检索，测试系统应对各种不同干扰的能力。这里比较了本文算法和传统基于全局特征的算法。对于没有任何干扰的图像，它们都有很高的正确率。但是在切割干扰和像素值干扰测试上，基于颜色特征算法和基于纹理特征算法的正确率都有了明显的下降，其中当图像存在像素干扰时，基于颜色算法的正确率甚至不足10%。从实验中不难发现，本文算法的正确率虽然也有小幅下降，但是它的抗干扰能力明显强于其他两种算法。
eBay每天都会新增成千上万的商品，有些图像是禁止用户上传的。这里我们有一个黑名单图像库，共计有11579张图片，以它为样本建立视觉词典。此外还有一个记录2011年第一季度eBay美国站点新上传图片的图像库（314293张），我们称它为待测图库。现在的任务是在待测图库中找出那些违规图片。可以想象，在实际上传图片的过程中，卖家很可能会对商品打上自己的水印，或者是对图片进行一定的处理，这样会造成图像的干扰很大。实验结果表明，基于颜色特征的算法找出的违规图片数量最少；基于纹理特征找出的图片数量要高于基于颜色特征的算法；而通过本文算法找到的违规图片最多，数量上要远远高于前两者。显而易见本文算法在查全率上要更胜一筹。
四、结论
本文的算法以关键点为基元，建立带权数据词典，通过所得权重大小来检索图像，打破了常规检索算法以图像为基元建立直方图的检索模式。实验结果表明，本算法在检索速度上要明显优于传统的视觉词袋法，同时在应对目标图像干扰时，本算法表现出很好的抗噪能力，鲁棒性强。
参考文献：
[1]G.Csurka,C.Bray,C.Dance,and L.Fan.Visual categorization with bags of keypoints[C].In Proc of ECCV Workshop on Statistical Learning in Computer Vision,Prague,Czech Republic,2004.
[2]Muja M,Lowe D.Fast approximate nearest neighbours with automatic algorithm configuration[C].4th International Conference on Computer Vision Theory and Applications.France,Springer Verlag,2009,331-340.