Selective Search for Object Recognition

惠惠碎碎念：四月最后一天了，从4月23日中期答辩之后我就一直没有学习，吃吃吃，睡睡睡，无比堕落。寝室真是让人放纵的地方，现在好心疼自己浪费掉的那几天，没有做任何有意义的事情，哎，哪怕是出去玩玩也好啊…唯一让我稍微觉得不那么罪恶的也就是补了几部电影。哎，以后不能总待在寝室了，虚度光阴的感觉太糟糕了，或许之后应该尝试每天写篇日记，记录或者反思当天的表现，也许会不错哦。言归正传，现在我要抓住四月的小尾巴，更新一篇经典算法的译文！

用于目标识别的选择性搜索 for

摘要

1 引言

在很长一段时间里，人们都是在确定物体之前先对其进行描绘。这就产生了分割，它的目的是通过一个通用算法对图像进行唯一的分割，其中有一个部分用于图像中所有的物体轮廓。在过去的几年中，关于这个课题的研究已经取得了极大的进展。但是图像本质上是分层的，在图片1a中，色拉和汤匙是在色拉碗里的，色拉碗在桌子上。此外，根据上下文，图中的物体，桌子，只能指木材或包括桌面上的所有内容。因此，图像的性质和物体类别的不同用法是分层的。除了最特定的用途外，这禁止对所有对象进行惟一分区。因此，对大部分任务来说，多尺度分割是有必要的。通过使用分层分区来最自然地描述它的就是等人所做得例子。

除了分区应该是分层的，使用单个策略的分割的通用解决方案可能根本不存在。有很多相矛盾的原因解释为什么一个区域应该被分在一起：在图像1b中，猫应该用颜色分开，但是他们的纹理是一样的。相反地，在图片1c中，变色龙和他周围的叶子的颜色是相似的，然而他们的纹理不同。最后，在图片1d中，轮子和车在颜色和纹理上都是显著不同的，但是它们被车子包围了。因此，单个的视觉特征不能解决模糊的分割问题。

并且，最终，有一个更基础的问题。有不同特征的区域，比如毛衣上的一张脸，只有被确定在旁边的物体是人，才能被结合成一个物体。因此，没有先前的识别，很难确定一张脸和一个毛衣是一个物体的一部分。

这也导致了传统方法的反面：通过一个物体的识别来做定位。这个在物体识别方面的最近的方法在不到十年的时间里已经做了很大的改进。用一个从样本中学习的表面模型，一个穷竭搜索表现出图像中的每一个位置都被检查以便不错过任何一个可能的物体位置。

然而，穷竭搜索本身也有很多缺点。从计算方面来讲，搜索每一个可能的位置是不可行的。搜索空间不得不被降低到用一个规律的网格，固定的规模和固定的纵横比。在大部分的例子中，要处理的位置数量都很大，以至于可供选择的限制条件需要被强加上。分类器被简化并且表面模型需要是快的。此外，一个统一的采样会产生许多盒子，对于这些盒子，我们可以立即清楚地看到它们并不支持某个对象。不像取样位置盲目地使用穷竭搜索，一个关键的问题是：我们可以通过一个数据驱动的分析来控制取样吗？

在这篇论文中，我们的目的是结合直觉分割的最好状态和穷竭搜索，提出一个数据驱动的选择性搜索。受自底向上的分割的启发，我们的目的是开发图像的结构来产生物体的位置。受穷竭搜索的启发，我们的目的是捕捉所有可能的物体位置。因此，不是用一个单一的取样方法，我们的目的是使取样方法多样化来解释尽可能多的图像情况。特殊地，我们用一个数据驱动的基于组的策略，通过使用许多补充的分组标准和许多有不同不变属性的补充颜色空间来增加多样性。这组位置被获得通过结合这些补充的分割物的位置。我们的目标是产生一个独立于类的，数据驱动的，选择性搜索的策略来产生一小组高质量的物体位置。

选择性搜索的应用领域是物体识别。我们因此用最常用于这个目的的数据集来进行评估， VOC检测挑战，由20个对象类组成。这个数据集的大小对我们的选择性搜索产生了计算限制。进一步地说，这个数据集的使用意味着位置的质量主要被标定框所评估。然而，我们的选择性搜索也应用到区域，也适用于概念，比如“草”。

在这篇文章中，我们用于物体检测的选择性搜索。我们主要的研究问题是：（1）作为一个选择性搜索策略，什么是适合分割的好的多样性策略？（2）选择性搜索在图片中产生一小组高质量的位置有多高效？（3）我们可以使用选择性搜索来使用更强大的分类器和外观模型进行对象识别吗?

2 相关工作

我们把相关工作限制在物体识别领域并且把它分成三类：穷竭搜索，分割，和不在任何一类的其他的选样策略。

2.1 穷竭搜索

由于一个物体可以在图片中的任何位置和任何规模，在每处都搜索是很自然的。然而，视觉搜索空间是巨大的，使得穷竭搜索计算成本很昂贵。这对每个位置和(或)所考虑的位置数目的评价费用施加了限制。因此大部分的滑动窗口技术使用一个粗糙的搜索网格和固定的长宽比，使用弱小的分类器和经济的图像特征，比如HOG（方向梯度直方图）。这个方法经常被用做分类过程中的一个预选择步骤。

与滑动窗口技术相关的是等人非常成功的基于部件的对象定位方法。他们的方法也表现了一个用线性支持向量机和HOG特征的穷竭搜索。然而，他们搜寻物体和物体的部件，这个结合导致了一个令人印象深刻的物体检测表现。

