Graph Cut 最常用的应用为图像前景、背景分割，本文记录其在图像去噪的应用思路。

简介

• Graph Cut 的核心是设置合理的能量函数，将能量函数映射到图模型中，依照最大流最小割算法寻找节点能量最小的二分类结果。
• 在去噪应用中，也是类似的路数，只是框架仍在二分类中，只能解决二分类的去噪问题。

问题描述

• 待去噪的二值图像 $Y$:

• 图像中噪声很多，我们想要保持图像信息、同时图像尽量平滑。
• 假设完成去噪的图像 $X$，需要像 $Y$ ，又要平滑:

• 如果像素数量为 $n$，那么总共的解空间大小为 $2^n$， NP Hard。

能量函数

• 那么对于任意 $X$ 图像，可以据此设计能量函数 $E$:

$$
E(X)=\sum_{v \in V} \lambda\left|Y_{v}-X_{v}\right|+\sum_{(u, v) \in N_E} \kappa\left|X_{u}-X_{v}\right|
$$

• 其中 $V$ 为所有像素，$Ne$ 为相邻像素
• 可以理解 $ E$ 为损失函数，前半部分表示和原始图像 $Y$ 接近，后半部分表示相邻像素接近
• $\lambda, \kappa$ 为系数，我们的目标是找到使得 $E$ 最小的 $X$。

Graph Cut

• 我们以一维数据为例，假设有如下数据 $Y$:

• 那么在这种情况下，我们期望的数据 $X$ 是如下的样子：

• Graph Cut 该如何完成该去噪任务呢，首先建立图模型：

• 当 $K<\lambda<2K$ 时，便可以得到我们想要的最小割：

• 也就完成了在一维数据下的去噪任务。
• 在 2D 图像数据下，情况类似，只是相邻像素边连接复杂一些：

• 二分类仍然由 $S,T$ 节点率领：

• 设置能量函数与使用最大流最小割算法求解的思路是一致的。

参考资料

• https://zhuanlan.zhihu.com/p/557410313
• http://www.f.waseda.jp/hfs/PSIVT2009.pdf

文章链接：
https://www.zywvvd.com/notes/study/image-processing/graph-cut/graph-cut-denoise/graph-cut-denoise/