selective search算法

目标检测任务中由于我们事先不知道需要检测哪个类别，因此第一张图的桌子、瓶子、餐具都是一个个候选目标，而餐具包含在桌子这个目标内，勺子又包含在碗内。这张图展示了目标检测的层级关系以及尺度关系，那我们如何去获得这些可能目标的位置呢。

在selective search算法之前，在图片上使用穷举法或者滑动窗口选出所有物体可能出现的区域框，就是在原始图片上进行不同尺度不同大小的滑窗，获取每个可能的位置。而这样做的缺点也显而易见，复杂度太高，产生了很多的冗余候选区域，而且由于不可能每个尺度都兼顾到，因此得到的目标位置也不可能那么准。

selective search算法不使用暴力方法，而是用候选区域方法（region proposal method）创建目标检测的感兴趣区域（ROI）。在选择性搜索（selective search，SS）中，我们可以先利用基于图的图像分割的方法得到小尺度的区域，然后一次次合并得到大的尺寸。考虑所有特征，例如颜色、纹理、大小等，同时照顾下计算复杂度。

在介绍Selective Search之前，先说明一下需要考虑的问题：

适应不同尺度（Capture All Scales）:穷举搜索通过改变窗口大小来适应物体的不同尺度，选择搜索同样无法避免这个问题。算法采用图像分割以及使用一种层次算法有效地解决了这个问题
多样化（Diversification）：单一的策略无法应对多种类别的图像，使用颜色、纹理、大小等多种策略对分割好的区域进行合并
速度快

输入：一张图片
输出：候选的目标位置集合
算法：
利用切分方法得到候选的区域集合R = {r1,r2,…,rn}
初始化相似集合S = ϕ
foreach 遍历邻居区域对 (ri,rj) do
计算相似度s(ri,rj）
S = S ∪ s(ri,rj)
while S not=ϕ do
从s中得到最大的相似度s(ri,rj)=max(S)
合并对应的区域rt = ri ∪ rj
移除ri对应的所有相似度：S = Ss(ri,r*)
移除rj对应的所有相似度：S = Ss(r*,rj)
计算rt对应的相似度集合St
S = S ∪ St
R = R ∪ rt
L = R中所有区域对应的边框
-------算法解读参考墨麟非攻

首先通过基于图的图像分割方法初始化原始区域，就是将图像分割成很多很多的小块，使用贪心策略，计算每两个相邻区域的相似度，然后每次合并最相似的两块，直至最终只剩下一块完整的图片。然后这其中每次产生的图像块包括合并的图像块我们都保存下来，这样就得到图像的分层表示。

保持多样性的策略

区域合并采用了多样性的策略，如果简单采用一种策略很容易错误合并不相似的区域，比如只考虑纹理时，不同颜色的区域很容易被误合并。选择性搜索采用三种多样性策略来增加候选区域以保证召回：

多种颜色空间，考虑RGB、灰度、HSV及其变种
多种相似度度量标准，既考虑颜色相似度，又考虑纹理、大小、重叠情况等
通过改变阈值初始化原始区域，阈值越大，分割的区域越少

a.颜色空间转换

通过色彩空间转换，将原始色彩空间转换到多达八种色彩空间。也是为了考虑场景以及光照条件等，主要应用于图像分割算法中原始区域的生成（两个像素点的相似度计算时，计算不同颜色空间下的两点距离）。

主要使用的颜色空间有：

1）RGB

2）灰度I

3）Lab

4）rgI（归一化的rg通道加上灰度）

5）HSV

6）rgb（归一化的RGB）

7）C

8）H（HSV通道的H）

b.区域相似度计算

我们在计算多种相似度的时候，都是把单一相似度的值归一化到[0, 1]之间，1表示两个区域之间相似度最大

颜色相似度
纹理相似度
有限合并小的区域
区域的合适度距离
合并上面四种相似度

给区域打分

通过上述步骤，我们可以得到很多区域，但是并不是每个区域作为目标的可能性都是相同的，我们要进行筛选。

给予最先合并的图片块较大的权重，比如最后一块完整图像权重为1，倒数第二次合并的区域权重为2，以此类推。但是当我们策略很多，多样性很多的时候，权重就会有太多的重合，这样排序就不太方便。我们可以给他们乘以一个随机数，然后对于相同的区域多次出现的也叠加下权重，毕竟多个方法都说你是目标，也是有理由的嘛。这样我们就得到所有区域的目标分数，也就可以根据自己的需要选择多少个区域了。

选择性搜索性能评估

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

$mathrm{ABO}=frac{1}{left|G^{c} ight|} sum_{g_{i}^{c} in G^{c}} max _{l_{j} in L}$ Overlap $left(g_{i}^{c}, l_{j} ight)$

重叠率的计算方式：

$operatorname{Overlap}left(g_{i}^{c}, l_{j} ight)=frac{operatorname{area}left(g_{i}^{c} ight) cap operatorname{area}left(mathrm{l}_{mathrm{j}} ight)}{operatorname{area}left(g_{i}^{c} ight) cup operatorname{area}left(mathrm{l}_{mathrm{j}} ight)}$

上面结果给出的是一个类别的ABO，对于所有类别下的性能评价，很自然就是使用所有类别的ABO的平均值MABO（Mean Average Best Overlap）来评价。

a.单一策略评估

我们可以通过改变多样性策略中的任何一种，评估选择性搜索的MABO性能指标。采取的策略如下：