Poisson Image Editing

poisson

1. 问题描述

给定以下两幅图：

girl

sea

现我们需要将第一幅图中的女孩搬到第二幅图的海水中，为使得复制粘贴更加逼真自然，我们需要设计算法来满足我们两幅图像融合的需要

2. 算法描述

Poisson Image Editing算法[1]的基本思想是在尽可能保持原图像内部梯度的前提下，让粘贴后图像的边界值与新的背景图相同，以实现无缝粘贴的效果。从数学上讲，对于原图像$f(x,y)$，新背景$f^*(x,y)$和嵌入新背景后的新图像$v(x,y)$，等价于解最优化问题：
$$
\min\limits_f \iint \Omega |\nabla f-\boldsymbol v |^2 \ \ \mathrm{with}\ f|{\partial \Omega}=f^*|_{\partial \Omega}
$$
利用变分法，令$F=|\nabla f-\boldsymbol v |^2=(\nabla f_x-\boldsymbol v_x)^2+(\nabla f_y-\boldsymbol v_y)^2$

代入欧拉-拉格朗日方程：
$$
F_f-\frac{\mathrm d}{\mathrm d x}F_{f_x}-\frac{\mathrm d}{\mathrm d y}F_{f_y}=0
$$
由于$F$是关于$\nabla f$的函数，因此$F_f=0$

所以有：
$$
\begin{align}
&\frac{\partial F}{\partial f}=\frac{\mathrm d}{\mathrm dx}\left[\frac{\partial F}{\partial(\nabla f_x-\pmb v_x)^2}\right]+\frac{\mathrm d}{\mathrm dy}\left[\frac{\partial F}{\partial(\nabla f_y-\pmb v_y)^2}\right]\\\\
&\Rightarrow 0=\frac{\mathrm d}{\mathrm dx}[2(\nabla f_x-\pmb v_x)]+
\frac{\mathrm d}{\mathrm dy}[2(\nabla f_y-\pmb v_y)]\\\\
&\Rightarrow 0=\left(\frac{\partial ^2f}{\partial x^2}-\frac{\partial \pmb v}{\partial x}\right)+\left(\frac{\partial ^2f}{\partial y^2}-\frac{\partial \pmb v}{\partial y}\right)\\\\
&\Rightarrow \Delta f=\mathrm{div}\pmb v
\end{align}
$$
可转化为具有Dirichlet边界条件的Poisson方程：

$$
\Delta f= \mathrm{div} \boldsymbol v\ \ \mathrm{over}\ \Omega\ \ \mathrm{with} \ \ f|_{\partial \Omega}=f^\ast|_{\partial\Omega}
$$

以第一幅图和第二幅图为例，将图1中需要复制的区域设为$S$，定义$N_p$为$S$中的每一个像素$p$四个方向连接邻域，令$<p,q>$为满足$q\in N_p$的像素对。边界$\Omega$定义为$\partial \Omega ={p\in S\setminus \Omega: N_p \cap \Omega \neq \emptyset }$，设$f_p$为$p$处的像素值$f$，目标即求解像素值集$f|_\Omega ={f_p,p\in \Omega}$

利用Poisson Image Editing算法的基本原理，上述问题转化为求解最优化问题：
$$
\min\limits_{f|\Omega}\sum\limits{<p,q>\cap \Omega\neq \emptyset}(f_p-f_q-v_{pq})^2,\mathrm{with}\ f_p=f_p^*,\forall\ p\in \partial\Omega

$$
化为求解线性方程组：
$$
\forall\ p\in \Omega,\ |N_p|f_p-\sum\limits_{q\in N_p\cap \Omega} f_q=\sum\limits_{q\in N_p\cap \partial \Omega}f_p^*+\sum\limits_{q\in N_p}v_{pq}
$$
对于梯度场$\boldsymbol{v}(\boldsymbol{x})$的选择，文献[1]给出两种方法，一种是完全使用前景图像的内部梯度，即：
$$
\forall\ <p,q>,v_{pq}=g_p-g_q
$$
另一种是使用混合梯度：
$$
\forall\ \boldsymbol{x}\in \Omega,\ \boldsymbol{v}(\boldsymbol{x})=\begin{cases}
\nabla f^*(\boldsymbol{x})&\mathrm{if}\ |\nabla f^*(\boldsymbol{x})>|\nabla g(\boldsymbol{x})|,\\\\
\nabla g(\boldsymbol{x})&\mathrm{otherwise}
\end{cases}
$$
扫描线算法

为实现多边形和自由绘制闭合图形区域的Poisson Image Editing算法，需通过扫描线算法获取多边形内部掩膜。这里从网上资料了解到一种有序边表法，其基本思想是定义边表ET和活动边表AET，ET记录当前扫描线与边的交点坐标、从当前扫描线到下一条扫描线间x的增量、该边所交的最高扫描线，AET记录只与当前扫描线相交的边的链表，通过迭代得到当前扫描线与待求多边形各边的交点，再利用奇偶检测法判断该点是否在多边形内部进行填充。