分水嶺分割算法研究綜述

沈夏炯，吳曉洋，韓道軍

（河南大學數據與知識工程研究所，河南 開封 475004）

分利用綜合距離度量

分水嶺分割算法研究綜述

沈夏炯，吳曉洋，韓道軍

（河南大學數據與知識工程研究所，河南 開封 475004）

傳統分水嶺分割算法存在過分割和對噪音敏感等問題，為此，研究者針對算法中前處理和后處理過程分別展開研究。介紹自上而下的模擬降水算法和自下而上的模擬泛洪算法，分析待輸入梯度圖像的重構處理過程、分割后區域的合并處理過程以及前后結合處理過程，歸納前、后處理及前后結合處理的分水嶺分割算法改進，評價改進效果，總結并提出待解決的研究方向及解決思路。

分水嶺分割；過分割；前處理；后處理；梯度重構；區域合并

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

1 概述

分水嶺分割算法建立在數學形態學的理論基礎之上，模擬的是立體的地形表面，屬于一種基于區域的圖像分割方法［1］。在遙感領域，改進的分水嶺分割算法廣泛應用于遙感影像分割尤其是高分辨率遙感影像的分割［2］；在醫學領域，改進的分水嶺分割算法廣泛應用于彩色白細胞分割、磁共振腦圖像分割、組織細胞分割、乳腺癌粘連細胞分割等［3］；在智能識別領域，改進的分水嶺分割算法廣泛應用于圖像目標識別、多目標車輛跟蹤、道路識別、路面裂縫檢測等［4］。

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

法；（3）圖像分割是圖像處理中很重要的一個操作，如何評價圖像分割的優良是至關重要的，一些文獻也提出了一些評價標準［8］，然而目前尚沒有一個完整、完善的評價機制。故在評價方面，發展趨勢傾向于如何制定一個規范的評價標準來評定分割效果的優良；（4）由于大數據量圖像的廣泛應用以及算法因不斷改進而復雜性增加，導致算法的運算效率和準確性降低［9］。故在改進方法的目標方面，發展趨勢傾向于并行計算和智能計算方向。

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

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

2 傳統的分水嶺分割算法

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

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

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

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

（2）水滴從上向下降落，如果某些水滴最終落到地形圖中的同一個盆地，則說明這些水滴落入地形圖中對應的點屬于同一個區域，如果某些水滴落入相鄰2個盆地的概率是相近的，則說明這些水滴落入地形圖中對應的點屬于分水嶺。

自上而下的模擬降水過程是一個遞歸過程。定義如下：

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

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

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

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

（2）水從地形圖的最低部分開始向上漲水，當2個盆地的水交匯的時候建立起一個大壩將各個區域隔開，建立起的大壩就被稱為分水嶺。

自下而上的模擬泛洪過程是一個遞歸過程。定義如下：

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

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

3 改進的分水嶺分割算法

3.1 改進方法歸納

眾多學者在對分水嶺分割算法進行改進的過程中對傳統部分改進較小，多數是在分水嶺分割前或分割后進行改進。因此，根據圖3中對分水嶺分割算法改進的時機，將其改進劃分為前處理、后處理和前、后結合處理，圖3中上面的虛線框為前處理，下面的虛線框為后處理。

圖3 基于處理過程的改進方式

傳統的分水嶺分割算法雖然取得了良好的效果，然而針對具體的環境遇到了諸如過分割、對噪聲敏感等問題。后來的眾多學者根據自身的研究需要提出了不少的改進分水嶺分割算法，根據領域可以劃分為智能識別、醫學、遙感等。根據分水嶺分割算法的過程可以將其歸納為在傳統分水嶺分割算法之前進行處理、傳統分水嶺分割算法之后進行處理和將兩者結合起來，從而來滿足自身的研究需要。在這里將在傳統分水嶺分割算法之前進行處理稱為“前處理”，將在傳統分水嶺分割之后進行處理稱為“后處理”，將在傳統分水嶺分割之前和分割之后同時結合起來進行處理稱為“前、后結合處理”。前處理的方法有預處理濾波、標記、小波變換、擴展最小變換、形態學開閉重構技術、對比度增強、距離變換、中值濾波等；后處理的方法有空間聚類、異質性最小區域合并、距離度量區域合并等；前、后結合處理的方法就是將以上前處理和后處理的方法結合使用。

3.2 前處理

