基于图的图像分割-引言
学习R-CNN过程中发现其前期使用了选择性搜索方法进行区域提取，而在选择性搜索方法中使用了论文Efficient Graph-Based Image Segmentation提出的基于图的图像分割算法
内容列表
先导知识
基于图的图像分割算法主要运用了数据结构图的概念和最小生成树的实现（kruskal算法），并且在最小生成树的实现中运用了并查集
论文下载
算法解析
成对区域比较渭词
基于图的图像分割算法将图像解析成无向图，最开始每个像素表示一个分量，创建相邻像素之间的边集，通过不断合并分量，最终目标是图中各个分量能够表示感知上重要的组织或区域
其中的关键在于如何划分最终分量的边界，对此论文提出一个成对区域比较渭词\(D\)，通过比较分量间差异和分量内差异，判断相邻两个分量之间是否存在边界
分量内部差异定义为分量内的最大边权重
\[ Int(C) = \max_{e\in MST(C,E)} w(e) \]
分量间差异定义为连接两个分量的边的最小权重
\[ Dif(C_{1}, C_{2}) = \min_{v_{i}\in C_{1}, v_{j}\in C_{2},(v_{i},v_{j})\in E} w((v_{i}, v_{j})) \]
直观上理解，分量内像素差异应该小于分量间像素差异，所以同一分量中两个顶点之间的边应该具有相对较低的权重，而不同分量中顶点之间的边应该具有较高的权重
于此同时，渭词\(D\)还定义了一个阈值函数\(τ(C)\)
\[ τ(C) = k / |C| \]
参数\(|C|\)表示分量\(C\)的像素个数，参数\(k\)是一个参数，用于控制分量间差异必须大于最小内部差异的程度，以增强算法对于异常值的健壮性，同时能够控制最终分量的大小。\(k\)越大，最终得到的分量越大，个数越少
渭词\(D\)的算法定义如下：
\[ M Int(C_1, C_2) = min(Int(C_1) + τ(C_1), Int(C_2) + τ(C_2)). \]
\[ D(C_{1}, C_{2}) = \left\{\begin{matrix} true & if Dif(C_{1}, C_{2}) >M Int(C_{1}, C_{2})\\ false & otherwise \end{matrix}\right. \]
\(MInt\)表示两个分量中的最小内部差异，如果连接两个分量的边的最小权重大于最小内部差异，则两个分量存在边界；否则，进行分量合并
算法实现难点
如何实现成对区域比较渭词，有以下几个难点：
- 如何找到分量内的最大边权重？
- 如何找到分量间的最小边权重?
通过最小生成树的Kruskal算法实现，能够完美解决上述问题
Kruskal算法需要对边集按边权重进行升序排序，然后遍历边集进行分量合并。在遍历过程中，每次得到的边权重既是分量间的最小边权重，如果符合条件能够进行分量合并，这条边又变成了分量内的最大边权重
如何计算边权重
如何计算边权重，是后续算法的关键基础步骤。论文提出两种方式进行边权重的计算
- 网格图
- 最近邻图
网格图
将彩色图像划分为3个单色图像，分别计算各个图像，将边连接像素的绝对强度差作为边权重
\[ w((v_{i}, v_{j})) = |I(p_{i}) - I(p_{j})| \]
分别输入3个单色图像到算法中，只有各个图像中的相邻像素均属于同一分量时，才将其放置在最终分量中
最近邻图
计算彩色图像的相邻像素点之间的\(L2\)距离作为边权重
算法流程
结合论文和实际实现算法，整体算法流程如下：
- 高斯滤波，减轻异常值影响，需要设置参数
sigma - 创建无向图和边集
- 通过并查集合并分量，需要设置参数
k - 去除极小分量，需要设置参数
min_size
源码解析
研究基于图的图像分割方法过程中，作者提供了工程源码，同时OpenCV上也实现了相应功能，通过相互印证能够加快算法理解
源码工程地址：Graph Based Image Segmentation
OpenCV实现：
- 头文件
segmentation.hpp - /path/to/include/opencv4/opencv2/ximgproc/segmentation.hpp - 源文件
graphsegmentation.cpp - /path/to/opencv_contrib/modules/ximgproc/src/graphsegmentation.cpp - 实现示例
graphsegmentation_demo.cpp - /path/to/opencv_contrib/modules/ximgproc/samples/graphsegmentation_demo.cpp