分水嶺分割演算法

A. 分水嶺演算法的應用

數學形態學一個應用是分水嶺演算法，為了便於理解，可以將圖像的灰度空間與地球表面的地形高度相類比，據此，發明了應用於圖像領域的分水嶺演算法。

假設，如下圖所示的一個島嶼，要從 點走到 點，虛線所表示的是最短的直線距離，也就是歐式距離，考慮到現實情況，不能穿過水面到達目標地點，所以，能夠從起點到終點的實際通行路線中最短的距離成為測地線距離。

通過以上分析，給出測地線距離的定義：

給定指定連通域 ,測地線距離就是 中兩個像素點 和 之間的最短（可執行）路徑的長度，用公式定義如下：

如下圖所示，假定一個連通域 包含了若干個子區域 ，用公式表示 所表示的測地線影響域為：

以上公式可以理解為，區域 中的像素點到 域的測地線距離比其他域更小的點的軌跡的集合，也就是以 域中的種子點出發，其測地線距離比其他域的種子點都要小的點集所構成的區域。如下圖所示:

SKIZ表示區域 中的點不屬於任何一個測地線影響域，也就是域 中的點到兩個測地線影響域的中測地線距離相等。區域 中構成 的SKIZ，記作 ，用公式的表述如下：

注意：， 表示區域 以外的 中的所有點的集合集合

如下圖所示的山脈地形圖，包含山谷和山峰，在水平面不斷上升的過程中，會逐漸淹沒掉一些較低的區域，而為了防止水溢出，需要不斷在山脊上修建大壩，這個過程不斷進行，最後會得到一個區域分割的效果。

在一副圖像上實現分水嶺演算法，與上述過程相似，只不過是通過灰度值充當水平面的角色，對圖像進行不斷的填埋，最後得到區域分割的效果圖。

如上圖所示的動畫中，不斷用灰度值代表的水平面淹沒圖像中的最小值，最後得到分割後的圖像。綜上，分水嶺演算法的步驟可以總結如下：

如下圖所示，另外一種分水嶺演算法的原理是，指定初始的種子點，只對種子點所在的鄰域像素進行分類，而不考慮其他區域。

如下圖所示的圖片，以最小點開始，進行分水嶺演算法，會將整幅圖分割成許多小區域，造成過分割的效果。為了解決這一問題，有以下三種解決方案：

最後，通過合並一些小區域再利用分水嶺演算法進行分割的效果如下圖所示：

如下圖所示，展示了通過分水嶺演算法分割血細胞的流程：

B. 分水嶺的計算過程

分水嶺的計算過程是一個迭代標注過程。分水嶺比較經典的計算方法是L. Vincent提出的。在該演算法中，分水嶺計算分兩個步驟，一個是排序過程，一個是淹沒過程。首先對每個像素的灰度級進行從低到高排序，然後在從低到高實現淹沒過程中，對每一個局部極小值在h階高度的影響域採用先進先出(FIFO)結構進行判斷及標注。
分水嶺變換得到的是輸入圖像的集水盆圖像，集水盆之間的邊界點，即為分水嶺。顯然，分水嶺表示的是輸入圖像極大值點。因此，為得到圖像的邊緣信息，通常把梯度圖像作為輸入圖像，即
g(x,y)=grad(f(x,y))={[f(x,y)-f(x-1,y)]2[f(x,y)-f(x,y-1)]2}0.5
式中，f(x,y)表示原始圖像，grad{.}表示梯度運算。
分水嶺演算法對微弱邊緣具有良好的響應，圖像中的雜訊、物體表面細微的灰度變化，都會產生過度分割的現象。但同時應當看出，分水嶺演算法對微弱邊緣具有良好的響應，是得到封閉連續邊緣的保證的。另外，分水嶺演算法所得到的封閉的集水盆，為分析圖像的區域特徵提供了可能。
為消除分水嶺演算法產生的過度分割，通常可以採用兩種處理方法，一是利用先驗知識去除無關邊緣信息。二是修改梯度函數使得集水盆只響應想要探測的目標。
為降低分水嶺演算法產生的過度分割，通常要對梯度函數進行修改，一個簡單的方法是對梯度圖像進行閾值處理，以消除灰度的微小變化產生的過度分割。即
g(x,y)=max(grad(f(x,y)),gθ)
式中，gθ表示閾值。
程序可採用方法：用閾值限制梯度圖像以達到消除灰度值的微小變化產生的過度分割，獲得適量的區域，再對這些區域的邊緣點的灰度級進行從低到高排序，然後在從低到高實現淹沒的過程，梯度圖像用Sobel運算元計算獲得。對梯度圖像進行閾值處理時，選取合適的閾值對最終分割的圖像有很大影響，因此閾值的選取是圖像分割效果好壞的一個關鍵。缺點：實際圖像中可能含有微弱的邊緣，灰度變化的數值差別不是特別明顯，選取閾值過大可能會消去這些微弱邊緣。

