选择性搜索（selective search）

Posted on | read numbers

该文翻译整理自：selective search for object detection（c++ / python）

一、目标检测 VS 目标识别

目标识别（objec recognition）是指明一幅输入图像中包含那类目标。其输入为一幅图像，输出是该图像中的目标属于哪个类别（class probability）。而目标检测（object detection）除了要告诉输入图像中包含了哪类目标外，还要框出该目标的具体位置（bounding boxes）。

在目标检测时，为了定位到目标的具体位置，通常会把图像分成许多子块（sub-regions / patches），然后把子块作为输入，送到目标识别的模型中。分子块的最直接方法是滑动窗口法（sliding window approach）。滑动窗口的方法就是按照子块的大小在整幅图像上穷举所有子图像块。这种方法产生的数据量想想都头大。和滑动窗口法相对的是另外一类基于区域（region proposal）的方法。selective search就是其中之一！

二、region proposal 方法

当前的区域候选方法有如下几种：

在所有的区域候选方法中，因为其快速、recall较高的特点，selective search是最常被使用的（尽管从FASTER-RCNN的时代开始人们几乎都改用RPN而不再用它，但在RCNN、FAST-RCNN论文中，第一步均使用该方法生成候选框）

三、selective search算法

选择性搜索是一种用于对象检测的区域提案算法。它的设计是为了快速的召回。它基于基于颜色、纹理、大小和形状兼容性的类似区域的分层分组。
选择性搜索首先是通过Felzenszwalb和Huttenlocher的基于图形的分割方法对图像的强度进行过度细分。该算法的输出如下所示。
图２
图3
我们可以在这个图像中使用分段的部分作为区域的提议吗？答案是否定的，我们不能这样做有两个原因：

  • 原始图像中的大多数实际对象包含两个或多个分段部分
  • 对于被遮挡的物体，如杯子所覆盖的盘子或装满咖啡的杯子的Region proposals不能用这种方法产生

如果我们试图通过进一步合并相邻的区域来解决第一个问题，我们最终会得到一个包含两个对象的分段区域。
完美的分割不是我们的目标。我们只是想预测多个区域提议，以至于其中一些应该与实际的对象有非常高的重叠。
selective search(选择性搜索)使用从Felzenszwalb和Huttenlocher的方法作为初始种子。一个过分割的图像看起来像这样。
图４

选择性搜索算法将这些过分割作为初始输入，主要执行三个步骤:将与分割部分对应的所有边界框添加到区域提案列表中、基于相似性将不同分割组进行连接、返回执行第１步

伪代码和具体流程如下：
图１

  • step0：生成区域集R，具体参见论文《Efficient Graph-Based Image Segmentation》
  • step1：计算区域集R里每个相邻区域的相似度S={s1,s2,…}
  • step2：找出相似度最高的两个区域，将其合并为新集，添加进R
  • step3：从S中移除所有与step2中有关的子集
  • step4：计算新集与所有子集的相似度
  • step5：跳至step2，直至S为空

在每次迭代中，都会形成更大的部分并添加到区域提案列表中。因此，我们通过自下而上的方法，从较小的部分到更大的部分，创建区域提案。

图５
上面这张图显示了有层次的分割过程（hierarchical segmentation）的初始、中间和最后一步。

四、相似度计算

颜色相似度（color similarity）

将色彩空间转为HSV，每个通道下以bins=25计算直方图，这样每个区域的颜色直方图有25*3=75个区间。 对直方图除以区域尺寸做归一化后使用下式计算相似度：
图６

纹理相似度（texture similarity）

论文采用方差为1的高斯分布在8个方向做梯度统计，然后将统计结果（尺寸与区域大小一致）以bins=10计算直方图。直方图区间数为8310=240（使用RGB色彩空间）。
图7
其中，$t_i^k$是直方图中第$k_{th}$个bin的值。

尺寸相似度（size similarity）

图８
保证合并操作的尺度较为均匀，避免一个大区域陆续“吃掉”其他小区域。

例：设有区域a-b-c-d-e-f-g-h。较好的合并方式是：ab-cd-ef-gh -> abcd-efgh -> abcdefgh。 不好的合并方法是：ab-c-d-e-f-g-h ->abcd-e-f-g-h ->abcdef-gh -> abcdefgh。

形状相容相似度（shape compatibility measure）

图9
形状相容性测量两个区域（$r_i$和$r_j$）彼此适配的程度。如果$r_i$ fits $r_j$，我们希望将它们合并以填充间隙，如果它们不相互接触，它们就不应该合并。

最终的相似度

图11
这里$r_i$和 $r_j$是一幅图的两个区域或者分割部分， $a_i∈0, 1$ 决定了某个相似性指数是否应该合并。

在OpenCV的contrib模块中实现了selective search算法。类定义为：

cv::ximgproc::segmentation::SelectiveSearchSegmentation

Opencv中的ss接口，根据候选框中有物体的概率给出了候选框的降序排列，为了清晰，我们通常选择200-250个候选框绘制在图片中来距离，事实上，通常1000-1200个候选框就足够得到所有正确的region proposals（区域提案）。
图12

代码示例(运行环境：OpenCV3.４ + contrib)：
C++

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include "opencv2/ximgproc/segmentation.hpp"
#include "opencv2/highgui.hpp"
#include "opencv2/core.hpp"
#include "opencv2/imgproc.hpp"
#include <iostream>
#include <ctime>
 
