====== 第十一课 水平集（一）======


==== 内容提要　====
本次课共分为四部分内容，如下：
  - 数学基础 （微分几何简介、数学形态学、隐函数、距离函数、动态可变形模型）
  - Level Set方法概念
  - Level Set数值解法
  - Level Set与变分方程的关系
\\
--- //[[ lpcs@zju.edu.cn|李 平]](ID:11021070) Created at 16：58 2011/06/02 //



===== 数学基础 =====
\\

==== 微分几何简介====
本节主要对曲线的微分几何进行介绍:\\

<note tip>   Level Set 和 Possion 方程比较，有啥不同呢？\\
1. 一般来说，level set的应用效果更好；\\ 2. 但level set需要复杂的
数学知识，工程界不太接受；\\ 3. Possion方程呈线性，而level set为
非线性，故需要稳定的算法求解。 
</note>

1. 给定映射$C(p):[a,b]\in R \rightarrow R^2$，定义一个平面的曲线，$p$是参数，对每个$p_0 \in [a,b]$，可得到曲线上的
一点：$C(p_0)=[x(p_0),y(p_0)]$.\\

2. 正则曲线：$C'(p)=[x'(p),y'(p)]\ne 0$，亦即$x'(p),y'(p)$不能同时为零\\

3. 曲线的切线：$C'(p)=[x'(p),y'(p)]=\frac{\partial C}{\partial p}$\\

4. 弧长参数:曲线的参数满足$\|\frac{\partial C}{\partial p} \| = 1$，其中$p$表示曲线上以某点为标准的弧长。\\

5. 弧长：$L(t_0,t_1)=\int_{t_0}^{t_1}[(x'(t)^2 + (y'(t)^2))^2]^(1/2)dt$\\

6. 弧长参数$s$：$<C'(s),C'(s)=1>$，求导后等式变成0.\\

7. 曲率： 设曲线二阶可导，则曲率 $\kappa = \|C''(s)\|$，曲率数值上等于曲线改点密切圆半径的倒数\\

8. 假设$T$表示切线，$N$表示法线，则 $\frac{dC}{ds}=T$,
$\frac{d^2C}{ds^2}= \kappa N$\\

9. Frenet公式： $\frac{dT}{ds}= \kappa N$,$\frac{dN}{ds}=-\kappa T$\\

10. 曲率的其他定义：
-假设$\theta$为切线T与$x$轴之间的夹角，则：$\kappa = \frac{d\theta}{ds}$\\

11. 隐式曲线的曲率： $C\equiv {(x,y):u(x,y)=0}$,
$\kappa = \frac{u_{xx}u_{y}^2 - 2u_xu_yu_{xy} + u_{yy}u_{x}^2}{(u_x^2 + u_y^2)^{3/2}}$\\

<note>**曲率在旋转及平移操作时不变，但缩放将发生变化**</note>

11. 隐式的法向量： $u(x,y)=0$,$N = +(-)\frac{\nabla u}{\|\nabla u\|}$\\

12. 因为$T，N$互相垂直，所以平面上的任何曲线都可以用曲线上的任意一点的$T,N$线性组合来表示： $\frac{\partial C}{\partial t} = \alpha T + 
\beta N$\\

13. 如果只考虑**几何形状**的变化，那么该变化只与法线方向的变化有关系，
则 $\frac{\partial C}{\partial t} = \beta N$\\
例如，沿着曲率变化最大方向的曲线变形 $\frac{\partial C}{\partial t}
= \frac{\partial^2 C}{\partial s^2} = \kappa \vec{N}$

14. 平均曲率和高斯曲率：\\
a) 每个正则曲面都有两个主曲率\\
b) 这两个曲率的平均值称为**平均曲率**,而两者之积称为**高斯曲率**\\

<note important> Revised by Ping Li(李平, ID: 11021070) 
<patriclouis.lee@gmail.com> AT 2011/06/02 23:24 </note>

