[Intensive Reading]目标检测(object detection)扩展系列（一） Selective Search：选择性搜索算法

小鱼儿 2021-11-02 10:48 220阅读 0赞

**目标检测系列：**  
[目标检测(object detection)系列（一） R-CNN：CNN目标检测的开山之作][object detection_ R-CNN_CNN]  
[目标检测(object detection)系列（二） SPP-Net：让卷积计算可以共享][object detection_ SPP-Net]  
[目标检测(object detection)系列（三） Fast R-CNN：end-to-end的愉快训练][object detection_ Fast R-CNN_end-to-end]  
[目标检测(object detection)系列（四） Faster R-CNN：有RPN的Fast R-CNN][object detection_ Faster R-CNN_RPN_Fast R-CNN]  
[目标检测(object detection)系列（五） YOLO：目标检测的另一种打开方式][object detection_ YOLO]  
[目标检测(object detection)系列（六） SSD：兼顾效率和准确性][object detection_ SSD]  
[目标检测(object detection)系列（七） R-FCN：位置敏感的Faster R-CNN][object detection_ R-FCN_Faster R-CNN]  
[目标检测(object detection)系列（八） YOLOv2：更好，更快，更强][object detection_ YOLOv2]  
[目标检测(object detection)系列（九） YOLOv3：取百家所长成一家之言][object detection_ YOLOv3]  
[目标检测(object detection)系列（十） FPN：用特征金字塔引入多尺度][object detection_ FPN]  
[目标检测(object detection)系列（十一） RetinaNet：one-stage检测器巅峰之作][object detection_ RetinaNet_one-stage]  
[目标检测(object detection)系列（十二） CornerNet：anchor free的开端][object detection_ CornerNet_anchor free]  
[目标检测(object detection)系列（十三） CenterNet：no Anchor，no NMS][object detection_ CenterNet_no Anchor_no NMS]  
[目标检测(object detection)系列（十四）FCOS：用图像分割处理目标检测][object detection_FCOS]

**目标检测扩展系列：**  
[目标检测(object detection)扩展系列（一） Selective Search：选择性搜索算法][object detection_ Selective Search]  
[目标检测(object detection)扩展系列（二） OHEM：在线难例挖掘][object detection_ OHEM]  
[目标检测(object detection)扩展系列（三） Faster R-CNN，YOLO，SSD，YOLOv2，YOLOv3在损失函数上的区别][object detection_ Faster R-CNN_YOLO_SSD_YOLOv2_YOLOv3]

# 简介 #

在Faster R-CNN算法之前，R-CNN，SPP-Net和Faster R-CNN这些方法中，都用到了SS（Selective Search）算法，它其实是一种区域建议算法为后续的检测任务提供候选框，SS的论文是[《Selective Search for Object Recognition》][Selective Search for Object Recognition]，即便是这篇论文自己的任务最后都是目标识别：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]  
如果我们再把时间往前推移一段，在[HOG行人检测任务][HOG]里，也在做类似的事情，只是HOG用的是滑动窗遍历，这就比较尴尬，图像中的目标总会以不同的尺寸，位置出现，滑动窗的大小和步长是个不好选择的参数，所以在RPN和one stage的检测方法没有出来的时候，类似SS的区域建议方法是个不错的选择。

# Selective Search原理 #

选择性搜索算法使用基于图的分割算法（Graph-Based Segmentation）生成初始区域，随后使用一系列的相似度判别规则决定哪些区域应该被合并到一起，再次合并后最终实现区域建议生成。

## 基于图的分割算法 ##

基于图的图像分割算法其实是一个独立经典的图像分割的方法，它更加古老，是一篇2004年的论文《Efficient Graph-Based Image Segmentation》，不过，目前直接用它做分割的应该比较少，很多算法用它作预处理过程，比如Selective Search。

**最小生成树（MST）**

基于图的分割算法将图像用加权图的形式抽象化表示，一个无向图 G G G由顶点集 V V V与边集 E E E组成，那么图 G G G可以表示为 G = ( V , E ) G=(V,E) G=(V,E)，连接一对顶点 ( V i , V j ) (V\_\{i\},V\_\{j\}) (Vi,Vj)的边 e ( V i , V j ) e(V\_\{i\},V\_\{j\}) e(Vi,Vj)具有权重 w ( V i , V j ) w(V\_\{i\},V\_\{j\}) w(Vi,Vj)，无向图指顶点间的边没有方向，下面这张图就是一个无向图的示例，其中数字表示边 E E E的权重 w w w，比如边 e ( a , b ) e(a,b) e(a,b)的权重是4 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1]  
树结构是一种特殊的图，树中的点的集合互不交叉，这意味着在图中将不存在使集合产生回路的边。上图中实线表示的边与其连接的点组成的就是一棵树。  
而最小生成树（minimun spanning tree，MST）又是一种特殊的树结构，给定需要连接的顶点，选择边的权重之和最小时的树结构就是最小生成树，我们假设上面的树结构就是最小生成树。

