Cooperative Optimization for Energy Minimization A

arXiv:cs/0701057v1[cs.CV]9Jan20071CooperativeOptimizationforEnergyMinimization:ACaseStudyofStereoMatchingXiaofeiHuangSchoolofInformationScienceandTechnologyTsinghuaUniversity,Beijing,P.R.China,[e-mail],individualsworkingtogetherasateamcansolvehardproblemsbeyondthecapabilityofanyindividualintheteam.Cooperativeoptimizationisanewlyproposedgeneralmethodforattackinghardoptimizationproblemsinspiredbycooperationprinciplesinteamplaying.Ithasanestablishedtheoreticalfoundationandhasdemonstratedoutstandingperformancesinsolvingreal-worldoptimizationproblems.Withsomegeneralsettings,acooperativeoptimizationalgorithmhasauniqueequilibriumandconvergestoitwithanexponentialrateregardlessinitialconditionsandinsensitivetoperturbations.Italsopossessesanumberofglobaloptimalityconditionsforidentifyingglobaloptimasothatitcanterminateitssearchprocessefficiently.Thispaperoffersageneraldescriptionofcooperativeoptimization,addressesanumberofdesignissues,andpresentsacasestudytodemonstrateitspower.I.INTRODUCTIONOptimizationisacoreproblembothinmathematicsandcomputerscience.Itisaveryactiveresearchareawithmanyinternationalconferenceseveryyear,alargeamountofliterature,andmanyresearchersandusersacrossmanyfieldsforawiderangeofapplications.Combinatorialoptimization[1],[2]isabranchofoptimizationwherethesetoffeasiblesolutionsofproblemsisdiscrete,countable,andofafinitesize.Thegeneralmethodsforcombinatorialoptimizationare1)localsearch[3],2)simulatedannealing[4],[5],3)geneticalgorithms[6],[7],[8],5)2antcolonyoptimization[9],4)tabusearch[10],5)branch-and-bound[11],[12]6)dynamicprogramming[12].Thesuccessfulapplicationsofdifferentcombinatorialoptimizationmethodshavebeenreportedinsolvingalargevarietyofoptimizationproblemsinpractice.Optimizationisimportantintheareasofcomputervision,patternrecognition,andimageprocessing.Forexample,stereomatchingisoneofthemostactiveresearchproblemsincomputervision[13],[14],[15],[16].Thegoalofstereomatchingistorecoverthedepthimageofascenefromapairof2-Dimagesofthesamescenetakenfromtwodifferentlocations.Likemanyotherproblemsfromtheseareas,itcanbeformulatedasacombinatorialoptimizationproblem,whichisNP-hard[17]incomputationalcomplexityingeneral.Theresearchersincomputervisionhavedevelopedanumberofsearchtechniqueswhichhavebeenproveneffectiveinpracticeforfindinggoodsolutionsforcombinatorialoptimizationprob-lems.Twowell-knownonesarethecooperativealgorithmproposedbyD.MarrandT.Poggioin[16]forstereomatchingandtheprobabilisticrelaxationproposedbyA.Rosenfieldetal[18]forscenelabeling.Recently,therearesomeremarkableprogressesindiscoveringnewoptimizationmethodsforsolvingcomputervisionproblems.Graphcuts[14],[19],[13],[20]isapowerfulspecializedoptimizationtechniquepopularincomputervision.Ithasthebestknownresultsinenergyminimizationinthetworecentevaluationsofstereoalgorithms[13],[21],morepowerfulthantheclassicsimulatedannealingmethod.However,graphcutshasalimitationinitsscopebecauseitisonlyapplicablewhentheenergyminimizationofavisionproblemcanbereducedintoaproblemoffindingtheminimumcutinagraph[20].Thesecondoptimizationmethodissocalledthesum-productalgorithm[22],ageneralizedbeliefpropagationalgorithmdevelopedinAI[23].Thesum-productalgorithmisthemostpow-erfuloptimizationmethodeverfoundsofarforattackinghardoptimizationproblemsraisedfromchanneldecodingincommunications.Themin-sumalgorithmandmax-productalgorithm[24],[25]areitsvariations.Ithasalsobeensuccessfulappliedtosolveseveralcomputervisionproblemswithpromisingexperimentalresults[26].Thethirdmethodproposedrecentlyissocalledmax-producttree-reweightedmessagepass-ing[27].Itisbasedonalowerboundingtechniquecalledlinearprogrammingrelaxation.Itsimprovementhasbeenproposedrecentlyanditssuccessfulapplicationsincomputervisionhavebeenreported[28].3Thecooperativeoptimizationisanewlydiscoveredgeneraloptimizationmethodforattackinghardoptimizationproblems[29],[30],[31],[32].Ithasbeenfoundintheexperiments[33],[34],[35],[36],[37]thatcooperativeoptimizationhasachievedremarkableperformancesatsolvinganumberofreal-worldNP-hardproblemswiththenumberofvariablesrangingfromthousandstohundredsofthousands.Theproblemsspanseveralareas,provingitsgeneralityandpower.Forexample,cooperativeoptimizationalgorithmshavebeenproposedforDNAimageanaly-sis[33],shapefromshading[32],stereomatching[30],[34],andimagesegmentation[38].Inthesecondcase,itsignificantlyoutperformedtheclassicsimulatedannealinginfindingglobaloptimalsolutions.Inthethirdcase,itsperformanceiscomparablewithgraphcutsintermsofsolutionquality,andistwiceasfasterasgraphcutsinsoftwaresimulationusingthecommonevaluationframeworkforstereomatching[13].Inthefourthcase,itistentimesfasterthangraphcutsandhasreducedtheerrorratebytwotothreefactors.Inallthesecases,itsmemoryusageisefficientandfixed,itsoperationsaresimple,regular,andfullyscalable.Allthesefeaturesmakeitsuitableforparallelhardwareimplementations.Thispaperisorganizedinthreemajorthemesas1)aformalpresentationforcooperativeoptimization,2)designissues,and3)acasestudy.Theyarethegeneralizationandtheextensi