任智格

【摘 要】本文通過介紹分水嶺的數(shù)學意義、 BCUCHER基于有向箭頭的有序算法與基于形態(tài)學濾波預(yù)處理和形態(tài)學梯度重建的分水嶺圖像分割方法，并比較了他們的計算復(fù)雜性，且在MATLAB的環(huán)境下進行了驗證知第二種方法在圖像分割中的應(yīng)用較好，降底了時間復(fù)雜度。

【關(guān)鍵詞】分水嶺；有序算法；計算復(fù)雜性；時間復(fù)雜度

分水嶺分割方法的基本思想是：假設(shè)在每個區(qū)域最小值的位置上打一個洞并且讓水以均勻的上升速率從洞中涌出，從低到高淹沒整個地形。當處在不同的匯聚盆地中的水將要聚合在一起時，修建的大壩將阻止聚合，水將只能到達大壩的頂部處于水線之上的程度。這些大壩的邊界對應(yīng)于分水嶺的分割線。在求解圖像問題方面，關(guān)鍵概念是將初始圖像變成另一幅圖像，在變換后的圖像中，匯水盆地就是我們想要識別的對象或區(qū)域。

數(shù)學描述：令，，…，為表示圖像的局部最小值點的坐標的集合。它屬于一幅典型的梯度圖像。令為一個點的坐標的集合，這些點位于與局部最小值相聯(lián)系的匯水盆地內(nèi)。符號min和max代表的最小值和最大值。最后，令表示坐標的集合，其中，即：

（3-1）

在幾何上，是中的點的坐標集合，集合中的點均位于平面的下方。隨著水位以整數(shù)量從到不斷增加，圖像中的地形會被水漫過。在水位漫過地形的過程中的每一階段，算法都需要知道處在水位之下的點的數(shù)目。從概念上來說，假設(shè)中的坐標處在平面之下，并被“標記”為黑色，所有其他的坐標被標記為白色。然后，當我們在水位以任意增量增加的時候，從上向下觀察平面，會看到一幅二值圖像。在圖像中黑色點對應(yīng)于函數(shù)中低于平面的點。這種解釋對于理解下面的討論很有幫助。

令表示匯水盆地中點的坐標的集合。這個盆地與在第階段被淹沒的最小值有關(guān)。參考前一段的討論，也可以被看作由下式給出的二值圖像

（3-2）

換句話說，如果且則在位置有。否則。對于這個結(jié)果幾何上的解釋是很簡單的。我們只需在水溢出的第個階段使用“與（AND）”算子將中的二值圖像分離出來即可。是與局部最小值相聯(lián)系的集合。令表示在第個階段匯水盆地被水淹沒的部分的合集：

（3-3）

然后令為所有匯水盆地的合集：

（3-4）

可以看出處于和中的元素在算法執(zhí)行期間是不會被替換的，而且這兩個集合中的元素的數(shù)目與保持同步增長。因此，是集合的子集。根據(jù)式（3-2）和（3-3），是的子集，所以也是的子集。從這個結(jié)論我們可以得出重要的結(jié)果：中的每個連通分量都恰好是的一個連通分量。

找尋分水線的算法開始時設(shè)定。然后算法進入遞歸調(diào)用，假設(shè)在第步時，已經(jīng)構(gòu)造了。根據(jù)求得的過程如下：

令表示中連通分量的集合。然后，對于每個連通分量，有下列三種可能性[2]：（1）為空；（2）包含中的一個連通分量；（3）包含多于一個的連通分量。

根據(jù)構(gòu)造取決于這3個條件。當遇到一個新的最小值時，符合條件（1）時，則將并入構(gòu)成。當位于某些局部最小值構(gòu)成的匯水盆地中時，符合條件（2），此時將合并到構(gòu)成。當遇到全部或部分分離兩個或更多匯水盆地的山脊線的時候，符合條件（3）。進一步的注水會導(dǎo)致不同盆地的水聚合在一起，從而使水位趨于一致。因此，必須在內(nèi)建立一座水壩（如果涉及多個盆地就要建立多座水壩）以阻止盆地內(nèi)的水溢出。當用個1的結(jié)構(gòu)元素膨脹并且需要將這種膨脹限制在內(nèi)時，一條一個像素寬度的水壩是能構(gòu)造出來的。

通過使用與中存在的灰度級值相對應(yīng)的值，可以改善算法效率；根據(jù)的直方圖，可以確定這些值及其最小值和最大值。

1.第一種方法[1]

BCUCHER還提出了一種基于有向箭頭的有序算法。算法有三個主要步驟：首先，找到圖像中的區(qū)域最小值像素點（這些像素的領(lǐng)接像素的灰度值都不小于當前像素的灰度值）。然后，對于每一對像素，如果的灰度值嚴格大于，那么用一個箭頭從指向，如圖1.這樣就可以用一種簡潔的方式表示像素的領(lǐng)接的情況。最后，對區(qū)域最小值標記編號，并根據(jù)第二步中的箭頭將這個標記值進行擴展。這種算法比前面的算法計算的速度快，但計算的結(jié)果也不是十分的精確。

圖1

上述的這種方法存在幾個問題：第一，運算量巨大，都必須連續(xù)的對整幅圖像進行連續(xù)的多次掃描，非常的消耗時間。第二，迭代次數(shù)很不確定，并且每一次迭代都可能會對全圖進行掃描，這樣迭代次數(shù)可能十分巨大。所以此方法對圖像處理的運算效率是非常低的。

2.第二種算法[3]

一種基于形態(tài)學濾波預(yù)處理和形態(tài)學梯度重建的分水嶺圖像分割方法。首先通過形態(tài)學濾波對圖像進行濾波預(yù)處理，再求取圖像的形態(tài)學梯度，之后對梯度圖像進行開閉濾波重建。在簡化梯度圖像的同時，保持了輪廓分水線的準確定位，消除了產(chǎn)生過分割現(xiàn)象的根源，最后對重建后的梯度圖像運用基于標記約束的分水嶺算法進行分割。

分割過程可描述為：（1）對待分割圖像進行形態(tài)學濾波；（2）計算濾波后圖像的形態(tài)學梯度；（3）對梯度圖像進行重建；（4）對重建后的梯度圖像進行基于標記約束的分水嶺 變換。

3.實例分析

用Matlab分割圖像的結(jié)果是：

可以看出過分割得到了更好的抑制，同時邊緣定位也比較準確，分割精度有了很大的改善，降底了算法的時間復(fù)雜度，所用時間比前一種方法少。

4.結(jié)論

本文通過介紹分水嶺的數(shù)學意義，論述BCUCHER的基于有向箭頭的有序算法與基于形態(tài)學濾波預(yù)處理和形態(tài)學梯度重建的分水嶺圖像分割方法，并對這兩種算法進行了計算復(fù)雜性的比較，且在MATLAB的環(huán)境下進行了驗證，得出的結(jié)論是：第二種方法在圖像分割中的應(yīng)用較好，降底了時間復(fù)雜度。但這兩種方法都有可能產(chǎn)生過分割的情況，現(xiàn)在還不能找到避免此情況的方法，這有待我們進一步發(fā)展。

參考文獻：

[1]吳海波.基于分水嶺和水平集方法的圖像分割算法研究[OL].（2012-02-27）.http：//www.doc88.com/p-846684201742.html.

[2]于慶剛.基于小波變換和分水嶺算法的圖像分割算法的研究[OL].（2012-04-07）.http：//www.doc88.com/p-084413955276.html.

[3]姬寶金，呂建平.基于梯度重建與形態(tài)學分水嶺算法的圖像分割[J].通信技術(shù)，2009，42（5）：99-102.