如果采用未經前處理的圖像直接進行分水嶺分割會由于圖像本身的噪聲及量化誤差影響，而產生大量的小區域即人眼看不到或者理論上不想存在的小區域，即過分割問題。傳統分水嶺分割算法輸入數據為圖像梯度，如果對圖像梯度進行處理后，再進行分水嶺分割，將會出現更好的分割效果，故學者們對輸入圖像梯度之前進行了大量的研究，用來濾除圖像噪音從而將梯度圖重建，這樣再進行傳統的分水嶺分割就會盡量避免原有的缺點。

文獻［16］提出了一種基于開閉運算和距離變換的分水嶺分割算法，利用開運算f·b=（fΘb）⊕b，閉運算f·b=（f⊕b）Θb，距離計算等方法實現了梯度重構，克服了傳統算法的過分割問題。

文獻［17］提出了一種對比度增強的改進分水嶺分割算法，該算法采用隨機概率方法Pr［P→q］=來提高圖像的對比度，從而降低了圖像噪音對分割所產生的影像，較好地解決了過分割問題。

文獻［18］提出了一種新的基于低通濾波的標記提取方法，用來對要輸入的原始梯度圖像進行梯度重構，從而再進行分水嶺分割，該方法有效地去除了分割結果在地物邊緣處仍會存在破碎多邊形的情況。

文獻［20］提出了采用混合開閉重構運算：

3.3 后處理

在改進的分水嶺分割算法中，由于其算法特性，通常分割結果都是封閉的區域，因此為了解決過分割的問題，在后處理部分，往往采用各種方法及規則，消除那些理論上不應該存在的微小局部區域。

文獻［21］提出了一種基于K-means聚類的改進分水嶺算法，該算法定義為分割

以后區域i和區域j之間的相似度，其中，Mij為區域i和區域j之間的平均強度差，Bij為區域i和區域j之間的強度差異，通過將相似度 Cij與閾值Tc進行比較，確定哪些區域之間進行合并，進而解決了傳統分水嶺算法的過分割嚴重的問題。

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

在實際應用過程中，單獨進行后處理研究的較少，通常在進行后處理研究工作時，都與前處理的研究工作結合起來，從而獲得更好的分割效果。

3.4 前后結合處理

在分水嶺分割算法改進的過程中，很多學者發現不是單一的一種改進就可以達到需要的研究結果，因此，很多學者將前處理和后處理結合起來進行研究和改進，并且取得了不錯的處理效果。

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

然后利用擴展最小變換E=EM（G，h）標記局部最小區域，其中h為高度閾值，G為相位一致梯度圖像，E為二值圖像。利用強制最小技術修改相位一致梯度圖像，從而獲得重建后的梯度圖像，利用前處理部分獲得了地物準確邊界。

在后處理部分，首先進行屬性特征聚類即依次對光譜與紋理聚類，在對紋理和光譜進行初步分類后，進行空間關系分析，判定聚類后不確定對象的類別屬性，合并區域，通過后處理部分表達了各類地物的真實面貌，從而進行了合理的區域合并，保證了分割結果的準確性。

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

文獻［25］提出了在前處理部分利用高斯低通濾波減少圖像噪聲和暗紋理細節的影響；利用形態學擴展最小變換技術設定閾值參數，消除小于閾值的局部極小值，從而減少過分割的區域。在后處理部

分利用綜合距離度量

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

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

4 結束語

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

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

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

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

［4］ 黎 蔚，高 璐.基于改進的分水嶺算法的路面裂縫檢測［J］.計算機工程與應用，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］ 尹高飛，肖鵬峰，馮學智.基于改進標記的高分辨率遙感圖像分水嶺分割方法［J］.遙感信息，2010，2：13-18.

［19］ 安素珍，王茂芝，張 濤，等.形態梯度重構的標記分水嶺高光譜影像分割［J］.四川理工學院學報：自然科學版，2012，25（4）：59-63.

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

［21］ Ng H P，Ong S H，Foong 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］ 林 卉，劉 培，夏俊士，等.基于分水嶺變換的遙感影像面向對象多尺度分割算法研究［J］.測繪通報，2011，（10）：17-19.

［23］ 陳 杰，鄧 敏，肖鵬峰，等.基于分水嶺變換與空間聚類的高分辨率遙感影像面向對象分類［J］.遙感技術與應用，2010，25（5）：597-603.

［24］ 楊家紅，劉 杰，鐘堅成，等.結合分水嶺與自動種子區域生長的彩色圖像分割算法［J］.中國圖象圖形學報，2010，15（1）：63-68.

［25］ 余旺盛，侯志強，宋建軍.基于標記分水嶺和區域合并的彩色圖像分割［J］.電子學報，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］.計算機工程，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

國家自然科學基金資助項目（61272545）；河南省科技攻關計劃基金資助項目（142102210390）。

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

2014-09-22

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