查看“︁水平集方法”︁的源代码

'''水平集方法'''（'''Level Set Method'''） 是一种用于界面追踪和[[形状建模]]的[[数值分析|数值]]技术.水平集方法的优点是可以在[[笛卡尔网格]]（Cartesian grid）上对演化中的[[曲线]][[曲面]]进行数值计算而不必对曲线曲面[[参数化]]（这是所谓的''欧拉法''（Eulerian approach））.）.<ref>{{Harvard reference 
 | Surname1 = Osher
 | Given1 = S.
 | Surname2 = Sethian
 | Given2 = J. A.
 | Title = Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations
 | Journal = J. Comput. Phys.
 | Volume = 79
 | Year = 1988
 | Pages = 12–49.
 | id =
}}</ref>水平集方法的另一个优点是可以方便地追踪物体的[[拓扑]]结构改变.例如当物体的形状一分为二，产生空洞，或者相反的这些操作.所有这些使得水平集方法成为随时间变化的物体建模的有力工具，例如膨胀中的气囊， 掉落到水中的油滴.

==水平集方法==
[[Image:level_set_method.jpg|thumb|right|400px|水平集方法示例]]
理解水平集方法的最简单有效地方式是先学习相应的例子，然后学习技术性很强的定义.右侧的图片示例了水平集的几个重要思想.在左上角有一个形状--由一个良性边界包围的有界区域.在它的下面，红色的曲面是相应的水平集函数<math>\varphi</math>的图像, <math>\varphi</math>的某个水平面决定了左上角的形状，假设其中的蓝色平面即为x-y平面，则形状的边界可以表示为<math>\varphi</math>的零水平集，并且该形状是平面上满足<math>\varphi</math>大于等于零的点的集合.
 
在上面的一行，形状改变其拓扑结构，分裂为两个形状.如果用边界曲线参数表示形状，这一演化过程是很难表达的.这需要一个算法能够检测到形状分裂的时刻，然后为分裂后的曲线构造新的参数.另一方面，从下面的一行可以看出水平集函数仅仅是向下方移动了一点.由于在直接法中我们需要监视所有形状可能发生的变化情况，水平集方法处理形状曲线要比直接方法容易得多.

在二维情况下，水平集方法意味着将平面上的[[闭曲线]]<math>\Gamma </math> (正如示例中的形状)表示为二维辅助[[函数]]<math> \varphi </math>,的零[[水平集]]
:<math>\Gamma = \{(x, y)|\, \varphi(x, y) = 0 \}, \,</math>
然后通过函数<math>\varphi</math> ''隐式''的处理曲线<math>\Gamma </math>.这一函数便被叫做''水平集函数''.假设<math>\varphi</math>在曲线<math>\Gamma </math>的内部取正值，在曲线<math>\Gamma </math>的外部取负值. <ref name=osher>{{cite book |last=Osher |first=Stanley J. | authorlink = Stanley Osher |coauthors = [[Ronald Fedkiw|Fedkiw, Ronald P.]] |title=Level Set Methods and Dynamic Implicit Surfaces|publisher=[[Springer-Verlag]] |year=2002 |isbn= 0-387-95482-1}}</ref><ref name=sethian>{{cite book |last=Sethian |first=James A. | authorlink = James Sethian |coauthors = |title= Level Set Methods and Fast Marching Methods : Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science|url=https://archive.org/details/levelsetmethodsf0000seth |publisher=[[Cambridge University Press]] |year=1999 |isbn= 0-521-64557-3}}</ref>

==水平集方程==
如果零水平集以速度''v''沿着其法线运动，这一运动可以表示为水平集函数的''[[哈密頓-雅可比方程]]''（''Hamilton-Jacobi equation''）:
:<math>\varphi_t = v|\nabla \varphi|.</math>
这是一个[[偏微分方程]]，并且可以求得数值解，例如可以在笛卡尔网格上采用[[有限差分法]]. 

然而，水平集方程的数值解需要复杂的技术.简单的有限差分法会很快导致不收敛. [[迎风]]方法，诸如[[Godunov格式|Godunov方法]]前进缓慢;然而在水平对流场中，水平集方法不保持水平集的体积和形状的守恒.

==历史==
美国数学家Stanley Osher和James Sethian于20世纪80年代开发出了水平集方法.这一方法在许多学科广泛使用，例如[[图像处理]]，[[计算几何]]，[[最优化]]和[[计算流体力学]].

大量的有关[[水平集数据结构]]被开发出来，使得水平集方法在计算中的应用变得更加方便.

==参阅==
* [[流体体积法]]
*[[b:Fractals/Iterations_in_the_complex_plane/Julia_set|LSM/J Level set method for drawing dynamical plane]]
*[[b:Fractals/Iterations_in_the_complex_plane/Mandelbrot_set|LSM/M Level set method for drawing parameter plane]]

==参考文献==
{{reflist}}

{{数值偏微分方程}}

[[Category:数学规划]]
[[Category:数值分析]]
[[Category:计算机制图算法]]
[[Category:图像处理]]
[[Category:计算流体动力学]]