等人提出用表面模型来引导搜索。这既缓解了使用一个常规的网格，固定的尺寸和固定的长宽比的限制，同时也降低了需要访问的位置的数量。这个最近被用来在一张图片中使用分支定界方法来找最优窗口。当他们为线性分类器获得一个令人印象深刻的结果时，[1]发现对非线性分类器来说，在实践中，这个方法仍然需要在一张图片中访问多于个窗口。

不像盲目的穷竭搜索或者分支定界搜索，我们提出了选择性搜索。我们用潜在的图片结构来产生物体位置。与讨论的方法不同，这产生一个完全独立于类的一组位置。此外，因为我们不用一个固定的长宽比，我们的方法不仅限于物体，也可以发现像“草地”和“沙子”这些物体。最后，我们希望产生更少的位置，这可以使样本多样性降低时，问题变得更简单。并且更重要的是，它释放出的计算能力可以用于更强大的机器学习方法和更强大的表面模型。

2.2 分割

和以及和Hoiem都提出了利用分割生成一组独立于类的对象假设。这两种方法都会生成多个前景/背景分割，学习预测前景分割是一个完整对象的可能性，并使用这个方法对分割进行排序。这两种算法都显示出了一种很有前途的精确描绘图像内目标的能力，这一点得到了[19]的证实，[19]在使用[4]进行像素级图像分类方面取得了最先进的结果。与分割中常见的方法一样，这两种方法都依赖于单一的强算法来识别好的区域。它们通过使用许多随机初始化的前景和背景种子来获得各种位置。与此相反，我们通过使用不同的分组标准和不同的表示来显式地处理各种图像条件。这意味着较低的计算投资，因为我们不必投资于单一的最佳分割策略，如使用优秀但昂贵的轮廓检测器的[3]。此外，由于我们分别处理不同的图像条件，我们希望我们的位置具有更一致的质量。最后，我们的选择性搜索范式表明，最有趣的问题不是我们的区域与[4,9]相比如何，而是它们如何互补。

Gu等人陈述了基于他们的部分精细分割好识别物体的问题。他们首先用基于 等人的分组方法生成了一组部分假设。每一部分的假设都被外观和形状特征所描述。然后，对物体进行识别，利用物体的各个部分进行细致的描绘，取得良好的形状识别效果。在他们的工作中，分割是分层的并且产生各种尺寸的分割。然而，他们使用一个单一的分组策略，这个策略发现物体或者部件的能力尚未被评估。在这项工作中，我们用多个补充策略来处理尽可能多的图像条件。我们包含用我们的评估生成的位置。

2.3 其他的取样策略

Alexe et al.[2]通过提出搜索任何独立于类的对象来解决穷举搜索的大采样空间问题。在他们的方法中，他们训练一个基于物体窗口的分类器，这些物体有良好定义的形状（不是“草地”，“沙地”这些物体）。不是一个完全的穷竭搜索，他们随机取样一些边框来应用他们的分类器。测量出有很大可能性存在物体的边框被看作一组物体假设。这一组随后被用来极大地降低被特定物体类检测器所评估的边框的数量。我们将我们的方法与他们的工作作比较。

另一种策略是用词袋模型中的视觉词汇来预测物体位置。等人用跳跃窗口，学习单个视觉词与目标位置的关系，预测新图像中的目标位置。Maji和Malik[23]将这些关系的多个组合在一起，使用Hough-来预测对象的位置，然后他们随机抽取接近Hough最大值的窗口。与学习相反，我们使用图像结构来采样一组类无关的对象假设。

总结一下，我们的创新如下。不像穷竭搜索，我们使用分割作为选择性搜索产生一小组独立于类的物体位置。和分割相反，不是专注于最好的分割算法，我们用一系列算法来处理尽可能多的图片，因此极大地降低了计算成本并潜在地更准确地捕捉到了物体的位置。我们使用自底向上的分组过程来生成良好的对象位置，而不是在随机采样框学习对象度量。

3 选择性搜索

在这个部分，我们详细讲述用于物体识别的选择性算法，并且展示一系列多样策略来处理尽可能多的图像情况。一个选择性算法从属于以下的考虑设计：

捕获所有规格 图片中的物体可以是任何规格的。进一步讲，一些物体不如其他物体的边界清晰。因此，在选择性搜索中，所有物体规模都要纳入考虑，就像图片2中显示的那样。通过使用一个分层的算法，这可以很自然地获得。

多样化 没有一个单一的最优策略来将这些分区分组。像前面图片1观察到的，分区可以仅通过颜色，纹理或者被包围的部分来形成一个物体。此外，光照条件比如阴影，光的颜色可能会影响区域怎么形成一个物体。因此，我们想要一个多样的组合策略来处理所有情况，而不是在大部分案例都做得很好的单一策略。

计算更快 选择性搜索的目标是产生一组可能的物体位置用于实际的物体检测框架。这个集合的创作不应该成为一个计算瓶颈，因此我们的算法应该更快。

图2: 我们选择性搜索的两个例子表明了不同尺度的必要性。在左边，我们发现许多不同尺度的物体。在右边，我们必须找到不同尺度的物体，因为女孩被电视所包含

3.1 分层分组的选择性搜索

我们用一个分层分组的算法来形成选择性搜索的基础。自底向上的分组是一个分割的流行方法，因此我们采用他来进行选择性搜索。因为分组过程本身就是分层的，我们可以很自然地产生各种规格的位置通过继续分组过程，直到整个图像变成一个单一的区域。这满足了捕捉所有尺寸的情况。

