选择性搜索算法(Selective Search)超详解(通俗易懂版)

简介: 选择性搜索算法(Selective Search)超详解(通俗易懂版)

0.引言


近几年来,目标检测算法取得了很大的突破。比较流行的算法可以分为两类:

  1. 一类是基于Region Proposal(区域推荐)的R-CNN系算法(R-CNN,Fast R-CNN, Faster R-CNN等),这些算法需要two-stage,即需要先算法产生目标候选框,也就是目标位置,然后再对候选框做分类与回归。
  2. 而另一类是Yolo,SSD这类one-stage算法,其仅仅使用一个卷积神经网络CNN直接预测不同目标的类别与位置。

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

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

示例如下:

image.png

image.png

1. Selective Search(SS)


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


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


 先来看一组图片:

image.png

  1. 图 a ,物体之间可能存在层级关系,比如:碗里有个勺;
  2. 图 b,我们可以用颜色来分开两只猫,却没法用纹理来区分;
  3. 图 c,我们可以用纹理来区分变色龙,却没法用颜色来区分;
  4. 图 d,轮胎是车的一部分,不是因为它们颜色相近、纹理相近,而是因为轮胎包含在车上。

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

1.1 SS的策略

  1. 我们没法事先得知物体的大小,在传统方法中需要用不同尺寸的矩形框检测物体,防止遗漏。而 Selective Search 采用了一种具备层次结构的算法来解决这个问题;
  2. 检测的时间复杂度可能会很高。Selective Search 遵循简单即是美的原则,只负责快速地生成可能是物体的区域,而不做具体的检测;
  3. 另外,结合上一节提出的,采用多种先验知识来对各个区域进行简单的判别,避免一些无用的搜索,提高速度和精度。

1.2 算法流程


image.png

1.3 具体过程解释


image.png

2. 相似度计算方法:


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


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


2.1 颜色相似度


image.png


2.2 纹理相似度Stexture(ri,rj)S_{texture}(r_i,r_j)Stexture(ri,rj)


image.png

2.3 尺度相似度S s i z e ( r i , r j ) S_{size}(r_i,r_j)


 优先合并小的区域,如果仅仅是通过颜色和纹理特征合并的话,很容易使得合并后的区域不断吞并周围的区域,后果就是多尺度只应用在了那个局部,而不是全局的多尺度。因此我们给小的区域更多的权重,这样保证在图像每个位置都是多尺度的在合并。

image.png

2.4 填充相似度


image.png

2.5 相似度计算公式


image.png

3. 代码实现:


%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)算法

第三十三节,目标检测之选择性搜索-Selective Search

相关文章
|
3月前
|
算法
【算法】二分算法——搜索插入位置
【算法】二分算法——搜索插入位置
|
12天前
|
算法 搜索推荐 数据库
二分搜索:高效的查找算法
【10月更文挑战第29天】通过对二分搜索的深入研究和应用,我们可以不断挖掘其潜力,为各种复杂问题提供高效的解决方案。相信在未来的科技发展中,二分搜索将继续发挥着重要的作用,为我们的生活和工作带来更多的便利和创新。
20 1
|
1月前
|
算法 决策智能
基于禁忌搜索算法的VRP问题求解matlab仿真,带GUI界面,可设置参数
该程序基于禁忌搜索算法求解车辆路径问题(VRP),使用MATLAB2022a版本实现,并带有GUI界面。用户可通过界面设置参数并查看结果。禁忌搜索算法通过迭代改进当前解,并利用记忆机制避免陷入局部最优。程序包含初始化、定义邻域结构、设置禁忌列表等步骤,最终输出最优路径和相关数据图表。
|
2月前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
在数据密集型应用中,高效搜索算法至关重要。Trie树(前缀树/字典树)通过优化字符串处理和搜索效率成为理想选择。本文通过Python实战演示Trie树构建与应用,显著提升搜索性能。Trie树利用公共前缀减少查询时间,支持快速插入、删除和搜索。以下为简单示例代码,展示如何构建及使用Trie树进行搜索与前缀匹配,适用于自动补全、拼写检查等场景,助力提升应用性能与用户体验。
54 2
|
1月前
|
存储 算法 C++
【搜索算法】 跳马问题(C/C++)
【搜索算法】 跳马问题(C/C++)
|
1月前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)
|
3月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
39 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
3月前
|
机器学习/深度学习 算法 文件存储
【博士每天一篇文献-算法】 PNN网络启发的神经网络结构搜索算法Progressive neural architecture search
本文提出了一种名为渐进式神经架构搜索(Progressive Neural Architecture Search, PNAS)的方法,它使用顺序模型优化策略和替代模型来逐步搜索并优化卷积神经网络结构,从而提高了搜索效率并减少了训练成本。
55 9
|
3月前
|
算法
【算法】递归、搜索与回溯——汉诺塔
【算法】递归、搜索与回溯——汉诺塔
|
3月前
|
算法
【算法】递归、搜索与回溯——简介
【算法】递归、搜索与回溯——简介