基于反馈框架的交互式图像检索系统∗

朱 翔 林学飞

（南京理工大学计算机科学与工程学院 南京 210094）

基于反馈框架的交互式图像检索系统∗

朱 翔 林学飞

（南京理工大学计算机科学与工程学院 南京 210094）

随着图像数量的迅猛增长，图像检索已经在计算机视觉领域引起了越来越多的关注。遗憾的是，其中也存在着人们的检索需求和搜索结果不一致的问题。为此，论文基于改进的聚类算法和重排名算法，提出一种基于反馈框架的交互式图像检索系统来自适应地展示检索结果，从而获得更佳的用户体验。检索结果的多样性由一个缩放因子来控制，用户可以根据自己的意图自由地放大或缩小缩放因子，相当于调整了聚类中心数目k。该系统演示上传于https：//youtu.be/hYnx3UkVQEA。

图像检索；用户界面；缩放因子；多样性

1 引言

近几年来，图像数量的快速增长已经在多媒体领域引起了巨大关注。在这期间，前人提出了许多的图像检索算法，例如基于内容的图像检索和基于标签的图像检索［1～2，17］。这些方法的主要出发点在于考虑如何有效地提高检索的精度。不过遗憾的是，通常这些方法存在检索结果和用户期望不一致的鸿沟。需要强调的一点是，在设计图像检索系统时将用户意图纳入考虑是一件非常具有挑战性的任务。

在文献［3］的主要思想中，相关反馈包含正反馈和负反馈，作者通过设计反馈框架来表述用户对检索结果相关性程度的评估。在该文章中，用户需要给出检索结果与其期望是否相符的反馈。不过，这样的做法会带来额外的认为参与，从而导致更差的用户体验。另一方面，由于存在大量的图片，当前搜索引擎返回的优先检索结果基本上是重复的。纵观前人的工作，很少关注如何能够在任何情况下，从用户执行的操作推断出隐式的相关性反馈，例如眼睛的眨动［4］。不同于先前的工作，我们注重设计一个更加自然的隐式相关性反馈框架从而完成交互式的图像检索任务。

为了解决上述存在的问题，本文提出一个可以自由控制检索结果的相关性和多样性的全新的反馈框架。基于上述目标，我们引入一个缩放因子来捕捉用户在图像检索中的意图。通过调节缩放因子，实际上是对聚类算法中的初始聚类中心数目k进行调整修改，用户可以直接浏览具有不同相关性和多样性得分的返回结果。为了确保缩放因子能够有效控制检索结果，我们利用改进的聚类算法来对相似性相关的图片进行有效分组。通过缩放因子的调节和提出的重排算法，可以使得检索结果与用户期望达成一致，从而缓解用户期望与检索结果之间的鸿沟。因此，该系统取得了更好的用户体验。

2 相关工作

前人对图像检索技术［6］的研究已经有了很多年的积累，关于相关性的研究远远超过了多样性。赵等［7］从贝叶斯角度和图像特征方向来计算图像的语义相关性从而获得最符合查询的结果标签。钱等［9］通过利用社交图片的多样性语义给图片重新打上标签进而改善图像的标签质量。上述的这些方法可以改善基于标签的图像检索方法，但是存在着丢失多样性的问题。

近几年关于相关结果多样化的研究大致可以分为三个方面：重排名，聚类和去重。Thomas等［10］定义了一套标准来评价检索结果的相关性和多样性，王等［8］通过计算候选集图像的视觉和语义相似性得分，提出了一种重排名策略，他们设计了一种贪婪算法来优化平均多样精度（ADP）。Marina等［11］提出一种名为DisC的多样性定义，在一个查询结果的多样性子集中，每个返回值都应当代表一个子主题，并且彼此之间不相似。

通过对检索结果进行有效聚类［12］，我们可以找到每个类别具有代表性的图片。蔡等［13］利用视觉和文本信息进行层次聚类，Alex等［5］提出一种新的聚类方法，主要思想源于聚类中心比邻居点具有更高的密度。区别于聚类算法，去重法直接对检索结果中的重复图片进行删除。Fishchlla等［14］基于局部敏感哈希的思想对检索结果中的重复项进行检测，他们利用存在的相似点对，动态地进行查询。

不难发现的是，上述方法都存在相同的缺点，例如聚类中心数目的不确定性以及在聚类过程中忽略图片的相关性。去重算法需要设定一个阈值，该值对检索结果的多样性结果具有直接的重要影响。此外，在单个矩阵中同时考量相关性和多样性是一件很困难的事。为了解决上述存在的问题，我们提出了一种新的重排名算法来进行联合优化。

