本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.Selective Search
本文只着重介绍论文中的第3部分，即Selective Search的实现细节。
R-CNN使用Selective Search生成region proposals。
Selective Search需考虑以下设计因素：
捕获所有尺寸（Capture All Scales）：
图像中的目标可能是任意尺寸。并且，有些目标的边缘可能并不清晰。所以，Selective Search需要将所有尺寸的目标都纳入考虑。如Fig2所示，Selective Search找到了很多不同尺寸的目标。
这部分通过一个分层算法来实现（an hierarchical algorithm）。
多样性（Diversification）：
区域的产生不是只有一个最优的策略。如Fig1所示，区域的产生可以来自很多不同的原因。在Fig1(b)中，我们可以通过颜色来区分这两只猫。在Fig1(c)中，我们可以通过纹理来区分叶子和变色龙。在Fig1(d)中，我们可以区分出车轮是因为它们是车的一部分，而不是因为颜色或者纹理相近。所以，在找寻这些目标时，有必要使用多样化的策略。并且，图像的本质是分层的（类似于PS中图层的概念），通俗点说就是多个目标位于不同的图层，之间可能会有遮挡。例如在Fig1(a)中，我们看不到完整的桌子、碗以及勺子等目标物体。
此外，光线的明暗（例如阴影）以及颜色的亮度也会影响区域的产生。所以为了能够解决所有可能的情况，我们需要一个多样化的策略。
快速计算（Fast to Compute）：
Selective Search的目标是在实际的目标检测框架下，为其生成一系列可能的目标位置。所以Selective Search的速度不应该成为计算瓶颈。
1.1.Selective Search by Hierarchical Grouping
我们使用一个分层分组算法（a hierarchical grouping algorithm）作为Selective Search的基础。自下而上的分组（Bottom-up grouping）是一个非常流行的分割方法，所以我们将其应用于Selective Search。因为分组的过程本身就是分层（hierarchical），我们可以继续分组过程直至图像全部变为单一区域。这也刚好满足了捕获所有尺寸的要求。
因为区域包含的信息比像素更丰富，所以我们想尽可能的使用基于区域的特征。我们使用“Felzenszwalb and Huttenlocher (2004)”的方法来产生初始的划分区域。因为该方法速度快，且产生的区域不会横跨多个目标，很适合我们这种任务。
我们的分组过程见下。首先我们使用“Felzenszwalb and Huttenlocher (2004)”的方法来产生初始划分区域。然后我们应用贪心算法迭代的整合这些区域：首先计算所有相邻区域的相似度。相似度最高的一组相邻区域将会被整合在一起，即合并为一个新的区域。然后我们会重复这个步骤直至整幅图像变成一个单一的区域。详细的实现细节见下：
这里需要注意下，集合S里的元素随着区域的合并是不断减少的，直至其为空集。但是集合R里的元素是逐渐变多的，里面存储了最初始的划分区域以及后续每一次合并得到的新区域。这样的话就保证了R里面的区域有大有小，适用于不同尺寸的object。
为了加快计算，当把$r_i$和$r_j$合并为$r_t$时，我们希望可以根据$r_i$和$r_j$的特征便可计算出$r_t$的特征，而不需再访问图像像素。
1.2.多样性策略（Diversification Strategies）
多样性主要体现在三方面：
- 使用不同的色彩空间。
- 不同的相似度计算方式。
- 改变初始划分区域。
接下来依次说明这三个方面。
👉第一个方面：Complementary Colour Spaces.
考虑到不同的场景和亮度。我们使用了8个色彩空间：
- RGB色彩空间。
- 灰度图像I。
- Lab色彩空间。
- rgI色彩空间。其中，r和g为RGB图像归一化后的r通道和g通道，再额外加上灰度图像I，凑成rgI三通道图像。
- HSV色彩空间。
- rgb色彩空间。即归一化后的RGB图像。
- C色彩空间。详见论文：Geusebroek, J. M., van den Boomgaard, R., Smeulders, A. W. M., & Geerts, H. (2001). Color invariance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 1338–1350.。
- HSV色彩空间的H通道。
上述8种色彩空间的不变性见表1：
其中，“+/-”表示部分不变性（“+”表示全部都有变化，“-”表示全部都没有变化）。分数，例如$\frac{1}{3}$表示三个通道中有一个通道具有不变性。表1是从亮度、阴影以及高亮三个维度来测试是否具有不变性（可以理解为：如果色彩空间变化后对这三个维度的敏感程度没有变化，即可视为不变）。从表1中可以看出，色彩空间从1到8的不变性是逐渐降低的。
算法每次执行的时候，只使用一种色彩空间。
👉第二个方面：Complementary Similarity Measures.
我们定义了四种互补的并且可以快速计算的相似性度量。相似度的值都被归一化为$[0,1]$，这也有助于不同相似度之间的组合。
$S_{colour}(r_i,r_j)$表示色彩相似度。计算色彩相似度，首先需要计算图像中每个区域的颜色直方图，例如区域$r_i$的颜色直方图为$C_i=\{ c^1_i,…,c^n_i \}$，分通道计算，每个通道的颜色直方图设置为25个bin。例如，对于三通道图像，共有$n=75$个bin。此外，对颜色直方图进行L1归一化处理（直方图相关知识请戳：链接）。
\[S_{colour}(r_i,r_j)=\sum^n_{k=1} \min (c_i^k,c_j^k) \tag{1}\]$r_i$和$r_j$合并后的区域$r_t$的颜色直方图可通过下式快速计算：
\[C_t =\frac{size(r_i) \times C_i + size(r_j) \times C_j}{size(r_i)+size(r_j)} \tag{2}\]并且有：
\[size(r_t)=size(r_i)+size(r_j)\]使用$S_{texture}(r_i,r_j)$表示纹理相似度。鉴于SIFT特征对不同材料识别的很好，因此使用类SIFT特征来度量纹理。作者计算了8个方向的高斯导数（高斯导数的讲解见本文第2部分）且有$\sigma = 1$。对于每个通道的每个高斯导数方向有计算其直方图，且设置$bin=10$。据此，我们便可得到区域$r_i$的纹理直方图$T_i = \{ t_i^1,…,t_i^n \}$。如果是三通道图像，则有$n=240$（$3 \times 10 \times 8=240$）。此外，对纹理直方图也进行了L1归一化处理。纹理相似度的计算见下：
\[S_{texture}(r_i,r_j)=\sum^n_{k=1} \min (t_i^k,t_j^k) \tag{3}\]合并区域的纹理直方图的快速计算方式和式(2)类似，在此不再赘述。
大小相似度$S_{size}(r_i,r_j)$鼓励小区域更早合并。这样能使得S中的子区域都保持差不多的大小，不至于相差太多。这也可以防止一个区域一直在吞并其他区域，以至于其他区域没有吞并别人的机会。大小相似度的计算见下：
\[S_{size}(r_i,r_j)=1-\frac{size(r_i)+size(r_j)}{size(im)} \tag{4}\]size(im)指的是图像的像素点个数。
$S_{fill}(r_i,r_j)$衡量区域$r_i$和区域$r_j$适合合并为一个区域的程度。我们用$BB_{ij}$表示可以包覆区域$r_i$和$r_j$的最小bounding box。$S_{fill}(r_i,r_j)$的计算见下：
\[fill(r_i,r_j)=1-\frac{size(BB_{ij})-size(r_i)-size(r_j)}{size(im)} \tag{5}\]这里分母为size(im)是为了和式(4)保持一致。
最终相似度S的计算：
\[S(r_i,r_j)=a_1 S_{colour}(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) \tag{6}\]这里需要注意的是，$a_i$只有0和1两种取值，作者在此处并没有考虑使用加权的方式合并这些相似度。
👉第三个方面：Complementary Starting Regions.
多样性的第三个方面体现在初始划分区域的改变。据我们所知，“Felzenszwalb and Huttenlocher (2004)”的方法是最快的，并且算法开源，划分的区域质量也比较高。作者在论文中说他找不到具有相似效率和性能的其他算法，所以其只使用了这一种划分初始区域的算法。但是不同的色彩空间会产生不同的初始划分区域。此外，作者也改变了“Felzenszwalb and Huttenlocher (2004)”方法中的阈值参数k的值。
1.3.Combining Locations
有了集合R之后，我们需要从中挑选出哪些区域是可能包含object的。作者所用的方法是将最后一次合并得到的整幅图像的权重设置为1，前一次合并得到的区域权重设置为2，这样依次类推便可得到每个区域的权重，然后将每个区域的权重乘以一个[0,1]的随机数作为该区域的得分。最后按照得分的高低筛选出最后的location。具体筛选出得分前几的区域取绝于后续的算法设置，用户可自行确定。
这种方法使得一直在被合并的区域的权重会更大一些，算法认为如果一个区域一直在被合并，则这个区域很有可能是包含object的。
2.高斯导数
一维高斯函数方程：
\[G(x)=\frac{1}{\sqrt{2\pi} \sigma}e^{-\frac{x^2}{2\sigma^2}}\]二维高斯函数方程：
\[G(x,y)=\frac{1}{2\pi \sigma^2} e^{-\frac{x^2+y^2}{2\sigma^2}}\]二维高斯函数的一阶偏导数：
\[\frac{\partial G}{\partial x}=(-\frac{1}{2\pi \sigma^4})xe^{-\frac{x^2+y^2}{2\sigma^2}}\] \[\frac{\partial G}{\partial y}=(-\frac{1}{2\pi \sigma^4})ye^{-\frac{x^2+y^2}{2\sigma^2}}\]二维高斯函数的二阶偏导数：
\[\frac{\partial ^2 G}{\partial x^2}=(-\frac{1}{2\pi \sigma^4})(1-\frac{x^2}{\sigma^2})e^{-\frac{x^2+y^2}{2\sigma^2}}\] \[\frac{\partial ^2 G}{\partial y^2}=(-\frac{1}{2\pi \sigma^4})(1-\frac{y^2}{\sigma^2})e^{-\frac{x^2+y^2}{2\sigma^2}}\] \[\frac{\partial ^2 G}{\partial x \partial y}=(\frac{xy}{2\pi \sigma^6})e^{-\frac{x^2+y^2}{2\sigma^2}}\]二维高斯函数的一阶、二阶梯度为：
\[\nabla G(x,y)=\lvert \frac{\partial G}{\partial x} \rvert + \lvert \frac{\partial G}{\partial y} \rvert\] \[\nabla ^2 G(x,y)=\frac{\partial^2 G}{\partial x^2} + \frac{\partial^2 G}{\partial y^2}\]二维高斯函数的一阶、二阶方向导数：
\[\frac{\partial G}{\partial \vec{l}}=\frac{\partial G}{\partial x} \cos \theta+\frac{\partial G}{\partial y}\sin \theta\] \[\frac{\partial^2 G}{\partial \vec{l}^2}=\frac{\partial^2 G}{\partial x^2} \cos^2 \theta +\frac{\partial^2 G}{\partial y^2} \sin^2 \theta + 2 \frac{\partial^2 G}{\partial x \partial y}\cos \theta \sin \theta\]在selective search算法的纹理相似度计算部分，个人理解应该使用的是二维高斯函数的一阶方向导数，每个像素点与周边的八个相邻像素点构成了八个方向，即$\theta = \{0°,45°,90°,135°,180°,225°,270°,315° \}$。
3.原文链接
👽Selective Search for Object Recognition