**分割策略**

在基于图的分割算法中，将每一个像素点做为图中一个顶点，然后将顶点逐步合并为一个区域。合并区域是以最小生成树作为依据连接，保证整个无向图中没有重叠的区域，而且每个区域的权重和都是最小的。那么在图像中，顶点间的权重应该怎么表示？  
对于一对像素点 ( a , b ) (a,b) (a,b)的边 e ( a , b ) e(a,b) e(a,b)，其权值 w ( a , b ) w(a,b) w(a,b)用两点灰度值的欧氏距离来表示，当图像为RGB三通道时，权值的公式为：  
 w ( a , b ) = ( R a − R b ) + ( G a − G b ) + ( B a − B b ) w(a,b) = \\sqrt\{(R\_\{a\}-R\_\{b\})+(G\_\{a\}-G\_\{b\})+(B\_\{a\} - B\_\{b\})\} w(a,b)=(Ra−Rb)\+(Ga−Gb)\+(Ba−Bb)  
 R a R\_\{a\} Ra表示像素点 a a a的 R R R通道的灰度值，其余的同理。权重 w ( a , b ) w(a,b) w(a,b)可以做为衡量两个像素点间差异的标准，即两点间的不相似度。两个区域间的不相似度同样依照该方法求取，对于两个区域 G 1 G\_\{1\} G1和 G 2 G\_\{2\} G2，其连接方式如下图。  
![在这里插入图片描述][2019081410083866.png]  
其中，像素点 a a a， b b b， c c c构成区域 G 1 G\_\{1\} G1，像素点 d d d， e e e， f f f构成区域 G 2 G\_\{2\} G2，图中虚线为可能使 G 1 G\_\{1\} G1和 G 2 G\_\{2\} G2合并的连接方式。根据MST定义，如果 G 1 G\_\{1\} G1和 G 2 合 并 为 一 个 区 域 ， 将 选 择 权 重 G\_\{2\} 合并为一个区域，将选择权重 G2合并为一个区域，将选择权重w(G\_\{1\},G\_\{2\}) 最 小 的 边 最小的边 最小的边e(G\_\{1\},G\_\{2\})$，定义其为类间差异  d i f f ( G 1 , G 2 ) diff(G\_\{1\},G\_\{2\}) diff(G1,G2) ，并与设定**阈值**的比较决定是否合并这两个区域。  
下面的问题就是，**阈值**是什么？  
基于图的分割算法使用一种局部自适应阈值的方式，避免了全局阈值带来的分割过细或过粗糙的问题。阈值选择为区域的类内差异 I n t ( G ) Int(G) Int(G) ：  
 I n t ( G ) = M a x ( E ) , E ∈ G Int(G)=Max(E) ,E\\in\{G\} Int(G)=Max(E),E∈G  
其中 E E E为 G G G的边集，类内差异为边集中每个边的不相似度的最大值。最终两个区域是否合并的条件是类间差异是不是小于类内差异：  
 d i f f ( G 1 , G 2 ) ≤ M i n ( I n t ( G 1 ) , I n t ( G 2 ) ) diff(G\_\{1\},G\_\{2\})\\leq Min(Int(G\_\{1\}),Int(G\_\{2\})) diff(G1,G2)≤Min(Int(G1),Int(G2))  
这样一来，就解决了两个区域是否要合并的问题，但是问题是，在一张图像开始的时候用最小生成树生成区域，它会有只剩下一个像素点的情况，这就是区域的特殊情况，一个像素点就是一个区域。单个像素点的类内差异是0，想要让上面的公式成立，就要类间的差异也是0，这显然不可能，这样一来，就会造成过分割。  
为了解决这个问题，要为每个像素点分配一个初始的类内差异 r C = k C r\_\{C\}=\\frac\{k\}\{C\} rC=Ck， C C C是像素点的个数， k k k是一个人为设定的超参数。当区域内像素点个数逐渐增多，  r C r\_\{C\} rC的作用将越来越小，而对于单个的像素点， r C = k r\_\{C\}=k rC=k将保持初始值不变。增加初始值后的类间差异为：  
 I n t ( G ) = M a x ( E ) + r C , E ∈ G Int(G)=Max(E)+r\_\{C\} ,E\\in\{G\} Int(G)=Max(E)\+rC,E∈G

