翻译：Selective Search for Object Detection

原文：Selective Search for Object Detection

在这篇指导，我们将会理解一个在目标检测中的重要概念——Selective Search。我们也会在 C++ 的和 Python 上分享 OpenCV 代码。
#目标检测与目标识别
一个目标识别算法识别图像中出现了哪些目标。把整张图片作为输入，输出该目标的类别标签和属于该类别的可能性。例如，一个类别标签为 “dog” 和为该标签可能性为 97%。
另一方面，一个目标检测算法不仅告诉你哪些物体在图像上出现，而且输出边界框（x, y, width, height）来指明图像中该物体的位置。
所有目标检测算法的核心都是一种目标识别算法。假设我们训练一个在图片子块识别狗的目标识别模型。这个模型将会分辨一张图片是否含有狗。但是不会分辨物体的位置。
为了定位物体，我们必须要选择图片的次区域（子块）然后对这些图片子块应用目标识别算法。物体的位置由目标识别算法返回的类别可能性高的图片子块位置给定。

最直接的生成较小的次区域的方法为滑动窗口方法。然而，滑动窗口方法有许多限制。这些限制被一类叫区域建议的算法克服了。选择性搜索就是区域建议算法中最流行的一种。

#滑动窗口算法
在滑动窗口方法中，我们在图像上滑动一个框或窗口来选择一个子块，并使用目标识别模型对窗口所覆盖的每个图像补丁进行分类。这是一个在整张图片对目标的彻底搜索。我们不仅仅需要在图片中搜索所有可能的位置，还必须要在不同尺度上搜索。这是因为目标识别模型通常在一个特殊的尺度上训（或者一个特殊的尺度范围）。这就导致了对成千上万个图像补丁的分类。
问题还不仅仅如此。滑动窗口方法对于固定的纵横比对象，如人脸或行人表现是好的。图像是三维物体的二维投影。根据图像拍摄的角度，诸如纵横比和形状等物体特征有很大的不同。因此当我们搜索多个纵横比时，滑动窗口方法的计算非常昂贵。

#区域建议算法
到目前为止我们讨论的问题可以用区域建议算法来解决。这些方法将图像作为输入，输出边界框，对应于图像中所有最有可能是对象的补丁。这些区域的提议可能是嘈杂的、重叠的，并且可能不能完美地包含这个对象，但是在这些区域的提议中，将会有一个非常接近于图像中的实际对象的建议。然后我们可以使用对象识别模型对这些建议进行分类。有高概率分数的区域建议就是该物体的位置。

区域建议案算法使用分割识别图像中的预测对象。在分割中，我们根据一些标准，比如颜色，纹理等，对相邻区域进行分组。与滑动窗口方法不同的是，我们在滑动窗口方法中在所有像素位置和所有尺度内寻找对象，而在区域建议算法中通过将像素分组到更小的分割中工作。
区域建议方法的一个重要特性是具有很高的回忆能力。
这只是一种奇特的说法，即包含我们正在寻找的对象的区域必须在我们的区域建议列表中。为了完成这一任务，我们的区域建议列表可能会有很多不包含任何对象的区域。换句话说，只要它能抓住所有的真积极因素（正确建议），即使区域建议算***产生大量的误报也是可以的。大多数这些错误建议将被目标识别算法所排除。当我们有更多的错误建议时，检测的时间就会增加，准确性也会受到轻微的影响。但是，高回忆仍然是一个好主意，因为会丢失包含实际对象的区域的其他方***严重影响检测率。

已经有几个区域建议方法被提出了，例如：

1. Objectness
2. Constrained Parametric Min-Cuts for Automaticobject Segmentation
3. Category Independent Object Proposals
4. Randomized Prim
5. Selective Search

在所有这些区域建议方法中，选择性搜索最常用，因为它是快速的，并且有很高的回忆。
#目标检测中的选择性搜索
##什么是选择性搜索？
选择性搜索是一种用于目标检测的区域建议算法。它的设计是为了快速的召回。它基于计算相似区域的分层分组，这些分组基于颜色、纹理、大小和形状兼容性分组。
选择性搜索首先是通过使用 Felzenszwalb 和 huttenlocher 的基于图形的分割方法对图像像素的强度进行过分割开始的。该算法的输出如下所示。右边的图像包含了用纯色表示的分割区域。