==== 数学形态学 ====

    形态学（Morphology）一词通常代表生物学的一个分支。它是研究动植物的形态和结构的学科。数学形态学（Mathematical Morphology）是一种用于图像处理的理论和方法，它通过物体和结构元素相互作用的某些运算，得到物体更本质的形态，比如边界、骨架、凸壳等等，为大量的图像处理问题提供了一种一致的有力方法。

    数学形态学的语言是集合论，集合表示图像中不同的对象。例如，在二值图像中，所有黑色像素的集合是图像完整的形态学描述。

    数学形态学的四种基本运算
  - 腐蚀：减少物体边界的象素数
{{ http://en.wikipedia.org/wiki/File:Erosion.png |腐蚀}}
  - 膨胀：增加物体边界的象素数
{{ http://en.wikipedia.org/wiki/File:Dilation.png |膨胀}}
  - 开运算：腐蚀，然后膨胀
{{ http://en.wikipedia.org/wiki/File:Opening.png |开运算}}
  - 闭运算：膨胀，然后腐蚀
{{ http://en.wikipedia.org/wiki/File:Closing.png |闭运算}}

**腐蚀**\\ 
结构元B平移x后得到B_x，若B_x包含于A，则记下这个x点，所有满足上述条件的点x的全体构成结构元B与目标图像A的最大相关点集，这个点集称为B对A的腐蚀，记为
A \ominus B = \{x \mid B_x \subset A}\
\\ **膨胀** 
对于给定的目标图像A和结构元B，将A中每一个点x扩大为的操作称为膨胀运算，记为
A \oplus B = \bigcup _x_\in_A B_x
\\ **开运算** 
对目标图像A及结构元B，A对B的开运算记为
A \circ B = (A \ominus B)\oplus B
\\ **闭运算**
目标图像A与结构元B的闭运算可以记为
A \bullet B = (A \oplus B)\ominus B

<note important> Revised by Yefeng Zhao(赵叶峰, ID: 11021069) 
<yefeng_zhao@zju.edu.cn> AT 2011/06/17 20:30 </note>
==== 隐函数和距离函数 ====
\\
===数学基础-隐函数===
隐函数（implicit function）:自变量和因变量之间的法则是由一个方程式所确定
$\F(x,y)\=\0\\
$\y=y(x)$\\
<note> 例子：$\x^2+y^2-1=0$\\
===数学基础-距离场函数===
<note>距离函数定义
$\d(x)、=min(|x-x_l|) \forall x \in \partial\Omega$\\
<note>距离函数的性质
$\ |\nabla \d |=1$\\

<note important> Revised by Wei sun(孙威)(ID: B1024001) 
<gydyt@zju.edu.cn> AT 2011/06/17 10:24 </note>

===== Level Set方法概念 =====
\\
=== Level set的数学定义===
假设隐函数$\phi(x,t)$表示一个高维空间的方程，其在低维空间上的接触面
为$\phi(x,t)=0$，其中$x=(x_1,x_2,\cdots,x_n)\in R^n$,则level set
方程$\Gamma(t)$有如下的性质，其中接触面表示为：
$\phi(x,t)<0 \forall x \in \Omega$\\
$\phi(x,t)>0 \forall x \notin \bar{\Omega}$\\
$\phi(x,t)=0 \forall x \in \partial\Omega=\Gamma(t)$\\

水平集的标准定义是：与实数c对应的可微函数 的水平集是实点集 {(x1, x2, ...,xn) | f(x1, x2,...,xn) = c} 称可微函数f为水平集函数。也许这个比较难以理解，这里给一个例子：水平集函数 对应于常数c的水平集是一个以(0，0，0)为球心，sqrt(c) 为半径的球面（注意这里是球面不是线）。
 
当自变量参数个数n=2时，水平集是一个水平曲线，我们可以理解为一个空心的球体的切面。同理，当自变量的个数n=3时（上面 对应常数c的水平集），水平集是一个水平面，就像一个实心的球体的切面一样。
 
有上面的定义我们可以有这样的感性认识，所谓的水平集关键在于水平的概念。顾名思义，水平集就是水平切面上的一个集合。

而维基百科中的定义为：在数学领域中，一个具有n变量的实值函数f的水平集是具有以下形式的集合{ (x1,...,xn) | f(x1,...,xn) = c }其中c是常数。即使得函数值具有给定常数的变量集合。
 
当具有两个变量时，称为水平曲线(等高线)，如果有三个变量，称为水平曲面，更多变量时，水平集被叫做水平超曲面。
 
集合{ (x1,...,xn) | f(x1,...,xn) ≤ c }被称为f的子水平集。

=== Level Set的运动 ===
数学表达式为：$\frac{\partial \phi}{\partial t} + v \cdot \nabla \phi =0 \$\\
假设 $v_N = v \cdot \frac{\nabla \phi}{|\nabla \phi|}$，则上式
可以写为： $\frac{\partial \phi}{\partial t} + v_N \cdot |\nabla \phi| =0 \$\\

=== Level Set方法的几何意义 ===
给定一个高维空间在低维空间上的接触面，分析并计算其边界在速度$v$时的运动
轨迹，其中速度是与位置、时间和接触面的几何形状有关的（如平均曲率，法向量等），此外还包括外部的物理作用力.

<note> Level Set的优点：考虑了物体几何的一些更为本质的特征，如曲率和梯度等，所以得到的结果比其他方法更令人满意！</note>

=== 小结 ===
1. Level set方法实际上是求解一个随着时间变化的偏微分方程： $\frac{\partial \phi}{\partial t} + v_N \cdot |\nabla \phi| =0 \$\\,其中$v_N$可以是任何关于时间、位置和几何度量的函数.\\

2. 通常提到的Level set方法均是指数值解方法。

<note>  应用Level set方法需要解决两个实际问题：
1）如何列出有意义的方程求解实际问题；2）如何快速稳定地求出方程的数值解. </note>

<note important> Revised by Ping Li(李平)(ID: 11021070) 
<patriclouis.lee@gmail.com> AT 2011/06/03 0:24 </note>

水平集的标准定义是：与实数c对应的可微函数 的水平集是实点集 {(x1, x2, ...,xn) | f(x1, x2,...,xn) = c} 称可微函数f为水平集函数。也许这个比较难以理解，这里给一个例子：水平集函数 对应于常数c的水平集是一个以(0，0，0)为球心，sqrt(c) 为半径的球面（注意这里是球面不是线）。

当自变量参数个数n=2时，水平集是一个水平曲线，我们可以理解为一个空心的球体的切面。同理，当自变量的个数n=3时（上面 对应常数c的水平集），水平集是一个水平面，就像一个实心的球体的切面一样。
 
有上面的定义我们可以有这样的感性认识，所谓的水平集关键在于水平的概念。顾名思义，水平集就是水平切面上的一个集合。

具体方法：给定平面上的一条封闭曲线，以曲线为边界，把整个平面划分为两个区域：曲线的外部和内部区域。在平面上定义距离函数φ(x ,y ,t )=±d，其中d是点(x ,y)到曲线的最短距离，函数符号取决于该点在曲线内部还是外部，一般定义曲线内部点的距离为负值，t表示时间。在任意时刻，曲线上的点就是距离函数值为零的点(即距离函数的零水平集)。尽管这种转化使问题在形式上变得复杂，但在问题的求解上带来很多优点，最大的优点是曲线的拓扑变化能够得到很自然的处理，而且可以获得唯一的满足熵条件的解。

<note important> Revised by karenkaka(吴颖青)(ID: 11021068) 
<41897580@qq.com> AT 2011/06/27 19:54 </note>

=== 学习Level Set相关数学知识 ===
学习和应用Level Set需要掌握偏微分方程理论及其数值化方法，其中又应该着重掌握偏微分方程中的Conversation Law，The Theory of Viscosity Solution(粘性溶液 ) and Hamilton-Jacobi Equation( 哈密尔顿-雅可比方程 )及其数值化方法。同时，在学习Level Set的时候也会经常遇到变分法和测度论的一些内容，但对这两方面的要求不高，了解一下就行了

=== 学习Level Set相关书籍 ===
（1） Stanley Osher and Ronald Fedkiw. Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag (2002). 评点：这本书是创始人之一Osher写的，这本书是论述Level Set的最完整的书籍之一，更偏重于数值化的高精度解，应用领域涉及图像处理以及计算物理。
（2） James A. Sethian. Level Set Methods and Fast Marching Methods. Cambridge University Press (1999). 评点：这是另外一个创始人Sethian的作品，与Osher的书互有侧重，互相补充，这本书更偏重于Fast Marching Methods, 非结构化网格，涉及的应用领域更广泛。
（3） Guillermo Sapiro, Geometric Partial Differential Equations and Image Analysis, Cambridge University. 评点：这本书对理解Level Set也非常有帮助，它更偏重于图像中的几何特征，如曲率等，对几何偏微分方程介绍的比较详细。
（4） Gilles Aubert and Pierre Kornprobst，
Mathematical problems in image processing: Partial Differential Equations and the Calculus of Variation, Springer, Applied Mathematical Sciences, Vol 147, 2002。这本书数学味太浓，一般人没兴趣读下去，但如果你确实想对你的方法奠定更好的理论基础，这本书就非常有用了，它可以指导你应该在哪方面下功夫。另外，这边书的前言和第一章写的非常好，非常值得一读。

=== 学习Level Set相关网站 ===
（1）http://math.berkeley.edu/~sethian/level_set.html
评点：这是Sethian的网站，上面关于Level Set的论述非常多，分门别类，非常清晰。
（2）http://www.math.ucla.edu/~imagers/
评点：这是UCLA的研究组，由Osher创办，关于Level Set的新进展几乎都跟他们相关，这个网站是关注Level Set的最新新闻的最好的地方。

<note>  应用Level set相关知识：
1) 相关数学知识 2) 相关书籍. 3) 相关网站</note>

<note important> Revised by Canghong Jin(金苍宏)(ID: 11021066) 
<canghong.jin@gmail.com> AT 2011/07/13 0:24 </note>