水平集方法

在二维中透过水平集模拟螺旋（曲率流（curvature flow））的影片。左图为零水平集解，右图为水平集标量场。

水平集方法（Level Set Method）是一种使用水平集作为界面追踪和形状建模的数值分析技术。水平集方法的优点是可以在笛卡尔网格（英语：Cartesian grid）（Cartesian grid）上对演化中的曲线曲面进行数值计算而不必对曲线曲面参数化（英语：Parametric surface），即所谓的欧拉法（Eulerian approach）。^[1]水平集方法的另一个优点是可以方便地追踪物体的拓扑结构改变。例如当物体的形状一分为二，产生空洞，或者相反的这些操作。所有这些使得水平集方法成为随时间变化的物体建模的有力工具，例如膨胀中的气囊，或掉落到水中的油滴。

水平集方法

理解水平集方法的最简单有效地方式是先学习相应的例子，然后学习技术性很强的定义。右侧的图片示例了水平集的几个重要思想。在左上角有一个形状--由一个良性边界包围的有界区域。在它的下面，红色的曲面是相应的水平集函数 $\varphi$ 的图像， $\varphi$ 的某个水平面决定了左上角的形状，假设其中的蓝色平面即为x-y平面，则形状的边界可以表示为 $\varphi$ 的零水平集，并且该形状是平面上满足 $\varphi$ 大于等于零的点的集合。

在上面的一行，形状改变其拓扑结构，分裂为两个形状。如果用边界曲线参数表示形状，这一演化过程是很难表达的。这需要一个算法能够检测到形状分裂的时刻，然后为分裂后的曲线构造新的参数。另一方面，从下面的一行可以看出水平集函数仅仅是向下方移动了一点。由于在直接法中我们需要监视所有形状可能发生的变化情况，水平集方法处理形状曲线要比直接方法容易得多。

在二维情况下，水平集方法意味着将平面上的闭曲线 $\Gamma$ （正如示例中的形状）表示为二维辅助函数 $\varphi$ 的零水平集

\Gamma =\{(x,y)|\,\varphi (x,y)=0\},\,

然后通过函数 $\varphi$ 隐式的处理曲线 $\Gamma$ 。这一函数便被叫做水平集函数。假设 $\varphi$ 在曲线 $\Gamma$ 的内部取正值，在曲线 $\Gamma$ 的外部取负值。 ^[2]^[3]

水平集方程

如果零水平集以速度v沿着其法线运动，这一运动可以表示为水平集函数的哈密顿-雅可比方程（Hamilton-Jacobi equation）：

\varphi _{t}=v|\nabla \varphi |.

这是一个偏微分方程，并且可以求得数值解，例如可以在笛卡尔网格上采用有限差分法。

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

历史

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

大量的有关水平集数据结构（英语：Level set (data structures)）被开发出来，使得水平集方法在计算中的应用变得更加方便。

参阅

参考文献

^ Osher, S.; Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys. 79, 1988, 79: 12–49.
^ Osher, Stanley J.; Fedkiw, Ronald P. Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag. 2002. ISBN 0-387-95482-1.
^ Sethian, James A. Level Set Methods and Fast Marching Methods : Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press. 1999. ISBN 0-521-64557-3.

[1] Osher, S.; Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys. 79, 1988, 79: 12–49.

[osher-2] Osher, Stanley J.; Fedkiw, Ronald P. Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag. 2002. ISBN 0-387-95482-1.

[sethian-3] Sethian, James A. Level Set Methods and Fast Marching Methods : Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press. 1999. ISBN 0-521-64557-3.

[1]

[2]

[3]