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

## 1. Introduction

$A=(A_1, \cdots, A_p, \cdots, A_{\lvert\mathcal{P}\rvert})$ 表示二值向量, 元素 $A_p$ 代表集合 $\mathcal{P}$ 中像素 $p$ 的一种赋值(0或1, 前景或背景), 从而 $A$ 即表示一种分割. 那么我们加在分割 $A$ 的边界和区域上的软约束可以表示为损失函数 $E(A)$ :

## 3. Segmentation Technique

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

### 3.1 Details

$% %]]>$ , 其中顶点包括图像中的像素点和两个端点(源点 $S$ 和汇点 $T$), 所以有

 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

• 在每个像素点 $p$ 上只有一条 t-link 属于 $C$
• $(p, q)\in C$ 当且仅当 $p, q$ 连接到不同的端点
• 如果 $p\in\mathcal{O}$ , 则 $(p, T)\in C$
• 如果 $p\in\mathcal{B}$ , 则 $(p, S)\in C$

## 5. Appendix*

### A. Maxflow Basic Algorithm

• Inputs Given a Network $G=(V,E)$ with flow capacity $c$, a source node $s$, and a sink node $t$ .
• Output Compute a flow f from $s$ to $t$ of maximum value
1. Residual graph $G_f(u, v)\leftarrow G(u, v)$ for all edges $(u, v)$ . $maxflow\leftarrow 0$ .
2. while there is a path $p$ from $s$ to $t$ in $G_f$ , such that $c_f(u, v)>0$ for all edges $(u, v)\in p$ :
1. Find $c_f(p)=\min[c_f(u, v): (u, v)\in p]$
2. Accumulate: $maxflow \leftarrow maxflow + c_f(p)$ .
3. Update residual graph $G_f$ . For each edge $(u, v)\in p$ :
1. $G_f(u, v)\leftarrow G_f(u, v)-c_f(p)$ (Send flow along the path)
2. $G_f(v, u) \leftarrow G_f(v, u) + c_f(p)$ (The flow might be “returned” later)
3. Get edges of the min-cut (if need):
1. Run BFS(breadth first search) from $s$ in $G_f$
2. Traversed points construct $O$ and non-traversed points construct $B$ .
4. Return $maxflow$ and $O$ and $B$ (min-cut is the edges between $O$ and $B$ in $G_f$ ).

### B. Maxflow for Energy Minimization

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

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

Graph-Cuts 示例

### C. GrabCut

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

Author: Carsten Rother, Vladimir Kolmogorov, Andrew Blake

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

GrabCut 示例

• 初始化
• 用户绘制的矩形框 $T_B$, 前景集合设为 $T_F=\emptyset$, 背景集合 $T_U=\overline{T_B}$. 对于 $n\in T_B$, 初始化 $\alpha_n=0$, 其他为 $1$.
• 前景和背景的 GMMs 分别根据 $\alpha_n$ 取值初始化.
• 迭代优化
1. Assign GMM components to pixels: for each $n$ in $T_U$,
1. Learn GMM parameters from data $\mathbf{z}$:
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.