A Fully Global Approach to Image Segmentation

JournalofVisualCommunicationandImageRepresentation13,195–216(2002)doi:10.1006/jvci.2001.0500,availableonlineat“fieldofview,”endowingthealgorithmwitharobustnesstoinitialcontourplacementaboveandbeyondthesignificantimprovementexhibitedbyotherregionbasedsnakesoverearlieredgebasedsnakes.C2002ElsevierScience(USA)KeyWords:activecontours;curveevolution;snakes;segmentation;gradientflows.1.INTRODUCTIONCurveevolutionmethodshavebeenappliedtoavarietyofproblemsinimageprocess-ingandcomputervisionincludingimagesmoothing,morphology,shapemodeling,edge-detection,andsegmentation.Sincetheintroductionofthesnakemethodology[10,27]activecontourshavebecomeparticularlypopularforsegmentationapplications(see[1]andthereferencesthereinformoregeneralapplications).Anumberofrecentworks[5,6,21,29]havesoughttocombinecurveevolutiontechniqueswithstatisticalapproachestosegmentation.MuchofthisworkhasbeenmotivatedbytheearlierworkofRonfard[23]aswellasZhuandYuille[31,32].1ThisworkwassupportedbyONRGrantN00014-91-J-1004,bysubcontractGC123919NGDfromBostonUniversityundertheAFOSRMultidisciplinaryResearchProgramonReducedSignatureTargetRecognition,andbyAROGrantDAAH04-96-1-0494throughWashingtonUniversity.1951047-3203/02$35.00C2002ElsevierScience(USA)Allrightsreserved.196YEZZI,TSAI,ANDWILLSKYIn[29,30],Yezzietal.proposedanewclassofactivecontours,combiningcurveevolutionandstatisticsinanaturalwayforimagesconsistingofaknownnumberofregiontypes.Incontrasttoothersnakealgorithms,multiplesetsofcontours,evolvingviaseparatebutcoupledcurveevolutionequations,areemployedtosegmentanimageintomultipleregionclasses.Thecouplingbetweentheevolutionequations,whichdoesnotdependuponthemutualproximitiesofeachsetofcontours,causeseverysinglepixelintheimagetoinfluencetheflowofeveryindividualcontour.Thisfullyglobalapproachtosegmentationis,thus,evenmorerobusttoinitialcontourplacementwhencomparedtootherregionbasedapproaches[6,23,31,32](inwhichtheevolutionofaboundarydependsonlyuponthepixelswithinregionswhichsharethegivenboundary)whicharealreadymorerobustthanlocaledge-basedapproaches[2,3,7,10,11,16,26–28](inwhichtheevolutionofacurvedependsonlyuponnearbypixels).See[4,5,21]forsomeheterogeneousapproacheswhichblendbothregionandboundaryinformation.Standardlevelsetimplementations(seeOsherandSethian[20,25]andthereferencestherein)ofthesecoupledcurveevolutionsinvolveseparatelevelsetfunctionsforeachsetofcurves.Thisoffersasimplemechamismtotreattriplepointsandothermultiplejunctions.Someotherrecentlevel-set,coupledsnakealgorithms[22,24],thoughdifferent,enjoymanyofthesameadvantagesasourmodel.Thekeyideabehindthecoupledcurveevolutionmodelpresentedin[29,30]wastodesigncurveevolutionequationswhich“pullapart”thevaluesofoneormoreimagestatistics(e.g.,means,variances,textures)withineachregion.Inthispaper,weintroduceanewconstraintwhichguaranteesthattherelevantstatisticsevolve“awayfromeachother”asopposedtojust“apart.”ThisconstraintwillbetreatedinSection4.WefirstpresenttheoriginalmodelinSection2,followedbyacomparisoninSection3withotherrecentregion-basedmodels.InSection5wediscussthenumericalimplementationofboththeoriginalandtheconstrainedmodelsusinglevelsettechniques[20,25]followedbysimulationsinSection6.2.COUPLEDCURVEEVOLUTIONMODELSInthissection,wepresenttheoriginalcoupledcurveevolutionmodelsoutlinedin[29,30].Thesearebasedupongradientflowsdesignedto“pull-apart”thevaluesoftwoormoreimagestatisticsandarethereforeusefulforsegmentingimagesinwhichregionsaredifferentiatedbythevaluesofaknownsetofstatistics.Westartoutwiththesimplecaseofbimodalimageryinwhichtherearetwotypesofregions,foregroundandbackground.Inthiscase,asinglesetofcurves(andasinglestatistic)issufficienttodelineatetheboundariesbetweenforegroundandbackground.Werefertotheresultinggradientflowsasbinaryflows.Fortrimodalimagery,weusetwosetsofcurvestodistinguishtwodifferentforegroundclassesfromacommonbackground(orvice-versa),explainingourreferencetothesetechniquesascoupledcurveevolutionmodels.Weconcludethissectionbydiscussingageneralapproachformorethanthreeregionclasses(byemployingmorethantwosetsofcurves).2.1.BinaryFlowsWebeginbyconsideringimageswhichconsistofjusttworegiontypes.ThemosttrivialcaseisthatofabinaryimageI(x,y)con