目标检测之 Selective Search


最近因为工作上的事,搞了一点非常基础目标检测相关的东西。正好在学习之余梳理了下之前自己认知错误的一些地方,记录一下。

起因


之前对于目标检测的了解停留于深度学习部分,比如 Fast-RCNN / Faster-RCNN / Yolo 等等,对于候选框域搜索算法主要还是对于 RPN 的认知。


但是这次在工作中了解到了 Selective Search 的概念,没想到在小样本训练的过程中精度也不错,性能还很好,哈哈。因此决定深入研究下。Selective Search 从大类上也可以属于 Region Proposal 的思想,但是主要的思想却是来源于传统的图像处理。


相关的论文发表于 IJCV 2013 《Selective Search for Object Detection》,大家可自行阅读获取更多细节。

主要还是学习目的,业界主流的还是采用 Faster-RCNN 的做法。


目标检测问题相对来说比图像分类复杂点,因为一般情况下要同时检测出多个子物体的位置(及可能需要的分类目的)。最原始的做法就是对于一张图像的每个可能位置都进行搜索,但是这里会产生一个两个互相增加复杂度的问题?

  • 我们要识别的物体在哪?我们要识别的物体大小是多少?长宽比要不要考虑?


简单来说,假设知道一个待识别的物体左上角顶点处于(x, y),那么长和宽分别设置多少呢?设置小了,可能没有办法得到正确要识别的物体;设置大了,可能又把要分开区分的两个或多个物体合在了一起。


因此,这种传统的做法产生的搜索空间基本可以认为是无穷尽的。


那么自然而然地,我们的优化的想法肯定是减少搜索空间的大小!怎么做呢?


答案说难也不难,就是只找哪些可能是物体的区域。从区域这个维度进行搜索,而不是全图像的像素级查询。

全图搜索绝大多数的搜索像素包含区域是不包含物体的,实质上是浪费,可以通过如下两张图进行直观对比。








基于此,作者首先利用图像分割的想法,来获取可能是物体的区域;当然,这种层次的分割肯定不准


进一步地,考虑掉物体之间诸如包含等关系,通过
合并的方式来构建层次化**的潜在物体区域。


所以整篇论文的核心就可以归纳为如下的数学公式:



  • 通过图像分割算法得到初始区域集合 R = {r1, ….. rn},这个很容易理解吧,就是图像分割。
  • 设定一个相似集合 S,初始为
  • 对于初始区域集合相邻中的每一对(ri, rj),计算相似度(下文会说如何计算相似度),得到 s(ri, rj),将其加入之前的相似集合 S 中。
  • 当 S 不为空的时候,从 S 中获取相似度最大的一对 s(ri, rj),将这两个 ri, rj 区域合并,称为 rt。
  • 把所有和 ri, rj 相关的相似度对都从 S 中移除掉。(ri, rj 已经不存在了,变身为 rt)
  • 把新得到的 rt,在分别和其邻区域的 rx 们,计算相似度对,存入 S 中。
  • 把 rt 加入到区域集合 R 中。
  • 重复步骤,知道合并到最后只有一个区域了(即 S 为空)。


这个时候,R 集合中的所有区域,就是通过 Selective Search 得到的候选框区域。


值得注意的是,这种计算方式得到的 R,本身就包含了多层次的关系。

如何合并


前面我们提到了,我们初始的待定区域是基于图像分割得到的一批候选集,但是这些候选集的质量还比较“糙”,粒度也不一定对,需要合并甚至多次合并来处理一下。因此,如何合并也是一个相对值得思考的问题。

截屏2020-04-07上午12.33.29.png

上两张图不难看出,初始化的图像分割对于目标检测来说是不能直接使用的。


其实这篇文章,作者也坦诚道:图片的样式千变万化,某些图片里面可行的方案到了另外一些图片中就不适用了。 因此,作者采用了多种方案混合的合并方法。

  • 比如,背景色大块区域和前景色不同的主体可以很明显区分。
  • 比如,材质 / 纹理等也可以比较明显区分出待检测的物体。
  • 比如,形状和大小也可以做为检测手段区分待检测物体。


有了这些可以参考的思路,作者设计了四合一的合并公式。

  • 颜色相似度
  • 纹理相似度,这里使用了 SIFT 算法。
  • 小区域合并优先级度。这里解释下,作者为了避免出现“大鱼吃小鱼”的现象,即一块区域不断膨胀,吞并周围区域,所以采用了尽量将小区域先分别合并,始终保持大小类似的方式。
  • 距离。如果区域ri包含在rj内,毫无疑问应该立刻合并,另一方面,如果ri很难与rj相接,不应该合并在一块。这里定义区域的合适度距离主要是为了衡量两个区域是否更加“吻合”,其指标是合并后的区域的Bounding Box(能够框住区域的最小矩形BBij)越小,其吻合度越高。

Selective Search 代码理解


读顶尖学术会议论文的好处就是一般对应的代码都会开源,即使论文读的云里雾里,但是只要能大致理解思路,配合源代码深入分析,总是能懂。


这篇论文对应的代码开源在Selective Search,代码总计也就 300+ 行(当然有些非核心代码直接依赖了库),很容易理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def selective_search(
im_orig, scale=1.0, sigma=0.8, min_size=50):
'''Selective Search

assert im_orig.shape[2] == 3, "3ch image is expected"

# load image and get smallest regions
# region label is stored in the 4th value of each pixel [r,g,b,(region)]


1】图像分割
img = _generate_segments(im_orig, scale, sigma, min_size)

if img is None:
return None, {}


2】获取对象总大小
imsize = img.shape[0] * img.shape[1]

3】获取初始集合
R = _extract_regions(img)

# extract neighbouring information

4】计算相邻的区域
neighbours = _extract_neighbours(R)

5】计算初始化的相邻区域相似度
S = {}
for (ai, ar), (bi, br) in neighbours:
S[(ai, bi)] = _calc_sim(ar, br, imsize)


6】就是之前我们说的搜索过程
# hierarchal search
while S != {}:

# get highest similarity
i, j = sorted(S.items(), key=lambda i: i[1])[-1][0]

# merge corresponding regions
t = max(R.keys()) + 1.0
R[t] = _merge_regions(R[i], R[j])

# mark similarities for regions to be removed
key_to_delete = []
for k, v in list(S.items()):
if (i in k) or (j in k):
key_to_delete.append(k)

# remove old similarities of related regions
for k in key_to_delete:
del S[k]

# calculate similarity set with the new region
for k in [a for a in key_to_delete if a != (i, j)]:
n = k[1] if k[0] in (i, j) else k[0]
S[(t, n)] = _calc_sim(R[t], R[n], imsize)

regions = []
for k, r in list(R.items()):
regions.append({
'rect': (
r['min_x'], r['min_y'],
r['max_x'] - r['min_x'], r['max_y'] - r['min_y']),
'size': r['size'],
'labels': r['labels']
})

return img, regions

  • 第一步,通过经典的图像分割算法获取分割的块。这一步留到后续研究 felzenszwalb 算法再说吧,暂时我也不会。
  • 其实第一步已经得到对应的区域了,但是在算法实现上只是做了一个个标记,所以还需要处理下,变成我们需要的 R 集合。这步里面已经做好了大量的计算处理,后续直接按照论文层级化调用就行。
  • 计算相邻的区域,对应产生初始的 S 集合。
  • 对相邻的区域计算最大相似度,然后合并。
  • 后面就重复我上问的内容了。


大致内容就这样,当然细节还有不少值得研究的,可以继续深入,后续再读读。


最后,作者这 Python 写的真是溜。