搜索
FINDINGTHEGLOBALMINIMUMFORBINARYIMAGERESTORATIONTonyF.Chan†,SelimEsedo¯glu†andMilaNikolova?†MathematicsDepartment,UCLA.LosAngeles,CA90095.?CentredeMathematiquesetdeLeursApplications,ENSdeCachan,France.ABSTRACTRestoringbinaryimagesisaproblemwhicharisesinvariousap-plicationfields.Inourpaper,thisproblemisconsideredinavari-ationalframework:thesought-aftersolutionminimizesanenergy.Energiesdefinedoverthesetofthebinaryimagesareinevitablynonconvexandtherearenogeneralmethodstocalculatetheglobalminimum,whilelocalminimziersareveryoftenoflimitedinter-est.Inthispaperwedefinetherestoredimageastheglobalmin-imizerofthetotal-variation(TV)energyfunctionalconstrainedtothecollectionofallbinary-valuedimages.Wesolvethiscon-strainednon-convexoptimizationproblembyderivinganotherfunc-tionalwhichisconvexandwhose(unconstrained)minimumisproventobereachedfortheglobalminimizerofthebinarycon-strainedTVfunctional.Practicalissuesarediscussedandanu-mericalexampleisprovided.1.INTRODUCTIONInvariousapplicationswearegivenabinary-valuedfunctionf(x):RN→{0,1},N≥2,whichisknowntobethecorruptedver-sionofanotherbinary-valuedfunctionu(x)thatneedstobees-timated.Wecanevoketextdenoisinganddocumentprocessing,two-phaseimagesegmentation,shaperestoration,channel-noisecancellationincommunications,fairingofsurfacesincomputergraphicsandothers.Thisproblemcanbestatedeitherasdenois-ingorassegmentation.Sincebothuandfarebinary,theycanberepresentedasthecharacteristicfunctionofashape.Thecor-ruptionincurredbyfisthusinthegeometryoftheshape:Itsboundarymightbeveryrough,andtheusermightbeinterestedinsmoothingoutitsboundary,andperhapsremovingsmall,un-necessaryconnectedcomponentsoftheshape.Thistaskisacom-monfirststepinmanyobjectdetectionandrecognitionalgorithms.Variationalandpartialdifferentialequationsbasedapproachestodenoisingandsegmentationhavehadgreatsuccess,essentiallybe-causethesemodelsarewellsuitedtoimposegeometricregularityonthesolutionssought.Amongthebestknownandmostinflu-entialexamplesaretheRudin-Osher-Fatemi(ROF)totalvariationbasedimagedenoisingmodel,andtheMumford-Shahimageseg-mentationmodel.Thesemodelsareeasilyadaptedtobinaryim-ages.However,acommondifficultythatarisesisthepresenceofspuriouslocalminimathatarenotglobalminima.Thereasonisthattheconstraintset—thefamilyofallcharacteristicfunctionsofsubsetsofRN—isanon-convexcollection.Thisisamuchmoreseriousdrawbackthannon-uniquenessofglobalminimizersbe-causelocalminimaofsegmentationanddenoisingmodelsoftenhavecompletelywronglevelsofdetailandscale:whereasglobalminimizersofagivenmodelareusuallyallreasonablesolutions,thelocalminimatendtobeblatantlyfalse.Manysolutiontech-niquesforvariationalmodelsarebasedongradientdescent,andarethereforepronetogettingstuckinsuchlocalminima.Thismakesinitialguessforgradientdescentbasedalgorithmssome-timescriticallyimportantforobtainingsatisfactoryresults.InthispaperweproposeamethodthatguaranteestoreachtheglobalminimumoftheROFmodelrestrictedtothesetofbi-naryimages.Ourapproachistoconsidertheunconstrainedmini-mizationofaconvexfunctionalwhoseminimumisreachedfortheconstrainedglobalminimizeroftheROFmodel.Thetheoryinthisworkreliesontheresultsestablishedin[1].Asimilarideainthesimplercontextofimagesonafinitegridwasusedin[2]inordertofindquasi-binarysolutionsbyminimizingaconvexfunctional.2.BINARYIMAGERESTORATIONUSINGCONSTRAINEDMINIMIZATIONLetf(x):RN→[0,1]denotethegiven(grayscale)possiblycorrupted(noisy)image.Since[3],anusualapproachforimagerestorationistominimizeanenergyoftheformE(u)=ZRNϕ(|∇u|)+λZRN³u(x)−f(x)´2dx(1)whereλ0isaparametertobechosenbytheuser,oresti-matedifthelevelofnoiseisknownandϕ:R+→Risafunc-tion[4,5,6,7].Oneofthemostpopularexamplesisϕ(t)=twhichcorrespondstotheRudin-Osher-Fatemi(ROF)totalvaria-tionbasedimagedenoisingmodel[4].Inthebinaryimagedenois-ingcase,f(x)canbeexpressedasf(x)=1Ω(x)whereΩisaboundedsubsetofRNwhoseboundary∂Ωcanbeveryroughbecauseofthenoise.Anaturalwaytosolvesuchaproblemistoconstrainttheunknownuin(1)tobebinary,i.e.tohavetheformu(x)=1Σ(x).Thispossibilitywasconsideredin[8].FortheROFmodelonethenobtainsthefollowingconstrainedoptimizationproblem:minΣ⊂RNu(x)=1Σ(x)ZRN|∇u|+λZRN³u(x)−1Ω(x)´2dx|{z}E2(u)(2)Problem(2)isnon-convexbecausetheminimizationisoveranon-convexsetoffunctions.Noticethat(2)inequivalenttothefollow-inggeometryproblem:minΣ⊂RNPer(Σ)+λ|Σ4Ω|(3)wherePer(·)denotestheperimeter,|·|istheN-dimensionalLebesguemeasure,andS14S2denotesthesymmetricdifferencebetween0-7803-9134-9/05/$20.00©2005IEEEI-121thetwosetsS1andS2.TheunknownsetΣin(3)canbede-scribedbyitsboundary∂Σ.Soacommonapproachofsolving(3)hasbeentousesomecurveevolutionprocess,sometimesreferredtoasactivecontours,where∂Σisupdatediteratively,usuallyac-cordingtogradientflowfortheenergyinvolved.Numerically,thereareseveralwaysofrepresenting∂Σ.Ex-plicitcurverepresentationsasinKass,Witkin,Terzopoulos[9]arenotappropriatesincesuchmethodsdonotallowchangesincurvetopology(andhaveanumberofotherdrawbacks).Actually,themostsuccessfulalgorithmsarethosebasedoneitherthelevelsetmethodofOsherandSethian[10],oronthevariationalapprox-imationapproachknownasGam