由于区域可以产生比像素更丰富的信息，我么想要在可能的时候用基于区域的特征。为了得到一小组理想上不跨越多个物体的开始区域，我们使用了 and 的快速方法，他被发现很适合于这个目标。

我们的分组过程现在如下进行。我们首先用[13]来创造一个初始区域。然后我们用一个贪心算法来一起迭代分组区域：首先，所有相邻区域的相似度被计算。两个最相似的分区分组在一起，新的相似性在结果区域和他的相邻区域之间被计算。最相似区域的分组过程被重复，直到整个图像成一个单一的区域。一般的方法在算法1中被详细描述。

算法1： 分层分组算法
输入：（彩色）照片
输出：一组物体位置假设L
获得初始分区R={r1,...,rn}用[13]
初始化相似度集合 S=∅
对每一个相邻区域(ri,rj) 执行ri,rj的相似度，S=S∪s(ri,rj) 
直到S≠∅ 执行得到最高相似度的s(ri,rj) =max(S)合并相应的区域rt=ri∪rj移除关于ri的相似性：S = S \s(ri,r∗) 移除关于rj的相似性：S = S \s(r∗,rj) 计算rt和他的邻居之间的集合St的相似性S=S∪StR=R∪rt
从R中的所有区域中提取物体位置边框

ri和rj之间的相似度我们希望在能够快速计算的限制下用一系列的补充测量。实际上，这意味着基于特征的相似性能够通过分层进行传播。比如，当合并ri,rj成rt时，rt的特征需要从ri,rj的特征中计算出，而不需要处理像素。

3.2 多样化的策略

选择搜索的第二个设计准则是使抽样多样化，并创建一组互补的策略，然后将这些策略的位置组合起来。我们丰富我们的选择性搜索(1)通过使用具有不同不变性的颜色空间来，(2)通过使用不同的相似性度量sij，和(3)通过改变我们的起始区域。

补充的颜色空间 我们想要解释不同的场景和灯光条件。因此我们执行我们的分层分组算法在有一系列不变属性的不同的颜色空间中。具体来说,我们下面的颜色空间不变性程度逐渐增加:(1)RGB,(2)强度(灰度图像)I,(3)Lab,(4)规范化RGB的rg通道加上强度表示为rgI, (5)HSV,(6)规范化RGB表示RGB, (7) C[14]这是一个强度被划分出来的对手色彩空间,最后(8)从HSV颜色通道H。表1列出了特定的不变性属性。

表1:本文根据不变性程度对色彩通道和色彩空间的不变性特性进行了分类。“+/-”表示部分不变性。分数1/3表示三个颜色通道中的一个对上述性质是不变的

当然，对于黑白照片，颜色空间的改变对算法的最终结果有很小的影响。这些图片，我们依赖于其他多样化方法确保好的物体位置。

在这篇文章中，我们一直在算法中用一个单一的颜色空间，意味着[13]的初始分组算法和我们之后的分组算法都是在这个颜色空间被执行。

补充的相似度测量 我们定义四个补充的，快速计算的相似度测量。这些测量都在排序[0,1]之间，这样促进了这些测量结果的结合。

(ri,rj)度量了颜色的相似度。特别地，对每一个区域，我们对每个使用了的颜色通道获得了一维的颜色直方图，我们发现这个效果很好。当三种颜色通道都被使用时，这对每一个维度n=75的区域ri产生了一个颜色直方图Ci = {c1i ,··· ,cn i } 。颜色直方图使用L1标准标准化。相似度采用直方图相交测量:

颜色直方图可以通过分层高效地进行传播

结果区域的尺寸就是组成部分之和。

本文的相似度测度是以上四种的结合

补充开始区域 1/3的多样化策略是在补充开始区域不同。在我们的认知中，[13]的方法最快，开源的算法产生了高质量的开始区域。我们不能找到有相似计算效率的任何其他算法，因此我们只用这篇论文中的过分割方法。但是注意，不同的开始区域的获得通过使颜色空间不同，每一个都有一个不同的不变属性。此外，我们使[13]中的阈值参数k不同。

3.3 结合位置

在本文中，我们结合了几种不同的层次分组算法的对象假设。理想地，我们想要使对象假设有序，最可能是物体的假设位置先出现。这使得在结果物体假设之间找到一个好的质量和数量的交易，取决于后面的特征提取和分类方法的效率。

我们根据每一组策略中产生假设的顺序来选择组合对象假设集。然而，由于我们结合的结果来自多于80个不同的策略，这样的排序将会太强调大区域。为了防止这个，我们包含了如下这些随机性。给定分组策略j，令rij为层次结构中位置i处创建的区域，其中i = 1表示层次结构的顶部(其对应区域覆盖整个图像)。现在我们计算位置值vij RND×i,RND是一个随机数在区间[0,1]。最后的排名是通过使用vij对区域进行排序得到的。

当我们为了边界框使用位置时，我们首先像上面一样排序所有的位置。然后过滤掉排序更低的复制品。这确保了复制框有一个更好的机会获得高排名。这是令人渴望的，因为如果多个分组策略建议同一个边界框位置，很有可能来自于这幅图片中视觉连贯的一部分。

4 用选择性搜索的物体检测

本文利用选择性搜索产生的位置进行目标识别。本节详细介绍了对象识别的框架。

在物体检测方面两种类型的特征是起主导作用的：梯度梯度直方图(HOG)[8]和词袋直方图[7,27]。HOG与等人的基于部分的模型相结合已经被证明是成功的。然而，他们使用的是穷竭搜索，HOG特征通过一个线性分类型来结合是从计算角度来说唯一一个可行的选择。相反，我们的选择性搜索确保了使用更昂贵和潜在更有力的特征。因此，我们使用词袋模型用于物体检测。然而，通过使用各种颜色- sift描述符[32]和更精细的空间金字塔划分[18]，我们使用了比[16,17,34]更强大(和更昂贵)的实现。

