This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
keynote:2011-lesson11 [2011/06/27 18:30] karenkaka [隐函数和距离函数] |
keynote:2011-lesson11 [2023/08/19 21:02] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== 第十一课 水平集(一)====== | ||
+ | |||
+ | ==== 内容提要 ==== | ||
+ | 本次课共分为四部分内容,如下: | ||
+ | - 数学基础 (微分几何简介、数学形态学、隐函数、距离函数、动态可变形模型) | ||
+ | - 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> |