目标检测之 Selective Search

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

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


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


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

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

Selective Search

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

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

简单来说，假设知道一个待识别的物体左上角顶点处于（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，本身就包含了多层次的关系。

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

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

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

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

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

• 颜色相似度
• 纹理相似度，这里使用了 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 写的真是溜。