目标检测-selective search算法

1、简介

selective search算法是应用在R-CNN中的选择性搜索算法

2、selective search算法如下

Algorithm1:Selective Search
Input:(color)image
Output:Set of object location hypotheses L
1、生成初始化区域集R
2、初始化相似集合S为空集
3、foreach (ri,rj) do #计算区域内每个相邻区域的相似度
     计算s(ri,rj)
     把s(ri,rj)合并到S里面
4、while S不等于空集的时候 do  #对S集合中相似度最高的区域进行合并为一个区域
     取出S集合中相似度最高的s(ri,ji)
     对ri，ji进行合并成为rt
     把rt加入到S中
     删除S集合中与ri有关的子集
     删除S集合中与rj有关的子集
     计算新集合与所有集和的相似度
5、跳转到步骤4，知道S为空

3、生成初始化区域集R的方法

Algorithm2:区域分割算法
Input:有n个节点和m条边的图G
Output:一系列区域集R
1、	将边按照权重值以非递减方式排序
2、	最初的分割记为S(0)，即每一个节点属于一个区域
3、	按照以下的方式由S(q-1)构造S(q)：记第q条边连接的两个节点为vi和vj，如果在S(q-1)中vi和vj是分别属于两个区域并且第q条边的权重小于两个区域的区域内间距，则合并两个区域。否则令S(q) = S(q-1)。
4、	从q=1到q=m，重复步骤2
5、	返回S（m）即为所求分割区域集合

4、区域内间距的求法：

区域内间距求取公式如下

MST为区域对应最小生成树，即区域内间距为区域对应最小生成树中权值最大的边对应的权值

5、区域间间距的求法：

区域间间距求取公式如下：

即在所有分别属于两个区域且有边链接的点对中，寻找权值最小的那对边的权值即为区域间间距（若两个区域内的点没有边相连，则定义间距为正无穷大）

6、判断两个集合是否可以合并的方法

如上公式三求取两个区域是否可以合并的结果为true表示不可合并（也即是区域间间距远大于区域内间距），fasle表示可以合并

7、图的最小生成树

（转载）https://blog.csdn.net/qq_35644234/article/details/59106779

8、区域相似度的计算（转载：https://blog.csdn.net/zizi7/article/details/70274050）

    1）颜色相似度

    将色彩空间转为HSV，每个通道下以bins=25计算直方图，这样每个区域的颜色直方图有25*3=75个区间。 

对直方图除以区域尺寸做归一化后使用下式计算相似度

可以看到，就是简单的取每个区间最小的值累加。（可以这么理解：假设两个直方图波峰和波谷高度重合，那么计算下来的值比较大；反之如果波峰和波谷错开的，那么累加的值一定比较小。因此这里提前归一化很重要）

    2）纹理相似度

论文采用方差为1的高斯分布在8个方向做梯度统计，然后将统计结果（尺寸与区域大小一致）以bins=10计算直方图。直方图区间数为8*3*10=240（使用RGB色彩空间）。

    3）空间交叠相似度

两个区域交叠越大相似度越高

def _sim_fill(r1, r2, imsize):
    """
        calculate the fill similarity over the image
    """
    bbsize = (
        (max(r1["max_x"], r2["max_x"]) - min(r1["min_x"], r2["min_x"]))
        * (max(r1["max_y"], r2["max_y"]) - min(r1["min_y"], r2["min_y"]))
    )
    return 1.0 - (bbsize - r1["size"] - r2["size"]) / imsize