论文复现：coordinates for instant image cloning

本论文最重要的理论基础，自然就是泊松图像编辑[Pe ́rez et al. 2003]，通过聚焦于图像的梯度域，可以将两张图片融合在一起，即，前景图片在背景上的边缘为方程的已知条件，通过解决一个从外向内的巨大的方程组，就能一步步的解出前景区域内每个像素点的插值，通过这个插值就能将前景插到背景图上，但是这个问题有一个很大的问题就是耗时很长，因为且由于该方程的非封闭性质，不能使用GPU并行计算，所以这是泊松式插值的问题之一。

那本文就针对与这个缺点，提出了新的插值，能很好的模拟出泊松插值，且公式封闭，执行速度快。

由已知图像编辑的目的就是去解，满足一定狄利克雷边界条件的这样一个泊松等式：

$$Delta f=operatorname{div} nabla g quad text { w/ Dirichlet boundary conditions }left.fright|_{partial P_{t}}=f^{*}$$

当然也可将之转化为一个满足狄利克雷边界条件的拉普拉斯等式：

$$Delta tilde{f}=0, quad text { w/ Dirichlet boundary conditions }left.tilde{f}right|_{partial P_{t}}=f^{*}-g$$

这里引入一个定理：

A function u that satisfies laplace equation is called harmonic function.

一个满足拉普拉斯条件的等式也可以叫作调和函数。所以如果我们能找到一个类调和的函数，是否就能替代以上方程的解呢？

这里引入中值坐标(Mean Value Coordinates[Floater 2003]，以下称为MVC)，该论文主要有针对调和函数的中值定理提出来的，即：

如果一个函数是调和函数，在函数上找任意一点，那么该点上的调和函数值，等于在以该点为圆心的任意圆上的所有点的函数值的平均值：

$$u(a, b)=frac{1}{2 pi r} oint_{partial B_{t}(a, b)} u(x, y) d s$$

那本论文就在该论文的基础上，提出了新的中值条件，不同的是，不用要求是圆形，多边形也行：

那么如果已经知道了边缘上所有点的函数值，用该坐标方法表示的中间每个点的函数值之后，所有点也可以形成一个类调和函数，也就是可以一定程度上近似拉普拉斯方程的解了。

可以发现这样求出来的插值与拉普拉斯求出来的类似：

主要的方法就是通过求出边缘上的点的前景图和背景图的差，作为边界条件，然后作为坐标，求出前景图每个像素点的插值，与每个像素点的像素值相加，就能得到合成的图像。

其实就算是封闭的方法，但是不加优化的执行起来，与泊松方法的速度也差不多，但是本算法可以使用很多加速的方法。

本文提出，通过观察，插值在远离边界的地方表现出一种非常平滑的现象：

那么本文就提出，针对图像内部的像素点，并不用每个点都求出插值，所以本文首先用CGAL求出一个Mesh：

通过只求mesh的顶点的插值，其它点的插值通过求其所在三角形的三个顶点的插值，与该点与这三个顶点的距离关系的权值，就能快速求出所有点的插值。如果说$m$是边缘的点的个数，$n$是前景内的所有点的个数，其中$m$ << $n$，那么这个策略能将时间复杂度从$Oleft(mnright)$降到$Oleft(m^{2}right)$。

本文还提出，其实针对每个顶点，其实也不用求所有的边界上的点相对于它的中值坐标，来模拟其调和函数值。只需采样其中的部分点就行了，具体策略如下：
首先根据已有信息求出以下阈值：

$$varepsilon_{d i s t}=frac{# text { boundary pixels }}{16 cdot 2.5^{k}} text { and } varepsilon_{a n g}=0.75 cdot 0.8^{k}$$

然后如果两个点边界上的两个点能满足以下条件：

$$begin{aligned}left|mathbf{x}-mathbf{p}_{i}^{k}right| &amp;&gt;varepsilon_{d i s t} \ Delta mathbf{p}_{i-s}^{k}, mathbf{x}, mathbf{p}_{i}^{k} &amp;&lt;varepsilon_{a n g} \ angle mathbf{p}_{i}^{k}, mathbf{x}, mathbf{p}_{i+s}^{k} &amp;&lt;varepsilon_{a n g} end{aligned}$$

那么这两个点就能足够表示这两点之间的所有点了，就不用再采样这两点之间的任何点了(当然是两点相当较近的那一条边)。

当然实验表明这个阈值的参数的设置并非最佳(效果好又执行时间短)，不过也足够了。

不过这个优化方法也会有缺点，因为有时候一个点代表了周围很大一块，那如果这个点的数据出错，就会影响相当大一部分的结果(Aliasing效果)，可能的解决办法是给前景值减背景值(边界条件)设置一个最大值阈值。

Poisson VS MVC

除了一些极端的场景外，效果基本一样。

但是MVC能比Poisson快上许多，当然是仅在采用了优化方法的时候才会这样。

当然本论文不仅可利用与图形编辑，在Border Matting或者Image Stitching或者Video Cloning也能有很好的利用。

• CARRIER, J., GREENGARD, L., AND ROKHLIN, V. 1988. A fast adaptive multipole algorithm for particle simulations. SIAM Journal on Scientific and Statistical Computing 9, 669–686.
• FLOATER, M. S. 2003. Mean value coordinates. Comput. Aided Geom. Des. 20, 1, 19–27.
• HANRAHAN, P., SALZMAN, D., AND AUPPERLE, L. 1991. A rapid hierarchical radiosity algorithm. Computer Graphics (SIG- GRAPH ’91 Proceedings) 25, 4 (July), 197–206.
• PE ́REZ, P., GANGNET, M., AND BLAKE, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 3, 313–318.