R-CNN之selective search选择搜索原理及实现

selective search 属于传统机器学习方法

在Faster R-CNN中被RPN所取代

在目标检测时，为了定位到目标的具体位置，通常会把图像分成许多子块，然后把子块作为输入，送到目标识别的模型中。分子块的最直接方法叫滑动窗口法。滑动窗口的方法就是按照子块的大小在整幅图像上穷举所有子图像块。这种方法产生的数据量非常大，复杂度太高，产生了很多的冗余候选区域，在现实当中不可行，选择性搜索selective search有效地去除冗余候选区域，使得计算量大大的减小。

我们看上面的一组图片，由于我们事先不知道需要检测哪个类别，因此第一张图中的桌子，瓶子，餐具都是一个个候选目标，而餐具包含在桌子这个目标内，勺子又包含在碗内。这张图展示了目标检测的层级关系以及尺度关系，那我们如何去获得这些可能目标的位置呢？能否通过视觉特征去减少候选框的数量并提高精度呢？

图像可用的特征很多，到底什么特征是有用的呢？

（1) 看第二幅图片中的两只猫咪，他们的纹理是一样的，所以通过纹理特征区分猫是不可行的，但两只猫颜色不一样，因此通过颜色特征比较有用。

(2) 看第三幅图片，变色龙，会发现颜色特征在这里不好用，但会发现若用边缘特征，纹理特征就会较好用。

（3) d图中，我们很容易把车和轮胎看作是一个整体，但车和轮胎的特征差距非常大，无论是颜色还是纹理还是边缘都差异巨大。

这里只有4幅图，自然图像那么多，我们通过什么特征去区分？区分到什么程度？

selective search选择搜素的策略是：既然不知道尺度是怎样的，那就尽可能遍历所有的尺度好了，但是不同于暴力穷举，我们可以先用基于图的图像分割方法得到小尺度的区域，然后一次次合并得到大的尺寸就好了，这也符合人类的视觉认知。既然特征很多，那就把我们知道的特征都用上，但是同时也要照顾下计算复杂度，不然和穷举法也没啥区别了。最后还要做的是对每个区域进行排序，这样你想要多少个候选我就产生多少个，不然总是产生那么多你也用不完不是吗？

问题：什么是图像分割？

      图像分割就是把图像分成若干个特定的、具有独特性质的区域并提出感兴趣目标的技术和过程。它是由图像处理到图像分析的关键步骤。现有的图像分割方法主要分以下几类：基于阈值的分割方法、基于区域的分割方法、基于边缘的分割方法以及基于特定理论的分割方法等。从数学角度来看，图像分割是将数字图像划分成互不相交的区域的过程。图像分割的过程也是一个标记过程，即把属于同一区域的像索赋予相同的编号。

在深入介绍selective search之前，先说下其要考虑的几个问题：

一、适应不同尺度（capture all scales):穷举搜素（exhaustive selective)通过改变窗口大小来适应物体的不同尺度，选择搜索（selective search)同样无法避免这个问题，算法采用了图像分割image segmentation以及使用一种层次算法hierarchical algorithm有效的解决了这个问题。

二、多样化（diversification)，单一的策略无法应对多种类别的图像，使用颜色color，纹理texture,大小size等多种策略对分割好的区域region进行合并

三、速度快（fast to compute)

 

方法：

1. 在较高层次上进行选择性搜素，如下图所示，通过不同大小的窗口查看图像，并且对于每个尺寸，尝试通过纹理，颜色或强度将相邻像素组合在一起以标识对象。类似一个聚类的过程。

2. 在窗口的size更大的时候，相邻聚类尝试合并。

3. 最后把不同窗口大小下的不同聚类区块都提交作为proposal

 

step1: 通过简单的区域划分算法，将图片划分成很多小区域，再通过相似度和区域大小（小的区域先聚合，这样是防止大的区域不断的聚合小区域，导致层次关系不完全），这样就能解决object层次问题。

对于计算速度来说，这个思路相对于穷举，大答减少了后期分类过程中的计算量

step 1: 生成区域集R,具体参见论文《efficent graph-based image segmentation>>

step 2：计算区域集R中里每个相邻区域的相似度S={S1,S2,...}

step 3: 找出相似度最好的两个区域，将其合并为新集，添加进R

step 4: 从S中移除所有与stpe2中有关的子集

step 5: 计算新集与所有子集的相似度

step 6: 跳直step 2,直至S为空

 

给区域打分：

通过以上步骤我们能够得到很多很多的区域，显然，每个区域作为目标的可能性是不相同的，因此我们需要筛选区域建议的个数，对所有区域打一个分数。