特别是我们在每个像素样本描述符在一个规模(σ= 1.2)。利用[32]软件，我们提取了SIFT[21]和两种对图像结构检测最敏感的颜色筛选，分别是扩展的[31]和[32]。我们使用一个大小为4000的可视码本和一个4层的空间金字塔，使用1x1、2x2、3x3和4 x4部门。这就给出了一个36万的特征向量长度。在图像分类中，已经使用了这种大小的特征[25,37]。因为空间金字塔会导致比组成HOG描述符的单元格更粗的空间细分，所以我们的特征所包含的关于对象的特定空间布局的信息更少。因此，HOG更适合于刚性对象，而我们的特性更适合于可变形对象类型。

作为分类器，我们使用一个支持向量机与直方图相交核使用幕府工具箱[28]。为了应用训练过的分类器，我们使用了[22]的快速近似分类策略，该策略在[30]的词袋分类中效果良好。

我们的培训过程如图3所示。最初的正面例子包括所有地面真值对象窗口。作为初始的负面例子，我们从所有由我们的选择性搜索生成的对象位置中选择，它们与一个积极的例子有20%到50%的重叠。为了避免几乎重复的负面例子，如果一个负面例子与另一个负面例子重叠超过70%，就会被排除在外。为了使每个类的初始负片数量保持在20,000以下，我们将car、cat、dog和类的负片随机去掉一半。直观上，这组例子可以看作是困难的负本，因为它们与正面例子很接近。这意味着它们接近决策边界，因此很可能成为支持向量，即使考虑的是完整的负面例子的集合。实际上，我们发现这些训练示例的选择提供了相当好的初始分类模型。

图3：物体检测过程的悬链过程。作为一个正面学习例子，我们用基本事实。作为一个负面例子我们用和正面例子有20%~50%重合的例子。我们使用再训练阶段迭代地增加困难的负样本。

然后我们进入再训练阶段，迭代地添加困难的负面例子(如[12]):我们使用我们的选择性搜索生成的位置将学习的模型应用到训练集。对于每个负面图像，我们添加最高得分位置。由于我们的初始训练集已经产生了很好的模型，我们的模型只在两次迭代中收敛。

对于测试集，最终的模型应用于由我们的选择性搜索生成的所有位置。这些窗口按照分类器评分进行排序，而与得分较高的窗口重叠超过30%的窗口被认为是接近重复的，并被删除。

5 评估

在这个部分，我们评估我们的选择性搜索的质量。我们把我们的实验分成四个部分，每个部分生成一个单独的子部分：

多样性策略 我们用一系列颜色空间，相似度测量和初始区域的阈值进行试验，所有这些在3.2部分被详细描述。我们寻找一个生成的物体假设的数量和计算时间，物体位置之间的权衡。我们做这个为了得到边界框。这导致了一些互补的技术的选择，这些技术一起作为我们最终的选择搜索方法。

位置的质量 我们测试选择性搜索的物体位置假设。

物体检测 我们用在4部分详细描述的物体检测框架的选择性搜索到的位置。我们在 VOC检测挑战中评估性能。

位置质量的上界 我们研究了我们的对象识别框架在使用“完美”质量的对象假设集时的表现。这与我们的选择性搜索产生的位置相比如何？

为了评估我们的对象假设的质量，我们定义了平均最佳重叠(ABO)和平均最佳重叠均值(MABO)得分，这稍微概括了[9]中使用的度量。计算一个特定的类c的平均最佳重叠,我们计算每个真值之间最好的重叠注释gci∈gc和对象假设L生成相应的图像,和平均:

重叠评分从[11]中选择，测量两个区域的交集面积除以其并集：

与平均精度和平均精度均值类似，平均最佳重叠均值现在定义为所有类别的ABO均值。

其他研究通常使用重叠准则派生的召回量来度量边框的质量[1,16,34]。该准则在方程8的重叠大于0.5时，认为找到了一个目标。然而，在我们的许多实验中，大多数类的召回率都在95%到100%之间，这使得该方法对于本文来说太不敏感。然而，与其他研究比较时，我们仍然报告了这个测量结果。

为了避免过拟合，我们在 VOC 2007 TRAIN+VAL 集合上进行了分散化策略实验。其他实验在 VOC 2007 TEST 集合上进行。此外，我们的目标识别系统是以 VOC 2010检测挑战为基准，使用独立的评估服务器。

5.1 多样化策略

在这部分，我们通过在合理时间内计算出合理数量的边框来评估了许多策略，以获得质量良好的目标位置假设。

**5.1.1 平面与层次结构 **

在描述我们的方法的时候，我们声明用一个完整的层级是比通过改变阈值来使用多层的平面分割更自然的。在这一部分，我们测试了层级的使用使用是否也能得出一个更好的结果。我们因此比较了与我们提出的算法不同的使用多个阈值的[13]的方法。特别地，我们演示两个策略在RGB颜色空间中。对于[13]，我们设置不同的阈值从k=50到k=1000,每次变化50。这个范围既捕捉了小的区域也捕捉了大的区域。此外，作为阈值的一个特殊类型，我们包括整张图片作为一个物体位置因为有一小部分图片只包含一个达吾提。除此之外，我们也采用了一个更粗糙的范围从k=50到k=950，每次变化100。对于我们的算法，为了创造一个初始范围，我们使用阈值k=50，确保两个策略都有一个完全相同的最小规模。另外，由于我们产生更少的区域，我们结合k=50和k=100的结果。作为相似性测量的S，我们用方程6中定义的四个相似性的相加。结果在表2中。

