英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

PageRank for Product Image Search

摘要

在本文中，我们将图像排序问题转换为识别一张视觉相似的图片中重要节点的任务并且提出一种可以分析图像集之间的视觉链接结构的算法。通过一个基于 PageRank 计算的迭代过程，一个数值权重会被分配给每一张图像；它会衡量它与其他参与排序的图像之间的相对重要性。处理过程中视觉信号的加入是与如今在用的大多数大规模商业搜索引擎最主要的区别。商业搜索引擎往往完全依赖于嵌有图片的页面的文本信息，并且往往完全忽略了将图像内容也作为一种排序的影响因素。为了量化我们的方法在现实生活中的性能，我们进行了一系列针对于最受欢迎的2000种产品查询的图像检索实验。就用户满意度和图片关联度而言，与最新的 Google 图像搜索结果相比，我们的实验结果展现了非常显著的优势。

分类和主题描述

H.3.3 [Information systems]: Information Search and Retrieval; I.4.9 [Computing Methodologies]: Image Processing and Computer Vision

一般条款

Algorithms

关键词

PageRank, Graph Algorithms, Visual Similarity

引用

虽然在许多搜索引擎中（比如雅虎、MSN、谷歌等等），图像搜索已经变成一种很受欢迎的功能了，但绝大多数图像搜索引擎都是使用图像信息来对图像进行排序的（如果有的话）。然而，通常只使用嵌有图片的页面中的文本（比如正文、锚文本、图片名，等等）来进行排序。导致这种情况的原因有三：一，网页的基于文本的搜索是一个已经研究得很透彻并且已经获得大量成功的问题。二，图像分析的基础任务很大程度上还算是一个未解决的问题：人类能识别的物体通常无法在图像中自动的识别出来。虽然有些问题（比如，人脸识别^{[17] [15]}以及识别 CD^[12] 表面这种高质感的物体）已经成功地解决了，然而一般物体的检测和识别问题仍然存在。只有以上提到的几种物体可以在大部分的图像中可靠地检测到。三，即使对于成功解决的问题，其处理过程也会比分析网页文本信息付出更多的代价。不仅信号处理算法会增加额外的复杂性，而且图像迅速增长的平均大小也会使得传输和分析大量数据这种简单的任务更加的困难而且计算代价更加昂贵。

没有图像处理的查询响应经常会产生质量不一致的搜索结果。比如，将 “Eiffel Tower” 作为关键字提交给 Google 的图像搜索引擎中（打开成人内容滤波开关），返回的商品结果如图1(a)。然而，查询 “McDonalds” 返回混杂的结果如图1(b)；那个我们所期望的经典的黄色的 “M” 标志并不是作为图像的最主要的组成部分，而出现在第6和第13个结果中。

1. 埃菲尔铁塔

1. 麦当劳

图1: 在谷歌搜索中“Eiffel Tower”的查询能得到好的结果。但是，“McDonalds”的查询返回混合结果。

图1(b)为我们的方法将能够有力地改进图像排序的问题提供了一个极其具有说服力的示例。我们的方法依赖于分析图像中视觉相似处的分布。前提很简单：网页的作者可能会选择从他（她）自己的角度看来和主题有关的图片。而不是假设每一个拥有和关键字相关联的网页的用户都将会主动链接到一张其他用户也会发现到关联之处的图片。例如，在图1(b)中，许多张图片都包含相似的 “M”。只有少部分图片中的标志才是图像的主要焦点，而其他图片中都只占据了一小部分。但是，大部分图片中 “M” 的重复出现是个重要的信息，这个信息可以用来推断出整个图片集的共同“视觉主题”。在这项研究中，图像排序系统的基础就是查找大量图片集中的多视觉主题及其相对权重。

要想提出一种能推断出共同视觉主题的可扩展的有效的算法，会遇到两个核心挑战。第一个挑战就是必需的图像处理过程。注意，每一次查询都可能会有一些完全独立的视觉特征，这些特征是结果集中的图像所共有的特征。研究目标就是为了找出图像集的共同特征，即使这些共同特征并不是能够先知的，并且共同特征可能会出现在图像中的任何位置以及任何方向。例如，它们可能变得弯曲（如图1(b)的第5张图片），或旋转过（如图1(b)的第4,9,16张图片），又或者不是图像的主要组成部分（如图1(b)的第1,8,20张图片），甚至可能会是一种非标准的颜色（如图1(b)的第7,10张图片）。想要让这种情况变得可控需要一种比较特殊的方法，这个方法要求首先通过识别人类可识别的物体来分析图像的相似性（比如，这些图片都包含树和车），而不是先去检测出可以被检测出来的物体。相反地，我们会去寻找一些图像中的弱特征，比如规模、方向这种我们所期望遇到的不变特性。为了解决这一项任务，我们转向于使用局部特征^{[10] [2]}。Mikolajczyk等人^[11]提出了各种描述符的比较研究。虽然局部特征的完整描述符已经超出了本文的范畴，但我们将会在下一节提供一个简要的回顾。

