2.2 Selective Search

在目标检测任务中，我们不仅需要判断出图像中包含的对象类别，还需要检测出目标所在位置，理论上图片任何位置都可能存在任意尺度大小的某对象，然而如果采用暴力搜索模式，对任意空间位置进行搜索，这在时间复杂度上是不切实际的。另外对象之间的界限也很难用单一搜索指标去检索，
【图 1】

例如上图（b），虽然两只猫在像素空间上是粘连在一起的，但是利用颜色可以很好区分，图（c）中的变色龙与背景绿色树叶融为一体，然而通过纹理可以很好区分，图（d）中，骑车轮胎无论从颜色还是纹理与汽车主体差异都很大，却被汽车主体像素包围。此外在图（a）中，可以很明显感受到图像的层次组合关系，例如，小勺在碗里，碗在桌子上。

选择搜索（Selective Search）算法就是一种基于图像颜色、纹理、尺度大小及形状兼容性，对相似区域计算层次分组的区域选择算法，它的计算速度很快，召回率很高。因此在早期目标检测算法中，主要使用该算法进行目标区域搜索。

选择搜索算法结合了图像分割算法与暴力搜索算法的优势，利用图像的结构来生成目标位置同时尽可能捕获所有的目标位置，这是一种独立于对象类别，以数据为驱动的所有算法，因此具有很强的实用价值。

2.2.1 算法设计原则

选择搜索算法若想称为一种通用的算法，就需要满足一些特殊的性能，而对于目标区域搜索而言，最重要的性质包括：

• 计算速度快，单纯的暴力搜索其计算复杂度使之几乎不可能，而一个良好的区域搜索算法若想应用于目标识别框架中，其计算量不应该成为框架的瓶颈，所以速度应相当快速
• 多样化搜索策略，在上文中，我们提到，没有任何单一的搜索策略可以解决所有的区域组合问题。因此，若想搜索算法行之有效能够解决大部分问题，需要结合颜色、纹理等等诸多搜索策略
• 能够捕获所有不同比例大小的对象，对象在图像中可以以任何尺寸比例存在，因此很自然的引入分层架构体系。

2.2.2 层次聚合

以 EGBIS 算法为例，其图像分割的过程本质就是一种分层聚合的过程，我们可以在该过程基础上继续进行区域聚合，很自然的在所有尺度上生成潜在的目标位置，直到整个图像被聚合为一个区域。

该过程与 EGBIS 的合并过程相似，首先计算所有相邻区域之间的相似度，强制性合并相似度最低的两个区域，形成新的大区域，并依次迭代，直至所有区域被合并为一个大区域。具体过程如下：
【图 2】

假设通过 EGBIS 算法得到划分后的区域集合为 $R=r_1,\dots ,r_n$，$S$ 为所有相邻区域之间的相似度值的集合，两个区域越相似值越大，初始化时 $S=\varnothing$，两个区域间的相似度度量函数为 $s(r_i,r_j)$，基于此，计算所有相邻区域间的相似度值并将其加入到 $S$ 中。

算法执行过程中，首先从 $S$ 中获取相似度值最大的两个区域，即通过 $s(r_i,r_j)=\max (S)$ 获取 $r_i,r_j$ 两个区域，并强制性将其合并为 $r_t=r_i\cup r_j$，同时在区域集合 $R$ 中分别移除 $r_i,r_j$ 区域，其在相似度值集合 $S$ 中，移除所有与原 $v_i,v_j$ 相邻区域的相似度值，即 $S=S-s(r_i,r_{\ast })-s(r_{\ast },r_j)$。然后将合并后的 $r_t$ 区域加到 $R$ 中，并重新计算与 $r_t$ 相邻区域的相似度值加入到 $S$ 中。整个算法的原理还是非常简单的。

上面提到的相似度计算函数 $s(r_i,r_j)$ 该如何定义呢？我们希望它具有较低的计算复杂度，因此良好的性质应该是基于区域特征的，且在层次聚合过程中这种性质具有向上传播的能力，而不需要从合并后区域的像素值层面进行计算。

2.2.3 多元化采样策略

选择搜索的第二个关键核心是采用多元化采样方法集成为一个综合性的采样策略。例如我们可以通过具有不同不变性的颜色空间进行采样，可以使用不同的相似度度量函数 $s_{ij}$，也可以选用不同的初始化图像分割方法。然而通过第一种策略得到的效果最为理想，因此着重介绍第一种策略。

在这里，我们考虑到场景已经光照条件等的不用，可以在 8 种不同的不变性颜色空间下应用上述层次聚类算法，每次只使用其中的一种颜色空间。

