1. 摘要
本文主要介绍物体识别中的一种选择性搜索（Selective Search）方法。
物体识别，在之前的做法主要是基于穷举搜索（Exhaustive Search）：选择一个窗口扫描整张图像（image），改变窗口的大小，继续扫描整张图像。这种做法是比较原始直观，改变窗口大小，扫描整张图像，非常耗时。若能过滤掉一些无用的box将会节省大量时间。这就是本文中Selective Search(选择性搜索)的优点。
选择性搜索（Selective Search)综合了穷举搜索（Exhausticve Search)和分割（Segmentation)的方法，意在找到一些可能的目标位置集合。作者将穷举搜索和分割结合起来，采取组合策略保证搜索的多样性，其结果达到平均最好重合率为0.879。能够大幅度降低搜索空间，提高程序效率，减小计算量。
2. 背景
在图像中，同一个物体在像素点尺度上具有一定的相似性，如颜色值相似性，纹理相似性，尺度相似性等等。Selective Search正是利用了同一物体在像素点尺度范围的相似性，不断的去合并一些达到预设相似性阈值的相邻像素点，从而将可能属于同一物体的像素点合并，形成一个区域box。这样将一张图像中所有具有一定相似性的像素点合并，形成一些可能属于同一物体的区域集，作为下一步用来检测的区域集，即可能的目标boxes。
图像包含的信息非常的丰富，其中的物体（Object）有不同的形状（shape）、尺寸（scale）、颜色（color）、纹理 （texture），要想从图像中识别出一个物体非常的难，还要找到物体在图像中的位置，这样就更难了。图中给出四个例子，来说明物体识别 （Object Recognition）的复杂性以及难度。
（a）中的场景是一张桌子，桌子上面放了碗，瓶子，还有其他餐具等等。比如要识别“桌子”，我们可能只是指桌子本身，也可能包含其上面的其他物体。这里显示出了图像中不同物体之间是有一定的层次关系的。
（b）中给出了两只猫，可以通过纹理（texture）来找到这两只猫，却又需要通过颜色（color）来区分它们。
（c）中变色龙和周边颜色接近，可以通过纹理（texture）来区分。
（d）中的车辆，我们很容易把车身和车轮看做一个整体，但它们两者之间在纹理（texture）和颜色（color）方面差别都非常地大。
这些问题说明：在做物体识别过程中，不能通过单一策略来区分不同的物体，需要充分考虑图像物体的多样性（diversity）。另外，在图像中物体的布局有一定的层次（hierarchical）关系，考虑这种关系才能够更好地对物体的类别（category）进行区分。物体布局层次怎么理解呢？以图(a)为例，勺子在碗里，碗在桌子上，这就是层次化关系。那么算法中是如何体现的呢？就是从图中的小区域开始合并，类似于构造哈夫曼树一样，分层而上。
3. 选择性搜索(Selective Search)
3.1 层次归类算法(Hierarchical Grouping Algorithm)
输入：彩色图片（三通道）
输出：物体位置的可能结果L
- 使用《Efficient Graph-Based Image Segmentation》方法，获取初始分割区域R={r1,r2,…,rn}
- 初始化相似度集合S=∅
- 计算R中两两相邻区域（ri,rj）之间的相似度，将其添加到相似度集合S中。
- 从相似度集合S中找出，相似度最大的两个区域ri和rj，将其合并成为一个区域 rt。然后从相似度集合中除去原先与ri和rj相邻区域之间计算的相似度。计算新的rt与其相邻区域（原先与ri或rj相邻的区域）的相似度，将其结果添加的到相似度集合S中。同时将新区域 rt 添加到区域集合R中。迭代直至S为空，即可合并区域的都已合并完。 区域的合并方式类似于哈夫曼树的构造过程，因此称之有层次（hierarchical）。
-
获取R中每个区域的Bounding Boxes，这个结果就是图像中物体可能位置的可能结果集合L。
3.2 多样性策略
论文给出了两个方面的多样化策略：颜色空间多样化，相似度计算的多样化。
3.2.1 颜色空间多样化
作者采用了8种不同的颜色方式，主要是为了考虑场景以及光照条件等。主要使用的颜色空间有： （1）RGB，（2）灰度I，（3）Lab，（4）rgI（归一化的rg通道加上灰度），（5）HSV，（6）rgb（归一化的RGB），（7）C，（8）H（HSV的H通道）
3.2.2 相似度计算多样化
得到原始区域后，就要开始区域合并。通过计算区域间的相似度来合并。文章给出四种相似度的计算策略，最后计算加权和。
1. 颜色（color）相似度
使用L1-norm归一化，获取图像中每个区域的每个颜色通道的25 bins的直方图，这样每个区域都可以得到一个75维的向量。
区域ri的颜色直方图（n=75）：
2. 纹理（texture）相似度
这里的纹理采用SIFT-Like特征。具体做法是对每个颜色通道的8个不同方向计算方差σ=1的高斯微分（Gaussian Derivative），每个通道每个颜色获取10 bins的直方图（L1-norm归一化），这样就可以获取到一个8310=240维的向量。区域之间纹理相似度计算方式和颜色相似度计算方式类似，合并之后新区域的纹理特征计算方式和颜色特征计算相同：
3. 大小（size）相似度
这里的大小是指区域中包含像素点的个数。使用大小的相似度计算，主要是为了尽量让小的区域先合并（size（im）是图像的像素点大小）。
4. 吻合（fit）相似度
这里主要是为了衡量两个区域是否更加“吻合”。其指标是合并后的区域的Bounding Box（能够框住区域的最小矩形）越小，其吻合度越高。其计算方式：
4、算法应用：物体识别
利用Selective Search对图像进行处理后，形成了可能的目标区域集L。下一步集合Sift或者CNN或者bag-of–words等一些特征提取方法，对每一个可能的目标区域进行特征处理，形成该区域的特征向量V。然后将V送入训练好的SVM多分类器进行判别。在穷举搜索（Exhaustive Search）方法中，寻找合适的位置假设需要花费大量的时间，能选择用于物体识别的特征不能太复杂，只能使用一些耗时少的特征。由于选择搜索 （Selective Search）在得到物体的位置假设这一步效率较高，其可以采用诸如SIFT等运算量大，表示能力强的特征。
4.1. 特征生成
系统在实现过程中，使用color-SIFT特征以及spatial pyramid divsion方法。在一个尺度下σ=1.2下抽样提取特征。使用SIFT、Extended OpponentSIFT、RGB-SIFT特征，在四层金字塔模型 1×1、2×2、3×3、4×4，提取特征，可以得到一个维的特征向量。
4.2.训练过程
训练方法采用SVM。首先选择包含真实结果（ground truth）的物体窗口作为正样本（positive examples），选择与正样本窗口重叠20%~50%的窗口作为负样本（negative examples）。在选择样本的过程中剔除彼此重叠70%的负样本，这样可以提供一个较好的初始化结果。在重复迭代过程中加入hard negative examples（得分很高的负样本）。其训练过程框图如下：
5. 性能评价
很自然地，通过算法计算得到的包含物体的Bounding Boxes与真实情况（ground truth）的窗口重叠越多，那么算法性能就越好。这是使用的指标是平均最高重叠率ABO（Average Best Overlap）。对于每个固定的类别c，每个真实情况（ground truth）表示为 ，令计算得到的位置假设L中的每个值l，那么 ABO的公式表达为：
上面结果给出的是一个类别的ABO，对于所有类别下的性能评价，很自然就是使用所有类别的ABO的平均值MABO（Mean Average Best Overlap）来评价。
