第十一课 水平集（一）

本次课共分为四部分内容，如下：

1. 数学基础 （微分几何简介、数学形态学、隐函数、距离函数、动态可变形模型）
2. Level Set方法概念
3. Level Set数值解法
4. Level Set与变分方程的关系

— 李 平(ID:11021070) Created at 16：58 2011/06/02

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

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}}

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) 这两个曲率的平均值称为平均曲率,而两者之积称为高斯曲率

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

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

  数学形态学的四种基本运算
- 腐蚀：减少物体边界的象素数

1. 膨胀：增加物体边界的象素数

1. 开运算：腐蚀，然后膨胀

1. 闭运算：膨胀，然后腐蚀

腐蚀
结构元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

隐函数（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© 为半径的球面（注意这里是球面不是线）。 当自变量参数个数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方法均是指数值解方法。

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

当自变量参数个数n=2时，水平集是一个水平曲线，我们可以理解为一个空心的球体的切面。同理，当自变量的个数n=3时（上面 对应常数c的水平集），水平集是一个水平面，就像一个实心的球体的切面一样。

有上面的定义我们可以有这样的感性认识，所谓的水平集关键在于水平的概念。顾名思义，水平集就是水平切面上的一个集合。

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

学习和应用Level Set需要掌握偏微分方程理论及其数值化方法，其中又应该着重掌握偏微分方程中的Conversation Law，The Theory of Viscosity Solution(粘性溶液 ) and Hamilton-Jacobi Equation( 哈密尔顿-雅可比方程 )及其数值化方法。同时，在学习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。这本书数学味太浓，一般人没兴趣读下去，但如果你确实想对你的方法奠定更好的理论基础，这本书就非常有用了，它可以指导你应该在哪方面下功夫。另外，这边书的前言和第一章写的非常好，非常值得一读。

（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的最新新闻的最好的地方。