Applied Mathematics for Computer Science

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 第六课 泊松方程 ======
===== 关于泊松 =====
泊松的老师-拉普拉斯。LOL都是大牛呀。
泊松也是大牛，以泊松命名的词汇，如
  - 泊松方程
  - 泊松分布
  - 泊松常量

===== 背景知识 =====
==== 变分命题与一般极值问题 ====
历史上有很多有名的极值问题，其求解方法可以统称为变分法，如：
  - 两点间的最短连线问题
  - 最速下降线问题
  - 短线程问题
  - ...
=== 两点间的最短连线问题 ===
为什么”任意两点间的最短连线是连接两端的连线“？
{{:keynote:l.gif|}}
<note tip>8-)很常识的问题，但要问为什么，估计很少人能够用数学的方法来回答。</note>
  - 问题的假设
       - 二维平面空间，一点坐标是原点(0,0)，一点在(a,b)
      - 两点间的连接曲线是y=y(x)
      - 曲线的弧长微分是<jsmath>ds^2=dx^2+dy^2</jsmath>或    {{:keynote:111-1.jpg|}}
      - 曲线的总弧长是{{:keynote:111-2.jpg|}}
    
  - 问题的数学描述
找出具有曲线y(x)使得
{{:keynote:6-1-10-1.jpg|}}
同时必须满足端点的约束条件(constraint condition)
{{:keynote:6-1-10-2.jpg|}}
  - 其变分极值问题为
{{:keynote:6-1-11-1.jpg|}}
  - 略去的高次微量得
{{:keynote:6-1-11-2.jpg|}}
  - 分部积分，并利用，得
{{:keynote:6-1-11-3.jpg|}}
  - 由变分法预备定理，给出以下微分方程
{{:keynote:6-1-12-1.jpg|}}
  - 积分得
{{:keynote:6-1-12-2.jpg|}}
  - 由端点约束条件得
y=(b/a)x

===== 变分命题 =====
  * 第一类变分问题：
    * 被积函数包括一阶导数的变分问题
    * 满足端点约束条件
    * 在所有的足够光滑函数y(x)中，求使以下泛函为极值
               <jsmath> \Pi(y)= \int^β_αF(x,y,y')dx</jsmath>
  * 第二类变分问题：
    * 两个待定函数：y(x),z(x)
    * 满足约束条件：φ(x,y,z)=0
    * 满足端点条件
    * 在所有的足够光滑函数y(x),z(x)中，求使以下泛函为极值
           <jsmath>\Pi(y,z)=\int^β_αF(x,y,y',z,z')dx</jsmath>  
 --- //[[qiuweiwei@zju.edu.cn|邱炜伟]] 2010/04/11 21:28//

===== 变分中的符号 =====
  * 给定函数y(x)
    * 宗量：x
    * 函数：y(x)
    * 宗量的增量：Δx
    * 函数的增量：
      * Δy=y(x+Δx)-y(x)
    * 当两点无限接近：
      * Δx→dx,Δy→dy
    * 略去高阶微量：
      * dy=y’(x)dx
    * 当在x处取得函数极值
      * dy=0 
  * 给定泛函 Π(y)
    * 宗量：y
    * 泛函：Π(y)
    * 函数的变分：δy （函数y(x)在定义域内与y(x)+δy(x)处无限接近
    * 泛函的变分：
      * δΠ=Π(y+δy)-Π(y)
      * 在计算δΠ时可以展开Π(y+δy)中的被积函数只保留线性项
    * 当在y处取得泛函极值
      * δΠ=0
 --- //[[qiuweiwei@zju.edu.cn|邱炜伟]] 2010/04/11 21:32//
===== 第一类变分问题 =====
  * 设函数y(x)是下式的极值解 <jsmath>\Pi(y)=\int^\beta_\alpha F(x,y,y')dx</jsmath>
    * 且满足端点条件<jsmath>y(\alpha)= \overline{y_1}，y(\beta)= \overline{y_2}</jsmath>
  * 设其邻近的函数y(x)+δy(x)也满足端点条件
    * 因此端点变分满足δy(α)=δy(β)=0
  * 泛函的变分为<jsmath>\delta\Pi=\Pi(y+\delta{y})-\Pi(y)=\int^\beta_\alpha{F(x,y+\delta{y},y'+\delta{y}')-F(x,y,y')}dx </jsmath>
  * 根据微量计算规则，设y(x)和y(x)+δy(x)是有一阶接近的曲线<jsmath>F(x,y+\delta y,y'+\delta y')=F(x,y,y')+\bigg[\frac{\partial}{\partial y}F(x,y,y')\bigg ]\delta y+\bigg[\frac{\partial}{\partial y'}F(x,y,y')\bigg ]\delta y'</jsmath>
  * 引入简写符号<jsmath>F=F(x,y,y'),F_y=\frac{\partial}{\partial y}F(x,y,y'),F_y'=\frac{\partial}{\partial y'}F(x,y,y')</jsmath>
  * 可得<jsmath>\delta F=F_y\delta y + F_y'\delta y'</jsmath>
  * 泛函的变分为:<jsmath>\delta \Pi=\int^\beta _\alpha \delta Fdx=\int^\beta _\alpha \Big [F_y\delta y+F_y'\delta y'\Big ]dx</jsmath>
  * 可以证明：函数y(x)的导数的变分等于函数y(x)的变分的导数，亦即导数和变分两种运算**可以互换**运算顺序：<jsmath>\delta y'=\big(\delta y\big )'</jsmath>
 --- //[[qiuweiwei@zju.edu.cn|邱炜伟]] 2010/04/12 20:51//

===== 变分问题的欧拉方程 =====
  * 由预备定理可知：<jsmath>F_y-\frac{d}{dx}F_y'=0,\alpha \leq x\leq\beta</jsmath>
  * 如果展开dF<sub>y'/</sub>dx\[ F_y-\frac{{\partial}^2 F}{\partial x\partial y}-\frac{{\partial}^2 F}{\partial y\partial y'}y'-\frac{{\partial}^2 F}{\partial y'\partial x}y''=0 \]
  * 其中F(x,y,y’)必须具有二阶偏导数，y(x)也必须具有二阶偏导数。
