User Tools

Site Tools


keynote:2011-lesson11

第十一课 水平集(一)

内容提要 

本次课共分为四部分内容,如下:

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


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

数学基础


微分几何简介

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

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

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

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

数学形态学

  形态学(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

Revised by Yefeng Zhao(赵叶峰, ID: 11021069) yefeng_zhao@zju.edu.cn AT 2011/06/17 20:30

隐函数和距离函数


数学基础-隐函数

隐函数(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方法均是指数值解方法。

应用Level set方法需要解决两个实际问题: 1)如何列出有意义的方程求解实际问题;2)如何快速稳定地求出方程的数值解.

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

水平集的标准定义是:与实数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表示时间。在任意时刻,曲线上的点就是距离函数值为零的点(即距离函数的零水平集)。尽管这种转化使问题在形式上变得复杂,但在问题的求解上带来很多优点,最大的优点是曲线的拓扑变化能够得到很自然的处理,而且可以获得唯一的满足熵条件的解。

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

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

应用Level set相关知识: 1) 相关数学知识 2) 相关书籍. 3) 相关网站

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

keynote/2011-lesson11.txt · Last modified: 2014/05/22 08:34 (external edit)