图分割-算法解析

参考

基于图的图像分割-引言

[译]高效的基于图的图像分割

基于图的图像分割-工程源码

基于图的图像分割-OpenCV源码

原理解析

算法利用图操作进行分割,将图像转换成图G=(V, E),每个结点(v_{i}\in V)表示一个像素点,每条无向边((v_{i}, v_{j})\in E)表示一个相邻像素对,将图像分割的过程转换成图分量合并的过程

通过定义一个成对区域比较谓词D名字比较拗口,就是一种合并标准),评估相邻两个分量(图像的两个区域)是否存在边界(是否需要合并

如何定义初始分量集

初始情况下,每个像素点表示一个分量

如何生成无向边集

论文实现和OpenCV实现中使用固定几个方向的相邻像素对作为无向边:

  1. 论文实现:创建当前顶点和右上、右中、右下和中下顶点之间的无向边
  2. OpenCV实现:创建当前顶点和上/下/左/右顶点的无向边(存在重复边,后续会处理

如何保存不同分量

使用Kruskal算法创建最小生成树保存不同分量

如何判断两个像素点是否属于同一个分量

使用并查集进行搜索

如何定义成对区域比较谓词

将分量内部差异定义为分量C的最小生成树MST(C,E)中的最大权重

Int(C) = \max_{e\in MST(C,E)} w(e)

将分量间(C_{1}, C_{2})的差异定义为连接两个分量的边的最小权重

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_{1}, C_{2}) = \left\{\begin{matrix} true & if Dif(C_{1}, C_{2}) >M Int(C_{1}, C_{2})\\ false & otherwise \end{matrix}\right.

其中最小内部差异M Int定义如下,

M Int(C_1, C_2) = min(Int(C_1) + τ(C_1), Int(C_2) + τ(C_2)).

额外设置了一个阈值函数τ,用于控制两个分量之间的差异必须大于其内部差异的程度

τ(C) = k / |C|

其中|C|表示分量C的大小(像素个数),k是超参数,值越大,那么更多的小分量会被合并,最终得到更大的分割区域

边权重函数

论文提供了两种边权重函数:

  • 一是网络图(Grid Graph)模式,计算边连接像素之间的绝对强度差作为边权重函数
    • 需要将彩色图像分割成单个通道图像,分别进行分割。只有两个相邻像素在这3个颜色平面上都属于同一分量时,才最终将其放置在同一分量中
  • 二是最近邻图(Nearest Neighbor Graph)模式,计算点之间的L2(欧几里得)距离作为边权重

算法解析

流程

实现算法如下:

  1. 从图像中提取初始分量集V和边集E
  2. 按边权重递增排序边集Eπ = (o_1 , . . . , o_m )
  3. 从分割S_{0}开始,此时每个顶点v_i都表示一个分量
  4. 对于q=1,...,m,重复第5
  5. 给定S^{q-1},按如下方式构造S^{q}v_{i}v_{j}表示按序第q个条边的顶点,比如o_{q}=(v_{i}, v_{j})。如果v_{i}v_{j}S^{q-1}的不同分量中,并且w(o_q)比这两个分量各自的内部差异还小,那么合并这两个分量,否则不做任何事。更正式地说,C_{i}^{q-1}S^{q-1}中包含v_{i}的分量,C_{j}^{q-1}是包含v_{j}的分量。如果C_{i}^{q-1} \neq C_{j}^{q-1}并且w(o_{q}) ≤ M Int(C_{i}^{q−1} , C_{j}^{q−1}),那么通过合并C_{i}^{q-1}C_{j}^{q-1},从S^{q-1}中得到S^{q}。否则S^{q} = S^{q-1}
  6. 返回S=S^{m}

遍历完按权重值递增排序的边集后,就能够完成图像分割

优点

  • 算法运行时间与图像边缘数呈线性关系,在实际运行中速度很快
  • 在低变率图像区域(低频区域)保留细节,在高变率图像区域(高频区域)忽略细节