沈夏炯，吳曉洋，韓道軍

（河南大學(xué)數(shù)據(jù)與知識(shí)工程研究所，河南 開(kāi)封 475004）

分利用綜合距離度量

分水嶺分割算法研究綜述

沈夏炯，吳曉洋，韓道軍

（河南大學(xué)數(shù)據(jù)與知識(shí)工程研究所，河南 開(kāi)封 475004）

傳統(tǒng)分水嶺分割算法存在過(guò)分割和對(duì)噪音敏感等問(wèn)題，為此，研究者針對(duì)算法中前處理和后處理過(guò)程分別展開(kāi)研究。介紹自上而下的模擬降水算法和自下而上的模擬泛洪算法，分析待輸入梯度圖像的重構(gòu)處理過(guò)程、分割后區(qū)域的合并處理過(guò)程以及前后結(jié)合處理過(guò)程，歸納前、后處理及前后結(jié)合處理的分水嶺分割算法改進(jìn)，評(píng)價(jià)改進(jìn)效果，總結(jié)并提出待解決的研究方向及解決思路。

分水嶺分割；過(guò)分割；前處理；后處理；梯度重構(gòu)；區(qū)域合并

DO I：10.3969/j.issn.1000-3428.2015.10.006

1 概述

分水嶺分割算法建立在數(shù)學(xué)形態(tài)學(xué)的理論基礎(chǔ)之上，模擬的是立體的地形表面，屬于一種基于區(qū)域的圖像分割方法［1］。在遙感領(lǐng)域，改進(jìn)的分水嶺分割算法廣泛應(yīng)用于遙感影像分割尤其是高分辨率遙感影像的分割［2］；在醫(yī)學(xué)領(lǐng)域，改進(jìn)的分水嶺分割算法廣泛應(yīng)用于彩色白細(xì)胞分割、磁共振腦圖像分割、組織細(xì)胞分割、乳腺癌粘連細(xì)胞分割等［3］；在智能識(shí)別領(lǐng)域，改進(jìn)的分水嶺分割算法廣泛應(yīng)用于圖像目標(biāo)識(shí)別、多目標(biāo)車(chē)輛跟蹤、道路識(shí)別、路面裂縫檢測(cè)等［4］。

分水嶺分割算法的發(fā)展趨勢(shì)可以歸納如下：（1）隨著遙感影像分辨率的提高，地物類(lèi)型也變得更加復(fù)雜，傳統(tǒng)的基于像元的分類(lèi)技術(shù)已經(jīng)不能滿(mǎn)足需要，而分水嶺分割算法對(duì)于復(fù)雜的地物能夠產(chǎn)生較好的分割效果［5］。此外，現(xiàn)階段的醫(yī)學(xué)影像普遍具有信息量大且要求分割精確，分水嶺分割算法可以很好地滿(mǎn)足這一分割要求［6］。故在應(yīng)用領(lǐng)域方面，發(fā)展趨勢(shì)傾向于遙感和醫(yī)學(xué)影像應(yīng)用。（2）到目前為止，分水嶺分割算法的改進(jìn)方法有很多，但這些改進(jìn)方法并不適用于所有的圖像，往往是根據(jù)特定的應(yīng)用背景進(jìn)行改進(jìn)［7］。故在使用方面，發(fā)展趨勢(shì)傾向于如何根據(jù)目標(biāo)圖像的特征選擇合適的改進(jìn)方

法；（3）圖像分割是圖像處理中很重要的一個(gè)操作，如何評(píng)價(jià)圖像分割的優(yōu)良是至關(guān)重要的，一些文獻(xiàn)也提出了一些評(píng)價(jià)標(biāo)準(zhǔn)［8］，然而目前尚沒(méi)有一個(gè)完整、完善的評(píng)價(jià)機(jī)制。故在評(píng)價(jià)方面，發(fā)展趨勢(shì)傾向于如何制定一個(gè)規(guī)范的評(píng)價(jià)標(biāo)準(zhǔn)來(lái)評(píng)定分割效果的優(yōu)良；（4）由于大數(shù)據(jù)量圖像的廣泛應(yīng)用以及算法因不斷改進(jìn)而復(fù)雜性增加，導(dǎo)致算法的運(yùn)算效率和準(zhǔn)確性降低［9］。故在改進(jìn)方法的目標(biāo)方面，發(fā)展趨勢(shì)傾向于并行計(jì)算和智能計(jì)算方向。