第二个挑战就是在我们从图片集中查找出共同的特征后，我们需要一种机制去利用这个特征来达到排序的目的。如将所示，简单地对共同视觉特征进行计数将无法得到理想的结果。为了解决这个问题，我们设计出一种图像间的图结构，图中的图像根据它们的相似度相互连接。一旦图被创建出来，我们就可以证明类似于 PageRank 的迭代过程可以被有效地利用到图像排序中。这些将会在第二节中描述。

1.1背景及相关工作

有许多将视觉信号结合到搜索引擎的排序算法中的方法。其中一种较受欢迎的方法是从排名靠前的搜索结果中训练出一个对象类别模型，并且基于图像与该模型的匹配程度进行重排序。^{[13] [5]}这些方法虽然也能获得令人满意的结果，但是相同对象类别的假设和实验规模的限制，在商业搜索引擎的实用性和性能方面都无法达到令人信服的效果。例如，有大量的网页查询包含多个视觉概念，比如 “nemo” （如图2）。在搜索引擎给出一些比较有限的并且还有可能会出现非常不同的搜索结果的情况下，要想得出一个强鲁棒性的模型显得更加地困难。进一步说，对象类别的训练目标和图像的排序目标之间也存在着基本的差异性。对象类别训练器是用来给图像和图像特征之间的关系建模的，然而图像搜索引擎是用来为图像之间的关系（次序）建模的。尽管一个受过良好训练的对象类别过滤器可以用来改善图像搜索结果的关联性，但是它并不能很好地解释一个视觉主题（一张图片）为什么会比另一个（张）的排名更靠前。

图2: 许多类似于”nemo”的查询包含许多视觉主题

在这项研究中，我们提出了一个基于内容的图像排序算法的直观图结构模型。给出要进行排序的图片的视觉相似度后，我们会对我们所期望的用户行为进行建模，而不是对图像特征和对象之间的关系进行建模。通过将图像看成网站文档以及将相似度看成有概率的视觉超链接，我们对用户通过遍历这些视觉超链接而浏览到某一张图片的可能性进行估计。那些更有可能被访问到的图片将会排列在其他图片之上。这个框架使我们能够利用这个很好理解的PageRank^[3] 和针对网页排序的 Centrality Analysis ^[4] 方法。

我们通过计算图像间的视觉相似度来求得视觉超链接，而不像普通网站，需要手工的定义超链接来连接到相应的文档。由于图结构能够唯一地确定图像的排名，所以我们的方法提供一个从用来计算图像相似度的特征集抽象出来的抽象层。相似度可以根据图像预期的类型和分布进行个性化的扩展；例如，对于查询人的时候，脸部的相似度、风景的颜色特征、建筑的本地化特征、产品图像等都派得上用场。

其他几个研究已经探索出针对半监督学习的基于图结构的相似度的使用^{[8] [19]}。给出一个邻接矩阵以及几个已标记的顶点，未标记的节点可以被描述为已标记节点基于图流形的函数。这项研究中，我们的目标不是分类；而是，将图像的核心部分建模成图像排序的一种工具。论文[7]中图像相似度被用来从图片搜索结果中查找出唯一一张最具有代表性或最“权威”的图片，而我们则是对该论文进行了扩展。在这里，我们使用非常容易理解的基于 PageRank 的图分析法，并且在性能和系统计算成本两方面做了一个大规模的研究。

1.2 本文的贡献

This paper makes three contributions:

本文实现了三个突破：

1. 我们提出一种基于视觉相似度的新颖的简单的图像排序算法。
2. 我们推出了一个对目前 Google 的图片搜索结果进行重排序的系统。尤其是，我们证明了，对于大量的查询集合，图像之间可靠的相似度权重可以通过它们的局部描述符的比较得出。
3. 据我们所知，我们的实验是目前已公开的基于内容的图像排序研究中规模最大的。基于我们对最常见的对象类别搜索的估计，我们明显提高了大多数人最感兴趣的查询的图片搜索结果的准确率。

论文的剩余部分组织如下。第二节介绍算法以及描述基于视觉相似度图结构的图像特征构造。第三节研究相同的和混杂的视觉类别的查询性能。第四节提出我们所进行的实验和搜索的分析。第五节对本文进行总结。

