选择性搜索-源码解析

工程结构

  1. 头文件
    1. include/segmentation.h:头文件入口
    2. include/graphsegment/:图分割算法头文件
    3. include/selectivesearch/:选择性搜索算法头文件
  2. 源文件:src文件夹
  3. 测试文件:samples/selectivesearchsegmentation_custom.cpp
├── CMakeLists.txt
├── include
│   ├── graphsegment
│   │   ├── edge.h
│   │   ├── graphsegmentation.h
│   │   ├── graphsegmentationimpl.h
│   │   ├── point_set_element.h
│   │   └── point_set.h
│   ├── segmentation.h
│   └── selectivesearch
│       ├── neighbor.h
│       ├── rect_comparator.h
│       ├── region.h
│       ├── selectivesearchsegmentation.h
│       ├── selectivesearchsegmentationimpl.h
│       ├── selective_search_segmentation_strategy_color.h
│       ├── selective_search_segmentation_strategy_color_impl.h
│       ├── selective_search_segmentation_strategy_fill.h
│       ├── selective_search_segmentation_strategy_fill_impl.h
│       ├── selective_search_segmentation_strategy.h
│       ├── selective_search_segmentation_strategy_multiple.h
│       ├── selective_search_segmentation_strategy_multiple_impl.h
│       ├── selective_search_segmentation_strategy_size.h
│       ├── selective_search_segmentation_strategy_size_impl.h
│       ├── selective_search_segmentation_strategy_texture.h
│       └── selective_search_segmentation_strategy_texture_impl.h
├── samples
│   └── selectivesearchsegmentation_custom.cpp
└── src
    ├── graphsegmentation.cpp
    ├── graphsegmentationimpl.cpp
    ├── neighbor.cpp
    ├── point_set.cpp
    ├── region.cpp
    ├── selectivesearchsegmentation.cpp
    ├── selectivesearchsegmentationimpl.cpp
    ├── selective_search_segmentation_strategy_color.cpp
    ├── selective_search_segmentation_strategy_color_impl.cpp
    ├── selective_search_segmentation_strategy_fill.cpp
    ├── selective_search_segmentation_strategy_fill_impl.cpp
    ├── selective_search_segmentation_strategy_multiple.cpp
    ├── selective_search_segmentation_strategy_multiple_impl.cpp
    ├── selective_search_segmentation_strategy_size.cpp
    ├── selective_search_segmentation_strategy_size_impl.cpp
    ├── selective_search_segmentation_strategy_texture.cpp
    └── selective_search_segmentation_strategy_texture_impl.cpp

类图

分两部分实现,首先是选择性搜索算法的全局类图,其次是选择性搜索算法的相似度计算策略

  • SelectiveSearchSegmentation声明了选择性搜索算法的公共函数
  • SelectiveSearchSegmentationImpl定义了选择性搜索算法的具体实现
  • GraphSegmentation声明了图分割算法的公共函数
  • SelectiveSearchSegmentationStrategy声明了相似度度量策略的公共函数
  • Region实现了并查集,作用于区域合并
  • Neighbor定义了相邻区域对

  • SelectiveSearchSegmentationStrategy声明了相似度度量策略的公共函数
  • SelectiveSearchSegmentationStrategyColorImpl定义了基于颜色特征的相似性度量
  • SelectiveSearchSegmentationStrategyTextureImpl定义了基于纹理特征的相似性度量
  • SelectiveSearchSegmentationStrategySizeImpl定义了基于区域大小的相似性度量
  • SelectiveSearchSegmentationStrategySizeImpl定义了基于区域形状的相似性度量
  • SelectiveSearchSegmentationStrategyMultiple声明了组合多个相似性度量策略的公共函数
  • SelectiveSearchSegmentationStrategyMultipleImpl定义了基于多特征的相似性度量计算

超参数

图分割相关:

  • k:用于计算阈值函数τ,控制两个分量之间的差异必须大于其内部差异的程度
  • \sigma:作用于高斯滤波

算法流程

根据测试代码samples/selectivesearchsegmentation.cpp,总体函数流程图如下所示

  1. 创建选择性搜索对象,输入原始图像,设置检测策略
  2. 处理图像,获取候选区域
  3. 绘制候选区域边框

第一步:预处理

分为3个步骤:

  1. 创建选择性搜索对象,使用函数createSelectiveSearchSegmentation
  2. 输入原始图像,使用函数setBaseImage
  3. 设置检测策略

