CNN相关要点介绍（三）——选择性搜索（selective search）

忘是亡心i 2022-03-27 07:02 233阅读 0赞

# 一、目标检测 VS 目标识别 #

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

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

**选择性搜索（selective search）可以比较快速的生成候选区域**

# 二、候选区域生成主要思想 #

1.  使用一种过分割手段，将图像分割成小区域 (1k~2k 个)
2.  查看现有小区域，按照合并规则合并可能性最高的相邻两个区域。重复直到整张图像合并成一个区域位置
3.  输出所有曾经存在过的区域，所谓候选区域

# 三、算法流程 #

# ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NzY0MTI5_size_16_color_FFFFFF_t_70][] #

**输入：**彩色图片（三通道）

**输出：**物体位置的可能结果L

*  step0：获取原始分割区域集R=\{r1,r2,…,rn\}，具体过程参见论文[《Efficient Graph-Based Image Segmentation》][Efficient Graph-Based Image Segmentation]
 *  step1：初始化相似度集合S=∅
 *  step2：计算区域集R里每个相邻区域的相似度S=\{s1,s2,…\} ，将其添加到相似度集合S中
 *  step3：从相似度集合S中找出相似度最高的两个区域 ri 和rj，将其合并为新集rt。
 *  step4：从相似度集合中除去原先与ri和rj相邻区域之间计算的相似度，计算rt与其相邻区域（原先与ri或rj相邻的区域）的相似度，将其结果添加的到相似度集合S中。同时将新区域 rt 添加到区域集合R中。
 *  step5：获取每个区域的**Bounding Boxes（具体位置）**，这个结果就是物体位置的可能结果L

# 四、合并规则：多样化策略 #

其中合并规则如下： 优先合并以下四种区域：

*  颜色（颜色直方图）相近的 
 *  纹理（梯度直方图）相近的 
 *  尺寸相似度（size similarity）
 *  交叠相似度（shape compatibility measure）

## 4.1 颜色相似度（color similarity） ##

使用L1-norm归一化将色彩空间转为HSV，获取图像每个颜色通道的25 bins的直方图，这样每个区域的颜色直方图有25\*3=75个区间（维）的向量![20190112171438576.png][]。 区域之间颜色相似度通过下面的公式计算：

![20190112154254536.png][]

在区域合并过程中使用需要对新的区域进行计算其直方图，计算方法：

![SouthEast][]

## 4.2 纹理相似度（texture similarity） ##

这里的纹理采用SIFT-Like特征。具体做法是对每个颜色通道的8个不同方向计算方差σ=1的高斯微分（Gaussian Derivative），每个通道每个颜色获取10 bins的直方图（L1-norm归一化），这样就可以获取到一个8\*3\*10=240维的向量（使用RGB色彩空间），区域之间纹理相似度计算方式和颜色相似度计算方式类似，合并之后新区域的纹理特征计算方式和颜色特征计算相同：

![20190112154541849.png][]

其中，![quicklatex.com-a9283008bc26743f78b7ac5644fa42d7_l3.png][]是直方图中第![quicklatex.com-19a1201960f1c720275a7fd8ab39ea27_l3.png][]个bin的值。

## 4.3 尺寸相似度（size similarity） ##

这里的尺寸是指区域中包含像素点的个数。使用大小的相似度计算，主要是为了尽量让小的区域先合并：

![20190112154719352.png][]

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

例：设有区域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。

## 4.4 交叠相似度（shape compatibility measure） ##

这里主要是为了衡量两个区域是否更加“吻合”，其指标是合并后的区域的Bounding Box（能够框住区域的最小矩形（没有旋转））越小，其吻合度越高。其计算方式：

![20190112154831534.png][]

合并后，总面积在其BBOX中所占比例大的： 保证合并后形状规则。

![20190112153842887.png][]

## 4.5 最终的相似度 ##

上述四条规则只涉及区域的颜色直方图、梯度直方图、面积和位置。合并后的区域特征可以直接由子区域特征计算而来，即上述相似度计算方式组合到一起的式子（如下），速度较快。其中![SouthEast 1][]：

![20190112154946529.png][]

# 四、OpenCV 3.3 实现了selective search #

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

cv::ximgproc::segmentation::SelectiveSearchSegmentation

举例：

#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
        // void cv::setUseOptimized(bool onoff), Enables or disables the optimized code.
        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;
    }

参考资料：

[https://blog.csdn.net/guoyunfei20/article/details/78723646][https_blog.csdn.net_guoyunfei20_article_details_78723646]

[https://zhuanlan.zhihu.com/p/23006190?refer=xiaoleimlnote][https_zhuanlan.zhihu.com_p_23006190_refer_xiaoleimlnote]

[Selective Search for Object Recognition：][Selective Search for Object Recognition]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NzY0MTI5_size_16_color_FFFFFF_t_70]: /images/20220327/12022aa7a1114fe79f0d3326961bf495.png
[Efficient Graph-Based Image Segmentation]: http://blog.csdn.net/guoyunfei20/article/details/78727972
[20190112171438576.png]: /images/20220327/119c7bd930a34fabb34c5198c07e4be6.png
[20190112154254536.png]: /images/20220327/c676e7edd9de40f38ee45f8fcb972914.png
[SouthEast]: /images/20220327/82abfcafa6b94369b91440c9ad6276e7.png
[20190112154541849.png]: /images/20220327/79e0b631df914d4bab5e04a08195e6e8.png
[quicklatex.com-a9283008bc26743f78b7ac5644fa42d7_l3.png]: https://www.learnopencv.com/wp-content/ql-cache/quicklatex.com-a9283008bc26743f78b7ac5644fa42d7_l3.png
[quicklatex.com-19a1201960f1c720275a7fd8ab39ea27_l3.png]: https://www.learnopencv.com/wp-content/ql-cache/quicklatex.com-19a1201960f1c720275a7fd8ab39ea27_l3.png
[20190112154719352.png]: /images/20220327/280e635f64594c278f1ca00c458dc568.png
[20190112154831534.png]: /images/20220327/9a48613575fd4ee5b0ee5b7dcb826faa.png
[20190112153842887.png]: /images/20220327/9f541f1f2b694f878d11dcf5b625e593.png
[SouthEast 1]: /images/20220327/22cba84707454069a2f0322e1c30500e.png
[20190112154946529.png]: /images/20220327/5f9eedc7dfff4192b3e39c352fd94c7a.png
[https_blog.csdn.net_guoyunfei20_article_details_78723646]: https://blog.csdn.net/guoyunfei20/article/details/78723646
[https_zhuanlan.zhihu.com_p_23006190_refer_xiaoleimlnote]: https://zhuanlan.zhihu.com/p/23006190?refer=xiaoleimlnote
[Selective Search for Object Recognition]: https://blog.csdn.net/surgewong/article/details/39316931