3 工作流程与方法

本文提出了一个基于反馈框架的交互式图像检索方案，图1说明了该系统的工作流程。该反馈框架可用于图像检索领域，有助于帮助用户获取更加符合期望的结果。从图1中我们可以看到，整个系统主要包含以下几个部分：

图1 基于反馈框架的交互式图像检索流程图

1）图像收集以及特征提取：我们从图像分享网站Fliker上大规模地收集具有元数据的图像，其中元数据包括用户提供的标签信息等。然后我们执行一些必要的预处理步骤，包括提取视觉特征和处理纹理信息。最后为我们数据库中的图片设置索引。

2）基于文献［5］的思想，我们同时计算每张图像的密度峰值，前k个图像用来执行初始化划分。然后基于K-means算法将结果进行聚类。

3）基于用户反馈调整自适应改变聚类结果，构建排序候选集，最终利用改进排序算法进行最终排序。

我们令符号I={i m1，im2，…，imN}表示图像集，令表示图像i的标签集，重排算法将利用图像的综合信息重新构建子集S={i ms1， ims2， …， imsk}，S∈I并且 | S|=K，K≤N 。

3.1 图像收集以及特征提取

从图像分享网站上大规模地收集具有元数据的图像，其中元数据包括用户提供的标签信息等。然后我们执行一些必要的预处理步骤，包括提取视觉特征和处理纹理信息。最后为我们数据库中的图片设置索引。

3.1.1 特征提取

这里综合考虑时间、效率等因素提取了颜色直方图［15］、全局 gist［16］特征、边缘直方图形成一个融合特征作为输入。

3.1.2 TF-IDF向量

图像对应的标签，类别众多，形式各异，因此就需要将所有的标签信息拼接成一个句子，作为图像

语义的描述信息。对于整个数据集的语义信息，需要计算图像标签中的TF-IDF权值向量。

3.1.3 归一化降维模块设计

特征归一化：特征之间存在着一定的差异性，每个特征的值域都各不相同，所以需要用归一化操作来消除这一影响。为了数据处理方便，系统利用线性函数归一化把数据映射到0～1范围之内处理，更加便捷快速。线性归一化方法为

特征降维：主成分分析（PCA）是多元统计分析中用来分析数据的一种方法，它是用一种较少数量的特征对样本进行描述以达到降低特征空间维数的方法，它的本质实际上是K-L变换。

3.2 优化聚类

本文基于文献［5］的思想，我们同时计算每张图像的密度峰值，前k个图像用来执行初始化划分。然后基于K-means算法将结果进行聚类。

K-means算法的基本思想是：以空间中k个随机点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。但是K-means的问题就是：1）初始聚类图像难以确定，随机选取就会导致每次聚类的结果会变化。2）聚类中心的个数难以确定。针对这两个问题，本系统通过两种方式很好的加以解决，详见图2。

图2 改进的K-means聚类算法

针对第一个问题，本文利用计算密度峰值，即图像的代表性来获取初始图像，这里需要两个重要的参数：

其中，dij表示imi与imj之间的距离并且dc表示截断距离。一般性来说，ρi表示与点i的距离小于dc所有点的连续值。dc取值本文取平均距离。

根据密度峰值的大小对图像进行排序，选取值最大的k幅图像进行K-means聚类的初始值，最终迭代生成聚类结果。

针对聚类中心个数的问题，我们将其交由用户调控，通过用户的反馈，来调整聚类结果，最终改变重排结果。

3.3 构建候选集

用户调整缩放因子，实际直接改变聚类数k，进而调整聚类结果，聚类结果的改变直接调整重排候选集，利用重排算法实现结果多样性和相关性的平衡以满足不同用户的意图。

这里，将缩放因子引入K-means以实现聚类的重新生成，针对每一个类，将所有的图像根据peak（密度峰值）的大小进行重排列以求出k个中心。

其中，我们有如下成立：

针对重排的聚类结果可以发现类与类之间差异性大，类间图像之间相似性大，分别对应结果中的多样性和相关性，但是，类中图像通过密度峰值即代表性排序之后，排序靠后的图像并不具有代表性，所以本文将利用每个类的前60%图像构建最后所需排序的候选集，这个候选集有来自同一个类的最具代表性的同类图像，又有不同类的差异性图像，所以这个候选集去除了过于相似且不具有代表性的图像，最终简化了候选集的大小。

