选择性搜索算法（Selective Search)

引言

计算机视觉领域有几个基本的任务：

object recognition：物体识别，即在给定的图片中辨认出其中的物体种类，例如猫，飞机，行人等。这里的输入是整个图片，输出是类别标签以及相应的概率（自信度）。
image classification = object recognition

from [https://github.com/apache/incubator-mxnet/tree/master/example/image-classification]

object detection: 物体检测，不仅要识别图片中的物体，还要定位 (localization)，即用 bounding box 将物体圈出来。如果图片中有多个物体，则每个物体都要有对应的 bounding box 和识别出的类型标签。

from https://medium.com/synapse-blog/tech-deep-dive-object-detection-ensembles-as-graph-cliques-a7f7d33b5477

object detection 的基础是 object recognition，只不过要先将图片进行分割，对每个分割之后的子图区域 region （也称为 patch）进行 object recognition.

由于事先并不知道物体在图片的哪个位置，为了避免漏检，我们应该对图片中尽量多的 region 进行搜索。理论上来说，可以有无穷多个 region。这里就需要一种 region proposal 的算法，以比较高效的方式提出图片划分 region 的方式，从而加速整个 object detection 的过程并且提高准确率。

本文将要介绍的 selective search 算法，是比较经典的，也是 R-CNN 中使用的 region proposal 算法。

参考文献：

基本思想

为了避免蛮力搜索，selective search 算法首先需要一个基于像素的图像分割。这里用的是 Felzenszwalb and Huttenlocher 算法（因为是当时速度最快的算法，而且是公开的），得到一个 oversegmented 的图像分割。例如：

oversegmented.png

这里之所以用 oversegmented 图像，是为了得到尽可能细分的区域，再以此为基础逐步合并，形成更大的区域。

image segmentation 可以用作 region proposal 的基础，每个分割的区域都可以看作一个潜在的 region，但是一个 object 往往包含了多个分割的区域，例如盛有咖啡的杯子，咖啡和杯子应该作为一个整体来看待。因此，还要根据某种相似性原则进行分割区域的合并，得到更大范围的 region。

Selective search 算法考虑了 4 种相似性度量，取值都在 [0,1] 之间，越大越相似。

颜色相似性 $s_{colour}(r_i, r_j)$
纹理相似性 $s_{texture}(r_i, r_j)$
size 相似性 $s_{size}(r_i, r_j)$ ，促使小的区域之间优先合并
shape 相似性 $s_{fill}(r_i, r_j)$ ，合并只能在紧邻的两个区域间进行，远离的两个区域不能合并

最终的相似性度量是上述四个度量的组合：
$s(r_i, r_j) = a_1\times s_{colour}(r_i, r_j) + a_2\times s_{texture}(r_i, r_j) + a_3 \times s_{size}(r_i, r_j) + a_4 \times s_{fill}(r_i, r_j)$
其中 $a_k$ 取 0 或 1.

总结起来，selective search 的算法步骤非常简单：

基于 oversegmented 得到细分的区域，作为初始的 region 集合。
计算 region 两两之间的相似性，合并具有最大相似性的两个 region，得到新的更大的 region，加入 region 集合中。
重复 step 2，直到整幅图只剩一个 region。至此，得到的 region 集合就是算法的输出。

hierarchical-segmentation-1.jpg

实例程序

环境配置：

opencv >= 3.3，本机用的 4.1.0 版本

安装 opencv-contrib-python package

pip install opencv-contrib-python --user

测试用的图片如下：

from https://people.com/pets/dog-breeds-diversity-verses-cats-breeds-explainer/

具体程序：

import sys
import cv2
 
# 读取照片，这里要根据具体情况设置路径
im = cv2.imread("./pic/cats-dogs.jpg")

# 重置图片大小，高设置为 400，保持高、宽比例
newHeight = 400
newWidth = int(im.shape[1]*400/im.shape[0])
im = cv2.resize(im, (newWidth, newHeight))    

# 创建 Selective Search Segmentation 对象
ss = cv2.ximgproc.segmentation.createSelectiveSearchSegmentation()

# 添加待处理的图片
ss.setBaseImage(im)

# 可以选择快速但是低 recall 的方式 
# 这里的 recall 指的是选择出来的 region 是否包含了所有应该包含的区域。recall 越高越好
#ss.switchToSelectiveSearchFast()

# 也可以选择慢速但是高 recall 的方式
ss.switchToSelectiveSearchQuality()


# 进行 region 划分，输出得到的 region 数目
rects = ss.process()
print('Total Number of Region Proposals: {}'.format(len(rects)))

# 设定要显示的 region 数目
numShowRects = 100

# 可以通过按键逐步增加或者减少显示的 region 数目
increment = 50

while True:
    # 不要在原图上画 bounding box，而是复制一个新图
    imOut = im.copy()

    # 遍历 regions
    for i, rect in enumerate(rects):
        # 通过 bounding box 显示出指定数量的 region
        if (i < numShowRects):
            x, y, w, h = rect  # bounding box 左上角坐标 x,y, 以及 box 的宽和高
            cv2.rectangle(imOut, (x, y), (x+w, y+h), (0, 255, 0), 1) # 绿色 box，线宽为 1
        else:
            break

    # 显示图片+bbox
    cv2.imshow("Output", imOut)

    # 接收按键输入
    k = cv2.waitKey(0) & 0xFF

    # “m” 键 is pressed
    if k == 109:
        # 增加显示的 bbox 数目
        numShowRects += increment
    # “l” 键 is pressed
    elif k == 108 and numShowRects > increment:
        # 减少显示的 bbox 数目
        numShowRects -= increment
    # “q” 键 is pressed
    elif k == 113:  
        break
# close image show window
cv2.destroyAllWindows()

最后效果如下：

regions.png

显示的 100 个 region 已经包含了我们感兴趣的待检测区域，说明了 selective search 算法的高效。

选择性搜索算法 （Selective Search)

引言

基本思想

实例程序

选择性搜索算法（Selective Search)