改進(jìn)的分水嶺算法在圖像分割中的研究

王改云，楊小娟

（桂林電子科技大學(xué) 電子工程與自動(dòng)化學(xué)院，廣西 桂林 541004）

圖像分割是計(jì)算機(jī)視覺(jué)研究中的一個(gè)極為重要的基本問(wèn)題，是由圖像處理到圖像分析的關(guān)鍵步驟“分割結(jié)果的優(yōu)劣直接影響到隨后的圖像分析!理解和景物恢復(fù)問(wèn)題求解的正確與否”圖像分割技術(shù)的發(fā)展與許多其它學(xué)科密切相關(guān)，例如電子學(xué)，計(jì)算機(jī)科學(xué)，醫(yī)學(xué)，數(shù)學(xué)等學(xué)科等隨著各學(xué)科新理論和新方法的提出，人們也提出了許多結(jié)合一些特定理論方法和工具的分割技術(shù)[1]。

雖然目前上千種圖像分割算法但還沒(méi)有一種普適性方法來(lái)解決所有圖像分割問(wèn)題，而且迄今為止，也沒(méi)有一種完善的理論來(lái)指導(dǎo)如何根據(jù)圖像特點(diǎn)來(lái)選擇合適的分割方法。國(guó)內(nèi)外學(xué)者在對(duì)圖像分割方法的不斷研究中，主要將傳統(tǒng)圖像分割方法進(jìn)行不斷的改進(jìn)，以及結(jié)合新理論新概念研究出新的可行的分割方法[2]。

經(jīng)過(guò)研究發(fā)現(xiàn)目前普遍的分水嶺算法存在如下缺點(diǎn)：1）對(duì)圖像中的噪聲極敏感，輸入圖像通常是圖像梯度，而原始圖像中的噪聲能直接惡化圖像的梯度，易于造成分割輪廓偏移；2）易于產(chǎn)生過(guò)分割。由于受噪聲、量化誤差以及區(qū)域內(nèi)紋理細(xì)節(jié)的影響，因此會(huì)產(chǎn)生很多局部最小值，在后續(xù)分割中將出現(xiàn)大量細(xì)小區(qū)域；3）對(duì)低對(duì)比度圖像易丟失重要輪廓。在此情況下，區(qū)域邊界像素的梯度值也較低，那么目標(biāo)的重要輪廓容易丟失[8]。

基于分水嶺算法的圖像分割逐漸受到了人們重視，它是幾年發(fā)展起來(lái)的形態(tài)學(xué)分割方法，它的分割思想至今仍是廣大學(xué)者關(guān)注的研究熱點(diǎn)，在圖像分割方法中占有一席之地。

1 分水嶺算法

分水嶺分割方法是近些年被人們廣泛應(yīng)用的一種基于拓?fù)淅碚摰臄?shù)學(xué)形態(tài)學(xué)的分割方法，基本思想是把圖像看作是測(cè)地學(xué)上的拓?fù)涞孛玻瑘D像中每一點(diǎn)像素的灰度值表示該點(diǎn)的海拔高度，每一個(gè)局部極小值及其影響區(qū)域稱為集水盆，而集水盆的邊界則形成分水嶺。分水嶺的概念和形成可以通過(guò)模擬浸入過(guò)程來(lái)說(shuō)明。在每一個(gè)局部極小值表面，刺穿一個(gè)小孔，然后把整個(gè)模型慢慢浸入水中，隨著浸入的加深，每一個(gè)局部極小值的影響域慢慢向外擴(kuò)展，在2個(gè)集水盆匯合處構(gòu)筑大壩，即形成分水嶺。分水嶺的計(jì)算過(guò)程是一個(gè)迭代標(biāo)注過(guò)程，比較經(jīng)典的計(jì)算方法是L.Vincent提出的。分水嶺算法包含排序和浸水2個(gè)過(guò)程，其中排序過(guò)程按照像素的灰度進(jìn)行排序，以便直接訪問(wèn)同一高度的像素：在浸水過(guò)程中，假設(shè)高度小于等于h的像素的貯水盆地已經(jīng)標(biāo)記出來(lái)了，則在處理高度為h+1的像素時(shí)，將這一層中與已標(biāo)記的貯水盆地相鄰的像素送入先入先出隊(duì)列，再由這些像素開(kāi)始，根據(jù)測(cè)地距離,將已經(jīng)標(biāo)記的貯水盆地?cái)U(kuò)展至h+1層；然后，通過(guò)掃描，將h+1層中可能存在的區(qū)域最小值賦予新的標(biāo)號(hào)；最后，在分水嶺變換的結(jié)果中，同一標(biāo)號(hào)的像素屬于同一貯水盆地,而將距不同貯水盆地距離相等的像素標(biāo)為分水嶺點(diǎn)。分水嶺變換得到的是輸入圖像的集水盆圖像，貯水盆之間的邊界點(diǎn)，即為分水嶺[3]。