同时，根据用户的调整因子的不同，候选集对多样性以及相关性的侧重点会有所不同。当用户的调整因子小时，那么聚类数就小，最终聚类结果就小，所以在构造候选集时类中相似图像会相对较多。那么最终的排序结果多样性相对较小。当用户增大缩放因子，那么候选集差异性图像增多，最终排序结果多样性增大。

3.4 改进排序算法

根据［8］提出的DRR排序算法，本文提出了一个基于多样性、代表性和相关性的重排算法。对提供的重排候选集进行重新排列最终形成重排的结果。排序的方法就是利用最优化的操作方式。首先提出一个计算标准，然后不停地迭代计算图片的在这个标准下的值。每次选取最大的那个图像插入到最终的图像列表中去。迭代的标准函数为

函数F(i)表示第i幅图像的综合多样性、相关性、和代表性的值。这里函数 R(⋅)，Div(⋅)，Peak(⋅)分别表示相关性、多样性以及代表性的值。Si表示最终排序列表中已经重排序好i幅图像。下面分别对表示相关性、多样性以及代表性的计算方法进行阐述：

相关性表示的是两个方面：图像与检索词的相关性，图像与图像之间的相关性，由于系统的图像是以相关性的方式进行检索下载的，所以图像的下载就是一个相关性递减的过程，因此我们将图片原始下载的排序位置作为图像相关性的表述（i表示图像的位置）：

多样性表述的是待选图像与已经重排好的所有图像的差异性，这里我们利用到上述的相似度矩阵，公式如下（R表示候选集，S(i，j)表示图像的混合相似度）：

代表性表述的是图像代表性计算值，之前已经提到过。公式如下（normalize表示归一化操作）

4 实验结果

图3简单说明了一个用户可以与之互动的应界面。界面的左边将聚类结果进行显示，每一类将选取最具代表性的三张图片，并且可以根据用户的选择显示出每类的所有图片，显示的所有的图像将按照代表性排序的方式展示。此外，相比较于传统的图像检索界面，我们特别在界面的下方加了滑动条。不同位置的滑动条正好对应于不同取值的缩放因子，最左边的位置对应于缩放因子取值为0，最右边对应于最大值的缩放因子。当用户调节滑动条时，改变了系统当前的缩放因子，也即是改变了当前聚类中心数k，系统将根据用户意图实时地显示当前返回结果。从左向右滑动滑动条时，图片在相关性的基础的逐步的增加图片的多样性，所呈现的靠前的图片所包含的话题量将会增大，用户将获得更多的信息，即所获取到的图片多样性得到增强。在图4中，我们将本文提出的DRCR算法与传统的基于相关性的检索算法和DRR［8］算法进行了实验对比，统计了在不同查询结果下的ADP值。实验结果表明了本文提出的方法的有效性。

图3 系统用户界面的一个样例

图4 实验结果对比

为了有效地执行图像检索的任务，我们首先需要从Fliker上爬取大量的图片。同时为了证明该反馈框架的有效性，我们也进行了用户调查，我们一共邀请了30位经常在线检索图像的用户来进行这份用户研究。每个用户根据他们对检索结果的满意度按照｛1，2，3，4，5｝进行打分，打分结果与用户满意度成正相关，打分越高，则代表其对结果的满意度越高。在图5中，我们将提出的系统与传统的不具有缩放因子的系统进行有效对比，对比结果有力地说明了我们的系统具有更好的用户的满意度，证明了该方法的有效性。此外，为了更加鲜明地展示缩放因子对聚类算法的作用，我们在图6中以“苹果”作为一条查询进行具体说明。从图6中不难看出，系统针对不同的缩放因子显示不同的检索结果，本质是当前（b）的聚类数目要多于（a）中。后者（b）显然返回了更加相关且多样性丰富的检索结果，也更加满足用户的检索需求。

图5 用户满意度的比较

图6 缩放因子的影响

5 结语

本文提出的基于反馈框架的交互式图像检索系统，不仅考虑到了检索结果的相关性要求，同时将多样性指标考虑其中，利用缩放因子的手动调整改变初始聚类中心数，利用密度峰值概念完成聚类样本中心的选取。实验证实本文提出的基于多样性，代表性和相关性的重排算法取得了更好的ADP值，使得最终的检索结果同时满足相关性与多样性的要求，更加契合用户需求，具有一定的优越性。

［1］Smeulders A W M，Worring M，Santini S，et al.Content-Based Image Retrieval at the End of the Early Years［J］.IEEE Transactions on Pattern Analysis&Machine Intelligence，2000，22（12）：1349-1380.