<note>**由此把变分问题转化为微分方程求解**</note>
 --- //[[qiuweiwei@zju.edu.cn|邱炜伟]] 2010/04/12 20:53//

===== 泛函变分问题的一般求解步骤 =====
<note tip>1.从物理上建立泛函及其条件\\
2.通过泛函变分，利用变分法基本预备定理求得欧拉方程\\
3.在边界条件下求解欧拉方程，即微分方程求解</note>
===== 变分法与欧拉方程 =====
  * 变分法与欧拉方程代表同一物理问题
  * 欧拉方程求解和从变分法求数值近似解（如有限元，利兹法，伽辽金法等），其效果一样

  * 欧拉方程求解很困难，但从泛函求近似解通常很方便，因而变分法一直被广为重视。
  * 但并不是所有的微分方程都能找到相对应的泛函问题。
 --- //[[qiuweiwei@zju.edu.cn|邱炜伟]] 2010/04/12 20:50//



===== 泊松方程 =====
==== 泊松方程 ====
泊松方程是数学中一个常见于静电学、机械工程和理论物理的偏微分方程。方程形式如下：

$\Delta f = -\rho$

这里的 $\Delta$ 代表的是拉普拉斯算子，

|  $\Delta\equiv\displaystyle {\partial ^2 \over\partial ^2x}+{\partial ^2 \over\partial ^2y}$  |

而 $f$ 和 $\rho$ 可以是在流形上的实数或复数值的方程。其中$\rho$可以表示为$\rho =\rho (x,y)$的形式。

==== 变分解释 ====

$f^*=arg\min_f\int\!\!\!\int_\Omega\|\nabla f-v\|^2$
满足
$f^*|_{\partial\Omega}=f|_{\partial\Omega}$

令$F=\|\nabla f-v\|^2$，那么，根据欧拉方程：$F_f-\displaystyle {\partial\over\partial x}F_{f_x}-{\partial\over\partial y}F_{f_y}=0$
可以得到如下的形式：

$\Delta f=div(v) $ 满足 $f^*|_{\partial\Omega}=f|_{\partial\Omega}$

其中$v$是一个向量场，但并不一定是梯度场。

<note tip>$div(v)$表示v的散度，如果把v表示成$v(x,y,z)=P(x,y,z)i+Q(x,y,z)j+R(x,y,z)k$的形式，则$div(v)$可以由公式

 $div(v)=\displaystyle {\partial P\over\partial x}+{\partial Q\over\partial y} + {\partial R\over\partial z}$

给出。</note>
====边界条件====
{{:keynote:boundaryconditions.png|}}

注：图中$\Omega$表示某一给定的区域，$\partial\Omega$表示区域的边界，$ds$的方向表示在边界$\partial\Omega$处的（向外的）法向。

  * Dirichlet 边界条件：$f|_{\partial\Omega}$
<note tip>狄利克雷边界条件（Dirichlet boundary condition）也被称为常微分方程或偏微分方程的“第一类边界条件”，指定微分方程的解在边界处的值。</note>
  * Neumann 边界条件:${\displaystyle{ {\partial f}\over{\partial s}}|_{\partial\Omega}}$
<note tip>诺伊曼边界条件（Neumann boundary condition) 也被称为常微分方程或偏微分方程的“第二类边界条件”。诺伊曼边界条件指定了微分方程的解在边界处的微分。</note>
===解的存在性===
如果指定了在$\partial\Omega$上的Dirichlet边界条件或Neumann边界条件，那么泊松方程在区域$\Omega$中的解是唯一可确定的
====泊松方程的物理原型====
前面也讲到，泊松方程在静电学和理论物理中是比较常见的，下面说的两个物理原型也是分别来自这两个领域的。
===静电势===
一个电荷的静电场如下图所示：