顯然，分水嶺表示的是輸入圖像極大值點(diǎn)。因此，為得到圖像的邊緣信息，通常把梯度圖像作為輸入圖像，即數(shù)學(xué)表達(dá)如下：

式中，f（x，y）表示原始圖像，grad（，）表示梯度運(yùn)算。

令 M1，M2，…，MR 為表示圖像 g（x，y）的局部最小值點(diǎn)的坐標(biāo)的集合。令G（Mi）為一個(gè)點(diǎn)的坐標(biāo)的集合，這些點(diǎn)位于與局部最小值Mi（回想無(wú)論哪一個(gè)匯水盆地內(nèi)的點(diǎn)都組成一個(gè)連通分量）相聯(lián)系的匯水盆地內(nèi)。符號(hào)min和max代表g（x，y）的最小值和最大值。最后，令 T[n]表示坐標(biāo)（s，t）的集合，其中 g（s，t）＜n，即

在幾何上，T[n]是 g（x，y）中的點(diǎn)的坐標(biāo)集合，集合中的點(diǎn)均位于平面g（x，y）=n的下方。隨著水位以整數(shù)量從n=min+1到n=max+1不斷增加，圖像中的地形會(huì)被水漫過(guò)。在水位漫過(guò)地形的過(guò)程中的每一階段，算法都需要知道處在水位之下的點(diǎn)的數(shù)目。從概念上來(lái)說(shuō)，假設(shè)T[n]中的坐標(biāo)處在g（x，y）=n平面之下，并被“標(biāo)記”為黑色，所有其他的坐標(biāo)被標(biāo)記為白色。然后，當(dāng)我們?cè)谒灰匀我庠隽縩增加的時(shí)候，從上向下觀察xy平面，會(huì)看到一幅二值圖像。在圖像中黑色點(diǎn)對(duì)應(yīng)于函數(shù)中低于平面g（x，y）=n的點(diǎn)。這種解釋對(duì)于理解下面的討論很有幫助。

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

對(duì)于這個(gè)結(jié)果幾何上的解釋是很簡(jiǎn)單的。只需在水溢出的第n個(gè)階段使用“與(AND)”算子將T[n]中的二直圖像分離出來(lái)即可。T[n]是與局部最小值Mi相聯(lián)系的集合。接下來(lái)，令C[n]表示在第n個(gè)階段匯水盆地被水淹沒(méi)的部分的合集：

然后令C[max+1]為所有匯水盆地的合集：

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

找尋分水線的算法開(kāi)始時(shí)設(shè)定C[min+1]=T[min+1] （9）

然后算法進(jìn)入遞歸調(diào)用，假設(shè)在第n步時(shí)，已經(jīng)構(gòu)造了C[n-1]。根據(jù)C[n-1]求得C[n]的過(guò)程如下：令Q代表T[n]中連通分量的集合。然后，對(duì)于每個(gè)連通分量q∈Q[n]，有下列3種可能性：

根據(jù)C［n-1］構(gòu)造C［n］]取決于這3個(gè)條件。當(dāng)遇到一個(gè)新的最小值時(shí)符合條件（a），則將 q 并人 C［n-1］構(gòu)成 C［n］。當(dāng)q位于某些局部最小值構(gòu)成的匯水盆地中時(shí)，符合條件（b），此時(shí)將 q 合并入 C［n-1］構(gòu)成 C［n］。 當(dāng)遇到全部或部分分離2個(gè)或更多匯水盆地的山脊線的時(shí)候，符合條件（c）。進(jìn)一步的注水會(huì)導(dǎo)致不同盆地的水聚合在一起，從而使水位趨于一致。因此，必須在q內(nèi)建立一座水壩（如果涉及多個(gè)盆地就要建立多座水壩）以阻止盆地內(nèi)的水溢出。正如前一節(jié)中的解釋，當(dāng)用3×3個(gè)1的結(jié)構(gòu)元素膨脹q∩C[n-1]并且需要將這種膨脹限制在q內(nèi)時(shí)，一條一個(gè)像素寬度的水壩是能夠構(gòu)造出來(lái)的。通過(guò)使用與g（x，y）中存在的灰度級(jí)值相對(duì)應(yīng)的n值，可以改善算法效率；根據(jù)g（x，y）的直方圖，可以確定這些值及其最小值和最大值[4]。

此次研究是基于數(shù)學(xué)形態(tài)學(xué)的分割算法，在對(duì)圖像去噪的前提下進(jìn)行分水嶺圖像分割方法處理，可以比較有效的消除過(guò)分割現(xiàn)象。

2 仿 真

本文中以土豆圖像為例，該圖像中多個(gè)對(duì)象相連,我們所要達(dá)到的目的就是在圖像分割后被分割成多個(gè)獨(dú)立對(duì)象,由于選取的圖片本身比較模糊，要先進(jìn)行處理，原圖如圖1所示。

圖1 原始圖像Fig.1 Original image

圖2 經(jīng)過(guò)預(yù)處理的對(duì)比圖Fig.2 After comparing the graph preprocessing

