Lazy Snapping

Lazy Snapping是一种基于图的图像分割方法[1]，能够将图像分割为前景和背景，通过用户交互挑选前景和背景种子，利用最大流最小分割的方法对图像进行分割。

1. 基本方法

文献中利用分水岭算法对图像进行预处理，这里我们直接将图像下采样到原分辨率的八分之一进行处理，然后求解以下优化问题：
$$
E(X)=\sum_{i\in\mathcal{V}}E_1(x_i)+\lambda\sum_{(i,j)\in\mathcal\varepsilon}E_2(x_i, x_j)
$$
其中，$E_1(x_i)$为似然能量，编码结点$x_i$的代价，$E_2(x_i,x_j)$为先验能量，代表邻接结点$x_i$和$x_j$的代价。

似然能量$E_1(x_i)$定义为：
$$
\begin{cases}
\begin{matrix}
E_1(x_i=1)=0&E_1(x_i=0)=\infty&\forall i\in\mathcal{F}
\end{matrix}\\\\
\begin{matrix}
E_1(x_i=1)=\infty&E_1(x_i=0)=0&\forall i\in\mathcal{B}
\end{matrix}\\\\
\begin{matrix}
E_1(x_i=1)=\frac{d_i^\mathcal{F}}{d_i^\mathcal{F}+d_i^\mathcal{B}}&E_1(x_i=0)=\frac{d_i^\mathcal{B}}{d_i^\mathcal{F}+d_i^\mathcal{B}}&\forall i\in\mathcal{U}
\end{matrix}
\end{cases}
$$

其中，$\mathcal{F}$表示前景种子集合，$\mathcal{B}$为背景种子集合，均由用户输入，而$\mathcal{U}$为补集。$d_i^\mathcal{F}$和$d_i^\mathcal{B}$分别表示当前颜色与前景种子平均值和背景种子平均值的距离平方

先验能量$E_2(x_i,x_j)$定义为：
$$
E_2(x_i,x_j)=\frac{1}{|C(i)-C(j)|^2+\varepsilon}
$$
实验中，取$\lambda=100$，$\epsilon=0.01$。

然后构建无向图，通过最大流最小割方法分离出前景和背景，提取轮廓得到结果

实验结果

原图像	交互图像	轮廓

参考文献

[1] Y. Li, J. Sun, C.-K. Tang, and H.-Y. Shum. Lazy snapping. ACM Transactions on Graphics (ToG), 23(3):303–308, 2004.