方法和算法

给出一个有多个顶点的图和一个带权边的集合，我们要去测量每个顶点的权重。顶点的基数或者周围节点的测量距离的和就是所有核心测量值的变量。Eigenvector Centrality 提出了一种将顶点权重和排序中邻近节点的权重结合在一起的原则性强的方法。例如，如果其他因素都相同，那么更接近“重要”顶点的顶点应该排得更靠前。作为 Eigenvector Centrality的一个成功应用，PageRank^[3] 预计算出一种通过分析与网站文档相关联的超链接来估计网页权重的排序向量。

Eigenvector Centrality 被定义为一种二维随机邻接矩阵的规则特征向量，由图中边的权重构造而得。它有一个直观的随机遍历（Random Walk）的解释：排序分数对应于通过遍历整个图（开始顶点随机选择）到达每个节点的可能性，遍历时每一条路径的选择都由带权边来决定。

使用基于随机遍历的视觉超链接的前提是，如果一个用户正在浏览一张图片，其他和这张图片相关的（或相似的）图片也可能感兴趣。特别是，如果图像 u 有一个到图像 v 的视觉链接，那么用户就有可能从 u 跳转到 v。可以直观地看出，与查询相关的图像将会有很多其他图像与它们关联，并且会因此经常被浏览（只要它们不是在一个孤立的小集合里面）。经常被浏览的图片被认为是非常重要的。进一步说，如果我们发现一张图片 v 是重要的，并且它链接到另一张图片 w，那么 w 的权重就会增加，并且因为 v 是重要的，所以 v 的一票会远远高于“不重要”的图像的一票。

就像网页排序一样，图像排序（IR）被迭代地定义为以下形式：

IR = S* times; IR (1)

S* 是归一化的、对称的邻接矩阵 S 的一列，矩阵元素 Su,v 表示图像 u 和图像 v 之间的视觉相似度。因为我们将设两张图片之间的相似度是相等的，所以相似度矩阵 S 是无向的。通过不断地用 Slowast; 乘以 IR 来求得矩阵 Slowast; 的主要特征向量。虽然 IR 已经有一种固定的解决方案了，但是在实践中它仍然可以用迭代的方法更直接地估计出来。

只有当矩阵 Slowast; 是非周期性的以及不可简化的，图像排序才算是收敛的。PageRank 对于 web 来说公式 (1) 都是适用的，但是 ImageRank 通常需要一个强连通图，在实践中往往通过向公式 (1) 引入一个阻碍因子 d 来保证。给出 n 张图片，IR 被定义如下：

这类似于给所有的顶点添加一组完整的带权的(outgoing)边。很明显，这可以增加一点点随机访问到图中一些其他图片的可能性，即使有些图片还没有关联到当前浏览的图片。在实践过程中，d 经常取值会大于 0.8；实践证明，我们发现 d 的取值会对图像的全局排列顺序造成相对轻微的影响。

特征生成和表示

一个可靠的图像相似度的衡量是高性能的关键，因为它决定了底层的图结构。例如颜色直方图和形状分析这种全局特征，单独使用的时候会因为需要处理的图片类型范围太大而导致效果收到一定的限制。如图3，“Prius” 的搜索结果中经常包含角度不同、照相机不同、焦距不同、成分不同的照片，也还会有其他不同因素下拍摄的照片。

图3: 相似性度量必须处理潜在的旋转、尺度和透视变换。

与全局特征相比，局部特征值包含一组更丰富的图像信息，并且在不同变换下和一定程度的亮度变化下相对稳定。全局特征的算法有 Harris 角点^[6]、尺度不变特征变换(SIFT) ^[10]、形状上下文^[2]以及自旋图像^[9]。Mikolajczyk等人^[11]提出了一项各种描述符的比较研究^{[18] [1]}，提出了一种改进它们的性能和计算效率的研究。在这项研究中，我们使用 SIFT 特征、基于高斯差分的兴趣点检测器以及方向直方图特征作为图像特征。尽管如此，任何一种局部特征都是可以被取代的。

我们使用了一种标准的 SIFT 的实现；为了追求完整性，我们会在这里详细描述。DoG 兴趣点检测器通过对原始图片迭代使用高斯过滤器来生成缩放图片的金字塔。相邻的高斯图片相减得到高斯图片的差分，通过在级别(scale)空间中找出高斯差分的局部极值，能够估算出于每个兴趣点关联的特征级别。给出 DoG

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[154017]，资料为PDF文档或Word文档，PDF文档可免费转换为Word