选择性搜索

目标检测的第一步是要做区域提名（Region Proposal），也就是找出可能的感兴趣区域（Region Of Interest，ROI）。区域提名类似于光学字符识别（OCR）领域的切分，OCR切分常用过切分方法，简单地说，就是尽量切碎到小的连通域（比如小的笔画之类的），然后再根据相邻块的一些形态学特征进行合并。但目标检测的对象相比OCR领域千差万别，而且图形不规则，大小不一，所以在一定程度上可以说区域提名是比OCR切分更难的一个问题。

区域提名可能的方法又：

1. 滑动窗口。滑动窗口本质上就是穷举法，利用不同的尺度和长宽比把所有可能的大大小小的块都穷举出来，然后送去识别，识别出概率大的就留下来。很明显，这样的方法复杂度太高，产生了很多的冗余候选区域，在现实当中不可行。

2. 规则块。在穷举法的基础上进行一些剪枝，只选用固定的大小和长宽比。这在一些特定的场景中有很有效的，比如拍照搜题App的汉子检测，因为汉字方方正正，长宽比大多比较一致，因此用规则块做区域提名是一种比较合适的选择。但是对于普通的目标检测来说，规则块依然需要访问很多的位置，复杂度高。

3. 选择性搜索。从机器学习的角度来说，前面的方法召回率是不错了，但是精度还较低，所以问题的核心在于如何有效地去除冗余候选区域。其实冗余候选区域大多是发生了重叠，选择性搜索利用这一点，自底向上合并相邻的重叠区域，从而减少冗余。

区域提名并不只有以上所讲的三种方法，实际上这个部分是非常灵活的，因此变种也很多。选择性搜素的具体算法如下所示，总体上，选择性搜索是自底向上不断合并候选区域的迭代过程。

选择性搜索算法

输入：一张图片

输出：候选的目标位置集合 $L$

• 1、利用过切分方法得到候选的区域集合 $R=\{r_1,r_2,\dots,r_n\}$

• 2、初始化相似集合 $S=\varnothing$

• 3、foreach 邻居区域对 $a = b$ do

• 4、 计算相似度 $s(r_i,r_j)$

• 5、 $S = S\cup s(r_i,r_j)$

• 6、while $S \neq \varnothing$ do

• 7、 得到最大的相似度 $s(r_i,r_j) = \max(S)$

• 8、 合并对应的区域 $r_t = r_i\cup r_j$

• 9、 移除 $r_i$ 对应的所有相似度： $S=S\backslash s(r_i,r_*)$

• 10、 移除 $r_j$ 对应的所有相似度： $S=S\backslash s(r_*,r_j)$

• 11、 计算 $r_t$ 对应的相似度集合 $S_t$

• 12、 $S = S\cup S_t$

• 13、 $R = R\cup r_t$

• 14、 $L = R$ 中所有区域对应的边框

从算法不难看出， $R$ 中的区域都是合并后的，因此减少了不少冗余，相当于提升了准确率，但是我们还需要保证召回率，因此上述算法中的相似度计算策略就显得非常关键了。如果采用一种策略，则很容易错误合并并不相似的区域，比如只考虑轮廓时，不同颜色的区域很容易被误合并。选择性搜索采用多样性策略来增加候选区域以保证召回率，比如颜色空间考虑RGB、灰度、HSV及其变种等，计算相似度时既考虑颜色相似度，又考虑纹理、大小、重叠情况等。

总体上，选择性搜索是一种比较朴素的区域提名方法，被早期的基于深度学习的目标检测方法（包括OverFeat和R-CNN等）广泛利用，但被当前的新方法弃用了。