Selective Search for Object Recognition

passbye@126.com

作者: J. R. R. Uijlings, K. E. A. van de Sande, T. Gevers, A. W. M. Smeulders.

引用: Uijlings, Jasper RR, et al. "Selective search for object recognition." International journal of computer vision 104.2 (2013): 154-171.

引用次数: 743(Google Scholar).

项目地址: http://disi.unitn.it/~uijlings/MyHomepage/index.php#page=projects1

1. 介绍

      如果想在一张图像上找到我们想要的目标(比如猫), 处理的流程一般分成两步: 第一步: 先找出可能的候选regions(有很多方法); 第二步: 从这些regions里面找出来一个region, 这个region把目标包含在内(提取特征, 然后分类). 本文所提出的selective search(下面简称SS)方法就是在第一步上(找到最可能的候选regions)上下功夫(原文表达是: This paper addresses the problem of generating possible object locations for use in object recognition). SS方法的思想是先使用图像分割的方法得到一些初始分割区域(在我看来是在图像上生成很多的超像素), 然后利用层次分组的策略(类似于层次聚类)将这些初始区域进行合并, 得到的这些区域作为目标定位的候选区域.相对于对候选区域的蛮力搜索, SS大幅度降低了搜索空间, 提高了算法速度.

      这篇文章2013年发表于IJCV, Google Scholar统计的被引用了743次. 我们要找到一张图像上特定的目标, 这个目标可以被一个矩形框圈起来, 如果我们确定了这个矩形框, 那么我们就定位到了这个目标. 但是矩形框如何确定呢? 即使是同一个目标(比如牛), 它在不同图像上, 甚至在同一张图像上的大小, 位置都是不确定的, 比如下面这张图像的两头牛, 一个距离比较近, 看起来比较大, 另一个距离比较远, 看起来比较小. 由于这种目标位置和尺度的变化性, 一般的做法就是使用穷举搜索(Exhaustive Search), 选择一个κ×ε大小的矩阵框在整张图像上进行扫描(保证不会遗漏当前尺度下的目标); 然后改变矩形框的大小(保证不同尺度的目标都可以检测到), 继续在整张图像上进行扫描. 这种方法最大的缺点就是太耗时, 于是现在研究者提出了很多其他的方法, 本文的SS就是这其中的一种.

                图1. 两头奶牛

图2. 作者论文给出的例子

      作者用图2说明了目标识别的复杂性和难度. 如果要在(a)中识别出桌子, 桌子上面同时放了很多餐具, 不同物品之间具有一定的层次关系; 我们可以利用纹理信息来识别出图(b)中的两个猫, 可以通过两只猫的颜色的不同将它们区分开来. (c)中变色龙的颜色和周围环境的颜色很相近, 通过颜色找到它并不容易, 我们需要借助纹理信息. 图(d)中的车轮和车身组成了一个不可分割的整体, 但是两者的纹理和颜色差距比较大. 因此, 如果想找到目标, 我们需要考虑图像中目标的多样性, 我们需要利用很多各式各样的策略(It‘s necessary to find a varity of diverse strategies.)(光靠纹理和颜色也是不行的)来解决这个问题.

      我们需要思考的几个问题有:

1.  穷举搜索利用不同大小的windows在图像上进行搜索, 可以适应目标所有的尺度; SS方法如何解决这个问题?(答案是利用图像分割和层次分组算法)
2.  既然单一的策略无法应对纷繁复杂的情况, SS方法的多样性策略是什么样的? (答案是: 颜色, 纹理, 大小, 区域相似度等)
3.  穷举搜索的一大诟病就是速度慢, SS方法速度怎么提高? 在哪些方面? (答案是: 速度提高了, 可以生成高质量的小候选区域集)

2. 相关工作

相关工作主要归为三个范畴: 穷举搜索(Exhaustive search)方法; 分割(Segmentation)方法; 其它方法.

2.1 穷尽搜索

      因为我们对目标的分布情况没有过多先验信息, 一般图像集上的目标也没有多少先验信息可循, 目标可以出现在任何位置, 因此一个很自然的想法就是对图像上所有的位置进行搜索. 这样做的优点是不会出现漏检, 但是缺点也是显而易见的: 计算量太大.

3. Selective Search

3.1 Selective Search by Hierarchical Grouping

 首先用一些方法在一张图像上产生很多初始的小区域(regions)-> 使用贪婪算法对这些region进行迭代分组(类似于层次聚类方法)

      比如现在有 n 个regions: R={R₁, R₂, ..., R_n}, 计算每个region与它相邻region(注意是相邻的区域)的相似度, 找出相似度最大的两个区域, 合二为一. 现在只剩下n-1 个区域, 重新计算相邻区域的相似度(只需要计算新的区域与它相邻区域的新相似度,其他的不用重复计算), 重复上面的过程, 直到只剩下1个区域(也就是所有的区域都合并了, 这借助了我们常见到的层次聚类的思想). 作者给出了算法的流程图, 如下图所示:

将这个流程图翻译成中文如下所示:

解释: 最开始的时候有n个regions, 每一次迭代区域的数据少1, 迭代n-1次之后所有的区域合成了同一个区域, 我们是不是可以设定最终区域的数目(比如L, L<n), 让算法迭代n-L次, 这样最终能够得到L个区域, 以每个区域的外接矩形框作为最终的候选区域!