表2：多个平面层划分和多层次划分在产生物体位置的比较显示，在小数量的位置时，多层级策略的平均最佳策略均值得分一贯的更高。

正如所见，我们的多层级策略产生的物体位置假设的质量比多个平面分割的效果更好：在小数量的区域时，我们的MABO得分一贯的更高。此外，通过结合两个变形的层级分组算法得到的MABO的增长比通过增加额外的阈值的平面分割得到的增长更高。我们得到这样的结论，相比于使用多个平面的分割，使用层级分组算法得到的所有的位置不仅更自然而且更有效率。

5.1.2 个人的多样化策略

在我们的论文中，我们提出了三个多样化策略来获得优质的物体假设：不同的颜色空间，不同的相似度测量和获得开始区域的不同的阈值。这部分调查了每个策略的影响。作为基础设置，我们使用了RGB颜色空间，所有四个相似度的结合和阈值k=50。每次我们变化一个参数。结果在表3中给出。

我们在表3的左边开始检查相似度测量的结合。首先单独地看颜色，纹理，尺寸和填充，我们发现纹理相似度表现的最差，MABO值仅有0.581，而其他的测量范围在0.63和0.64之间。为了测试相当低的纹理得分是否是由于我们对特征的选择，我们试着通过局部二分模式[24]来表现纹理。我们用4和8个不同规模的邻居，使用模式的不同的均一性和一致性做实验（见[24])，模式中我们结合了LBP直方图和独特的颜色通道。然而，我们获得了相似的结果（MABO=0.577）。我们相信纹理的弱表现性的一个原因是物体边界：当两个分割被一个物体边界分开，边界的两边都会产生相似的边缘反应，这无意地增加了相似度。

表3：基于边框的物体假设的平均最佳覆盖均值使用了多种分割策略。颜色，尺寸和填充变现相似。纹理表现脆弱。最好的结合是尽可能多地提供不同的来源。

由于纹理相似性产生了相当少的物体位置，在300个位置时，其他相似度测量仍能产生高于0.628的MABO。这说明当比较单个策略，表3中的最终MABO得分能很好的预测物体假设在质量和数量之间的权衡。另一个观察是结合的相似度测量通常比单个的测量效果好。事实上，使用所有的四个相似度测量表现效果最好，产生的MABO为0.676。

看表3右上部分的变更的颜色空间，我们观测到结果中一个很大的不同，MABO值从C颜色空间的125个位置的0.615到HSV颜色空间的463个位置的0.693。我们注意到lab颜色空间有一个相当好的MABO得分，为0.690，使用了仅仅328个边框。此外，每个垂直层级的顺序也是高效的：当使用前100个边框，产生了0.647的MABO。这显示当比较当个策略，我们可以仅仅使用MABO得分来展示物体假设集合中数量和质量的权衡。我们将在下一个部分使用这个来寻找好的结合方式。

[13]的阈值实验产生了开始区域，在表3的右下部分，使用更多的物体位置，一个更低的初始阈值产生了更高的MABO值。

5.1.3不同策略的结合

我们使用一个补充的分组策略来结合物体位置假设，为的是得到一系列优质的物体位置集合。由于最佳结合方式的一个完整的研究在计算方面是昂贵的，我们执行一个贪心搜索通过仅使用MABO得分作为优化标准。我们早前观测到这个得分代表物体位置数量和质量的权衡。

从结果排序我们创造了三个配置：一个单一的最佳策略，一个快速的选择性搜索和一个质量选择性搜索，使用单个组件的所有结合，比如，颜色空间，相似度，阈值，详情见表4。贪心搜索强调在结合相似度测量方面的变形。这证实了我们的多样性假设：在质量方面，紧邻着所有相似度的结合，填充和尺寸被单独地采用。本篇文章的剩余部分使用表4的三种策略。

表4：我们的选择性搜索方法来自于贪心搜索。我们采用选中的单个多样化策略的所有结合，产生了1,8和80个垂直层次分组算法的变体。随着窗口数量的增加，平均最佳覆盖均值得分保持稳定的上升。

表5：在测试集上的多种方法在召回率，MABO和窗口位置的数量上的比较。

5.2位置的质量

在这部分我们评估我们的选择性搜索算法在 VOC 2007 测试集上的ABO和位置数量。我们首先评估基于框体的位置，然后简单地评估基于区域的位置。

5.2.1基于框体的位置

我们比较[16]中的滑动窗口搜索，[12]中使用他们模型的窗口率的滑动窗口搜索，[34]的跳窗，[2]的物体边框，[3]的垂直层次物体分割算法的边框，[9]的区域边框，和[4]的区域边框。从这些算法中，只有[3]没有被设计来寻找物体位置。然而，[3]是公开可得的最佳边界探测器之一，并且产生一个自然的垂直层次的区域。我们将它包括在我们的评估中来看是否这个被设计用来分割的算法也在寻找好的物体位置方面变现良好。进一步来说，[4,9]被设计用来寻找好的物体区域而不是边框。结果展示在表5和图4中。

如表5所示，我们的“快速”和“质量”选择性搜索算法分别产生了接近于最优的98%和99%的召回率。至于MABO，我们分别达到了0.804和0.879。为了理解0.879的最佳重叠率意味着什么，图5展示了自行车，奶牛和人，例子的位置的重叠率在0.874和0.884之间。这说明，我们的选择性搜索算法产生了高质量的物体位置。

