选择性搜索(SS)算法

    Selective Search(选择性搜索)基于Graph-Based图像分割,是RCNN和Fast RCNN的区域推荐算法。SS算法由IJCV 2012的论文<Selective Search for Object Recognition>Uijlings,et.提出的。

    近几年来,目标检测算法取得了很大的突破。比较流行的算法可以分为两类,一类是基于Region Proposal(区域推荐)的R-CNN系算法(R-CNN,Fast R-CNN, Faster R-CNN等),这些算法需要two-stage,需要先算法产生目标候选框,也就是目标位置,然后再对候选框做分类与回归。而另一类是Yolo,SSD这类one-stage算法,其仅仅使用一个卷积神经网络CNN直接预测不同目标的类别与位置。

    也就是说,对于Two-stage来说,需要先Region Proposal。RCNN和Fast RCNN选用的就是SS算法来产生推荐的区域,之后two-stage模型改用RPN网络。


Graph-Based图像分割

    原理[https://blog.csdn.net/surgewong/article/details/39008861]

    python实现[https://blog.csdn.net/u014796085/article/details/83449972]

    论文和代码[http://cs.brown.edu/people/pfelzens/segment/]

    基于图表示的图像分割方法由论文<Graph Based Image Segmentation>是2004年由Felzenszwalb发表在IJCV上的一篇文章,主要介绍了一种基于图表示(graph-based)的图像分割方法。图像分割(Image Segmentation)的主要目的也就是将图像(image)分割成若干个特定的、具有独特性质的区域(region),然后从中提取出感兴趣的目标(object)。

    示例如下:

1.jpg

2.jpg


Selective Search(SS)

    在two-stage目标检测算法中,一般先要产生候选区域(region proposal)。一般可以在图片上使用穷举法或者滑动窗口选出所有物体可能出现的区域框,对这些区域框提取特征并进行使用图像识别分类方法,得到所有分类成功的区域后,通过非极大值抑制输出结果。

    在图片上使用穷举法或者滑动窗口选出所有物体可能出现的区域框,就是在原始图片上进行不同尺度不同大小的滑窗,获取每个可能的位置。而这样做的缺点也显而易见,复杂度太高,产生了很多的冗余候选区域,而且由于不可能每个尺度都兼顾到,因此得到的目标位置也不可能那么准,在现实当中不可行。而选择性搜索有效地去除冗余候选区域,使得计算量大大的减小。

    先来看一组图片:

3.png

    图 a ,物体之间可能存在层级关系,比如:碗里有个勺;

    图 b,我们可以用颜色来分开两只猫,却没法用纹理来区分;

    图 c,我们可以用纹理来区分变色龙,却没法用颜色来区分;

    图 d,轮胎是车的一部分,不是因为它们颜色相近、纹理相近,而是因为轮胎包含在车上。

    最常规也是最简单粗暴的方法,就是用不同尺寸的矩形框,一行一行地扫描整张图像,通过提取矩形框内的特征判断是否是待检测物体。但是这种方法的复杂度极高,所以又被称为 exhaustive search。在人脸识别中,由于使用了 Haar 特征,因此可以借助 Paul Viola 和 Michael Jones 提出的积分图,使检测在常规时间内完成。但并不是每种特征都适用于积分图,尤其在神经网络中,积分图这种动态规划的思路就没什么作用了。

    SS的策略是:

    1.我们没法事先得知物体的大小,在传统方法中需要用不同尺寸的矩形框检测物体,防止遗漏。而 Selective Search 采用了一种具备层次结构的算法来解决这个问题;

    2.检测的时间复杂度可能会很高。Selective Search 遵循简单即是美的原则,只负责快速地生成可能是物体的区域,而不做具体的检测;

    3.另外,结合上一节提出的,采用多种先验知识来对各个区域进行简单的判别,避免一些无用的搜索,提高速度和精度。

算法流程:

4.png

翻译一下:

    输入:彩色图片。

    输出:物体可能的位置,即是很多的矩形坐标。

    首先,我们使用Graph-Based图像分割将图片初始化为很多小区域 R=ri,…,rn。

    初始化一个相似集合为空集: S=∅。

    计算所有相邻区域之间的相似度(相似度函数后面列出来),放入集合 S 中,集合 S 保存的是区域对以及它们之间的相似度。

    找出 S 中相似度最高的区域对,将它们合并,并从 S 中删除与它们相关的所有相似度和区域对。重新计算这个新区域与周围区域的相似度,放入集合 S 中,并将这个新合并的区域放入集合 R 中。重复这个步骤直到 S 为空。

    从 R 中找出所有区域的 bounding box(即包围该区域的最小矩形框),这些 box 就是物体可能的区域。

    另外,为了提高速度,新合并区域的 feature 可以通过之前的两个区域获得,而不必重新遍历新区域的像素点进行计算。这个 feature 会被用于计算相似度。


相似度计算方法

    相似度计算方法将直接影响合并区域的顺序,进而影响到检测结果的好坏。论文中比较了八种颜色空间的特点,在实际操作中,只选择一个颜色空间(比如:RGB 空间)进行计算。

    正如一开始提出的那样,我们需要综合多种信息来判断。作者将相似度度量公式分为四个子公式,称为互补相似度测量(Complementary Similarity Measures) 。这四个子公式的值都被归一化到区间 [0, 1] 内。

5.png

6.png

7.png

8.png

9.png

10.png


代码实现

    Python代码已经有别人实现了,就不重复造轮子了。项目Github:github:https://github.com/AlpacaDB/selectivesearch 。

代码测试:

%matplotlib inline
from keras.preprocessing import image
import skimage.data
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import selectivesearch
import numpy as np
import cv2

# 加载图片数据
#img = skimage.data.checkerboard() 
img_path =r'D:\CV\datasets\mypic\2.png'
img = image.load_img(img_path, target_size=(480, 600))#(h,w)
img = image.img_to_array(img)
img=img.astype('uint8')

img_lbl, regions = selectivesearch.selective_search(img, scale=500, sigma=0.9, min_size=20)

#计算一共分割了多少个原始候选区域
temp = set()
for i in range(img_lbl.shape[0]):
    for j in range(img_lbl.shape[1]):    
        temp.add(img_lbl[i,j,3]) 
print(len(temp))

print(len(regions))#计算利用Selective Search算法得到了多少个候选区域

#创建一个集合 元素list(左上角x,左上角y,宽,高)
candidates = set()
for r in regions:
    if r['rect'] in candidates:#排除重复的候选区
        continue
    if r['size'] < 500:#排除小于 2000 pixels的候选区域(并不是bounding box中的区域大小)  
        continue
    x, y, w, h = r['rect']
    if w / h > 2 or h / w > 2: #排除扭曲的候选区域边框  即只保留近似正方形的
        continue
    candidates.add(r['rect'])
    
for x, y, w, h in candidates:
    #print(x, y, w, h)
    cv2.rectangle(img, (x, y), ( x+w,y+h), (0, 0, 255), 1) 
    
plt.figure(figsize=(12,10))
plt.imshow(img)
plt.axis('off')
plt.savefig('ss.png')
plt.show()

测试结果:

ss.png


参考文献

[1][博客园:大奥特曼打小怪兽]

[2][Jermmy]


上一篇:
下一篇:

首页 所有文章 机器人 计算机视觉 自然语言处理 机器学习 编程随笔 关于