3.2 多元(样)化策略(Diversification Strategies, DS)

不知道diversification strategies翻译成多元化策略是否合适,  下面简称DS. 为什么要有DS? 前面我们已经讲过, 图像千差万别, 目标形态各异, 要综合很多种不同的特征, 不同的信息才能够取得相对好的效果. 现在想想本文的SS模型有哪些地方是可以多样化的? 这里主要列举了3个方面(从头到尾):

1. 可以使用不同的区域初始化方法(因为SS算法要对初始区域进行层次合并, 因此初始区域的好坏显得比较重要);
2. 对输入图像可以采用它不同的颜色空间,提取不同的不变属性(RGB表达的图像未必是最好的,还可以利用它其他色彩空间信息).
3. 衡量两个区域之间相似度的方法(很难说哪种相似度衡量方法是最好的).

颜色空间多样化:

图像的色彩空间还是有很多的, 不同的色彩空间侧重点不同, 也考虑了图像的具体场景和光照条件. 考虑的颜色空间有(1) RGB; (2)灰度图 I; (3)Lab; (4)rgI; (5)HSV; (6)rgb(归一化后的RGB, 有区别吗???); (7)C(来自一篇论文); (8)H(来自HSV).

1 colorTypes = {‘Hsv‘, ‘Lab‘, ‘RGI‘, ‘H‘, ‘Intensity‘}; // 作者提供的Matlab代码可供选择的颜色空间

 下图是作者给出的图像单通道和多通道对于图像的阴影, 光线亮度的变化属性(也就是说有些通道对这些变化比较敏感, 有些不敏感). 比如HSV对Light intensity的不变程度是2/3, 我们看到H,S通道对Light intensity能保持不变,V对其要变化,因此HSV整体上就是2/3. 但是像a,b通道这样的局部不变性是什么意思? 这些不变性属性是如何得到的?

互补相似度测量:

作者定义了4种互补的, 可以快速计算的相似度测量方法, 这些量度的范围都在[0,1]之间. 

1. 颜色相似度(color similarity): s_color(r_i,r_j)

方法: 对于每个区域, 对其每个通道(共3通道)分别计算25bins的直方图(被归一化了), 这样, 每个区域就有25x3=75维的向量C_i={c_i¹,...,c_iⁿ}; 两个区域r_i换r_j之间的颜色相似度可以通过下面的公式计算(找到75维向量对应元素的最小值,然后加这些最小值加在一起): 

区域合并的时候, 比如r_i和r_j合并称为了r_t, 新区域r_t的颜色直方图可以用下式很方便地计算:

2. 纹理相似度(texture similarity): s_texture(r_i,r_j)

方法: 使用σ=1的高斯函数计算每个通道(共3通道)每个方向(共8个方向)上的高斯微分, 这样共可以得到24个微分图, 每个图上计算10bins的直方图(也归一化了), 这样每个区域可以得到一个维度为240的纹理直方图特征向量Ti={t_i¹,...,t_iⁿ}. 两个区域r_i换r_j之间的纹理相似度的计算和颜色相似度相同:

3. 尺寸相似度(size similarity): s_size(r_i,r_j)

 方法: 这个相似度的出发点是想让小的区域尽早地进行合并,这样可以使得没有合并的区域具有相似的大小. 两个区域r_i换r_j之间的尺寸相似度的计算如下所示:

这里, size(r_i)的表示区域r_i内像素的总数目, size(im)表示整个图像的像素总数目, 下同.

4. 填充相似度(fill similarity): fill(r_i,r_j)

方法: 这个主要是为了衡量两个区域的吻合程度, 两个区域合并后的外包Bounding Box越小, 就说明他们的吻合度越高. 如果r_i包含在了r_j里面, 逻辑上应该先将它们进行合并(为了避免any holes, 什么意思???), 另一方面, 如果r_i和r_j很难接触到, 如果将两者合并, 形成的区域可能会很奇怪. 为了计算的快速性, 这里仅用到了区域尺寸(包含像素数目)和包含这个区域的bounding box来计算. 将BB_ij定义为区域r_i和r_j合并后的Bounding Box. 公式如下:

本文最后的相似度定义为以上4种相似度的加权和:

加权值a的范围在[0-1]之间.

3.3 Combining Locations

4 Object Recognition Using Selective Search

本文目标识别模型如上图所示.

构造训练集: 

初始的正样本是标记好的目标区域(图中绿色高亮覆盖区域), 我们使用Selective Search生成很多的目标locations, 然后从中选取与与真实标记样本重合20-50%的区域作为负样本. 为了避免近似重复的负样本, 如果两个负样本之间的重合度大于70%, 则只取其中一个. 为了保证每一类的初始负样本数目小于20000(为什么?), 我们对每一类(如car, cat, dog,person)去除掉一般的样本.

测试过程:

测试的时候,由selective search产生的所有locations都要送到模型里面去预测, 分类器对每个window给出一个分数, 如果一个window和一个比它分数高的window有大于30%的重合, 那么把这个window去除(啥意思???).

参考:

[1] http://blog.csdn.net/charwing/article/details/27180421

[2] http://blog.csdn.net/mao_kun/article/details/50576003[Selective Search for Object Recognition解读]

论文阅读笔记--Selective Search for Object Recognition