CV03_06:选择性搜索算法

2020-03-19 本文已影响0人杨强AT南京

是选基于图的图像分割后，就可以使用选择性搜索算法找到目标的候选区域。本主题介绍了选择性搜索算法的原理，主要是基于OpenCV实现框架来说明，起核心是四个常规的相似度计算：颜色相似度、尺度相似度、交叠相似度、纹理相似度。可以根据特色的规则建立其他相似度：比如人脸可以选在高宽差别不大的区域等。
有了候选区域，就可以使用卷积神经网络做特征抽取，抽取的特征没有使用神经网络的分类器，标准算法中都是使用号称史上最好的分类器SVM来训练分类（请参考我们对OpenCV与Sklearn中SVM的解释）。
在老版本的OpenCV（3.4以前）采用的是级联分类，新版本提供了基于SS算法的分类目标检测训练。可以参考OpenCV的app提供的工具。

选择性搜索（Selective Search）

OpenCV的Selective Search模块使用

搜索的使用

基于质量的搜索

import cv2

# 准备一张图像
img = cv2.imread("gpu.jpeg")

# 创建SelectiveSearch对象
ss = cv2.ximgproc.segmentation.createSelectiveSearchSegmentation()

# 添加图像到处理列表
ss.setBaseImage(img)

# 初始化算法参数
ss.switchToSelectiveSearchQuality()
# int   base_k = 150,
# int   inc_k = 150,
# float sigma = 0.8f 

# ss.switchToSelectiveSearchFast()
# ss.switchToSingleStrategy()
# 所选择性搜索
rects = ss.process()

print(type(rects), rects.shape)

<class 'numpy.ndarray'> (51469, 4)

基于速度的搜索

import cv2

# 准备一张图像
img = cv2.imread("gpu.jpeg")

# 创建SelectiveSearch对象
ss = cv2.ximgproc.segmentation.createSelectiveSearchSegmentation()

# 添加图像到处理列表
ss.setBaseImage(img)

# 初始化算法参数
# ss.switchToSelectiveSearchQuality()
# int   base_k = 150,
# int   inc_k = 150,
# float sigma = 0.8f 

ss.switchToSelectiveSearchFast()
# ss.switchToSingleStrategy()
# 所选择性搜索
rects = ss.process()

print(type(rects), rects.shape)

<class 'numpy.ndarray'> (12569, 4)

单策略搜索

import cv2

# 准备一张图像
img = cv2.imread("gpu.jpeg")

# 创建SelectiveSearch对象
ss = cv2.ximgproc.segmentation.createSelectiveSearchSegmentation()

# 添加图像到处理列表
ss.setBaseImage(img)

# 初始化算法参数
# ss.switchToSelectiveSearchQuality()
# int   base_k = 150,
# int   inc_k = 150,
# float sigma = 0.8f 

# ss.switchToSelectiveSearchFast()
ss.switchToSingleStrategy()
# 所选择性搜索
rects = ss.process()

print(type(rects), rects.shape)

<class 'numpy.ndarray'> (2750, 4)

基于颜色、交叠、尺度、纹理的搜索策略

SelectiveSearchSegmentationStrategyColor

import cv2
# 基于颜色策略的搜索
ssc = cv2.ximgproc.segmentation.createSelectiveSearchSegmentationStrategyColor()
# 基于填充的策略
ssf = cv2.ximgproc.segmentation.createSelectiveSearchSegmentationStrategyFill()


img = cv2.imread("gpu.jpeg")
ss = cv2.ximgproc.segmentation.createSelectiveSearchSegmentation()
ss.clearStrategies()
ss.addStrategy(ssc)      ## 不用设置，下面几个方法意境是比较成熟的策略方案了，看源代码了解
ss.addStrategy(ssf)
ss.addImage(img)
ss.setBaseImage(img)
# ss.switchToSingleStrategy()
ss.switchToSelectiveSearchFast()
rects = ss.process()

print(type(rects), rects.shape)

<class 'numpy.ndarray'> (12569, 4)

OpenCV实现说明

上述只是一个演示，实际OpenCV的策略都是内部使用。下面是源代码实现的说明

策略类