using namespace cv;
using namespace cv::ximgproc::segmentation;
 
static void help() {
    std::cout << std::endl <<
    "Usage:" << std::endl <<
    "./ssearch input_image (f|q)" << std::endl <<
    "f=fast, q=quality" << std::endl <<
    "Use l to display less rects, m to display more rects, q to quit" << std::endl;
}
 
 
int main(int argc, char** argv) {
    // If image path and f/q is not passed as command
    // line arguments, quit and display help message
    if (argc < 3) {
        help();
        return -1;
    }
 
    // speed-up using multithreads
    setUseOptimized(true);
    setNumThreads(4);
 
    // read image
    Mat im = imread(argv[1]);
    // resize image
    int newHeight = 200;
    int newWidth = im.cols*newHeight/im.rows;
    resize(im, im, Size(newWidth, newHeight));
 
    // create Selective Search Segmentation Object using default parameters
    Ptr<SelectiveSearchSegmentation> ss = createSelectiveSearchSegmentation();
    // set input image on which we will run segmentation
    ss->setBaseImage(im);
 
    // Switch to fast but low recall Selective Search method
    if (argv[2][0] == 'f') {
        ss->switchToSelectiveSearchFast();
    }
    // Switch to high recall but slow Selective Search method
    else if (argv[2][0] == 'q') {
        ss->switchToSelectiveSearchQuality();
    } 
    // if argument is neither f nor q print help message
    else {
        help();
        return -2;
    }
 
    // run selective search segmentation on input image
    std::vector<Rect> rects;
    ss->process(rects);
    std::cout << "Total Number of Region Proposals: " << rects.size() << std::endl;
 
    // number of region proposals to show
    int numShowRects = 100;
    // increment to increase/decrease total number
    // of reason proposals to be shown
    int increment = 50;
 
    while(1) {
        // create a copy of original image
        Mat imOut = im.clone();
 
        // itereate over all the region proposals
        for(int i = 0; i < rects.size(); i++) {
            if (i < numShowRects) {
                rectangle(imOut, rects[i], Scalar(0, 255, 0));
            }
            else {
                break;
            }
        }
 
        // show output
        imshow("Output", imOut);
 
        // record key press
        int k = waitKey();
 
        // m is pressed
        if (k == 109) {
            // increase total number of rectangles to show by increment
            numShowRects += increment;
        }
        // l is pressed
        else if (k == 108 && numShowRects > increment) {
            // decrease total number of rectangles to show by increment
            numShowRects -= increment;
        }
        // q is pressed
        else if (k == 113) {
            break;
        }
    }
    return 0;
}

Python

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

#!/usr/bin/env python
'''
Usage:
    ./ssearch.py input_image (f|q)
    f=fast, q=quality
Use "l" to display less rects, 'm' to display more rects, "q" to quit.
'''
 
import sys
import cv2
 
if __name__ == '__main__':
    # If image path and f/q is not passed as command
    # line arguments, quit and display help message
    if len(sys.argv) < 3:
        print(__doc__)
        sys.exit(1)
 
    # speed-up using multithreads
    cv2.setUseOptimized(True);
    cv2.setNumThreads(4);
 
    # read image
    im = cv2.imread(sys.argv[1])
    # resize image
    newHeight = 200
    newWidth = int(im.shape[1]*200/im.shape[0])
    im = cv2.resize(im, (newWidth, newHeight))    
 
    # create Selective Search Segmentation Object using default parameters
    ss = cv2.ximgproc.segmentation.createSelectiveSearchSegmentation()
 
    # set input image on which we will run segmentation
    ss.setBaseImage(im)
 
    # Switch to fast but low recall Selective Search method
    if (sys.argv[2] == 'f'):
        ss.switchToSelectiveSearchFast()
 
    # Switch to high recall but slow Selective Search method
    elif (sys.argv[2] == 'q'):
        ss.switchToSelectiveSearchQuality()
    # if argument is neither f nor q print help message
    else:
        print(__doc__)
        sys.exit(1)
 
    # run selective search segmentation on input image
    rects = ss.process()
    print('Total Number of Region Proposals: {}'.format(len(rects)))
     
    # number of region proposals to show
    numShowRects = 100
    # increment to increase/decrease total number
    # of reason proposals to be shown
    increment = 50
 
    while True:
        # create a copy of original image
        imOut = im.copy()
 
        # itereate over all the region proposals
        for i, rect in enumerate(rects):
            # draw rectangle for region proposal till numShowRects
            if (i < numShowRects):
                x, y, w, h = rect
                cv2.rectangle(imOut, (x, y), (x+w, y+h), (0, 255, 0), 1, cv2.LINE_AA)
            else:
                break
 
        # show output
        cv2.imshow("Output", imOut)
 
        # record key press
        k = cv2.waitKey(0) & 0xFF
 
        # m is pressed
        if k == 109:
            # increase total number of rectangles to show by increment
            numShowRects += increment
        # l is pressed
        elif k == 108 and numShowRects > increment:
            # decrease total number of rectangles to show by increment
            numShowRects -= increment
        # q is pressed
        elif k == 113:
            break
    # close image show window
    cv2.destroyAllWindows()