SIAMJ.APPL.MATH.c2006SocietyforIndustrialandAppliedMathematicsVol.66,No.5,pp.1632–1648
ALGORITHMSFORFINDINGGLOBALMINIMIZERSOF
IMAGESEGMENTATIONANDDENOISINGMODELS∗
TONYF.CHAN†,SELIMESEDO¯GLU‡,ANDMILANIKOLOVA§
Abstract.Weshowhowcertainnonconvexoptimizationproblemsthatariseinimageprocessingandcomputervisioncanberestatedasconvexminimizationproblems.Thisallows,inparticular,thefindingofglobalminimizersviastandardconvexminimizationschemes.
Keywords.denoising,segmentation
AMSsubjectclassifications.94A08,65K10
DOI.10.1137/040615286
1.Introduction.Imagedenoisingandsegmentationaretworelated,funda-
mentalproblemsofcomputervision.Thegoalofdenoisingistoremovenoiseand/or
spuriousdetailsfromagiven,possiblycorrupted,digitalpicturewhilemaintaining
essentialfeaturessuchasedges.Thegoalofsegmentationistodividetheimageinto
regionsthatbelongtodistinctobjectsinthedepictedscene.
Approachestodenoisingandsegmentationbasedonthecalculusofvariationsand
partialdifferentialequations(PDEs)havehadgreatsuccess.Oneimportantreason
fortheirsuccessisthatthesemodelsareparticularlywellsuitedtoimposinggeometric
constraints(suchasregularity)onthesolutionssought.Amongthebestknownand
mostinfluentialexamplesaretheRudin–Osher–Fatemi(ROF)totalvariation–based
imagedenoisingmodel[22]andtheMumford–Shahimagesegmentationmodel[17].
DenoisingmodelssuchastheROFmodelcanbeeasilyadaptedtodifferent
situations.Aninterestingscenarioisthedenoisingofshapes:Here,thegivenimage
isbinary(representingthecharacteristicfunctionofthegivenshape),andthenoiseis
inthegeometryoftheshape:Itsboundarymightbeveryrough,andtheusermight
beinterestedinsmoothingoutitsboundary,andperhapsremovingsmall,unnecessary
connectedcomponentsoftheshape.Thistaskisacommonfirststepinmanyobject
detectionandrecognitionalgorithms.
Acommondifficultywithmanyvariationalimageprocessingmodelsisthatthe
energyfunctionaltobeminimizedhaslocalminima(whicharenotglobalminima).
Thisisamuchmoreseriousdrawbackthannonuniquenessofglobalminimizers(which
isalsoacommonphenomenon)becauselocalminimaofsegmentationanddenoising
modelsoftenhavecompletelywronglevelsofdetailandscale:whereasglobalmin-
imizersofagivenmodelareusuallyallreasonablesolutions,thelocalminimatend
tobeblatantlyfalse.Manysolutiontechniquesforvariationalmodelsarebasedon
gradientdescent,andarethereforepronetogettingstuckinsuchlocalminima.This
∗ReceivedbytheeditorsSeptember17,2004;acceptedforpublication(inrevisedform)November21,2005;publishedelectronicallyJune19,2006.http://www.siam.org/journals/siap/66-5/61528.html†MathematicsDepartment,UCLA,LosAngeles,CA90095(TonyC@college.ucla.edu).There-searchofthisauthorwassupportedinpartbyNSFcontractDMS-9973341,NSFcontractACI-0072112,ONRcontractN00014-03-1-0888,andNIHcontractP20MH65166.‡DepartmentofMathematics,UniversityofMichigan,AnnArbor,MI48109(esedoglu@umich.edu).TheresearchofthisauthorwassupportedinpartbyNSFawardDMS-0410085.§CentredeMathematiquesetdeLeursApplications,ENSdeCachan,61av.duPresidentWilson,94235CachanCedex,France(nikolova@cmla.ens-cachan.fr).
1632GLOBALMINIMAOFSEGMENTATIONANDDENOISINGMODELS1633
makestheinitialguessforgradientdescent–basedalgorithmssometimescritically
importantforobtainingsatisfactoryresults.
Inthispaperweproposealgorithmswhichareguaranteedtofindglobalmin-
imizersofcertaindenoisingandsegmentationmodelsthatareknowntohavelocal
minima.Asacommonfeature,themodelsweconsiderinvolveminimizingfunctionals
overcharacteristicfunctionsofsets,whichisanonconvexcollection;thisfeatureis
responsibleforthepresenceoflocalminima.Ourapproach,whichisbasedonob-
servationsofStrangin[23,24],istoextendthefunctionalsandtheirminimization
toallfunctionsinsuchawaythattheminimizersoftheextendedfunctionalscanbe
subsequentlytransformedintominimizersfortheoriginalmodelsbysimplethresh-
olding.Thisallows,amongotherthings,computingglobalminimizersfortheoriginal
nonconvexvariationalmodelsbycarryingoutstandardconvexminimizationschemes.
Ourfirstexampleisbinaryimagedenoising,whichwebrieflydiscussasaprecursor
toandamotivationforthemoregeneralsegmentationproblemthatwesubsequently
consider.HerethegivennoisyimagefortheROFmodelistakentobebinary,and
thesolutionisalsosoughtamongbinaryimages.Thisproblemhasmanyapplications
wheresmoothingofgeometricshapesisrelevant.Someexamplesarethedenoisingof
faxdocuments,andthefairingofsurfacesincomputergraphics.Becausethespaceof
binaryfunctionsisnonconvex,theminimizationprobleminvolvedisactuallyharder
thanminimizingtheoriginalROFmodel.Insection2,werecallresultsfrom[6]that
showhowthismodelcanbewrittenasaconvexoptimizationproblem,andweexhibit
itsuseasanumericalalgorithm.Inthissection,wealsoanalyticallyverifythatthe
energyconcernedpossesseslocalminimizersthatarenotglobalminimizers,which
cantrapstandardminimizationprocedures.
Insection3,weextendsomeoftheresultsof[6]tothemoreimportantproblem
ofimagesegmentation.Inparticular,weconsiderthetwo-phase,piecewiseconstant
Mumford–ShahsegmentationfunctionalproposedbyChanandVesein[7]andshow
thatpartoftheminimizationinvolvedcanbegivenaconvexformulation.Thismodel
hasbecomeaverypopulartoolinsegmentationandrelatedimageprocessingtasks
(alsosee[26]foritsmultiphaseversion).Theconvexformulationweobtainturns
outtobecloselyrelatedtothealgorithmofChanandVesepresentedin[7].Our
observationsindicatewhythisalgorithmissuccessfulinfindinginteriorcontoursand
otherhard-to-getfeaturesinimages.
2.Previouswork.Theresultsandtheapproachofthispaperfollowvery
closelytheobservationsofStrangin[23,24].Inthosepapers,optimizationprob-
lemsofthefollowingform,amongothers,arestudied:
inf{u:fudx=1}
|∇u|,(1)
wheref(x)isagivenfunction.Itisshowninparticularthattheminimizersof(1)
turnouttobecharacteristicfunctionsofsets.Themainideainvolvedistoexpress
thefunctionaltobeminimizedandtheconstraintintermsofthesuperlevelsetsof
thefunctionsu(x)andf(x).ThecoareaformulaofFleming,Rishel,andRishel[11]
istheprimarytool.
Inthispaper,theideaofexpressingfunctionalsintermsoflevelsetsisappliedto
somesimpleimageprocessingmodels.Forinstance,insection4,wherewestudythe
piecewiseconstantMumford–Shahenergy,weshowthattherelevantenergy,whichis
originallyformulatedintermsofsets,canbereformulatedasanoptimizationproblem
overfunctionsinsuchawaythattheresultingconvexenergyturnsouttobealmost
