基于加权特征空间信息视觉词典的图像检索模型
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于加权特征空间信息视觉词典的图像检索模型范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：针对传统的视觉词袋模型中视觉词典对底层特征量化时容易引入量化误差，以及视觉单词的适用性不足等问题，提出了基于加权特征空间信息视觉词典的图像检索模型。从产生视觉词典的常用聚类算法入手，分析和探讨了聚类算法的特点，考虑聚类过程征空间的特征分布统计信息，通过实验对不同的加权方式进行对比，得出效果较好的均值加权方案，据此对视觉单词的重要程度加权，提高视觉词典的描述能力。对比实验表明，在ImageNet图像数据集上，相对于同源视觉词典，非同源视觉词典对视觉空间的划分影响较小，且基于加权特征空间信息视觉词典在大数据集上更加有效。
关键词：图像搜索；视觉词袋模型；加权特征空间信息；视觉词典；聚类算法
0 引 言
智能终端设备如智能手机、平板电脑，以及数码相机和数码摄像机的普及和便携化，使这些多媒体采集设备已经成为人们日常生活中不可缺少的一部分。同时智能终端与互联网之间的交互越来越方便，人们大量地使用这些设备来上传、浏览和交流拍摄的数字图像。据Intel统计[1]，仅在Flickr上就有2000万的图像浏览次数。据统计[2]，截至2011年8月，Flickr上的图像总数已达60亿张。相对于文字的信息而言，数字图像具有直观易于理解、信息层次感强、重点突出的特点。面对这无比庞大的图像数据库，人们自然会产生这样的需要：从这海量图像中寻找满足自己要求的图像。因此，人们开发了各种各样的图像检索系统，以满足不同人群的各式各样的需求。
基于内容的图像检索（Content Based Image Retrieval，CBIR）模型[3-5]的核心思想是模拟人对图像的认知，通过对图像的内容进行计算机层面的分析，根据内容建立语义索引，记录图像深入层面的信息，从而更好地理解用户的需求，呈现更高质量的检索效果。目前有多个在线的基于内容的图像检索系统，比如国外的TinEye[6]，Google Images[7]和百度的百度识图等。
近年来，国内外对图像检索的研究主要集中在对图像的底层视觉特征以及全局特征的相关反馈的研究。Haas等[8]提出了基于感知学习的相关反馈算法；Wang等[9]提出了带重启的随机游走的图像注释提前算法，从其注释中找到相关视觉特征；针对图像旋转对图像检索造成的影响，朱正礼等[10]提出了预计非下采样轮廓变换、灰度共生矩阵和新相似性度量的旋转不变纹理图像检索算法。受文本领域信息检索的启发，Sivic等[11]将文本信息检索中的词袋模型（Bag of Word，BoW）引入了基于内容的图像检索领域，提出了视觉词袋模型（Bag of Visual Word， BoVW），其核心是将图像局部特征量化到事先聚类的视觉词典上，然后统计一幅图像中出现的视觉单词数量，将图像表示成视觉单词的统计直方图，然后通过倒排索引建立图像集合的数据库表示。尽管BoVW模型是一个较好的用于表示海量图像的方法，但是它仍然有很多不足之处，主要体现在视觉词典的使用上。常用的视觉词典主要具有以下几个缺点：1）在使用视觉词典量化图像的视觉单词时引入了噪声；2）视觉词典中单词的“多义性”没有得到充分挖掘；3）视觉词典这种表示形式本质上丧失了局部特征的空间信息；4）视觉单词和视觉词典的描述能力没有得到充分的挖掘。
针对上述问题，本文从用于产生视觉词典的常用聚类算法入手，分析和探讨了这些聚类算法的特点，同时考虑聚类过程中利用特征空间征分布的统计信息，产生视觉词典的优劣描述，并充分利用聚类算法产生的聚类中心会向特征空间征密集的方向移动这一特性，来提高视觉词典的表示能力。该方法与传统的词袋模型和词频逆文档频率（TFIDF）加权方式紧密结合，可以提升视觉词典的可迁移性和图像检索的检索效果
2 基于加权特征空间信息的视觉词典
2.1 对特征空间的分析
特征空间指的是由特征提取（Feature Extraction）步骤得到的特征向量（Feature Vector）生成的向量空间，该概念与线性代数中对应于特征向量（Eigen Vectors）的特征空间不一样。特征空间的每个点均对应一个特征向量，且每个定长的特征向量均对应于等维度的特征空间中的一个点。对特征空间和空间中的关系更简洁与准确的描述，意味着对由特征向量表示的图像数据集更为紧致与精确地表达，也就是说能够提高图像检索系统的图像存储量与检索的效果。因此，如何刻画特征空间，如何用一定的方式来描述在特征空间中匹配的特征向量之间的关系，是非常重要的问题。
视觉词典本质上是一种对特征空间中向量匹配关系的描述。一般来说，通过特征提取得到的特征向量，利用视觉词典量化为特定的视觉单词。这个过程在特征空间中的表现即为对特征空间中点的聚类。因此，基本的视觉词典模型中视觉词典对特征空间中点与点之间关系的刻画方法，即对距离较近、成簇的点进行聚类。如图2中，圆圈代表视觉单词，以这些视觉单词为中心，将特征空间划分为多个子空间，也称为簇。子空间中的单个特征，量化为子空间中的某个视觉单词。这种认为被分到一个簇中的两个点即匹配的量化方法创建了一种较为粗糙的特征空间中点的匹配关系。
区域2中的方块中的点与四个视觉单词的距离都比较近，从图中可看出该点与其他点形成的较为密集的团的距离都比较远，本不属于任何一个簇，但是在该视觉词典中被量化到区域2中。本来应该与区域2中方块的点距离较近的两个方块中的点在该视觉词典的量化方法下被分到了不同的视觉单词产生的簇中，这显然不够合理，而这一现象产生的根本原因在于对视觉单词的聚类过程中仅仅考虑到该点与聚类中心的距离，而没有考虑到视觉词典中视觉单词的重要性的不同，也就是视觉单词的权重问题。因此，针对该缺点，本文提出了基于加权的特征空间信息的视觉词典的方法。
2.2 基于加权特征空间信息的视觉词典
本节分析了视觉词典对特征空间中点与点间关系描述能力的重要性，并提出一种利用特征空间统计信息来对视觉词典中视觉单词的重要程度进行度量的方法，来提高视觉词典对点间关系的描述能力，从而提高检索的效果。
选用对检索效果的评价标准平均正确率均值（mean Average Precision，mAP）来评估视觉词典的可迁移性。
在传统的视觉词典方法中，单张图像中的特征量化为视觉词典中最近邻的视觉单词，图像表示为一个直方图向量X，其中X∈ik，k为视觉词典词汇量的大小。本文方法受到文献[16-17]的启发，这两篇文章均指出：随着k均值聚类的聚类中心数目的增加，聚类中心会向特征空间征点更为密集的方向移动。那么，如果一个簇征分布得越“松散”，那么这个簇对应的视觉单词的区分力可能更强。为了研究特征子空间的簇征点分布与视觉词典的关系，统计了每个簇征点到聚类中心的距离的分布信息随着图像数据集和视觉词典词汇量的改变对图像检索效果产生的影响，具体来说就是利用各种特征子空间簇的统计信息作为簇对应的视觉单词的权重，对视觉词典进行加权：计算统计向量D∈ik，然后每个视觉单词均被统计信息加权：
1） 对于特征空间中点距离的均值来说，非同源视觉词典对特征空间进行划分，点距离的均值基本不会随着视觉词典中视觉单词数量的增加而变化，从图4（a）和（c）中可以看出，随着非同源视觉词典视觉单词数量由1万增加到200万，而均值由0.97下降到0.7，且呈直线下降；同源视觉词典对特征空间进行划分，点距离的均值随着视觉词典中视觉单词数量的增加而逐渐减小。之所以出现这种情况是因为非同源视觉词典只能对图像的整体特征空间信息进行划分，也就是说非同源视觉词典对图像的具体特征空间信息区分不明显，而对于同源视觉词典而言，视觉词典数量的增加更加反映了图像具体的视觉信息，用该视觉词典来划分视觉空间意味着更小的划分尺度，因此点距离的均值会逐渐减小。此外，随着视觉词典词汇量增大，同源视觉词典与非同源视觉词典的均值曲线的差距越来越大，如图4（a）和（c）中两条曲线的差距越来越大。这验证了随着k均值聚类中心数目的增多，聚类中心会向特征空间征密集的方向移动，所以随着视觉单词数量的增加，聚类中心向密集区域移动的趋势也逐渐累积，从而均值逐渐减小。另外一种可能原因是，随着视觉词典的词汇量越来越大，聚类中心对特征空间的划分越来越密集，每个簇的大小也逐渐减小，因此均值逐渐减小。但这种可能性被非同源的视觉词典上对均值的统计实验排除，因为在非同源的视觉词典对特征空间的划分中，并未出现这种现象。
2）对于特征空间中点距离的平均方差来说，非同源视觉词典对特征空间进行划分，点距离的平均方差值基本不随着视觉词典中视觉单词数量的增加而变化，从图4（b）和（d）中other曲线可以看出来，视觉词典的单词数由1万增加到200万，其平均方差在0.18～0.21变动；同源视觉词典对特征空间进行划分，点距离的平均方差值随着视觉词典中视觉单词数量的增加而逐渐增大，从图4（b）和（d）中self曲线可以看出，平均方差在0.18～0.31变动。随着聚类中心向密集区域移动的趋势逐渐累积，在每个簇中，虽然聚类中心周围的特征向量到该聚类中心的平均距离在减小，在平均方差的变化过程中，也有例外出现，比如在图4（d）中，平均方差就是由0.19下降到0.18，然后才逐渐增加到0.19。这是因为每个簇中仍然存在一部分特征向量，这些特征向量到聚类中心的距离仍然比较大。正是因为这些点的存在，导致了点到聚类中心平均距离的变化范围较大，从而增大了平均方差。这些点使得该簇不能成为一个“好”的簇，因为该簇中不仅存在一些分布比较集中的特征点，还存在着一些比较零散的特征点，将这些零散的特征点量化为该簇的聚类中心实际上是有问题的。该分析在本节之后的实验中也得到了验证。
3）结合1）和2）中的现象，可以发现这也从另外一个方面证实了视觉词典存在可迁移性。从图4中可以看出，均值曲线和平均方差值曲线比较平缓，没有特别明显的变化趋势，比如在数据集为8×104时，均值的变化范围为0.8～1，而平均方差更小，在0.18～0.19。究其原因是由于同源的视觉词典由产生该视觉词典的图像数据集的局部特征聚类得到，k均值聚类过程的特点反映于平均方差值曲线上，如图4（b）所示，
平均方差随着视觉词典数量的增加，随着视觉词典征向量的增加，同源视觉词典的检索效果要明显好于非同源视觉词典的检索效果，
这是由于数据集越大，图像的特征向量越分散。而非同源的视觉词典中视觉单词的产生过程与图像数据集的局部特征没有任何关系，因此，同源的视觉词典反映了产生该视觉词典的图像数据集的特征分布的特点，利用同源视觉词典进行检索的效果会比非同源视觉词典表现得更好一些。
4）随着数据集中图像数量的增加，均值曲线、平均方差值曲线之间的差距在逐渐减小。这表明：随着数据集增大，特征向量数量增加，特征空间中每个簇中的点数量也随之增加，同源和非同源的视觉词典对特征空间的划分之间的差距也随之减小。
3.2 对加权视觉词典方法的验证
接下来将在不同大小的数据集上对加权视觉词典方法的有效性进行验证。在1万和8万这2个不同级别的数据集上进行检索的实验，结果如图5所示，selfw与otherw表示加权视觉词典方法。
当实验所用的混杂数据集较小时，如1万张图像的情况，本文方法在视觉词典小于20万时表现得比未加权的结果好，但是超过了20万之后，加权的方法就不如未加权的方法，这是因为在数据集较小时，以均值为权重的视觉单词更容易体现出该特征在数据集中的特别之处，但是当数据集数量大于20万之后，这些加权后的视觉词典会“淹没”在大量的混杂数据集中。同时因为视觉词典过多带来的特征空间的过分割和错误聚类，也在一定程度上降低了检索的效果：当实验数据集较小时，特征空间征点的数目也较少，因此产生过多的视觉单词将对特征空间进行过多的分割，导致每个簇中包含的特征数目较少，因此距离的均值不够稳定，用来作为权重的度量也不够好。当实验数据集的数目足够大时，每个簇中包含的特征数目上升，均值较为稳定了，因此权重的度量方法在这种情形下比没有权重的度量更好。
本方法在视觉词典上进行了加权，而图像索引系统为倒排表，由于倒排表表示的稀疏性，仅仅需要在图像的相似度计算时，对图像的词袋表示直方图中非0的bin进行加权。而从一幅中等分辨率的图像（如640×480像素）中提取的SIFT描述子数量一般为几百到上千个，也就是说，对每幅图像量化后，得到的视觉单词种类一般也就几百种。从倒排表的结构来看，进行检索时，仅仅需要对查询图像中出现的视觉单词对应的列表进行检索。对于一个10万大小的图像数据集来说，粗略估计，倒排表中索引了约1000×10万=1亿条目，使用100万量级的视觉词典时，每个视觉单词对应的列表长度约为100。也就是说，检索一张图像时，与标准的词袋模型方法相比，所增加的计算量为100×1000=10万次浮点计算。这对于现代的CPU来说计算时间仅为毫秒量级。因此，本文的方法几乎不会降低词袋模型图像检索的速度。
4 结语
针对传统视觉词袋模型中对视觉单词的重要程度的估计不足，以至于在图像视觉特征量化时引起误差等问题，本文提出了一种基于特征空间的统计信息进行加权的视觉词典方法。对BoVW图像检索框架进行简要介绍，分析了视觉词典在该模型中的重要性；对特征空间中的特征分布进行分析，并根据前人所描述的聚类方法中聚类中心移动的特点，设计了具有针对性的基于加权特征空间信息的视觉词典，然后在多组图像数据集上进行检索实验，分析了不同加权方式的优劣，从中选择了最优的均值加权方法；最后利用统计实验和检索实验分析特征空间的分布以及验证加权视觉词典方法的有效性。实验结果表明，利用非同源视觉词典来划分特征空间，均值和平均方差的加权方法与视觉单词数量无关；而对于同源视觉词典而言，均值的加权会随着视觉单词数量增加而降低，而平均方差的加权会随着视觉单词数量增加而增加。最后，通过实验证明了本文方法简单而且有效，内存占用低，因此易于与其他对标准词袋模型方法结合。
参考文献：
[1]TEMPLE K. What happens in an Internet minute？ [EB/OL]. （2012-03-13） [2013-05-15]. http：///whathappensinaninternetminute/.
[2]How many photos are uploaded to Flickr every day， month， year？ [EB/OL]. （2012-03-20） [2013-06-05]. http：///photos/franckmichel/6855169886/.
[3]SMEULDERS A W M， WORRING M， SANTINI S， et al.Contentbased image retrieval at the end of the early years [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 22（12）： 1349-1380.
[4]LEW M S， SEBE N， DJERABA C， et al. Contentbased multimedia information retrieval： state of the art and challenges [J]. ACM Transactions on Multimedia Computing， Communications， and Applications， 2011，2（1）：1-19.