一共四个策略类：颜色相似度，填充（Fill：就是交叠的意思）相似，纹理相似度，尺度相似合并策略。这类列出类的声明。


    class SelectiveSearchSegmentationStrategyColorImpl CV_FINAL : public SelectiveSearchSegmentationStrategyColor {
        public:
            SelectiveSearchSegmentationStrategyColorImpl() {
                name_ = "SelectiveSearchSegmentationStrategyColor";
                last_image_id = -1;
            }

            virtual void setImage(InputArray img, InputArray regions, InputArray sizes, int image_id = -1) CV_OVERRIDE;
            virtual float get(int r1, int r2) CV_OVERRIDE;
            virtual void merge(int r1, int r2) CV_OVERRIDE;

        private:
            String name_;

            Mat histograms; // [Region X Histogram]
            Mat sizes;
            int histogram_size;

            int last_image_id; // If the image_id is not equal to -1 and the same as the previous call for setImage, computations are used again
            Mat last_histograms;
    };

switchToSingleStrategy函数实现

其他几个函数类似，只是策略使用不同。
- 不同策略产生不同输出，可以阅读参考代码，直接判定出计算的快慢。
  - switchToSelectiveSearchFast（中等）
  - switchToSingleStrategy（最快）
  - switchToSelectiveSearchQuality（最慢）


    void SelectiveSearchSegmentationImpl::switchToSingleStrategy(int k, float sigma) {
        clearImages();
        clearGraphSegmentations();
        clearStrategies();

        Mat hsv;
        cvtColor(base_image, hsv, COLOR_BGR2HSV);
        addImage(hsv);

        Ptr<GraphSegmentation> gs = createGraphSegmentation();
        gs->setK((float)k);
        gs->setSigma(sigma);
        addGraphSegmentation(gs);

        Ptr<SelectiveSearchSegmentationStrategyColor> color = createSelectiveSearchSegmentationStrategyColor();
        Ptr<SelectiveSearchSegmentationStrategyFill> fill = createSelectiveSearchSegmentationStrategyFill();
        Ptr<SelectiveSearchSegmentationStrategyTexture> texture = createSelectiveSearchSegmentationStrategyTexture();
        Ptr<SelectiveSearchSegmentationStrategySize> size = createSelectiveSearchSegmentationStrategySize();

        Ptr<SelectiveSearchSegmentationStrategyMultiple> m = createSelectiveSearchSegmentationStrategyMultiple(color, fill, texture, size);

        addStrategy(m);

    }

process的实现


void SelectiveSearchSegmentationImpl::process(std::vector<Rect>& rects) {

    std::vector<Region> all_regions;

    int image_id = 0;

    for(std::vector<Mat>::iterator image = images.begin(); image != images.end(); ++image) {
        for(std::vector<Ptr<GraphSegmentation> >::iterator gs = segmentations.begin(); gs != segmentations.end(); ++gs) {

            Mat img_regions;
            Mat_<char> is_neighbour;
            Mat_<int> sizes;

            // Compute initial segmentation
            (*gs)->processImage(*image, img_regions);

            // Get number of regions
            double min, max;
            minMaxLoc(img_regions, &min, &max);
            int nb_segs = (int)max + 1;

            // Compute bouding rects and neighbours
            std::vector<Rect> bounding_rects;
            bounding_rects.resize(nb_segs);

            std::vector<std::vector<cv::Point> > points;

            points.resize(nb_segs);

            is_neighbour = Mat::zeros(nb_segs, nb_segs, CV_8UC1);
            sizes = Mat::zeros(nb_segs, 1, CV_32SC1);

            const int* previous_p = NULL;

            for (int i = 0; i < (int)img_regions.rows; i++) {
                const int* p = img_regions.ptr<int>(i);

                for (int j = 0; j < (int)img_regions.cols; j++) {

                    points[p[j]].push_back(cv::Point(j, i));
                    sizes.at<int>(p[j], 0) = sizes.at<int>(p[j], 0) + 1;

                    if (i > 0 && j > 0) {

                        is_neighbour.at<char>(p[j], p[j - 1]) = 1;
                        is_neighbour.at<char>(p[j], previous_p[j]) = 1;
                        is_neighbour.at<char>(p[j], previous_p[j - 1]) = 1;

                        is_neighbour.at<char>(p[j - 1], p[j]) = 1;
                        is_neighbour.at<char>(previous_p[j], p[j]) = 1;
                        is_neighbour.at<char>(previous_p[j - 1], p[j]) = 1;
                    }
                }
                previous_p = p;
            }

            for(int seg = 0; seg < nb_segs; seg++) {
                bounding_rects[seg] = cv::boundingRect(points[seg]);
            }

            for(std::vector<Ptr<SelectiveSearchSegmentationStrategy> >::iterator strategy = strategies.begin(); strategy != strategies.end(); ++strategy) {
                std::vector<Region> regions;
                hierarchicalGrouping(*image, *strategy, img_regions, is_neighbour, sizes, nb_segs, bounding_rects, regions, image_id);

                for(std::vector<Region>::iterator region = regions.begin(); region != regions.end(); ++region) {
                    all_regions.push_back(*region);
                }
            }

            image_id++;
        }
    }

    std::sort(all_regions.begin(), all_regions.end());

    std::map<Rect, char, rectComparator> processed_rect;

    rects.clear();

    // Remove duplicate in rect list
    for(std::vector<Region>::iterator region = all_regions.begin(); region != all_regions.end(); ++region) {
        if (processed_rect.find((*region).bounding_box) == processed_rect.end()) {
            processed_rect[(*region).bounding_box] = true;
            rects.push_back((*region).bounding_box);
        }
    }

}