此外，注意到我们的MABO得分的标准误差相当的低：快速的选择性搜索为0.046，质量选择性搜索为0.039。这表明选择性搜索对于物体特征的差异是强健的，并且图像条件通常与特色物体相关（一个例子是门内/门外的灯光）。

如果我们和其他的算法作比较，召回率第二高的是0.940，通过[34]使用每类10000个框体的跳窗达到。由于我们没有准确的框体，我们不能去获得MABO得分。在这之后是[12]的完全搜索，得到了0.933的召回率，每类个框体的MABO值为0.829（这个数量是所有类别的平均值）。当使用至少十多个物体位置时，这与我们的方法相比，相当的低。

此外，注意到[4,9]的分割方法有一个很高的标准差。这表明一个策略不能对所有类别都作用的很好。相反的，使用多个补充策略得到更多稳定的可靠的结果。

如果我们比较[3]的分割和我们方法中的单一最好策略，他们得到0.752的召回率和418个框体0.值，而我们得到0.875的召回率和286个框体0.698的MABO值。这表明一个好的分割算法不会自动地产生好的用于边界框的物体位置。

图4探索了物体假设在质量和数量之间的权衡。至于召回率，我们的“快速”方法胜过所有其他的方法。[16]的方法对于他们用的200个位置来说似乎是有竞争力的，但是在他们的方法中，框体的数量是每个类别的，而我们的方法中，同样的框体用于所有的类别。至于MABO，[4]和[9]的物体假设产生方法对于每张图片产生的多达790个物体边框位置都有一个好的质量和数量的权衡。然而，这些算法计算要114和59次，相比于我们的“快速”方法来说是更昂贵的。

有趣的是，[2]的”反对“方法在召回率方面变现很好，但是在MABO方面很差。这很有可能是由他们非极大值抑制引起的，它抑制了存在一个更高排名的窗口，本身重叠率大于0.5的窗口。并且当一个0.5的重叠率的得分确定找到一个物体，这很大程度地改进了结果，对于找到最高质量的位置的一般问题，这个策略是低效的并且可能是有害的，因为消除了更好的位置。

图6显示了几个方法每个类别的ABO值。可以推断出，[12]的穷举搜索，它使用了比类特定位置多10倍的位置，对于自行车、桌子、椅子和沙发类，执行类似于我们的方法，对于其他类，我们的方法生成最好的分数。通常，得分最高的类是cat、dog、horse和sofa，这在很大程度上很容易，因为数据集中的实例往往很大。得分最低的类是瓶子类、人类和植物类，这是困难的，因为实例往往很小。然而，牛、羊和电视并不比人大，但我们的算法可以很好地找到它们。

图4：根据 2007测试集上的边界框，在对象假设的质量和数量之间进行权衡。虚线表示的是那些以每个类的框数表示数量的方法。在召回率方面，“快速”选择性搜索具有最佳的权衡。在平均最佳重叠方面，“质量”选择搜索可与[4,9]相比，但计算速度更快，耗时更长，最终的MABO值更高，为0.879。

图5：最佳重叠值在我们的平均最佳重叠值0.879附近的对象的位置示例。绿色的盒子是真相。红色框是使用“”选择性搜索创建的。

图6：在 VOC 2007测试中，生成基于框的对象位置的几种方法的每个类的平均最佳重叠分数。对于所有类，除了表格，我们的“质量”选择性搜索产生最佳位置。对于20个类中的12个，我们的“快速”选择性搜索优于昂贵的[4,9]。我们总是跑赢[2]。

总而言之，选择性搜索对于使用有限数量的框来发现高质量的对象假设集非常有效，在这些框中，对象类的质量是合理一致的。对于多达790个对象位置，[4]和[9]的方法具有类似的质量/数量权衡。但是，它们在对象类上有更多的变化。此外，对于我们的“快速”和“高质量”的选择性搜索方法来说，它们的计算成本至少要高59倍和13倍，这对于当前用于对象识别的数据集大小来说是一个问题。一般来说，我们得出的结论是，在使用1097个类无关对象位置的情况下，选择性搜索在0.879 MABO生成的质量最好的位置。

5.2.2 基于区域的位置

在本节中，我们将研究选择性搜索生成的区域捕获对象位置的效果。我们对 VOC 2007测试集的分割部分进行了分割，并与[3]的分割以及两者的目标假设区域进行了比较[4,9]。表6显示了结果。注意，区域的数量要大于框的数量，因为几乎没有完全相同的副本。

这两个[4,9]的目标区域与我们的“快速”选择搜索的质量相似，分别为0.665 MABO和0.679 MABO，其中我们的“快速”搜索得到0.666 MABO。虽然[4,9]使用的区域较少，但这些算法的计算开销分别是前者的114倍和59倍。我们的“质量”选择性搜索生成22,491个区域，分别比[4,9]快25倍和13倍，目前的最高分为0.730 MABO。

表6：比较各种算法，找到一组较好的潜在目标位置，按区域划分，对 2007年部分进行测试。

图7显示了每个类中区域的平均最佳重叠。对于除自行车以外的所有类，我们的选择性搜索始终有相对较高的ABO得分。自行车的性能在区域位置而不是对象位置上非常低，因为自行车是一个线框对象，因此很难准确地描述。

如果我们将我们的方法与其他方法进行比较，[9]方法更适合于火车，对于其他类，我们的“质量”方法产生类似或更好的分数。鸟、船、车、椅、人、植物、电视得分均优于0.05。对于小汽车，我们得到了0.12高的ABO得分，而对于瓶子，我们甚至得到了0.17更高的ABO得分。观察表6中ABO评分的变化，我们发现选择性搜索的变化略低于其他方法:“质量”为0.093 MABO，[9]为0.108。然而，这个分数是有偏见的，因为线框自行车:没有自行车的差异变得更加明显。“质量”选择搜索的标准偏差为0.058，[9]为0.100。这再次表明，依靠多种互补策略而不是单一策略可以产生更稳定的结果。

