兩種分水嶺分割法的比較

任智格

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

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

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

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

（3-1）

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

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

（3-2）

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

（3-3）

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

（3-4）

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

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

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

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

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

1.第一種方法[1]

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

圖1

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

2.第二種算法[3]

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

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

3.實(shí)例分析

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

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

4.結(jié)論

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

參考文獻(xiàn)：

[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)學(xué)分水嶺算法的圖像分割[J].通信技術(shù)，2009，42（5）：99-102.