Please enable Javascript to view the contents

Poisson Image Editing

 ·  ☕ 3 分钟

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记录只与当前扫描线相交的边的链表,通过迭代得到当前扫描线与待求多边形各边的交点,再利用奇偶检测法判断该点是否在多边形内部进行填充。

3. 实验结果

3.1. 标准图像测试

原图像:

girl

bear

新背景图像:

sea

边界形式 图1选择区域 图2选择区域 结果图像
矩形边界 girlrect bearrect rect
多边形边界 girlpolygon bearpolygon polygon
自由绘制边界 girlfree bearfree freedraw

3.2. Poisson vs. Mix Poisson

背景图像:

back

前景图像:

smile

混合结果:

compare

如图,左上为直接复制粘贴,保留前景全部颜色梯度信息;左下为普通Poisson编辑,保留前景全部梯度信息,前景像素颜色与背景作融合;右上为应用混合梯度的Poisson编辑,前景梯度部分保留,效果上比普通Poisson编辑更加“透明”,适合用在水印等场景。

3.3. 其他应用

3.3.1. 遮盖不必要的信息(如去皱纹)

原图像:

wrinkles

处理效果:

wrinklesprocess

3.3.2. 恐怖片特效

原图:

mirror

掩盖镜子中人物:

3

使用电影《修女》中的角色:

nuts

处理效果:

4

3.3.3. 生成表情包

原图:

banana

处理效果:

bananaprocess

参考文献

[1] Patrick Pérez, Michel Gangnet, Andrew Blake. Poisson image editing. Siggraph 2003.

分享

Wenbo Chen
作者
Wenbo Chen
CG Student

目录