图7：在 2007测试集中，我们的方法与其他方法在每个类上的平均最佳重叠分数的比较。除了train之外，我们的“质量”方法始终生成更好的平均最佳重叠分数。

图8显示了来自我们的方法和[4,9]的几个示例分段。在第一张图片中，其他的方法在保持瓶子和书的白色标签分开方面有问题。在我们的例子中，我们的策略之一忽略了颜色，而“填充”相似性(Eq. 5)帮助将瓶子和标签组合在一起。缺少的瓶子部分是满是灰尘的，在这个瓶子部分形成之前就已经和桌子合并了，所以“填充”在这里没有帮助。第二幅图像是一个黑色图像的例子，由于使用了不同的颜色空间，我们的算法通常有很强的结果。在这张特定的图像中，部分强度不变的实验室颜色空间有助于隔离汽车。由于我们没有使用[3]的轮廓检测方法，所以我们的方法有时会生成边界不规则的线段，这可以用猫的第三幅图像来说明。最后的图像显示了一个非常困难的例子，只有[4]提供了一个精确的段。

现在，由于选择性搜索的本质，而不是方法之间的竞争，更有趣的是看它们如何互补。由于两者[4,9]的算法非常不同，根据我们的多样化假设，组合应该是有效的。确实，如表6的下半部分所示，结合我们的“快速”选择性搜索，可以在6,438个位置找到0.737 MABO。这是一个较高的MABO，比我们的“质量”选择性搜索使用较少的位置。将[4,9]与我们的“质量”抽样相结合，在25,355个位置得到0.758个MABO。这是一个很好的增长，只有少量的额外位置。

综上所述，选择性搜索对于根据区域生成目标位置非常有效。多种策略的使用使得它能够抵抗各种图像条件以及对象类。将[4]、[9]和我们的分组算法组合成一个单一的选择性搜索，显示出了有希望的改进。鉴于这些改进,考虑到有很多不同的分区算法用于选择性搜索,这将是有趣的,看看我们的选择性搜索范例仍然可以在计算效率、对象位置数量和质量方面走多远。

图8：选择性搜索、[4]和[9]的定性比较。对于我们的方法，我们观察到:忽略颜色可以找到瓶子，多个颜色空间在黑暗的图像是有用的(汽车)，而不使用[3]有时会导致不规则的边界，如猫。

5.3 物体识别

在本节中，我们将评估使用 VOC 2010检测任务的目标识别的选择性搜索策略。

我们的选择性搜索策略能够使用昂贵而强大的图像表示和机器学习技术。在本节中，我们将在第4节中描述的基于词袋的对象识别框架中使用选择性搜索。与穷举搜索相比，对象位置的减少使得使用这种强大的词袋的实现成为可能。

给出一个计算需求的指示:三个SIFT变体的像素提取加上可视化的单词分配大约需要10秒，每幅图像完成一次。支持向量机的最后一轮学习在GPU上每类大约需要8个小时，大约30000个训练示例[33]是由于在 VOC 2010上进行了两轮负样本挖掘而产生的。困难的负样本的挖掘是并行进行的，在10台机器上进行一次大约需要11个小时，每张照片大约需要40秒。这分为30秒计算可视单词频率和0.5秒每类分类。测试需要40秒的时间来提取特征、分配可视单词和计算可视单词频率，之后每个类需要0.5秒进行分类。为了进行比较，[12]的代码(没有级联，就像我们的版本一样)需要对每个类的每个图像进行略少于4秒的测试。对于20 类，这使我们的框架在测试过程中更快。

我们使用官方评估服务器评估结果。这个评估是独立的，因为测试数据还没有发布。我们与比赛的前四名进行比较。注意，虽然前四种方法都是基于穷举搜索，使用基于部分的[12]模型的变体和HOG-，但是我们的方法通过使用选择性搜索和词袋模型特性有很大的不同。结果如表7所示。

表7：结果来自于 VOC 2010检测任务测试集。我们的方法是唯一的基于词袋模型的目标识别系统。它在9个主要是非刚性对象类别中得分最高，其中差异高达0.056

AP。其他方法基于基于部件的HOG特性，并且在大多数刚性对象类上表现得更好。

结果表明，该方法对飞机类、猫类、牛类、桌子类、狗类、植物类、羊类、沙发类、电视类的分类效果最好。除了桌子、沙发和电视，这些类都是非刚性的。这是预期的，因为从理论上讲，词袋比hog特性更适合于这些类。确实，对于严格的类自行车，瓶子，公共汽车，汽车，人，和训练，基于hog的方法表现得更好。唯一的例外是严格的tv类。这可能是因为我们的选择性搜索在定位电视时表现得很好，请参见图6。

在 2011挑战赛中，有几个参赛作品的得分都比我们的参赛作品高得多。这些方法利用词袋作为附加信息，通过基于部件的模型找到位置，从而提高了检测精度。然而，有趣的是，通过使用词袋来检测位置，我们的方法对许多类[10]实现了更高的总召回率。