并行計(jì)算和智能計(jì)算等新型計(jì)算模式的出現(xiàn)為分水嶺分割算法效率的提高和過(guò)分割問(wèn)題的減少提供了一種新的解決思想。并行計(jì)算是提高處理能力和計(jì)算速度的一種有效方法，目前MPI［10］和GPU［11］等并行計(jì)算技術(shù)已經(jīng)在分水嶺分割算法中得到應(yīng)用，在圖像的數(shù)據(jù)量較大時(shí)取得了不錯(cuò)的效果。在智能計(jì)算算法中，遺傳算法［12］、粒子群算法［13］具有找到全局最優(yōu)的能力，可以很好地解決分水嶺分割算法中如何選擇最優(yōu)閾值的問(wèn)題，從而使分割的結(jié)果更加精確、合理，減少了過(guò)分割現(xiàn)象。

Luc Vincent和Pierre Soille于1991年提出了基于淹沒(méi)的分水嶺分割算法。此算法使用像素隊(duì)列來(lái)模擬洪水上漲過(guò)程，經(jīng)過(guò)驗(yàn)證該算法比當(dāng)時(shí)現(xiàn)有算法精度更高且速度更快［14］。Smet P D和Pires R L于2000年提出了基于降水的分水嶺分割算法［15］。為了克服分水嶺分割算法的缺點(diǎn)，比如容易丟失重要輪廓、過(guò)分割現(xiàn)象比較嚴(yán)重等，學(xué)者們進(jìn)行了大量的研究，并提出了很多改進(jìn)方法。根據(jù)分水嶺分割算法的不同時(shí)段，將其改進(jìn)劃分為前處理改進(jìn)、后處理改進(jìn)和前、后結(jié)合處理改進(jìn)，這些改進(jìn)在一定程度上克服了過(guò)分割嚴(yán)重等問(wèn)題，但是由于應(yīng)用的廣泛性，尚未從根本上解決過(guò)分割和噪聲敏感等問(wèn)題。本文在現(xiàn)有分水嶺分割算法研究的基礎(chǔ)上，對(duì)分水嶺分割算法進(jìn)行綜述，為以后學(xué)者對(duì)該算法的研究提供支持。

2 傳統(tǒng)的分水嶺分割算法

分水嶺分割算法早期來(lái)源于地理學(xué)，將圖像模擬或想象成為一個(gè)地形圖，地形圖的山脊即為圖像的分水嶺。源于此思想，產(chǎn)生了著名的2種分水嶺分割算法：自上而下的模擬降水算法和自下而上的模擬泛洪算法。

自上而下的模擬降水算法原理如下：

（1）將圖像理解成為一個(gè)如圖1所示的地形圖。

圖1 自上而下的模擬降水模型

（2）水滴從上向下降落，如果某些水滴最終落到地形圖中的同一個(gè)盆地，則說(shuō)明這些水滴落入地形圖中對(duì)應(yīng)的點(diǎn)屬于同一個(gè)區(qū)域，如果某些水滴落入相鄰2個(gè)盆地的概率是相近的，則說(shuō)明這些水滴落入地形圖中對(duì)應(yīng)的點(diǎn)屬于分水嶺。

自上而下的模擬降水過(guò)程是一個(gè)遞歸過(guò)程。定義如下：

其中，式（1）是遞歸過(guò)程的初始條件，設(shè) Xhmax是灰度值中最大值的像素點(diǎn)。式（2）是一個(gè)遞歸過(guò)程，h表示灰度值的范圍，從 hmax開(kāi)始遞歸。Pχh為像素點(diǎn)Xh所屬的盆地，Dχh為像素點(diǎn)Xh的鄰域，X（h）deepest為像素點(diǎn)Xh鄰域中最陡方向的點(diǎn)即Xh-1。每次遞歸過(guò)程，就是找到Xh-1并標(biāo)記其所屬的盆地。最后，若某像素點(diǎn)同時(shí)屬于 2個(gè)以上盆地的點(diǎn)，即為分水嶺中的點(diǎn)。

