Jarvis' Blog 成功的路上并不拥挤, 因为坚持的人不多

Graph Cuts for Segmentation

2019-05-01
Jarvis
Post

Update: 2019-05-12

Title: Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Object in N-D Images

Author: Yuri Y. Boykov, Marie-Pierre Jolly

本文是基于 Graph-Cuts 进行自然图像/医学图像分割的一篇奠基之作, 许多常用的图割方法(如 GrabCut)是基于本文而设计的. 本文的两名作者均来自于西门子公司研究中心.

1. Introduction

图割法是计算机视觉领域分割任务常用的方法. 本文提出了交互式图割法, 同时结合软约束(soft constraint)硬约束(hard constraint)明确地定义损失函数, 并得到全局最优解.

考虑任意一个点的集合 和点对的集合

表示二值向量, 元素 代表集合 中像素 的一种赋值(0或1, 前景或背景), 从而 即表示一种分割. 那么我们加在分割 的边界和区域上的软约束可以表示为损失函数 :

其中

区域项 表示给像素 赋以”前景”或”背景”的惩罚, 边界项 表示对像素 取值不连续性的惩罚, 取值越接近则 越大, 反之越小.

2. Graph Cuts and Computer Vision

无向图 定义为一族顶点 和连接这些点的边 . 每条边 都被赋予非负的权重(损失) . 我们引入两个特殊的顶点称为端点(terminals), 他们和图中所有其他点相连, 但彼此不直接相连. 一个割(cut)是边集的一个子集 使得图中的两个端点被分离开 . 在组合优化中我们一般把割的损失定义为边上损失的和

图割法求解优化目标(最小割)的方法是使用最大流最小割定理, 即求解最小割等价于求解最大流. 另外, 有两个端点的图的最小割有更高效的(低阶)多项式时间算法求解.

3. Segmentation Technique

假设 表示已经被用户标记为”(目标)object”和”(背景)background”像素的集合, 那么有 并且 . 我们的目标是计算公式(2)满足硬约束

的全局最优解. 从图像构建图如下图所示.

A simple 2D segmentation example for a 3x3 image.

3.1 Details

, 其中顶点包括图像中的像素点和两个端点(源点 和汇点 ), 所以有

边集包括两种类型的边: (1) n-links (neighborhood links) 和 t-links (terminal links). 每个像素点 都关联了边 . 集合 中的邻居像素 都关联了一条 n-link. 所以有

为了清晰, 我们把不同类型边的权重列在下面的表格中

edge weight(cost) for
$$ (p, q) $$ $$ B_{(p, q)} $$ $$ (p, q)\in\mathcal{N} $$
$$ \{p, S\} $$ $$ \lambda\cdot R_p(\text{"bkg"}) $$ $$ p\in\mathcal{P},\;p\notin\mathcal{O}\cup\mathcal{B} $$
$$ K $$ $$ p\in\mathcal{O} $$
$$ 0 $$ $$ p\in\mathcal{B} $$
$$ \{p, T\} $$ $$ \lambda\cdot R_p(\text{"obj"}) $$ $$ p\in\mathcal{P}, \;p\notin\mathcal{O}\cup\mathcal{B} $$
$$ 0 $$ $$ p\in\mathcal{O} $$
$$ K $$ $$ p\in\mathcal{B} $$

其中

3.2 Min-Cut

我们想要的最小割 应该满足以下条件:

  • 在每个像素点 上只有一条 t-link 属于
  • 当且仅当 连接到不同的端点
  • 如果 , 则
  • 如果 , 则

4. Examples

从用户标记的像素中提取直方图作为密度分布的先验 . 那么区域惩罚可以写为

而边界惩罚使用 ad-hoc 函数

注意: 在 2D 图像中使用 8-neighborhood, 在 3D 图像中使用 26-neighborhood.

5. Appendix*

网络流问题: 给定一个网络图和两个端点(源点s和汇点t), 每条边有一定的容量, 计算从s到t的最大流量.

A. Maxflow Basic Algorithm

基础算法 - Ford Fulkerson 算法:

  • Inputs Given a Network with flow capacity , a source node , and a sink node .
  • Output Compute a flow f from to of maximum value
    1. Residual graph for all edges . .
    2. while there is a path from to in , such that for all edges :
      1. Find
      2. Accumulate: .
      3. Update residual graph . For each edge :
        1. (Send flow along the path)
        2. (The flow might be “returned” later)
    3. Get edges of the min-cut (if need):
      1. Run BFS(breadth first search) from in
      2. Traversed points construct and non-traversed points construct .
    4. Return and and (min-cut is the edges between and in ).

B. Maxflow for Energy Minimization

Title: An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision

