[初窥目标检测]——《目标检测学习笔记（2）:浅析Selective Search论文——“Selective Search for object recognition”》_选择性搜索算法原论文

[初窥目标检测]——《目标检测学习笔记（2）:浅析Selective Search论文——Selective Search for object recognition》

本文介绍

前文我们提到了优于暴力搜索的selective search（选择性搜索），文本来浅析一下selective search的论文：《Selective Search for Object Recognition》，是J.R.R. Uijlings发表在2012 IJCV上的一篇文章。selective search（选择性搜索）综合了蛮力搜索（exhaustive search）和分割（segmentation）的方法，意在找出可能的目标位置来进行物体的识别。与传统的单一策略相比，选择性搜索提供了多种策略，并且与蛮力搜索相比，大幅度降低搜索空间，让我们可以用到更好的识别算法。

一、摘要

本文主要介绍物体识别中的一种选择性搜索（Selective Search）方法。

物体识别，在之前的做法主要是基于穷举搜索（Exhaustive Search）：选择一个窗口扫描整张图像（image），改变窗口的大小，继续扫描整张图像。这种做法是比较原始直观，改变窗口大小，扫描整张图像，非常耗时。若能过滤掉一些无用的box将会节省大量时间。这就是本文中Selective Search(选择性搜索)的优点。

选择性搜索（Selective Search)综合了穷举搜索（Exhausticve Search)和分割（Segmentation)的方法，意在找到一些可能的目标位置集合。作者将穷举搜索和分割结合起来，采取组合策略保证搜索的多样性，其结果达到平均最好重合率为0.879。能够大幅度降低搜索空间，提高程序效率，减小计算量。

二、介绍

在图像中，同一个物体在像素点尺度上具有一定的相似性，如颜色值相似性，纹理相似性，尺度相似性等等。Selective Search正是利用了同一物体在像素点尺度范围的相似性，不断的去合并一些达到预设相似性阈值的相邻像素点，从而将可能属于同一物体的像素点合并，形成一个区域box。这样将一张图像中所有具有一定相似性的像素点合并，形成一些可能属于同一物体的区域集，作为下一步用来检测的区域集，即可能的目标boxes。

图像包含的信息非常的丰富，其中的物体（Object）有不同的形状（shape）、尺寸（scale）、颜色（color）、纹理 （texture），要想从图像中识别出一个物体非常的难，还要找到物体在图像中的位置，这样就更难了。图中给出四个例子，来说明物体识别 （Object Recognition）的复杂性以及难度。（a）中的场景是一张桌子，桌子上面放了碗，瓶子，还有其他餐具等等。比如要识别“桌子”，我们可能只是指桌子本身，也可能包含其上面的其他物体。这里显示出了图像中不同物体之间是有一定的层次关系的。（b）中给出了两只猫，可以通过纹理（texture）来找到这两只猫，却又需要通过颜色（color）来区分它们。（c）中变色龙和周边颜色接近，可以通过纹理（texture）来区分。（d）中的车辆，我们很容易把车身和车轮看做一个整体，但它们两者之间在纹理（texture）和颜色（color）方面差别都非常地大。

三、基于层次分组的选择性搜索算法（Selective Search by Hierarchical Grouping）

给出这篇论文最重要的算法：

输入：彩色图片（三通道）

输出：物体位置的可能结果L

1. 使用《Efficient Graph-Based Image Segmentation》方法，获取初始分割区域R={r1,r2,…,rn}

2. 初始化相似度集合S=∅

3. 计算R中两两相邻区域（ri,rj）之间的相似度，将其添加到相似度集合S中。

4. 从相似度集合S中找出，相似度最大的两个区域ri和rj，将其合并成为一个区域 rt。然后从相似度集合中除去原先与ri和rj相邻区域之间计算的相似度。计算新的rt与其相邻区域（原先与ri或rj相邻的区域）的相似度，将其结果添加的到相似度集合S中。同时将新区域
   rt 添加到区域集合R中。迭代直至S为空，即可合并区域的都已合并完。
   区域的合并方式类似于哈夫曼树的构造过程，因此称之有层次（hierarchical）。

5. 获取R中每个区域的Bounding Boxes，这个结果就是图像中物体可能位置的可能结果集合L。

这种算法做个不太恰当的类比，就如同在生成曼哈顿树，计算生成最优相似像素树，归并成一个区域。