{{:keynote:electrostaticpotential.png|}} {{:keynote:electrostaticpotential_derivation.png|}}

其中，$\rho (x)$表示电荷密度，$\Phi$表示电势，$E$表示电场。电荷之间作用力的公式$\displaystyle F={{q_1 q_2 r}\over{4\pi\varepsilon _0r^3}}$，其中的$\varepsilon _0$为真空电容率。

我们知道，高斯定律的积分形式可以表示为：
<jsmath>\displaystyle\oint _s{E\cdot ds} = \int _V{{\rho (x)}\over{\varepsilon _0}}dv</jsmath>
高斯散度定理的向量表示为：
<jsmath>\displaystyle\oint _s{E\cdot ds} = \int _V{\nabla\cdot E}dv</jsmath>
根据以上两式，可以得到
<jsmath>\displaystyle \nabla\cdot E={{\rho (x)}\over{\varepsilon _0}}</jsmath>
再由$E=-\nabla\Phi$可得泊松方程如下：
<jsmath>\Delta\Phi = \displaystyle- {{\rho (x)}\over{\varepsilon _0}}</jsmath>

因此，电场$E$，电势$\Phi$，电荷密度$\rho$之间的关系可以表示成如下图所示的形式：
{{:keynote:electrostaticpotential_relationship.png|}}
===以及===
{{:keynote:electrical_field.jpg|}}

===重力场===
一个重力场的示意图如下：

{{:keynote:gravitationalpotential.png|}}

与静电场中类似的，在重力场中，$\rho (x)$表示质量密度，$\Phi$表示重力势，$g$表示力场(重力加速度)。物体受到的重力的公式表示为$\displaystyle F={{mMGr}\over{r^3}}$，由高斯定理、$g=-\nabla\Phi$以及$F=mg$可得到如下的泊松方程：
<jsmath>\Delta\Phi = -4\pi G\rho (x)</jsmath>
重力加速度$g$、质量密度$\rho$以及重力势$\Phi$之间具有如下的关系：

{{:keynote:gravitationalpotential_relationship.png|}}

===推广到图像中===
我们知道了泊松方程的两个物理原型，如果将其推广到图像领域中，我们可以把图像看作一个场$I$，用$\rho (x)$表示图像密度，用$g$表示图像梯度，则有泊松方程$g=-\nabla I$，以及三者之间的关系如下：

{{:keynote:imagepotential_relationship.png|}}

形象化一点表示，就是下面所示的样子：

{{:keynote:imagepotential_relationship2.png|}}

由于三者之间可以相互转换，所以如果我们知道了图像区域的密度函数以及边界处的颜色值，就可以计算出整幅图像的内容。

{{:keynote:lession6.possionimageexample.png|}}

<note important> Revised by Zhang Bin （张斌）, <zhangbin@zjucadcg.cn> </note>

===== 应用 =====

==== 泊松图像编辑 ====

泊松图像编辑是泊松方程的一个重要应用，首先提出该应用的是P.P\'erez, M. Gangnet, and A. Blake (Poisson image editing. SIGGRAPH 2003),该文章对现在的图像编辑技术有着非常重要的影响，随后的几年又出现了很多类似的图像编辑方法，如 [Jiaya Jia et al. Drag and-drop pasting]于2006年提出了最优的融合边界用于改进泊松图像编辑的效果，[Zeev Farbman et al. coordinates for instant image cloning]在SIGGRAPH 2009中提出了使用Mean-Value coordinates用于计算基于梯度域的图像编辑，该方法实现简单且运行速度快，从而避免了求解复杂的泊松方程。
下面通过几个典型的应用来说明泊松方程在图像编辑中的强大功能。

===无缝融合===
  * 传统的图像融合
       - 精确地选择融合区域：过程单调乏味且工作量大，常常无法得到好的结果
       - Alpha-Matting：功能强大，但是实现复杂
  * 基于**Poisson**方程的无缝融合
       - 选择融合区域的过程简单且方便
       - 最终可以得到无缝融合的结果
  * 因此，我们选择基于**Poisson**方程的方法进行图像的无缝融合！！

如下图所示，我们分别用两种不同的方法来进行图像融合：

{{:keynote:hard_copy.jpg|}}
{{:keynote:poisson_cloning_1.jpg|}}


 
<note important>Revised by Zhang Yun (张赟),<zhangyun_zju@zju.edu.cn></note>

==== 泊松/拉普拉斯曲面编辑 ====

===== 如何解偏微分方程 =====

===== 更多内容 =====
Applied Mathematics for Computer Science

User Tools

Site Tools

Page Tools