通过参考上面代码大致可以可以自己手撸代码！

SelectiveSearch算法的相似度计算公式

颜色相似度

将色彩空间转为HSV，每个通道下以bins=25计算直方图，这样每个区域的颜色直方图有 $25*3=75$ 个区间。对直方图除以区域尺寸做归一化后使用下式计算相似度：
- $S_{color}(r_i,r_j) = \sum \limits _{k=1} ^{n} \min(c_i ^k, c_j ^k)$
上面 $n=75$ , 理解这个公式的意义：
- 假设每一个颜色通道的直方图累加和为1.0(归一化后的值)，三个通道的累加和就为3.0，如果区域 $c_i$ 和区域 $c_j$ 直方图完全一样，则此时颜色相似度最大为3.0，如果不一样，由于累加取两个区域bin的最小值进行累加，当直方图差距越大，累加的和就会越小，即颜色相似度越小。

纹理相似度

论文采用方差为1的高斯分布在8个方向做梯度统计，然后将统计结果（尺寸与区域大小一致）以bins=10计算直方图。直方图区间数为8310=240（使用RGB色彩空间），纹理相似度计算方式和颜色相似度计算方式类似：
- $S_{texture}(r_i,r_j) = \sum \limits _{k=1} ^{n} \min(t_i ^k, t_j ^k)$
8个方向的梯度就是SIFT-Like特征。

尺寸相似度

保证合并操作的尺度较为均匀，避免一个大区域陆续“吃掉”其他小区域。计算公式使用区域大小：
- $S_{size}(r_i,r_j) = 1- \dfrac{size(r_i) + size(r_j)}{size(im)}$
im是两个区域合并的区域，如果是包含区域，则相似度为0.这时候是不合并的。

交叠相似度

两个区域的重叠度
- $S_{fill}(r_i,r_j) = 1- \dfrac{size(BB_{ij}) - size(r_i) - size(r_j)}{size(im)}$
BBij是合并后的区域的Bounding Box（能够框住区域的最小矩形BBij）越小
- 合并区域的外接矩阵。

最终相似度

$S(r_i,r_j) = S_{color}(r_i,r_j) + S_{texture}(r_i,r_j) + S_{size}(r_i,r_j) + S_{fill}(r_i,r_j)$
按照相似度合并区域即可。

附录

其他候选区域生成算法：
1. Objectness(需要权限)
  - 地址：http://groups.inf.ed.ac.uk/calvin/objectness/
2. Constrained Parametric Min-Cuts for Automatic Object Segmentation
  - 地址：http://www.maths.lth.se/sminchisescu/
3. Category Independent Object Proposals
  - 地址：http://vision.cs.uiuc.edu/proposals/
4. Selective Search
  - 地址：https://www.koen.me/research/selectivesearch/

CV03_06:选择性搜索算法

选择性搜索（Selective Search）

OpenCV的Selective Search模块使用

搜索的使用

基于颜色、交叠、尺度、纹理的搜索策略

OpenCV实现说明

策略类

switchToSingleStrategy函数实现

process的实现

SelectiveSearch算法的相似度计算公式

颜色相似度

纹理相似度

尺寸相似度

交叠相似度

最终相似度

附录

猜你喜欢

热点阅读