四、多样化策略（Diversification Strategies）

得到原始区域后，就要开始区域合并。通过计算区域间的相似度来合并。文章给出四种相似度的计算策略，最后计算加权和。
关于s(ri,rj)的计算，我们有多种方法，但要注意的是这些相似性特征应该是可以传递的。如当我们合并ri和rj成rt时，rt的特征可以由ri和rj直接计算，而不需要根据他们每个像素点的值进行重新计算。

1.颜色（color）相似度

Scolor(ri,rj)用于计算ri，rj的相似性。对每个区域，我们都可以得到一个一维的颜色分布直方图。直方图一共有25个区间，区域i的颜色分布直方图为

若有3个颜色通道，则n=75。还要用L1 norm来进行归一化。

当i和j合并成t，即为新的合并区域，区域t的颜色分布直方图可以用下面式子进行计算：

t 的size用下面式子计算：

2.纹理（texture）相似度

这里的纹理采用SIFT-Like特征。具体做法是对每个颜色通道的8个不同方向计算方差σ=1的高斯微分（Gaussian Derivative），每个通道每个颜色获取10 bins的直方图（L1-norm归一化），这样就可以获取到一个8*3*10=240维的向量。区域之间纹理相似度计算方式和颜色相似度计算方式类似，合并之后新区域的纹理特征计算方式和颜色特征计算相同：

同理，纹理的传递性也可以用（2）式解决。

3.大小（size）相似度

这里的大小是指区域中包含像素点的个数。使用大小的相似度计算，主要是为了尽量让小的区域先合并。

4.吻合（fit）相似度

这里主要是为了衡量两个区域是否更加“吻合”。其指标是合并后的区域的Bounding Box（能够框住区域的最小矩形）越小，其吻合度越高。其计算方式：

最后加权四个相似度公式，得到以下公式（In this paper, our final similarity measure is a combination of the above four）:

）

五、使用选择性搜索进行目标检测（Object Recognition using Selective Search）

利用Selective Search对图像进行处理后，形成了可能的目标区域集L。下一步集合Sift或者CNN或者bag-of–words等一些特征提取方法，对每一个可能的目标区域进行特征处理，形成该区域的特征向量V。然后将V送入训练好的SVM多分类器进行判别。在穷举搜索（Exhaustive Search）方法中，寻找合适的位置假设需要花费大量的时间，能选择用于物体识别的特征不能太复杂，只能使用一些耗时少的特征。由于选择搜索 （Selective Search）在得到物体的位置假设这一步效率较高，其可以采用诸如SIFT等运算量大，表示能力强的特征。

1.特征生成

系统在实现过程中，使用color-SIFT特征以及spatial pyramid divsion方法。在一个尺度下σ=1.2下抽样提取特征。使用SIFT、Extended OpponentSIFT、RGB-SIFT特征，在四层金字塔模型 1×1、2×2、3×3、4×4，提取特征，可以得到一个维的特征向量。

2.训练过程

训练方法采用SVM。首先选择包含真实结果（ground truth）的物体窗口作为正样本（positive examples），选择与正样本窗口重叠20%~50%的窗口作为负样本（negative examples）。在选择样本的过程中剔除彼此重叠70%的负样本，这样可以提供一个较好的初始化结果。在重复迭代过程中加入hard negative examples（得分很高的负样本）。其训练过程框图如下：

网上找到的流程图如下：

五、评估

很自然地，通过算法计算得到的包含物体的Bounding Boxes与真实情况（ground truth）的窗口重叠越多，那么算法性能就越好。这是使用的指标是平均最高重叠率ABO（Average Best Overlap）。对于每个固定的类别c，每个真实情况（ground truth）表示为 ，令计算得到的位置假设L中的每个值l，那么 ABO的公式表达为：


G应该是物体所在的目标区域。L是selective search算法算出的候选区域。找出Selective Search算法中与该类目标区域覆盖最多的区域。覆盖率由（8）式计算。然后再除以该类的数目。MABO(Mean Average Best Overlap)就是计算每一类的ABO值，再求均值。

以上，是本人在参考多个博客笔记后，根据论文来总结的笔记，算是对Selective Search for object recognition的浅析。若有错误希望大神斧正。
下篇博客笔记中，我们将要对博客1中的selectivesearch包源码进行一定的批注。

——Nuller
——2018.4.22
——多云转小雨