创建选择性搜索对象

createSelectiveSearchSegmentation是一个辅助性函数,用于创建SelectiveSearchSegmentation对象,其返回一个SelectiveSearchSegmentation指针

输入原始图像

通过调用类SelectiveSearchSegmentation的公共函数setBaseImage载入原始图像

设置检测策略

SelectiveSearchSegmentation提供了3种检测策略:

  1. 简单计算策略switchToSingleStrategy
  2. 快速计算策略switchToSelectiveSearchFast
  3. 高质量计算策略switchToSelectiveSearchQuality
简单计算策略

函数switchToSingleStrategy仅使用单个分组

  • 颜色空间:HSV
  • 图分割超参数:k=200,sigma=0.8
  • 相似性度量:0.25*color + 0.25*texture + 0.25*size + 0.25*size
快速分组策略

函数switchToSelectiveSearchFast使用多个分组

  • 颜色空间:HSV、Lab(共2种)
  • 图分割超参数:base_k = 150,inc_k = 150,sigma = 0.8(在程序中最高k值设置为base_k + inc_k * 2,所以k取值为150/300/450,共3种)
  • 相似性度量:0.25*color + 0.25*texture + 0.25*size + 0.25*fill0.3333*fill + 0.3333*texture + 0.3333*size(共2种)

所以快速计算策略使用了2*3*2=12个分组

高质量计算策略

函数switchToSelectiveSearchQuality使用了更多的分组

  • 颜色空间:HSV、Lab、I、H、bgI(共5种)
  • 图分割超参数:base_k = 150,inc_k = 150,sigma = 0.8(在程序中最高k值设置为base_k + inc_k * 2,所以k取值为150/300/450,共3种)
  • 相似性度量:0.25*color + 0.25*texture + 0.25*size + 0.25*fill、0.3333*fill + 0.3333*texture + 0.3333*size、fill、size(共4种)

所以高质量计算策略使用了5*3*4=60个分组

第二步:区域检测

区域检测操作在类SelectiveSearchSegmentationImpl的函数process中实现,步骤如下:

  • 获取初始分割集
  • 计算分层分组区域
  • 组合所有区域并过滤重复区域

获取初始分割集

基于不同颜色空间下的图像以及基于不同图分割参数的GraphSegmentation对象,调用函数processImage获取初始分割区域

计算分层分组区域

  • 计算初始分割区域个数
  • 计算初始分割区域大小
  • 计算初始分割区域所属边框坐标
  • 计算初始分割集中的相邻区域对

基于不同的分组策略,调用函数hierarchicalGrouping进行分层分组算法

  1. 计算初始分割集中相邻区域对的相似度
  2. 基于相似度进行排序,合并相似度最高的区域对
  3. 重新计算新区域与相邻区域的相似度
  4. 重新排序,重复上述步骤,直到合并成一个区域
  5. 通过随机数和合并level重新计算每个区域的秩(rank

组合所有区域并过滤重复区域

  1. 组合所有分组区域
  2. 按秩排序
  3. 过滤重复区域

第三步:绘制候选区域边框

每次绘制10个区域,按d键增加10个,按a键减去10个,按q键退出

相似性度量

共实现了4种相似性度量方法:

  1. 颜色特征:SelectiveSearchSegmentationStrategyColorImpl
  2. 纹理特征:SelectiveSearchSegmentationStrategyTextureImpl
  3. 形状特征:SelectiveSearchSegmentationStrategyFillImpl
  4. 大小特征:SelectiveSearchSegmentationStrategySizeImpl

每种相似性度量类都继承自SelectiveSearchSegmentationStrategy,定义了相同的公共函数入口:

  1. 预处理:setImage(cv::InputArray img, cv::InputArray regions, cv::InputArray sizes, int image_id = -1)
  2. 计算相似度:get(int r1, int r2)
  3. 合并区域特征:merge(int r1, int r2)
void setImage(cv::InputArray img, cv::InputArray regions, cv::InputArray sizes, int image_id = -1)

参数解析:

  • img:不同颜色空间下的图像
  • regions:图分割算法得到的初始分割集
  • sizes:各个区域大小
  • image_id:图像编号,是否处于同一颜色空间以及同一图分割对象.用于缓存操作
float get(int r1, int r2)

输入两个区域的编号,返回相似度

void merge(int r1, int r2

合并区域r1r2