本文作者：Vaibhaw Singh Chandel
本文编辑：kangsinx

在本教程中，我们将了解对象检测中一个称为“选择性搜索”的重要概念。我们还将共享C ++和Python中的OpenCV代码。

对象识别算法识别图像中存在哪些对象。它以整个图像为输入，并输出该图像中存在的对象的类别标签和类别概率。例如，类别标签可以是“狗”，并且相关的类别概率可以是97％。

另一方面，对象检测算法不仅可以告诉您图像中存在哪些对象，还可以输出边界框（x，y，宽度，高度）以指示对象在图像中的位置。

所有对象检测算法的核心是对象识别算法。假设我们训练了一个对象识别模型，该模型可以识别图像补丁中的狗。该模型将告诉您图像中是否有狗。它不会告诉对象在哪里。

为了定位对象，我们必须选择图像的子区域（补丁），然后将对象识别算法应用于这些图像补丁。对象的位置由图像块的位置给出，在这些图像块中，对象识别算法返回的类别概率很高。

image

生成较小子区域（补丁）的最直接方法是“滑动窗口”方法。但是，滑动窗口方法有几个局限性。通过称为“区域提议”算法的一类算法可以克服这些限制。选择性搜索是最受欢迎的区域提议算法之一。

在滑动窗口方法中，我们在图像上滑动一个框或窗口以选择一个补丁，并使用对象识别模型对窗口覆盖的每个图像补丁进行分类。这是对整个图像上的对象的详尽搜索。我们不仅需要搜索图像中所有可能的位置，而且还必须以不同的比例进行搜索。这是因为对象识别模型通常以特定比例（或比例范围）进行训练。这导致对成千上万个图像补丁进行分类。

问题不止于此。滑动窗口方法适用于固定长宽比的对象，例如人脸或行人。图像是3D对象的2D投影。诸如宽高比和形状之类的对象特征会根据拍摄图像的角度而显着变化。滑动窗口方法是因为当我们搜索多个长宽比时，计算量非常大。

到目前为止，我们讨论的问题都可以使用区域提议算法解决。这些方法将图像作为与图像中最有可能是对象的所有面片相对应的输入和输出边界框。这些区域提议可能是嘈杂的，重叠的，并且可能无法完美地包含对象，但是在这些区域提议之中，将存在一个非常接近图像中实际对象的提议。然后，我们可以使用对象识别模型对这些建议进行分类。具有高概率分数的区域建议是对象的位置。

image

<figcaption style="margin: 0px; padding: 0px; max-width: 100%; overflow-wrap: break-word !important; box-sizing: border-box !important;">蓝框：误报；绿箱：正面肯定</figcaption>

区域提议算法使用分割来识别图像中的预期对象。在分割中，我们基于颜色，纹理等标准将彼此相似的相邻区域分组。与滑动窗口方法不同，我们在所有像素位置和所有比例下寻找对象，而区域建议算法的工作原理是将像素分组为较少数量的细分。因此，最终生成的提案数量比滑动窗口方法少很多倍。这减少了我们必须分类的图像补丁的数量。这些生成的区域建议具有不同的比例和纵横比。

区域提议方法的重要属性是召回率很高。这只是一种奇特的说法，包含我们要查找的对象的区域必须位于区域建议列表中。为此，我们的区域提议列表可能最终会包含许多不包含任何对象的区域。换句话说，区域提议算法只要能捕获所有真实的肯定值，就可以产生很多错误的肯定值。这些误报中的大多数将被对象识别算法拒绝。当我们有更多的误报且准确性受到轻微影响时，进行检测所需的时间就会增加。但是，具有较高的召回率仍然是一个好主意，因为缺少包含实际对象的区域的选择会严重影响检测率。

已经提出了几种区域提议方法，例如

1. 客观性

2. 约束参数最小剪切，用于自动对象分割

3. 类别独立对象提案

4. 随机引物

5. 选择性搜寻

在所有这些区域提议方法中，选择性搜索是最常用的方法，因为它速度快且召回率很高。

什么是选择性搜索？

选择性搜索是在对象检测中使用的区域提议算法。它被设计为速度快，召回率很高。它基于基于颜色，纹理，大小和形状兼容性的相似区域的分层分组计算。

选择性搜索首先使用Felzenszwalb和Huttenlocher的基于图的分割方法，根据像素的强度对图像进行过分割。该算法的输出如下所示。右侧的图像包含使用纯色表示的分段区域。

image

输入图像

image

我们可以将此图像中的分割部分用作区域建议吗？答案是否定的，原因有两个：

1. 原始图像中的大多数实际对象包含2个或更多的分段部分