我们可以在这个图像中使用分割的部分作为区域的建议吗？答案是否定的，我们不能这样做有两个原因：

1. 原始图像中的大多数实际对象包含两个或多个分割部分
2. 对于被遮挡的物体，如杯子所覆盖的盘子或装满咖啡的杯子的区域建议不能用这种方法生成
   如果我们试图通过进一步合并相邻的区域来解决第一个问题，我们最终会得到一个包含两个对象的分割区域。
   完美的分割不是我们的目标。我们只是想预测许多区域的建议，比如其中一些应该与实际的对象有非常高的重叠。
   选择性搜索使用 Felzenszwalb 和 huttenlocher 的方法中的过分割作为初始种子。一个过分割的图像是这样的。
   

选择性搜索算法将这些过分割作为初始输入，并执行以下步骤

1. 将与分割部分对应的所有边界框添加到区域建议列表中
2. 基于相似度组合相邻分割
3. 回到第一步
   在每次迭代中，形成更大的部分并添加到区域提案列表中。因此，我们通过自下而上的方法，从较小的部分到更大的部分，创建区域建议。：这就是我们所说的使用 Felzenszwalb 和 huttenlocher 的过分割来计算“分层”分割的意思。
   

这张图片展示了分层分割过程的初始、中间和最后一步。
##相似性
让我们深入研究如何计算两个区域之间的相似性。
选择性搜索使用4种基于颜色、纹理、大小和形状兼容性的相似度测量方法。
###颜色相似度
为图片的每个通道计算一个25组的颜色直方图，然后连接所有通道的直方图来获得一个颜色描述符，结果为 25 × 3 = 75维的颜色描述符。
两个区域的颜色相似度是基于直方图相交的，可以按如下计算：
$$s_{color}(r_i,r_j)=\sum _{k=1}^{n}min(c_i^k,c_j^k)$$
$c_i^k$是在颜色描述符中直方图中$k^{th}$组的值
###纹理相似度
纹理特征是通过在每个通道的8个方向提取高斯导数来计算的。对于每一个方向和每个颜色通道，计算一个10组直方图，形成一个10 × 8 × 3=240维的特征描述符。
利用直方图相交法计算两个区域的纹理相似度。
$$s_{texture}(r_i,r_j)=\sum _{k=1}^{n}min(t_i^k,t_j^k)$$
$t_i^k$是在纹理描述符中直方图中$k^{th}$组的值
###大小相似度
大小相似促使较小的区域尽早合并。它确保了在所有尺度上的区域建议都是在图像的所有部分形成的。如果没有考虑到这种相似性度量，单个区域将会一个接一个地吞噬所有较小的相邻区域，因此在这个位置只会产生多个尺度的区域建议。大小相似性被定义为：
$$s_{size}(r_i,r_j)=1-\frac{size(r_i)+size(r_j)}{size(im)}$$
这里$size(im)$是图片像素级的大小
###形状兼容性
形状兼容性测量两个区域（$r_i$和$r_j$）之间的匹配程度。如果$r_i$适合$r_j$，我们想要合并它们以填补空白，如果它们之间没有相互接触，它们就不应该合并。
形状兼容性定义如下：
$$s_{fill}(r_i,r_j)=1-\frac{size(B{B}_{ij})-size(r_i)-size(r_j)}{size(im)}$$
这里$size(B{B}_{ij})$是在$r_i$和$r_j$周围的边界框
###最终相似度
两个区域之间的最终相似性被定义为上述4个相似点的线性组合。
$$s(r_i,r_j)=a_1{s}_{color}(r_i,r_j)+a_2{s}_{texture}(r_i,r_j)+a_3{s}_{size}(r_i,r_j)+a_4{s}_{fill}(r_i,r_j)$$
这里$r_i$和$r_j$为图像中的两个区域或段，而$a_i\in 0,1$，1表示是否使用了相似性度量。
#总结
OpenCV的选择性搜索实现为成千上万的区域建议提供了减少的目标顺序。为了清晰起见，我们将结果与图片上的200-250个盒子共享结果。在一般情况下，1000-1200的建议足以得到所有正确的地区建议

左：狗：前250区域建议；右：早餐桌：前200区域建议

#选择性搜索代码
在原网站中有代码，也有英文注释，有兴趣的自行前往学习。