2.2 水平集方法的基本理論

2.2.1 曲線演化理論

曲線演化是利用偏微分進行圖像分割的基本理論，它的中心思想是利用幾何特征來研究曲線隨時間發生的形變情況，曲線的單位法向矢量和曲率是常用的幾何參數。

設C（p, t）=（x（p, t）, y（p, t））為一條閉合的動態曲線。其中，p為曲線弧長的參數；t為時間參數（t≥0）。曲線C（p, t）隨時間演化的過程可用如下的偏微分方程來表示：

式中，T和N分別為單位切矢量和內法矢量；α和β分別為切向速度和法向速度；C0（p）為曲線的初始位置。

給定函數y=γ（x），其含義是以x為自變量的曲線局部y函數，則C（p, t）以x為參數可以表示為

由此可知，曲線C的切矢量為Cx=（1, γx），則曲線C的單位切矢量和單位法矢量可以示為

因此，當曲線C按式（2-12）進行演化時，曲線上任一點的坐標（x, y）按如下方程發生形變：

將y=γ（x）表示為x和t的函數，然后對t求導，可得到

則

上式說明，曲線的形變僅僅受到運動速度法向分量β的影響，據此可進一步去除切向速度α而獲得曲線演化的一般方程：

針對曲線演化方程（2-19）的求解一直是學者們研究的難點問題，直到Sethian[139]和Osher等人[140]于20世紀末提出了水平集方法，才使該問題的求解獲得了嚴格的數學理論支撐。

2.2.2 水平集方法

水平集方法[139]是為了解決描述火焰的外形方程而提出的，由于火苗的拓撲結構的不斷隨意變化，直接用方程是無法描述的，因此提出水平集方法來描述隨時間的變化而不斷變化的曲線。它的本質是用N+1維的水平集函數來隱含表達N維的空間多維函數（閉合曲線、三維的立體曲面或者多維的超曲面），當嵌入在水平集函數中的閉合曲線（曲面）的拓撲結構發生變化（分裂和合并）時，水平集函數仍能保持其函數的穩定性和有效性。基于水平集的圖像分割的本質就是將二維圖像空間中的形變曲線隱式地映射到三維的函數曲面?（x, y, t）進行演變，其零水平集就是投影到二維空間的目標輪廓。因此輪廓曲線在演化過程中的重點是在一個偏微分方程的演化作用下，不斷地更新水平集函數，計算出演化結束后的水平集函數在該時刻的零水平集，相應得到分割結果，而非時刻追蹤標記演化曲線的位置。

在二維平面上，定義?（x, y）:Ω→R為水平集函數，零水平集C（s）用來表示活動輪廓線：

在水平集函數中引入一個時間變量t，定義一個隨時間變化的水平集函數?（x, y, t），它為閉合曲線C（s, t）在t時刻的隱式表達，即

在水平集函數?（x, y, t）的演化過程中，要保持零水平集的活動輪廓線：

利用微分原理，將水平集函數?對t求導，可以得到

式中，為水平集函數?的梯度。

由水平集函數的定義可得，?在曲線C的切線方向的變化量為0，則

由上式可以看出，?的梯度方向與閉合曲線C的切線方向是垂直的，也就是說，??的方向與C的法向量是同方向的。因此，曲線C的單位法向量N可以表示為

可得

式（2-26）被稱為曲線演化的水平集方法的偏微分方程式。

運用水平集方法對圖像進行分割時，要對式（2-26）進行數值計算。在實際的計算中，首先要對水平集函數進行初始化，一般選取符號距離函數（Function Distance Signed, SDF）作為水平集函數的初始值，主要原因是SDF同時具備簡單性和精確性的特點。設SDF為?（x, y, t）=±d（x, y），其中，d（x, y）為圖像域中的點（x, y）到給定的閉合曲線C0之間的距離，其符號根據點（x, y）與C0的位置而定，表示如下[141]：

水平集函數初始化采用SDF，其優勢在于SDF的基本屬性??≡1，這表明?（x, y, t）沿著不同方向的變化率在任意點都可保持均勻狀態，這種特性使得數值計算保持較高的穩定性。

2.2.3 變分水平集方法

采用曲線演化理論解決圖像分割問題，曲線運動方程首先通過最小化關于閉合曲線C的能量泛函，得到C的演化方程，然后引入嵌入函數?，通過求解關于?的偏微分方程，來達到圖像分割的目的。

Zhao等人[125]提出了一種新的水平集方法，稱之為變分水平集方法[142]，是通過引入嵌入函數?和Heaviside函數來改造關于曲線C的能量泛函E（C），得到關于?的能量泛函E（?）。Heaviside函數定義如下：