最后，我们的选择性搜索使得参与 Large Scale 2011 ()的检测任务成为可能，如表8所示。该数据集包含1,229,413张训练图像和100,000张测试图像，包含1,000个不同的对象类别。可以加速测试，因为从选择性搜索位置提取的特性可以重用于所有类。例如，使用[30]的快速单词包框架，提取sift描述符和两个颜色变体的时间需要6.7秒，而对可视单词的赋值需要1.7秒。使用1x1、2x2和3x3的空间金字塔划分，需要14秒就可以得到所有172,032维的特征。在金字塔级别的级联分类中，每个类需要0.3秒。对于1000个类，整个测试过程将花费每张图像323秒。相比之下，使用基于部件的[12]框架，每个类每个图像需要3.9秒，因此每个图像测试需要3900秒。这清楚地表明，减少的位置数量有助于向更多的类扩展。

我们的结论是，与穷举搜索相比，选择性搜索能够随着类的增加更好地使用更昂贵的特性、分类器和伸缩性。

表8：大尺度视觉识别挑战2011 ()结果。如果根据层次结构，预测的类在语义上与实际类相似，则分级错误会减少错误。

5.4 VOC 2012

因为Pacal VOC 2012是最新的，也可能是最终的VOC数据集，所以我们简要介绍一下这个数据集的结果，以便与我们未来的工作进行比较。我们在使用官方评估服务器的测试集上使用1x1、2x2、3x3和4x4的空间金字塔来表示盒子的质量，以及训练集+验证集分割部分的片段的质量，以及我们的本地化框架。

定位质量结果如表9所示。我们看到，对于box-，结果略高于 VOC 2007。然而，对于分段来说，结果更糟。这主要是因为2012的细分集要困难得多。

对于2012的检测挑战，平均精度均值为0.350。这与在 VOC 2010上获得的0.351 MAP相似。

表9： VOC 2012 训练集+验证集的位置质量

5.5 位置质量的上界

在这个实验中，我们研究了我们的选择性搜索位置与最优位置之间的距离。我们在 VOC 2007测试集上做了这个。

图9:图中的红线显示了使用“质量”选择性搜索方法的前n个框时，我们的对象识别系统的MAP得分。性能从0.283 MAP开始，使用前500个对象位置，MABO值为0.758。使用MABO值为0.855的前3000个对象位置，MAP值迅速增加到0.356，然后使用所有MABO值为0.883的1097个对象位置，MAP值为0.360。

洋红色的线显示了我们的对象识别系统的性能，如果我们将地面真值对象位置包含到我们的假设集中，表示一个“完美”质量的对象假设集，MABO评分为1。当只使用地面真值框时，得到的MAP为0.592，这是我们的目标识别系统的上限。然而，每幅图使用500个位置，这一分数迅速下降到0.。值得注意的是，当全部使用1079个框时，性能下降到0.377 MAP，只比不包含地面真相时多0.017 MAP。这表明，在10000个目标位置上，我们的假设集接近于我们的识别框架所能达到的最优值。最有可能的解释是我们使用了SIFT，它被设计为移位不变的[21]。这使得图5中所示质量的近似框仍然足够好。然而，10000个盒子组成的“完美”对象假设集与我们的假设之间的小差距表明，我们已经达到了一个临界点，即词袋的不变性程度可能会产生不利影响，而不是有利影响。

随着框数的增加，“完美”假设集的减少是由于问题难度的增加:框数越多，变异性越大，使得目标识别问题更加困难。早些时候，我们假设穷举搜索检查了图像中所有可能的位置，这使得目标识别问题变得困难。为了测试选择性搜索是否缓解了这个问题，我们还使用了我们的词袋对象识别系统，使用[12]的位置进行了彻底搜索。这将得到0.336的MAP，而MABO为0.829，每个类的对象位置数为100,000。通过选择搜索，使用2000个位置可以获得相同的MABO。在2000个位置，目标识别精度为0.347。这表明，通过减少位置的可能变化，选择性搜索确实比穷举搜索更容易解决问题。

综上所述，目标假设的质量和数量与目标识别的准确性之间存在着权衡关系。高质量的物体位置是识别物体的首要条件。能够在不牺牲质量的情况下对更少的对象假设进行抽样，使得分类问题更容易，并有助于改进结果。值得注意的是，在合理的10,000个位置上，我们的目标假设集对于我们的单词袋识别系统来说是接近最优的。这表明，我们的位置质量如此之高，以至于现在需要比通常在词袋中找到的功能具有更高的识别能力。

6 结论

这篇文章提出了一种适用于选择搜索的分段算法。我们观察到，图像具有内在的层次性，区域形成对象的原因有很多。因此，单个自底向上的分组算法永远无法捕获所有可能的对象位置。为了解决这个问题，我们引入了选择性搜索，其主要观点是使用一组不同的互补和分层的分组策略。这使得选择性搜索稳定、健壮，并且独立于对象类，对象类型从刚体(例如car)到非刚体(例如cat)，从理论上讲还包括非晶态(例如水)。在对象窗口方面，结果表明，我们的算法优于[2]的“ -”，在[2]中，我们的快速选择搜索在2134个位置达到了平均0.804的平均最佳重叠质量。与[4,9]相比，我们的算法在最多790个位置生成的MABO约为0.790 MABO的窗口的质量和数量之间有着类似的权衡，这是它们生成的最大值。但是我们的算法要快13-59倍。此外，每幅图像最多可创建10097个位置，生成的MABO最高可达0.879个位置。在目标区域方面，我们的算法与[4,9]结合后，质量有了很大的提升(MABO从0.730增加到0.758)，这说明我们的多样化范式仍然有改进的空间。最后，我们证明选择性搜索可以成功地用于创建一个良好的基于词袋的定位和识别系统。事实上，我们证明了我们的选择性搜索位置的质量是接近于最优的版本的词袋为基础的对象识别。