中值濾波效果較好，經(jīng)過(guò)中值濾波后原先模糊的圖片可以變得更清晰，方便后續(xù)處理。如圖3運(yùn)用巴特沃斯低通濾波和中值濾波，接下來(lái)利用函數(shù)Info=im finfo（filename）；

從圖3看到形象生動(dòng)的原始分水嶺圖像和中值濾波處理后的分水嶺圖像，接下來(lái)構(gòu)造結(jié)構(gòu)元素（Structuring element），用分水嶺來(lái)增強(qiáng)圖像中感興趣的對(duì)象，結(jié)構(gòu)元素就是好比是一張小圖像，通常用于圖像的形態(tài)學(xué)運(yùn)算（如膨脹、腐蝕、開(kāi)運(yùn)算、閉運(yùn)算）[5]。在此次研究中，先設(shè)置參數(shù)，創(chuàng)建se=stel（‘disk,40）結(jié)構(gòu)，再對(duì)去噪后圖像進(jìn)行銳化增強(qiáng)，并且用bottom-hat來(lái)增強(qiáng)圖像對(duì)比度。利用Itop函數(shù)處理如圖4所示。

圖3 分水嶺對(duì)比圖Fig.3 Comparison chart ofWatershed

圖4 增強(qiáng)處理Fig.4 Enhancement

可是會(huì)從圖4發(fā)現(xiàn)，對(duì)象間隙比較緊密，為了達(dá)到更好分割效果，我們要增大間隙，還要再用imcomplement函數(shù)增強(qiáng)圖像中感興趣對(duì)象。

圖5 增大間隙和感興趣對(duì)象Fig.5 Increase the gap and the objectof interest

由圖5（a）發(fā)現(xiàn)圖像對(duì)象間隙明顯增大，較好的達(dá)到了預(yù)期效果。再利用rgb函數(shù)所得分水嶺如圖7所示。

圖6 temin圖和rag分水嶺圖Fig.6 temin image and ragerwater image

圖7 濾波前后對(duì)比圖Fig.7 Filter before and after comparison chart

由圖7可以看出經(jīng)過(guò)上述一系列處理后分割的更清楚，而且分水嶺分割會(huì)將本來(lái)連在一起的圖像分開(kāi)成單獨(dú)的圖像，達(dá)到較為理想的效果。

3 結(jié)束語(yǔ)

為了克服傳統(tǒng)分水嶺算法的缺點(diǎn)，已經(jīng)有很多學(xué)者努力進(jìn)行了相關(guān)研究，并且提出了一些改進(jìn)型分水嶺算法，并成功應(yīng)用到相關(guān)應(yīng)用領(lǐng)域。例如一些將分水嶺算法與其他方法相融合，為解決項(xiàng)目中遇到的實(shí)際問(wèn)題提供了思路。不過(guò)因?yàn)樵诔跏挤指顣r(shí)盡量抑制噪聲和細(xì)密紋理的影響，同時(shí)還要保留重要輪廓，這將成為解決傳統(tǒng)分水嶺算法問(wèn)題的根本途徑，相信隨著人們的不斷深入探索和進(jìn)一步研究，會(huì)出現(xiàn)更多更好更有效的解決方法。

[1]王鳳娥.改進(jìn)后的分水嶺算法在圖象分割中的應(yīng)用研究[D].濟(jì)南：山東大學(xué)，2008.

[2]徐琳俊.數(shù)字圖像分割算法研究[D].濟(jì)南:山東大學(xué)，2013.

[3]徐偉，王希常，鄭志寬.一種基于改進(jìn)分水嶺算法的圖像分割算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2008，18（12）:38-40.XU Wei， WANG Xi-chang， ZHENG Zhi-kuan.A segmentation algorithm for image based on improved watershed algorithm[J]. Computer Technology and Development，2008，18（12）:38-40.

[4]Rafael C.Gonzalez.Richard E.Woods數(shù)字圖像處理[M].北京：電子工業(yè)出版社，2011.

[5]唐曉強(qiáng)，賴惠成.形態(tài)學(xué)結(jié)構(gòu)元素選取算法的研究[J].通信技術(shù)，2010，223（7）：161-162.TANGXiao-qiang，LAIHui-cheng.Research on communication technology of[J].algorithm selects the structure element of mathematicalmorphology，2010，223（7）:161-162.

[6]羅勇.改進(jìn)后的分水嶺算法在圖象分割中的應(yīng)用研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2003.

[7]YongRui，HuangTS.Content-Based Image Retrieval with Relevance FeedbackinMARs[J].ICIP， 1997，2:815-818.

[8]刁智華，趙春江.分水嶺算法的改進(jìn)研究[J].計(jì)算機(jī)工程，2010，36（17）:10-12.DIAO Zhi-hua，ZHAO Chun-jiang.Study on the improvement ofwatershed algorithm[J].Computer Engineering， 2010， 36（17）:10-12.

[9]岡薩雷斯.數(shù)字圖像處理（MATLAB版）[M].北京：電子工業(yè)出版社，2005.