8 种颜色空间分别是：$RGB$ 基本颜色空间；亮度 $I$ （灰度图) 颜色空间；$Lab$ 色彩空间；$rgi$（正则化的$RGB$ 中的 $RG$ + 亮度 $I$）; HSV 色彩空间；$rgb$ (正则化的 $RGB$ 空间)；对立的颜色空间 $C$; $HSV$ 色彩空间中的色相 $H$

颜色相似度计算

对于每一个区域，我们可以使用颜色直方图来表示，其中每个颜色通道 25 维（bins=25），对于三通道的颜色空间，则第 $i$ 个区域可以表示为 75 维的向量 C i = { c i 1 , ⋯   , c i n } , n = 75 C_i = \{c^1_i, \cdots ,c^n_i\}, n=75 Ci​={ci1​,⋯,cin​},n=75
【图 3】

两个相邻区域之间的颜色相似度基于 $L_1$ 正则化表示，即

$s_{\text{colour}}(r_i,r_j)={\sum }_{k=1}^n\min (c_i^k,c_j^k)$

颜色直方图可以通过层级结构向上传播，合并后的区域颜色直方图表示为：

$C_t=\frac{\text{size}(r_i)\times C_i+\text{size}(r_j)\times C_j}{\text{size}(r_i)+\text{size}(r_j)}$

其中 $\text{size}(r)$ 指的是区域 $r$ 中像素点数。

纹理相似度计算

纹理相似度测量使用 SIFT-Like¹ 特征表示，具体的采用方差为 1 的高斯核对每个颜色通道的 8 个方向求梯度，并对结算结果做直方图统计（bins=10），则三通道的颜色空间纹理相似度共有 240 维，第 $i$ 个区域的纹理特征表示为 $T_i=t_i^1,\cdots ,t_i^n$，其两个相邻区域之间的纹理相似度计算方式以及层级传播关系计算方式与颜色相似度计算方式完全一致。
【图 4】

小区域优先合并

在合并前期，我们应该尽可能使小区域间进行合并，防止大区域和合并过程中的逐步吞并现象。这可以确保在图像的所有部分中创建所有比例大小的对象位置。因此，我们需要定义这样的一个评估指标，它可以使小区域更有可能被优先合并：

$$s_{\text{size}}(r_i,r_j)=1-\frac{\text{size}(r_i)+\text{size}((r_j)}{\text{size}(im)}$$

其中 $\text{size}(im)$ 指的是这个图像的像素点数，通过该公式我们发现，两个区域 $r_i,r_j$ 越小，则分子越小，整体值越大，越有可能被合并。

区域适应性评估

这一点主要是为了避免区域中出现空白以及出现形状怪异的合并区域，例如，两个环形区域嵌套，即使它们很不同，逻辑上讲合并它们也是较为合理的，就像图 1（d）中汽车轮子与汽车主体之间。而有一些相连部分很小的区域，若是合并则会形成很反直觉的区域。因此，我们在合并后区域上定义一个紧密的边界框划定其区域，如果两个区域相连很紧密，则合并后的边界框应该与实际合并面积相当，否则因为形状怪异性，则边界框的面积远大于实际合并面积。
【图 5】

$$s_{\text{fill}}(r_i,r_j)=1-\frac{\text{size}(B{B}_{ij})-\text{size}(r_i)-\text{size}(r_j)}{\text{size}(im)}$$

其中 $B{B}_{ij}$ 是定义在 $，r_i，r_j$ 合并后区域上的边界框。根据公式可知，如果合并后区域的边界框与合并后的实际面积相当，则分子很小，整体值变大，更有利于合并，反之，两个区域被合并的概率降低。

综合上述 4 种不同的度量角度，我们将其合并为一个综合性区域间相似度测量指标，即：

$$s(r_i,r_j)={\alpha }_1{s}_{\text{colour}}(r_i,r_j)+{\alpha }_2{s}_{\text{texture}}(r_i,r_j)+{\alpha }_3{s}_{\text{size}}(r_i,r_j)+{\alpha }_4{s}_{\text{fill}}(r_i,r_j)$$

这里的 α i ∈ { 0 , 1 } \alpha_i \in \{0,1\} αi​∈{0,1}，代表使用或不使用某项度量特征，这里仅仅考虑特征项的增加与减少，并未考虑到特征之间的重要性，即加权组合形式。

算法整体运行结果示例图 6 如下，对于”牛“主体对象有相对较好的候选框（貌似牛尾部分白色区域没有被包含），如果我们采用更多的候选框，则存在很好的候选区域较为完整的给出”牛“的完整位置，如图 7 所示：
【图 6】 【图 7】

参考资料

Selective Search for Object Recognition slides

---

1. C. Liu, L. Sharan, E.H. Adelson, and R. Rosenholtz. Exploring features in a bayesian framework for material recognition. In Computer Vision and Pattern Recognition 2010. IEEE, 2010. 4 ↩︎