## 相似度判别原理 ##

经过初始分割之后,效果就像下图中左侧最下方那张图，分割的效果过细，无法作为区域建议使用。在此基础上，SS算法根据颜色，纹理，尺寸和空间交叠率四个方面衡量区域间的相似度，对分割后的结果进行再一次的合并。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 2]

**颜色相似度**

颜色的相似度计算选用HSV颜色空间中的色调，对于RGB图像中的每个区域 G G G中单个通道的色调在bin=25的直方图上进行投票，其结果用 c i c\_\{i\} ci表示，所以三通道情况下bin=75。区域之间颜色相似度，通过归一化后直方图交叉核式子来计算：  
 S c o l o r ( G i , G j ) = ∑ k − 1 n m i n ( c i k , c j k ) S\_\{color\}(G\_\{i\},G\_\{j\})=\\sum\_\{k-1\}^\{n\}min(c\_\{i\}^\{k\},c\_\{j\}^\{k\}) Scolor(Gi,Gj)=k−1∑nmin(cik,cjk)  
**纹理相似度**

纹理相似度采用 的高斯分布在8邻域方向做梯度统计，然后每个通道的梯度方向以bins=10计算直方图，其结果用 t i t\_\{i\} ti表示，所以直方图维度为 8 × 3 × 10 = 240 8\\times3\\times10=240 8×3×10=240。最后使用与颜色相似度相同的方式计算纹理相似度：  
 S t e x t u r e ( G i , G j ) = ∑ k − 1 n m i n ( t i k , t j k ) S\_\{texture\}(G\_\{i\},G\_\{j\})=\\sum\_\{k-1\}^\{n\}min(t\_\{i\}^\{k\},t\_\{j\}^\{k\}) Stexture(Gi,Gj)=k−1∑nmin(tik,tjk)  
**尺寸相似度**

尺寸相似度采用像素面积计算，其中 s i z e i m a g e size\_\{image\} sizeimage 为整个图像的像素面积， s i z e G 1 size\_\{G\_\{1\}\} sizeG1为区域 G 1 G\_\{1\} G1的像素面积， s i z e G 2 size\_\{G\_\{2\}\} sizeG2为区域 G 2 G\_\{2\} G2的像素面积。显然当 G 1 G\_\{1\} G1与 G 2 G\_\{2\} G2都很小时，尺寸相似度趋近1，这保证了较小的区域优先合并，从而避免大区域不断合并小区域。  
 S s i z e ( G i , G j ) = 1 − s i z e G 1 + s i z e G 2 s i z e i m a g e S\_\{size\}(G\_\{i\},G\_\{j\})=1-\\frac\{size\_\{G\_\{1\}\}+size\_\{G\_\{2\}\}\}\{size\_\{image\}\} Ssize(Gi,Gj)=1−sizeimagesizeG1\+sizeG2

**空间交叠率**

交叠相似度同样采用像素面积计算，其中 s i z e B B i j size\_\{BB\_\{ij\}\} sizeBBij是区域 s i z e G i size\_\{G\_\{i\}\} sizeGi和区域 s i z e G j size\_\{G\_\{j\}\} sizeGj的最小外接矩形的像素面积。越高的重叠度意味着两个区域接触的像素点越多，两个区域占 s i z e B B i j size\_\{BB\_\{ij\}\} sizeBBij的比例就会越高，交叠相似度也就会越高，这保证了交叠度高的区域优先合并。  
 S f i l l ( G i , G j ) = 1 − s i z e B B i j − s i z e G i − s i z e G j s i z e i m a g e S\_\{fill\}(G\_\{i\},G\_\{j\})=1-\\frac\{size\_\{BB\_\{ij\}\}-size\_\{G\_\{i\}\}-size\_\{G\_\{j\}\}\}\{size\_\{image\}\} Sfill(Gi,Gj)=1−sizeimagesizeBBij−sizeGi−sizeGj