Author: Yuri Boykov, Vladimir Kolmogorov

改进算法: 维护两个不重叠的搜索树 , 它们的根分别是源 和汇 , 同时满足 树的父节点到子节点的边流量不满(nonsaturated), 树的子节点到父节点流量不满. 不在树中的其他节点为”自由节点”. 树节点分为激活的(active)和抑制的(passive, 暂且叫成抑制的吧). 激活的节点可以继续扩展新的子节点(从相邻的自由节点中选择, 2D 为8相邻, 3D为26相邻), 抑制的节点没有相邻的自由节点可扩展.

如图所示:

Example of the search tree S(read nodes) and T(blue nodes) at the end of the growth stage when a path(yellow line) from the source s to the sink t is found. Active and passive nodes are labeled by letters A and P, correspondingly. Free nodes appear in black.

算法流程:

  • “增长(growth)”阶段: 搜索树 增长, 直到两棵树”接触”到从而产生一条 路径.
    • 为了简便, 记树从根到叶方向的边为正向边, 从叶到根方向的边为反向边
  • “增广(augmentation)”阶段: 增广上一步找到的路径, 搜索树均变为森林.
    1. 寻找”瓶颈”容量
    2. 增广: (1) 更新残差图(residual graph): 树的正向边(根->叶)容量减少 , 反向边(叶->根)容量增加 ; 树做相反的增减(对于流图来说是做了相同方向的增减). (2) 打断流图满容量的正向边, 并把该边的头节点加入孤儿(orphan)列表.
      • 注意: 的正向边是流图“从源到汇”的正向边, 树的反向边是流图“从源到汇”的正向边.
  • “应用(adoption)”阶段: restore树 .
    • 依次处理孤儿列表中的节点
      1. 寻找一个新的父节点 , 父节点要满足三个条件: (1)边 容量不满, (2)父子来自于同一棵树(孤儿则考虑其原来的父亲来自于哪棵树), (3)父节点的”origin”为 .
      2. 如果找到了多个可行的父节点, 则选择离 最近的那个
      3. 如果找到了新的父节点 , 则把 设为 新的父节点; 如果没找到, 则把 恢复为自由节点, 并做以下操作
        • 扫描 的所有同一棵树上的邻居 , 如果边 容量不满, 则把 设为激活节点; 如果 的父节点是 , 则把 添加到孤儿列表.
        • 从激活节点列表中移除.
  • 以上三步循环直到没有新的激活节点.

技术报告和实现源码(第三方): Code

示例图片:

Graph-Cuts 示例

C. GrabCut

Title: “GrabCut” – Interactive Foreground Extraction using Iterated Graph Cuts

Author: Carsten Rother, Vladimir Kolmogorov, Andrew Blake

GrabCut 是 OpenCV 中标准的交互式图割算法.

本文基于文献[1], 为了简化交互负担, 允许用户开始只需要用矩形框框出目标物体即可. 在某些图像上可以达到和用户使用画笔涂抹一样甚至更好的效果. 此外, GrabCut 还允许用户在对风格结果不满意时进一步使用 Graph Cuts 的交互方式补全. 同时 GrabCut 支持彩色图像的分割. GrabCut 的分割例子如图所示.

GrabCut 示例

文献[1]中的能量函数中region项使用用户涂抹区域的密度分布的对数建模, 而本文 GrabCut 则使用两个有 个成分的高斯混合模型(Gaussian Mixture Model, GMM)分别对前景和背景进行建模. 为了方便优化, 增加一个向量 , 其中 是赋予每一个像素的一个 GMM 成分. 从而能量函数 中的 region 项 变为

其中 表示 GMM 分布函数的对数, 此处不再展开. 表示不透明度 (取值于0和1), 决定了一个像素属于前景还是背景.

算法流程:

  • 初始化
    • 用户绘制的矩形框 , 前景集合设为 , 背景集合 . 对于 , 初始化 , 其他为 .
    • 前景和背景的 GMMs 分别根据 取值初始化.
  • 迭代优化
    1. Assign GMM components to pixels: for each in ,
    1. Learn GMM parameters from data :
    1. Estimate segmentation: use min cut to solve:
    1. Repeat from step 1, until convergence.
    2. Apply border matting.

(未完待续…)

6. References

  1. Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Object in N-D Images
    Yuri Y. Boykov, Marie-Pierre Jolly.
    [link]. In ICCV, 2001.

  2. An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision
    Yuri Boykov, Vladimir Kolmogorov.
    [link]. In TPAMI 2004.

  3. “GrabCut” – Interactive Foreground Extraction using Iterated Graph Cuts
    Carsten Rother, Vladimir Kolmogorov, Andrew Blake
    [link]. ACM TOG, 2004


Content