自下而上的模擬泛洪算法原理如下：

（1）將圖像理解成為一個(gè)如圖2所示的地形圖。

圖2 自下而上模擬泛洪模型

（2）水從地形圖的最低部分開(kāi)始向上漲水，當(dāng)2個(gè)盆地的水交匯的時(shí)候建立起一個(gè)大壩將各個(gè)區(qū)域隔開(kāi)，建立起的大壩就被稱(chēng)為分水嶺。

自下而上的模擬泛洪過(guò)程是一個(gè)遞歸過(guò)程。定義如下：

其中，式（3）屬于遞歸過(guò)程的初始條件。Xhmin是圖像I中灰度值為最小值的像素點(diǎn)；式（4）是一個(gè)遞歸過(guò)程。h表示灰度值的范圍，hmin為灰度值范圍最小值，hmax為灰度值范圍最大值。Xh+1是灰度值即海拔高度為h+1上的所有像素點(diǎn)。minh+1表示此點(diǎn)屬于新產(chǎn)生盆地最小值點(diǎn)，即在h+1此海拔高度有產(chǎn)生了新的盆地；Xh∩Xh+1表示Xh+1點(diǎn)與Xh點(diǎn)相交，Cχh為Xh點(diǎn)所在的盆地，故Cχh（Xh∩Xh+1）為Xh+1點(diǎn)與Xh點(diǎn)同在一個(gè)盆地 Cχh的點(diǎn)。通過(guò)此遞歸過(guò)程，將圖像I中的所有像素點(diǎn)劃分盆地，最后，若某像素點(diǎn)同時(shí)屬于2個(gè)以上盆地的點(diǎn)，即為分水嶺中的點(diǎn)。

自上而下的模擬降水算法和自下而上的模擬泛洪算法都是將圖像理解成為地形圖，并分別從地形圖的上和下開(kāi)始算法的執(zhí)行。通常自下而上的模擬泛洪算法在研究過(guò)程中被使用得居多，但根據(jù)上述對(duì)2種算法的分析來(lái)看，2種算法可以取得相同的效果。

3 改進(jìn)的分水嶺分割算法

3.1 改進(jìn)方法歸納

眾多學(xué)者在對(duì)分水嶺分割算法進(jìn)行改進(jìn)的過(guò)程中對(duì)傳統(tǒng)部分改進(jìn)較小，多數(shù)是在分水嶺分割前或分割后進(jìn)行改進(jìn)。因此，根據(jù)圖3中對(duì)分水嶺分割算法改進(jìn)的時(shí)機(jī)，將其改進(jìn)劃分為前處理、后處理和前、后結(jié)合處理，圖3中上面的虛線框?yàn)榍疤幚?，下面的虛線框?yàn)楹筇幚怼?/p>

圖3 基于處理過(guò)程的改進(jìn)方式

傳統(tǒng)的分水嶺分割算法雖然取得了良好的效果，然而針對(duì)具體的環(huán)境遇到了諸如過(guò)分割、對(duì)噪聲敏感等問(wèn)題。后來(lái)的眾多學(xué)者根據(jù)自身的研究需要提出了不少的改進(jìn)分水嶺分割算法，根據(jù)領(lǐng)域可以劃分為智能識(shí)別、醫(yī)學(xué)、遙感等。根據(jù)分水嶺分割算法的過(guò)程可以將其歸納為在傳統(tǒng)分水嶺分割算法之前進(jìn)行處理、傳統(tǒng)分水嶺分割算法之后進(jìn)行處理和將兩者結(jié)合起來(lái)，從而來(lái)滿(mǎn)足自身的研究需要。在這里將在傳統(tǒng)分水嶺分割算法之前進(jìn)行處理稱(chēng)為“前處理”，將在傳統(tǒng)分水嶺分割之后進(jìn)行處理稱(chēng)為“后處理”，將在傳統(tǒng)分水嶺分割之前和分割之后同時(shí)結(jié)合起來(lái)進(jìn)行處理稱(chēng)為“前、后結(jié)合處理”。前處理的方法有預(yù)處理濾波、標(biāo)記、小波變換、擴(kuò)展最小變換、形態(tài)學(xué)開(kāi)閉重構(gòu)技術(shù)、對(duì)比度增強(qiáng)、距離變換、中值濾波等；后處理的方法有空間聚類(lèi)、異質(zhì)性最小區(qū)域合并、距離度量區(qū)域合并等；前、后結(jié)合處理的方法就是將以上前處理和后處理的方法結(jié)合使用。