2. 使用此方法无法生成诸如杯子盖住的盘子或装有咖啡的杯子等被遮挡对象的区域建议

如果我们试图通过进一步合并彼此相似的相邻区域来解决第一个问题，我们将最终得到一个覆盖两个对象的分段区域。

完美的细分并不是我们的目标。我们只想预测许多区域建议，以使其中一些应该与实际对象高度重叠。

选择性搜索使用Felzenszwalb和Huttenlocher方法的过度细分作为初始种子。分割过的图像看起来像这样。

image

<figcaption style="margin: 0px; padding: 0px; max-width: 100%; overflow-wrap: break-word !important; box-sizing: border-box !important;">分割过的图像</figcaption>

选择性搜索算法将这些超细分作为初始输入并执行以下步骤

1. 将与分段零件相对应的所有边界框添加到区域投标列表中

2. 根据相似度将相邻的片段分组

3. 转到步骤1

在每次迭代中，将形成较大的细分并将其添加到区域建议列表中。因此，我们采用自下而上的方法创建了从较小细分到较大细分的区域建议。这就是我们使用Felzenszwalb和Huttenlocher的过分细分计算“分层”细分的意思。

image

图片信用

此图显示了层次分割过程的初始，中间和最后一步。

让我们更深入地研究如何计算两个区域之间的相似度。

选择性搜索基于颜色，纹理，大小和形状兼容性使用4种相似性度量。

颜色相似度

为图像的每个通道计算25个bin的颜色直方图，并将所有通道的直方图连接起来以获得颜色描述符，从而生成25×3 = 75维颜色描述符。

两个区域的颜色相似度基于直方图相交，可以计算为：

image

image

image

颜色描述符中的bin

纹理相似度

通过为每个通道在8个方向上提取高斯导数来计算纹理特征。对于每个方向和每个颜色通道，都将计算10 bin直方图，从而生成10x8x3 = 240维特征描述符。

还使用直方图相交来计算两个区域的纹理相似度。

image

image

image

纹理描述符中的bin

尺寸相似度

大小相似性鼓励较小的区域尽早合并。它可以确保在图像的所有部分形成所有比例的区域建议。如果不考虑这种相似性度量，则单个区域将使所有较小的相邻区域一一吞并，因此仅在此位置会生成多个比例的区域建议。大小相似度定义为：

image

image

是图像大小（以像素为单位）。

形状相容性

image

image

image

image

我们希望将它们合并以填补空白，如果它们甚至彼此不接触，则不应合并。

形状兼容性定义为：

image

image

image

image

。

最终相似度

两个区域之间的最终相似度定义为上述4个相似度的线性组合。

image

image

image

image

表示是否使用相似性度量。

OpenCV中的选择性搜索实现提供了成千上万个区域建议，这些建议按客观性从高到低的顺序排列。为了清楚起见，我们与在图像上方绘制的前200-250个框共享结果。一般而言，1000-1200个提案足以满足所有正确的区域提案。

image

<figcaption style="margin: 0px; padding: 0px; max-width: 100%; overflow-wrap: break-word !important; box-sizing: border-box !important;">狗：排名前250位的地区提案</figcaption>

image

<figcaption style="margin: 0px; padding: 0px; max-width: 100%; overflow-wrap: break-word !important; box-sizing: border-box !important;">早餐桌：前200个区域提案</figcaption>

让我们来看看如何使用OpenCV中实现的基于选择性搜索的细分。

选择性搜索：C ++

下面的代码是使用OpenCV进行选择性搜索的C ++教程。请通读注释以了解代码。

#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
以下代码是使用OpenCV 3.3进行选择性搜索的Python教程。请注意代码块后面提到的OpenCV 3.2的错误警报。请通读注释以了解代码。

#!/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()

错误警报： “选择性搜索”的Python绑定中存在一个错误，该错误已在此commit中修复。因此，Python代码适用于OpenCV 3.3.0，但不适用于OpenCV 3.2.0。

如果您不想编译OpenCV 3.3.0并拥有先前编译过的OpenCV 3.2.0的构建文件夹，则也可以修复此错误。
如果您查看Github提交，那只是一个很小的变化。您必须更改文件中的第239行

opencv_contrib-3.2.0 / modules / ximgproc / include / opencv2 / ximgproc / segmentation.hpp

// from
CV_WRAP virtual void process(std::vector<Rect>& rects) = 0;
// to
CV_WRAP virtual void process(CV_OUT std::vector<Rect>& rects) = 0;

现在，再次重新编译您的OpenCV 3.2.0。如果您有一个较早编译OpenCV的build文件夹，则运行make命令将仅编译此模块。

原文:
https://learnopencv.com/selective-search-for-object-detection-cpp-python/