［2］Datta R，Joshi D，Li J，et al.Image retrieval：Ideas，influences，and trends of the new age［J］.Acm Computing Surveys，2008，40（2，article 5）：2007.

［3］Xiang S Z，Huang T S.Relevance feedback in image retrieval：A comprehensive review［J］.Multimedia Systems，2003，8（6）：536-544.

［4］Jech T.Can relevance of images be inferred from eye movements［M］.Following the tracks of Ennin's 9th c.journey：.China Intercontinental Press，2007：134-140.

［5］Rodriguez A，Laio A.：Machine learning.Clustering by fast search and find of density peaks.Science，2014，344（6191）：1492-6.

［6］Sun A，Bhowmick S S.Image tag clarity：in search of visual-representative tags for social images［C］//Sigmm Workshop on Social Media.ACM，2009：19-26.

［7］Zhao Y，Zha Z J，Li S，et al.Which Tags Are Related to Visual Content［C］//Advances in Multimedia Modeling，InternationalMultimediaModelingConference，MMM 2010，Chongqing，China，January 6-8，2010.Proceedings.2010：669-675.

［8］Wang M，Yang K，Hua X S，et al.Towards a Relevant and Diverse Search of Social Images［J］.IEEE Transactions on Multimedia，2010，12（8）：829-842.

［9］Qian X，Hua X S，Tang Y Y，et al.Social Image Tagging With Diverse Semantics［J］.Cybernetics IEEE Transactions on，2014，44（12）：2493-2508.

［10］Deselaers T，Gass T，Dreuw P，et al.Jointly optimising relevance and diversity in image retrieval［C］//ACM International Conference on Image and Video Retrieval，Civr 2009，Santorini Island，Greece，July.2009：1-8.

［11］Drosou M，Pitoura E.DisC diversity：result diversification based on dissimilarity and coverage［J］.Proceedings of the Vldb Endowment，2012，6（1）：13-24.

［12］Zechao Li，Jing Liu，Yi Yang，et al.Clustering-Guided Sparse Structural Learning for Unsupervised Feature Selection［J］.IEEE Transactions on Knowledges&sdata Engineering，2014，26（9）：1-1.

［13］Cai D，He X，Li Z，et al.Hierarchical Clustering of WWW Image Search Results Using Visual［C］//ACM International Conference on Multimedia，2004：952-959.

［14］Fisichella M，Deng F，Nejdl W.Efficient Incremental Near Duplicate Detection Based on Locality Sensitive Hashing.［C］//Database and Expert Systems Applications，International Conference，DEXA 2010，Bilbao，Spain，August 30-September 3，2010，Proceedings.2010：152-166.

［15］解洪胜，王连国，孙玉芳.模糊颜色直方图在基于内容的图像检索中的应用研究［J］.计算机系统应用，2009，18（5）：139-143.XIE Hongsheng，WANG Lianguo，SUN Yufang.Application of Content-Based Image Retrieval with Fuzzy Color Histogram［J］.Computer Systems Application，2009，18（5）：139-143.

［16］Oliva A，Torralba A.Modeling the Shape of the Scene：A Holistic Representation of the Spatial Envelope［J］.International Journal of Computer Vision，2001，42（3）：145-175.

［17］童振兴.基于内容的图像检索技术综述与展望［J］.计算机光盘软件与应用，2010，5（6）：88-88.TONG Zhenxing.Review and prospect of content-based image retrieval technology［J］.Computer CD-ROM Software and Application，2010，5（6）：88-88.

Interactive Image Search System Based on Feedback Framework

ZHU Xiang LIN Xuefei
（School of Computer Science and Engineering，Nanjing University of Science&Technology，Nanjing 210094）

With the explosive growth of the number of images，image search has been drawing much interest from the research community.However，there exists the inconsistency between people's search needs and the search results.Towards this end，this paper presents a new feedback framework for interactive image retrieval by adaptively displaying the search results，which can obtain better user experience.The diversity of search results is controlled by introducing a zoom factor，which makes users freely zoom in or out on the results according to their intents.The demo is available at https：//youtu.be/hYnx3UkVQEA.

image search，interface，zooming-factor，diversity

TP391

10.3969/j.issn.1672-9722.2017.11.041

Class Number TP391

2017年5月7日，

2017年6月28日

朱翔，男，硕士研究生，研究方向：图像检索模式识别。林学飞，男，硕士研究生，研究方向：图像检索。