3.2 前處理

如果采用未經(jīng)前處理的圖像直接進(jìn)行分水嶺分割會(huì)由于圖像本身的噪聲及量化誤差影響，而產(chǎn)生大量的小區(qū)域即人眼看不到或者理論上不想存在的小區(qū)域，即過(guò)分割問(wèn)題。傳統(tǒng)分水嶺分割算法輸入數(shù)據(jù)為圖像梯度，如果對(duì)圖像梯度進(jìn)行處理后，再進(jìn)行分水嶺分割，將會(huì)出現(xiàn)更好的分割效果，故學(xué)者們對(duì)輸入圖像梯度之前進(jìn)行了大量的研究，用來(lái)濾除圖像噪音從而將梯度圖重建，這樣再進(jìn)行傳統(tǒng)的分水嶺分割就會(huì)盡量避免原有的缺點(diǎn)。

文獻(xiàn)［16］提出了一種基于開(kāi)閉運(yùn)算和距離變換的分水嶺分割算法，利用開(kāi)運(yùn)算f·b=（fΘb）⊕b，閉運(yùn)算f·b=（f⊕b）Θb，距離計(jì)算等方法實(shí)現(xiàn)了梯度重構(gòu)，克服了傳統(tǒng)算法的過(guò)分割問(wèn)題。

文獻(xiàn)［17］提出了一種對(duì)比度增強(qiáng)的改進(jìn)分水嶺分割算法，該算法采用隨機(jī)概率方法Pr［P→q］=來(lái)提高圖像的對(duì)比度，從而降低了圖像噪音對(duì)分割所產(chǎn)生的影像，較好地解決了過(guò)分割問(wèn)題。

文獻(xiàn)［18］提出了一種新的基于低通濾波的標(biāo)記提取方法，用來(lái)對(duì)要輸入的原始梯度圖像進(jìn)行梯度重構(gòu)，從而再進(jìn)行分水嶺分割，該方法有效地去除了分割結(jié)果在地物邊緣處仍會(huì)存在破碎多邊形的情況。

文獻(xiàn)［20］提出了采用混合開(kāi)閉重構(gòu)運(yùn)算：

3.3 后處理

在改進(jìn)的分水嶺分割算法中，由于其算法特性，通常分割結(jié)果都是封閉的區(qū)域，因此為了解決過(guò)分割的問(wèn)題，在后處理部分，往往采用各種方法及規(guī)則，消除那些理論上不應(yīng)該存在的微小局部區(qū)域。

文獻(xiàn)［21］提出了一種基于K-means聚類(lèi)的改進(jìn)分水嶺算法，該算法定義為分割

以后區(qū)域i和區(qū)域j之間的相似度，其中，Mij為區(qū)域i和區(qū)域j之間的平均強(qiáng)度差，Bij為區(qū)域i和區(qū)域j之間的強(qiáng)度差異，通過(guò)將相似度 Cij與閾值Tc進(jìn)行比較，確定哪些區(qū)域之間進(jìn)行合并，進(jìn)而解決了傳統(tǒng)分水嶺算法的過(guò)分割嚴(yán)重的問(wèn)題。

文獻(xiàn)［22］提出了利用區(qū)域之間的綜合差異性f=wspectralhspectral+（1-wspectral）hshape進(jìn)行區(qū)域合并的方法，確保區(qū)域之間的異質(zhì)性最小，抑制了圖像的過(guò)分割，獲得了理想的分割結(jié)果，其中，wspectral為光譜差異性度量準(zhǔn)則在綜合準(zhǔn)則中所占的權(quán)值；hspectral為光譜的差異性度量準(zhǔn)則；hshape為形狀的差異性度量準(zhǔn)則。

在實(shí)際應(yīng)用過(guò)程中，單獨(dú)進(jìn)行后處理研究的較少，通常在進(jìn)行后處理研究工作時(shí)，都與前處理的研究工作結(jié)合起來(lái)，從而獲得更好的分割效果。

3.4 前后結(jié)合處理

