分水岭变换：定义-算法和并行策略

FundamentaInformaticae41(2001)187{2281IOSPressTheWatershedTransform:Denitions,AlgorithmsandParallelizationStrategiesJosB.T.M.RoerdinkandArnoldMeijsterInstituteforMathematicsandComputingScienceUniversityofGroningenP.O.Box800,9700AVGroningen,TheNetherlandsEmail:[e-mail],[e-mail]hemethodofchoiceforimagesegmentationintheeldofmathematicalmorphology.Wepresentacriticalreviewofseveraldenitionsofthewatershedtransformandtheassociatedsequentialalgorithms,anddiscussvariousissueswhichoftencauseconfusionintheliterature.Theneedtodistinguishbetweendenition,algorithmspecicationandalgorithmimplementationispointedout.Variousexamplesaregivenwhichillustratedierencesbetweenwatershedtransformsbasedondierentdenitionsand/orimplementations.Thesecondpartofthepapersurveysapproachesforparallelimplementationofsequentialwatershedalgorithms.Keywords:Mathematicalmorphology,watershedtransform,watersheddenition,se-quentialalgorithms,parallelimplementation.1.IntroductionIngreyscalemathematicalmorphologythewatershedtransform,originallyproposedbyDigabelandLantuejoul[9,20]andlaterimprovedbyBeucherandLantuejoul[4],isthemethodofchoiceforimagesegmentation[5,46,52].Generallyspoken,imagesegmentationistheprocessofisolatingobjectsintheimagefromthebackground,i.e.,partitioningtheimageintodisjointregions,suchthateachregionishomogeneouswithrespecttosomeproperty,suchasgreyvalueortexture[18].Thewatershedtransformcanbeclassiedasaregion-basedsegmentationapproach.Theintuitiveideaunderlyingthismethodcomesfromgeography:itisthatofalandscapeorto-pographicreliefwhichisoodedbywater,watershedsbeingthedividelinesofthedomainsofattractionofrainfallingovertheregion[46].Analternativeapproachistoimaginethelandscapebeingimmersedinalake,withholespiercedinlocalminima.Basins(alsocalled`catchment2J.B.T.M.RoerdinkandA.Meijster/TheWatershedTransformbasins')willllupwithwaterstartingattheselocalminima,and,atpointswherewatercomingfromdierentbasinswouldmeet,damsarebuilt.Whenthewaterlevelhasreachedthehighestpeakinthelandscape,theprocessisstopped.Asaresult,thelandscapeispartitionedintoregionsorbasinsseparatedbydams,calledwatershedlinesorsimplywatersheds.Whensimulatingthisprocessforimagesegmentation,twoapproachesmaybeused:eitheronerstndsbasins,thenwatershedsbytakingasetcomplement;oronecomputesacompletepartitionoftheimageintobasins,andsubsequentlyndsthewatershedsbyboundarydetection.Tobemoreexplicit,wewillusetheexpression`watershedtransform'todenotealabellingoftheimage,suchthatallpointsofagivencatchmentbasinhavethesameuniquelabel,andaspeciallabel,distinctfromallthelabelsofthecatchmentbasins,isassignedtoallpointsofthewatersheds.AnexampleofasimpleimagewithitswatershedtransformisgiveninFig.1(a-b).Wenoteinpassingthatinpracticeoneoftendoesnotapplythewatershedtransformtotheoriginalimage,buttoits(morphological)gradient[26].Thisproduceswatershedsatthepointsofgreyvaluediscontinuity,asiscommonlydesiredinimagesegmentation.Oneofthedicultieswiththisintuitiveconceptisthatitleavesroomforvariousformal-izations.Dierentwatersheddenitionsforcontinuousfunctionshavebeengiven,whichwillbebrieyreviewedinSection3.1.However,ourmaininteresthereisindigitalimages,forwhichthereisevenmorefreedomtodenewatersheds,sinceinthediscretecasethereisnouniquedenitionofthepathadropofwaterwouldfollow.Manysequentialalgorithmshavebeende-velopedtocomputewatershedtransforms,seee.g.[26,51]forasurvey.Theycanbedividedintotwoclasses,onebasedonthespecicationofarecursivealgorithmbyVincent&Soille[52],andanotherbasedondistancefunctionsbyMeyer[25].Inthecontextofparallelimplementationsthereexistsanotabletendencyforintroducingotherdenitionsofthewatershedtransform,enablingeasierparallelization.ExamplesarepresentedinSection5.(a)(b)(c)(d)Figure1.Examplesofwatershedsegmentationbyimmersion(seeDenition3.2).(a):syntheticimage;(b):watershedtransformof(a);(c):naturalimage;(d):watershedtransformof(c).Dierentbasinsareindicatedbydistinctgreyvalues.Theimpressionwhichthecurrentliteratureonwatershedalgorithmsmakesupontheunini-tiatedreadercanonlybeoneofgreatconfusion.Oftenitisuncertainexactlywhichdenitionforthewatershedtransformisused.SometimesthedenitiontakestheformofthespecicationJ.B.T.M.RoerdinkandA.Meijster/TheWatershedTransform3ofanalgorithm.Acarefuldistinctionbetweenalgorithmspecicationandimplementationisinmanycaseslacking.Withoutsuchaseparation,correctnessassessmentofproposedalgorithmsisimpossible.Evenwhenaspecicationisgiven,theimplementationoftendoesnotadheretoit.Adhocmodicationsaremadetoeliminate`undesirable'consequencesofawatersheddenition,butsuchchangestendtocreatenewproblemsbysolvinganoldone.Or`optimiza-tions'areintroduced,forgreaterspeedormemoryreduction,whichintheprocesschangetheoutcomeofthealgorithmaswell,althoughthismayoftengoundetectedinthecaseofnaturalimages.Thesequestionsarenotpurelyacademic,sincethealgorithmiswidelyusedine.g.medicalimageprocessingwhereunwantedsideeectsshouldbeavoided.Thepurposeofthispaperistwofold.Intherstpartwepresentacriticalreviewofseverald