在具體的計算中，常采用Hε來逼近Heaviside函數；在求解能量泛函過程中，使用Hε的導數δε（z）來進行計算：

變分水平集法和水平集法的主要區別在于：前者通過引入嵌入函數?和Heaviside函數來改造關于曲線C的能量泛函E（C），得到關于?的能量泛函E（?），然后通過變分法得到關于?的偏微分方程；后者直接通過用變分法最小化E（C）來獲取關于C的演化方程，接著引入嵌入函數?，得到?偏微分方程。兩者比較，前者具有穩定性高、對嵌入函數無須重新初始化等優點，而后者的適用面更廣。

基于水平集的方法在演化一段時間后，會受到數字圖像離散化的影響和噪聲干擾，在一段時間后會發生震蕩，使?逐漸偏離SDF，并使輪廓C出現尖角或平坦區域，最終將導致計算結果偏離真實情況和圖像分割失敗，作為距離函數的水平集函數必須不斷地重新初始化，直接代價就是犧牲算法的時間復雜度。為了解決此類問題不再進行初始化，Li等人[98]提出了一種改進的變分水平集方法，在原模型的基礎上增加一個懲罰項，可以在水平集演化的過程中完全避免重新初始化。

梯度下降流為

由式（2-31）可以看出，最小化P（?）意味著要使??≡1，也就能夠使水平集函數在演化過程中盡可能保持距離函數的穩定性，避免再次對其進行初始化，減少了算法的運行時間。在初始化時，可以利用簡單的正負常數來代替符號距離函數，即

2.2.4 水平集方法的數值求解

圖像分割模型中建立的偏微分方程大多是非線性的，其解析解的求取非常困難，只能借助數值計算方法得到對應偏微分方程的數值逼近或近似解。水平集方法的數值實現的關鍵就是要把定義于連續空間的偏微分方程進行離散化，使得計算機可執行計算。常見的偏微分方程數值解方法有有限差分法、有限元法、譜法等。在圖像處理中，待分割的圖像是在二維空間中以離散點的形式表達的，這主要是因為數字圖像的空間定義域是二維等間隔離散化的點集，構成了有限差分法所需的等分網格，使用（i, j）作為網格的坐標。因此，有限差分法是圖像處理中最為常用的一種數值求解方法。

有限差分法的基本思想是使用離散化的差分近似地代替微分。有限差分法是在離散情況下對于偏微分方程的近似求解，其精度必然低于偏微分方程的解析解。

對于偏導數，當步長Δx足夠小時，將其用泰勒公式展開可得到如下式子：

則

式中，O（Δx）為Δx的同價無窮小量。

同理，可得到另外兩個展開式：

通過以上分析，可知有限差分有三種格式，即前向差分（forward difference）、后向差分（backward difference）和中心差分（central difference），分別如下：

可以證明，前向差分和后向差分具有一階精度，中心差分具有二階精度。對于偏微分方程中的二階偏導數，可采用中心差分先求兩個半點()處的一階偏導數，得

將上面兩個一階差分作中心差分，得到二階偏導數的近似表達式為

同理可以得到的表達式，同樣使用中心差分計算二階偏導數為

其中，各“半點”處的函數值近似如下：

結合式（2-43）和式（2-44），可得二階偏導數的近似表達式為

利用有限差分法的思想近似地表達偏微分方程中的導數，可將偏微分方程轉化為計算機可計算的離散化的代數方程。選取一個合適的數值方案，就可以實現方程的演化。根據建立代數方程時選用的方法不同，數值實現方案可分為顯式、隱式和半隱式三類。使用一維Burgers方程對幾種常用的有限差分法的數值實現方案進行介紹。

1）顯式方案

對方程左邊進行關于時間變量t的向前差分，對方程右邊可以采用關于空間變量x的向前、向后或中心差分。全都使用n時刻的數據進行表達，即

這樣就可以求出第n+1時刻的未知數據，這種方案為顯式方案。

2）隱式方案

根據上述方程建立差分方程時，方程右側都使用n+1時刻的數據構造，即

在已知的情況下，得到具有N個未知數的N個方程構成的聯立代數方程組，這樣的方案被稱為隱式方案。

3）半隱式方案

同樣在上述方程中，與函數u有關的數據，一部分使用n+1時刻的數據，其余部分使用n時刻的數據，這種方案就是半隱式方案。

半隱式方案得到的代數方程組是線性的，但也能夠近似為線性的差分方程，并具有計算簡便和高穩定性的優點，因此被廣泛應用于偏微分方程的數值計算中。