在分水嶺分割算法改進(jìn)的過(guò)程中，很多學(xué)者發(fā)現(xiàn)不是單一的一種改進(jìn)就可以達(dá)到需要的研究結(jié)果，因此，很多學(xué)者將前處理和后處理結(jié)合起來(lái)進(jìn)行研究和改進(jìn)，并且取得了不錯(cuò)的處理效果。

文獻(xiàn)［23］提出了在前處理部分首先基于相位一致思想分析、提取梯度信息。相位一致計(jì)算式如下：

然后利用擴(kuò)展最小變換E=EM（G，h）標(biāo)記局部最小區(qū)域，其中h為高度閾值，G為相位一致梯度圖像，E為二值圖像。利用強(qiáng)制最小技術(shù)修改相位一致梯度圖像，從而獲得重建后的梯度圖像，利用前處理部分獲得了地物準(zhǔn)確邊界。

在后處理部分，首先進(jìn)行屬性特征聚類(lèi)即依次對(duì)光譜與紋理聚類(lèi)，在對(duì)紋理和光譜進(jìn)行初步分類(lèi)后，進(jìn)行空間關(guān)系分析，判定聚類(lèi)后不確定對(duì)象的類(lèi)別屬性，合并區(qū)域，通過(guò)后處理部分表達(dá)了各類(lèi)地物的真實(shí)面貌，從而進(jìn)行了合理的區(qū)域合并，保證了分割結(jié)果的準(zhǔn)確性。

文獻(xiàn)［24］提出了在前處理部分利用改進(jìn)的基于邊緣信賴(lài)度的各向異性擴(kuò)散算法對(duì)圖像進(jìn)行處理，其中，E，S，W，N為計(jì)算梯度的4個(gè)方向；傳導(dǎo)函數(shù)PDir是梯度▽DirIχ，y的函數(shù)。前處理部分，在去除噪聲的同時(shí)，良好的保持了圖像的邊緣信息。然而經(jīng)過(guò)分水嶺分割后的圖像仍然存在大量的分割區(qū)域，因此在后處理部分，楊家紅等人提出了自動(dòng)種子區(qū)域增長(zhǎng)算法，將種子區(qū)域與鄰接區(qū)域中顏色特征相同的區(qū)域合并起來(lái)，又利用小區(qū)域消解算法將區(qū)域尺寸低于設(shè)定閾值的區(qū)域合并到最相似的區(qū)域中去，從而使過(guò)分割問(wèn)題得到了改進(jìn)。

文獻(xiàn)［25］提出了在前處理部分利用高斯低通濾波減少圖像噪聲和暗紋理細(xì)節(jié)的影響；利用形態(tài)學(xué)擴(kuò)展最小變換技術(shù)設(shè)定閾值參數(shù)，消除小于閾值的局部極小值，從而減少過(guò)分割的區(qū)域。在后處理部

分利用綜合距離度量

文獻(xiàn)［2］在前處理部分提出最佳小波分解尺度選擇方法，利用：

計(jì)算各尺度下局部方差均值，最終取得最佳分解尺度即最小局部方差均值對(duì)應(yīng)的尺度，此時(shí)梯度幅值對(duì)地物刻畫(huà)最為準(zhǔn)確，其中（χ，y）為第 χ行，第y列對(duì)應(yīng)的梯度值，m，n為采樣模板長(zhǎng)寬，為第k種地物局部方差均值，為模板內(nèi)梯度均值，l為第k種地物的樣本數(shù)量。然后又提出灰度相關(guān)性引導(dǎo)的多層標(biāo)記提取方法，得到最終的標(biāo)記圖。在后處理部分采取光譜、紋理、面積、空間相鄰關(guān)系等多約束策略進(jìn)行區(qū)域合并，使區(qū)域合并更加準(zhǔn)確。

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

