水平集方法

在二維中透過水平集模擬螺旋（曲率流（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]