C. 分水嶺演算法的介紹

所謂分水嶺演算法有好多種實現演算法，拓撲學，形態學，浸水模擬和降水模擬等方式。要搞懂就不容易了。Watershed Algorithm(分水嶺演算法)，顧名思義，就是根據分水嶺的構成來考慮圖像的分割。現實中我們可以或者說可以想像有山有湖的景象，那麼那一定是水繞 山，山圍水的情形。當然在需要的時候，要人工構築分水嶺，以防集水盆之間的互相穿透。而區分高山（plateaus）與水的界線，以及湖與湖之間的間隔或 都是連通的關系，就是我們可愛的分水嶺（watershed）。為了得到一個相對集中的集水盆，那麼讓水漲到都接近周圍的最高的山頂就可以了，再漲就要漏 水到鄰居了，而鄰居，嘿嘿，水質不同誒，會混淆自我的。那麼這樣的話，我們就可以用來獲取邊界灰階大，中間灰階小的物體區域了，它就是集水盆。

D. 分水嶺演算法的產生與發展過程

分水嶺的計算過程是一個迭代標注過程.分水嶺比較經典的計算方法是L.Vincent為消除分水嶺演算法產生的過度分割,通常可以採用兩種處理方法,一是利用先驗知識

E. 圖像分割最好方法

1.基於閾值的分割方法

閾值法的基本思想是基於圖像的灰度特徵來計算一個或多個灰度閾值，並將圖像中每個像素的灰度值與閾值作比較，最後將像素根據比較結果分到合適的類別中。因此，該方法最為關鍵的一步就是按照某個准則函數來求解最佳灰度閾值。

閾值法特別適用於目標和背景占據不同灰度級范圍的圖。圖像若只有目標和背景兩大類，那麼只需要選取一個閾值進行分割，此方法成為單閾值分割；但是如果圖像中有多個目標需要提取，單一閾值的分割就會出現作物，在這種情況下就需要選取多個閾值將每個目標分隔開，這種分割方法相應的成為多閾值分割。
2.基於區域的圖像分割方法

基於區域的分割方法是以直接尋找區域為基礎的分割技術，基於區域提取方法有兩種基本形式：一種是區域生長，從單個像素出發，逐步合並以形成所需要的分割區域；另一種是從全局出發，逐步切割至所需的分割區域。
分水嶺演算法

分水嶺演算法是一個非常好理解的演算法，它根據分水嶺的構成來考慮圖像的分割，現實中我們可以想像成有山和湖的景象，那麼一定是水繞山山圍水的景象。

分水嶺分割方法，是一種基於拓撲理論的數學形態學的分割方法，其基本思想是把圖像看作是測地學上的拓撲地貌，圖像中每一點像素的灰度值表示該點的海拔高度，每一個局部極小值及其影響區域稱為集水盆，而集水盆的邊界則形成分水嶺。分水嶺的概念和形成可以通過模擬浸入過程來說明。在每一個局部極小值表面，刺穿一個小孔，然後把整個模型慢慢浸入水中，隨著浸入的加深，每一個局部極小值的影響域慢慢向外擴展，在兩個集水盆匯合處構築大壩，即形成分水嶺。