最终的相似度是上述四个相似度的加权和：  
 S ( G i , G j ) = a S c o l o r ( G i , G j ) + b S t e x t u r e ( G i , G j ) + c S s i z e ( G i , G j ) + d S f i l l ( G i , G j ) S(G\_\{i\},G\_\{j\})=aS\_\{color\}(G\_\{i\},G\_\{j\})+bS\_\{texture\}(G\_\{i\},G\_\{j\})+cS\_\{size\}(G\_\{i\},G\_\{j\})+dS\_\{fill\}(G\_\{i\},G\_\{j\}) S(Gi,Gj)=aScolor(Gi,Gj)\+bStexture(Gi,Gj)\+cSsize(Gi,Gj)\+dSfill(Gi,Gj)

## 合并候选框 ##

通过上面的相似度判别依据，接下来要逐个合并图分割生成的候选框，SS采用这样的策略：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 3]

算法：
    利用切分方法得到候选的区域集合R = {r1,r2,…,rn}
    初始化相似集合S = ϕ
    遍历邻居区域对(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 = S\s(ri,r*)
         移除rj对应的所有相似度：S = S\s(r*,rj)
         计算rt对应的相似度集合St
         S = S ∪ St
         R = R ∪ rt
    L = R中所有区域对应的边框

最终，候选框会被合并成一张图，但是每次的合并过程所对应的图层，以及它们合并时的相似度大小，都被记录下来了。这样一来就会有很多的图层，每个图层中又有若干的区域，这些区域还存在很大的重复，并且，不同的目标可能在这个图层中存在，在另一图层中又没了，所以我们需要一些策略对这些区域建议打分，最终的阈值决定将哪些区域最后输出出来。

# Selective Search效果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 4]  
上面这张图，说明了SS在多目标，多尺度，多形态下的区域建议效果，这个起码比滑动窗好多了。

[object detection_ R-CNN_CNN]: http://blog.csdn.net/chaipp0607/article/details/78112861
[object detection_ SPP-Net]: http://blog.csdn.net/chaipp0607/article/details/78446708
[object detection_ Fast R-CNN_end-to-end]: http://blog.csdn.net/chaipp0607/article/details/78458883
[object detection_ Faster R-CNN_RPN_Fast R-CNN]: http://blog.csdn.net/chaipp0607/article/details/78492328
[object detection_ YOLO]: https://zhangxu.blog.csdn.net/article/details/78535113
[object detection_ SSD]: https://zhangxu.blog.csdn.net/article/details/98962500
[object detection_ R-FCN_Faster R-CNN]: http://blog.csdn.net/chaipp0607/article/details/78525483
[object detection_ YOLOv2]: https://zhangxu.blog.csdn.net/article/details/79318396
[object detection_ YOLOv3]: https://zhangxu.blog.csdn.net/article/details/99700184
[object detection_ FPN]: https://zhangxu.blog.csdn.net/article/details/99988305
[object detection_ RetinaNet_one-stage]: https://zhangxu.blog.csdn.net/article/details/100035827
[object detection_ CornerNet_anchor free]: https://blog.csdn.net/chaipp0607/article/details/100057803
[object detection_ CenterNet_no Anchor_no NMS]: https://blog.csdn.net/chaipp0607/article/details/106991047
[object detection_FCOS]: https://zhangxu.blog.csdn.net/article/details/106991074
[object detection_ Selective Search]: https://zhangxu.blog.csdn.net/article/details/99442318
[object detection_ OHEM]: https://zhangxu.blog.csdn.net/article/details/100564629
[object detection_ Faster R-CNN_YOLO_SSD_YOLOv2_YOLOv3]: https://zhangxu.blog.csdn.net/article/details/102094625
[Selective Search for Object Recognition]: https://ivi.fnwi.uva.nl/isis/publications/2013/UijlingsIJCV2013/UijlingsIJCV2013.pdf
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: /images/20211101/39e93129c1424085940c5db5f5ef8be1.png
[HOG]: https://hal.inria.fr/file/index/docid/548512/filename/hog_cvpr2005.pdf
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1]: /images/20211101/3754b93cddaa477d915f2bb42861a4c1.png
[2019081410083866.png]: /images/20211101/b7672fcb7da84b85bb743ee4e24f9cf8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 2]: /images/20211101/aa2771ccd22d4e7fb0ab23bb74e1caaf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 3]: /images/20211101/d96f986540ef4dab98cff8e1eb1dcbea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 4]: /images/20211101/d74e4c7c8c004ce2a0c5b8f19039fe3c.png