分水嶺分割算法有很多的改進(jìn)方法，由于分水嶺分割算法的改進(jìn)多數(shù)是對(duì)分水嶺分割之前進(jìn)行預(yù)處理或者是對(duì)分水嶺分割之后進(jìn)行區(qū)域合并，還有將預(yù)處理和區(qū)域合并結(jié)合起來(lái)進(jìn)行算法的改進(jìn)，因此本文根據(jù)算法的過(guò)程將改進(jìn)的分水嶺分割算法進(jìn)行歸納，介紹了前處理、后處理和前、后結(jié)合處理的劃分方法。雖然這些改進(jìn)方法取得了較好的效果，但是分水嶺分割算法還存在需要進(jìn)一步改進(jìn)的一些方向，如由于圖像分辨率的提高、圖像紋理的復(fù)雜性及圖像應(yīng)用領(lǐng)域的更新，過(guò)分割問(wèn)題仍需進(jìn)一步研究；由于圖像容量的不斷增加，對(duì)分水嶺分割算法進(jìn)行并行研究，從而獲得更高的效率和更好的效果，并且解決內(nèi)存溢出等問(wèn)題也是未來(lái)的研究方向。

［1］ Bieniek A，Moga A.An Efficient Watershed Algorithm Based on Connected Components［J］.Pattern Recognition，2000，33（6）：907-916.

［2］ 陳 杰，鄧 敏，肖鵬峰，等.利用小波變換的高分辨率多光譜遙感圖像多尺度分水嶺分割［J］.遙感學(xué)報(bào)，2011，15（5）：908-926.

［3］ 張紅民，王一博.一種改進(jìn)的細(xì)胞圖像分水嶺分割方法［J］.重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)，2012，26（11）：59-62.

［4］ 黎 蔚，高 璐.基于改進(jìn)的分水嶺算法的路面裂縫檢測(cè)［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49（20）：263-266.

［5］ Su B，Noguchi N.Discrimination of Land Use Patterns in Remote Sensing Image Data Using Minimum Distance Algorithm and Watershed Algorithm［J］.Engineering in Agriculture，Environment and Food，2013，6（2）：48-53.

［6］ Zanaty E A，Afifi A.A Watershed Approach for Improving Medical Image Segmentation［J］.Computer Methods in Biomechanics and Biomedical Engineering，2013，16（12）：1262-1272.

［7］ Narkhede H P.Review of Image Segmentation Techniques［J］.International Journal of Science and Modern Engineering，2013，1（8）：54-61.

［8］ Nguyen K，Peng B，Li T，et al.Online Evaluation System of Image Segmentation［J］.Advances in Intelligent System s and Computing，2014，279：527-536.

［9］ Li Deren，Zhang Guifeng，Wu Zhaocong，et al.An Edge Em bedded Marker-based Watershed Algorithm for High Spatial Resolution Remote Sensing Image Segmentation［J］.IEEE Transactions on Image Processing，2010，19（10）：2781-2787.

［10］ Hu Yingshuai，Wu Suping.Parallelization Research on Watershed Algorithm［C］//Proceedings of International Conference on Automatic Control and Artificial Intelligence.［S.l.］：IET，2012：1524-1527.

［11］ Quesada-Barriuso P，Heras D B，Arguello F.Efficient GPU Asynchronous Implementation of a Watershed Algorithm Based on Cellular Automata［C］//Proceedings of the 10th International Symposium on Parallel and Distributed Processing with Applications.Washington D.C.，USA：IEEE Press，2012：79-86.

［12］ Maru D，Shah B.Image Segmentation Techniques and Genetic Algorithm［J］.International Journal of Advanced Research in Computer Engineering&Technology，2013，2（4）：1483-1487.

［13］ Deng Tingquan，Li Yanchao.An Improved Watershed Image Segmentation Algorithm Combining with a New Entropy Evaluation Criterion［C］//Proceedings of International Society for Optics Engineering.［S.l.］：Society of Photo-optical Instrumentation Engineers，2013：197-208.

［14］ Vincent L，Soille P.Watersheds in Digital Spaces：An Efficient Algorithm Based on Immersion Simulations［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（6）：583-598.

［15］ de Smet P，Pires R L.Implementation and Analysis of an Optimized Rainfalling Watershed Algorithm［C］// Proceedings of International Society for Optical Engineering.［S.l.］：Society of Photo-optical Instrumentation Engineers，2000：759-766.

［16］ Zhao Yuqian，Liu Jianxin，Li Huifen，et al.Improved Watershed Algorithm for Dowels Image Segmentation［C］//Proceedings of the 7th World Congress on Intelligent Control and Automation.Chongqing，China：［s.n.］.2008：7644-7648.

［17］ Khiyal M S H，Khan A，Bibi A.Modified Watershed Algorithm for Segmentation of 2D Images［J］.Issues in Informing Science&Information Technology，2009，6：877-886.

［18］ 尹高飛，肖鵬峰，馮學(xué)智.基于改進(jìn)標(biāo)記的高分辨率遙感圖像分水嶺分割方法［J］.遙感信息，2010，2：13-18.

［19］ 安素珍，王茂芝，張 濤，等.形態(tài)梯度重構(gòu)的標(biāo)記分水嶺高光譜影像分割［J］.四川理工學(xué)院學(xué)報(bào)：自然科學(xué)版，2012，25（4）：59-63.

［20］ 江 怡，梅小明，鄧 敏，等.一種結(jié)合形態(tài)濾波和標(biāo)記分水嶺變換的遙感圖像分割方法［J］.地理與地理信息科學(xué)，2013，29（2）：17-21.

［21］ Ng H P，Ong S H，F(xiàn)oong K W C，et al.Medical Image Segmentation Using K-means Clustering and Improved Watershed Algorithm［C］//Proceedings of IEEE Southwest Symposium on Image Analysis and Interpretation. Washington D.C.，USA：IEEE Press，2006：61-65.

［22］ 林 卉，劉 培，夏俊士，等.基于分水嶺變換的遙感影像面向?qū)ο蠖喑叨确指钏惴ㄑ芯浚跩］.測(cè)繪通報(bào)，2011，（10）：17-19.

［23］ 陳 杰，鄧 敏，肖鵬峰，等.基于分水嶺變換與空間聚類(lèi)的高分辨率遙感影像面向?qū)ο蠓诸?lèi)［J］.遙感技術(shù)與應(yīng)用，2010，25（5）：597-603.

［24］ 楊家紅，劉 杰，鐘堅(jiān)成，等.結(jié)合分水嶺與自動(dòng)種子區(qū)域生長(zhǎng)的彩色圖像分割算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2010，15（1）：63-68.

［25］ 余旺盛，侯志強(qiáng)，宋建軍.基于標(biāo)記分水嶺和區(qū)域合并的彩色圖像分割［J］.電子學(xué)報(bào)，2011，39（5）：1007-1012.

編輯 金胡考

Survey of Research on Watershed Segmentation Algorithms

SHEN Xiajiong，WU Xiaoyang，HAN Daojun
（Institute of Data and Know ledge Engineering，Henan University，Kaifeng 475004，China）

Researchers have made some related studies aiming at problem s of over-segmentation and noise sensitive in the pre-processing and post-processing of traditional watershed segmentation algorithms.A t first，this paper makes a detailed introduction on two classical algorithm s，that is，superincumbent simulation rainfall algorithm and bottom-up simulation flooding algorithm.Followed，three processes are proposed.The first is input gradient image reconstitution processing before the traditional watershed segmentation algorithm，the second is the merge application of region which is partitioned after traditional watershed segmentation algorithm，and the last is the combined processing before and after traditional watershed segmentation algorithm.Then it concludes and analyzes the effect of the improvement of watershed segmentation algorithms in the pre-processing，post-processing and their combined processing.Finally，it makes a conclusion and brings up some research directions to be resolved and basic solving ideas.

watershed segmentation；over-segmentation；pre-processing；post-processing；gradient reconstitution；region merging

沈夏炯，吳曉洋，韓道軍.分水嶺分割算法研究綜述［J］.計(jì)算機(jī)工程，2015，41（10）：26-30.

英文引用格式：Shen Xiajiong，Wu Xiaoyang，Han Daojun.Survey of Research on Watershed Segmentation Algorithms［J］. Computer Engineering，2015，41（10）：26-30.

1000-3428（2015）10-0026-05

A

TP312

國(guó)家自然科學(xué)基金資助項(xiàng)目（61272545）；河南省科技攻關(guān)計(jì)劃基金資助項(xiàng)目（142102210390）。

沈夏炯（1963-），男，教授、博士，主研方向：空間數(shù)據(jù)處理；吳曉洋（通訊作者），碩士研究生；韓道軍，副教授、博士。

2014-09-22

2014-11-21E-m ail：L-W-T-G@163.com