Lecture Notes in Computer Science 5681 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Daniel Cremers Yuri Boykov Andrew Blake Frank R. Schmidt (Eds.) Energy Minimization Methods in Computer Vision and Pattern Recognition 7th International Conference, EMMCVPR 2009 Bonn, Germany, August 24-27, 2009 Proceedings 1 3 VolumeEditors DanielCremers FrankR.Schmidt UniversitätBonn,InstitutfürInformatikIII Römerstraße164,53117Bonn,Germany E-mail:{dcremers;schmidtf}@cs.uni-bonn.de YuriBoykov ComputerScienceDepartment UniversityofWesternOntario N6A5A5London,ON,Canada E-mail:[email protected] AndrewBlake MicrosoftResearch,CB3OFBCambridge J.J.ThomsonAvenue,UnitedKingdom E-mail:[email protected] LibraryofCongressControlNumber:2001012345 CRSubjectClassification(1998):I.5,I.2.10,I.4,G.1.2,G.3,H.3.4,B.8 LNCSSublibrary:SL6–ImageProcessing,ComputerVision, PatternRecognition,andGraphics ISSN 0302-9743 ISBN-10 3-642-03640-6SpringerBerlinHeidelbergNewYork ISBN-13 978-3-642-03640-8SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. springer.com ©Springer-VerlagBerlinHeidelberg2009 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:12733095 06/3180 543210 Preface Overthelastdecades,energyminimizationmethodshavebecomeanestablished paradigm to resolve a variety of challenges in the fields of computer vision and patternrecognition.While traditionalapproachestocomputervisionwereoften based on a heuristic sequence of processing steps and merely allowed very lim- ited theoretical understanding of the respective methods, most state-of-the-art methods are nowadays based on the concept of computing solutions to a given problem by minimizing respective energies. This volume contains the papers presented at the 7th International Confer- ence on Energy Minimization Methods in Computer Vision and PatternRecog- nition (EMMCVPR 2009), held at the University of Bonn, Germany, August 24–28,2009.These papersdemonstrate thatenergyminimization methods have become a mature fieldof researchspanning abroadrangeofareasfromdiscrete graph theoretic approaches and Markov random fields to variational methods andpartialdifferentialequations.Applicationareasinclude imagesegmentation andtracking,shape optimizationandregistration,inpainting andimage denois- ing, color and texture modeling, statistics and learning. Overall, we received 75 high-qualitydouble-blindsubmissions.Basedonthe reviewerrecommendations, 36paperswereselectedforpublication,18asoraland18asposterpresentations. Both oral and poster papers were attributed the same number of pages in the conference proceedings. Furthermore, we were delighted that three leading experts from the fields of computer vision and energy minimization, namely, Richard Hartley (Can- berra, Australia), Joachim Weickert (Saarbru¨cken, Germany) and Guillermo Sapiro(Minneapolis,USA)agreedtofurtherenrichtheconferencewithinspiring keynote lectures. We would like to express our gratitute to those who made this event possi- ble and contributed to its success, in particular to a strong international Pro- gram Committee for providing excellent reviews and to the Hausdorff Center for Mathematics for providing financial support and guidance. We are partic- ularly grateful to Heidi Georges-Hecking, Mohamed Souiai and the staff of the Hausdorff Center for administrative support. It is our belief that this conference will help to advance the field of energy minimizationmethods andto further establishthe mathematicalfoundations of computer vision. August 2009 Daniel Cremers Yuri Boykov Andrew Blake Frank R. Schmidt Table of Contents Discrete Optimization and Markov Random Fields Multi-label Moves for MRFs with Truncated Convex Priors ........... 1 Olga Veksler Detection and Segmentation of Independently Moving Objects from Dense Scene Flow................................................ 14 Andreas Wedel, Annemarie Meißner, Clemens Rabe, Uwe Franke, and Daniel Cremers Efficient Global Minimization for the Multiphase Chan-Vese Model of Image Segmentation ............................................. 28 Egil Bae and Xue-Cheng Tai Bipartite Graph Matching Computation on GPU .................... 42 Cristina Nader Vasconcelos and Bodo Rosenhahn Pose-Invariant Face Matching Using MRF Energy Minimization Framework...................................................... 56 Shervin Rahimzadeh Arashloo and Josef Kittler ParallelHidden HierarchicalFields for Multi-scale Reconstruction...... 70 Ying Liu and Paul Fieguth General Search Algorithms for Energy Minimization Problems......... 84 Dmitrij Schlesinger Partial Differential Equations Complex Diffusion on Scalar and Vector Valued Image Graphs......... 98 Dohyung Seo and Baba C. Vemuri A PDE Approach to Coupled Super-Resolution with Non-parametric Motion ......................................................... 112 Mehran Ebrahimi and Anne L. Martel On a Decomposition Model for Optical Flow ........................ 126 Jochen Abhau, Zakaria Belhachmi, and Otmar Scherzer A Schro¨dinger Wave Equation Approach to the Eikonal Equation: Application to Image Analysis ..................................... 140 Anand Rangarajan and Karthik S. Gurumoorthy VIII Table of Contents Computing the Local Continuity Order of Optical Flow Using Fractional Variational Method .................................... 154 K. Kashu, Y. Kameda, A. Imiya, T. Sakai, and Y. Mochizuki A Local Normal-BasedRegion Term for Active Contours.............. 168 Julien Mille and Laurent D. Cohen Segmentation and Tracking Hierarchical Pairwise Segmentation Using Dominant Sets and Anisotropic Diffusion Kernels...................................... 182 Andrea Torsello and Marcello Pelillo Tracking as Segmentation of Spatial-Temporal Volumes by Anisotropic Weighted TV.................................................... 193 Markus Unger, Thomas Mauthner, Thomas Pock, and Horst Bischof Complementary Optic Flow ....................................... 207 Henning Zimmer, Andr´es Bruhn, Joachim Weickert, Levi Valgaerts, Agust´ın Salgado, Bodo Rosenhahn, and Hans-Peter Seidel Parameter Estimation for Marked Point Processes. Application to Object Extraction from Remote Sensing Images...................... 221 Florent Chatelain, Xavier Descombes, and Josiane Zerubia Three Dimensional Monocular Human Motion Analysis in End-Effector Space .......................................................... 235 Søren Hauberg, Jerome Lapuyade, Morten Engell-Nørreg˚ard, Kenny Erleben, and Kim Steenstrup Pedersen RobustSegmentationbyCuttingacrossaStackofGammaTransformed Images ......................................................... 249 Elena Bernardis and Stella X. Yu Shape Optimization and Registration Integrating the Normal Field of a Surface in the Presence of Discontinuities................................................... 261 Jean-Denis Durou, Jean-Franc¸ois Aujol, and Fr´ed´eric Courteille Intrinsic Second-Order Geometric Optimization for Robust Point Set Registration without Correspondence............................... 274 Dirk Breitenreicher and Christoph Schn¨orr Geodesics in Shape Space via Variational Time Discretization ......... 288 Benedikt Wirth, Leah Bar, Martin Rumpf, and Guillermo Sapiro Table of Contents IX Image Registration under Varying Illumination: Hyper-Demons Algorithm....................................................... 303 Mehran Ebrahimi and Anne L. Martel Hierarchical Vibrations: A Structural Decomposition Approach for Image Analysis .................................................. 317 Karin Engel and Klaus D. Toennies Inpainting and Image Denoising Exemplar-BasedInterpolation of Sparsely Sampled Images ............ 331 Gabriele Facciolo, Pablo Arias, Vicent Caselles, and Guillermo Sapiro A Variational Framework for Non-local Image Inpainting ............. 345 Pablo Arias, Vicent Caselles, and Guillermo Sapiro Image Filtering Driven by Level Curves............................. 359 Ajit Rajwade, Arunava Banerjee, and Anand Rangarajan Color Image Restoration Using Nonlocal Mumford-Shah Regularizers... 373 Miyoun Jung, Xavier Bresson, Tony F. Chan, and Luminita A. Vese Reconstructing Optical Flow Fields by Motion Inpainting ............. 388 Benjamin Berkels, Claudia Kondermann, Christoph Garbe, and Martin Rumpf Color and Texture Color Image Segmentation in a Quaternion Framework ............... 401 O¨zlem N. Subakan and Baba C. Vemuri Quaternion-Based Color Image Smoothing Using a Spatially Varying Kernel.......................................................... 415 O¨zlem N. Subakan and Baba C. Vemuri Locally ParallelTextures Modeling with Adapted Hilbert Spaces....... 429 Pierre Maurel, Jean-Franc¸ois Aujol, and Gabriel Peyr´e Global Optimal Multiple Object Detection Using the Fusion of Shape and Color Information............................................ 443 Marek Schikora Statistics and Learning Human Age Estimation by Metric Learning for Regression Problems ... 455 Leting Pan X Table of Contents Clustering-Based Construction of Hidden Markov Models for Generative Kernels............................................... 466 Manuele Bicego, Marco Cristani, Vittorio Murino, Elz˙bieta Pekalska, and Robert P.W. Duin (cid:2) Boundaries as Contours of Optimal Appearance and Area of Support... 480 Christina Pavlopoulou and Stella X. Yu Author Index.................................................. 493 Multi-label Moves for MRFs with Truncated Convex Priors OlgaVeksler ComputerScienceDepartment UniversityofWesternOntario London,Canada [email protected] Abstract. Optimization with graph cuts became very popular in recent years. As more applications rely on graph cuts, different energy functions are being employed.Recentevaluationofoptimizationalgorithmsshowedthatthewidely usedswapandexpansiongraphcutalgorithmshaveanexcellentperformancefor energieswheretheunderlyingMRFhasPottsprior.Pottspriorcorrespondstoas- sumingthatthetruelabelingispiecewiseconstant.Whilesurprisinglyusefulin practice,Pottspriorisclearlynot appropriateinmanycircumstances. However for more general priors, the swap and expansion algorithms do not perform as well.Bothalgorithmsarebasedonmovesthatgiveeachpixelachoiceofonly twolabels.Thereforesuchmovescanbereferredtoasbinarymoves.Recently, rangemovesthatactonmultiplelabelssimultaneouslywereintroduced.Asop- posed toswap and expansion, each pixel has achoice of more than twolabels inarangemove.Thereforewecallthemmulti-labelmoves.Rangemoveswere shown to work better for problems with truncated convex priors, which imply apiecewisesmooth labeling. Inspiredbyrange moves, wedevelop several dif- ferentvariantsofmulti-labelmoves.Weevaluatethemontheproblemofstereo correspondenceanddiscusstheirrelativemerits. 1 Introduction Energyoptimizationwithgraphcuts[1,2,3]isincreasinglyusedfordifferentapplica- tionsincomputervisionandgraphics.Someexamplesareimagerestoration[2],stereo and multi-view reconstruction [4,5,2,6,7], motion segmentation [8,9,10], texture syn- thesis[11],segmentation[12,13,14,15],digitalphotomontage[16].Optimizationwith graphcutseitherresultsin an exactminimumor anapproximateminimumwith non- trivialqualityguarantees.Thisfrequentlytranslatesintoaresultofhighaccuracy,given thattheenergyfunctionisappropriatefortheapplication. Atypicalenergyfunctiontobeminimizedisasfollows: (cid:2) (cid:2) E(f)= D (f )+ V (f ,f ). (1) p p pq p q p∈P (p,q)∈N InEq.(1),Lisafinitesetoflabels,representingthepropertyneededtobeestimatedat eachpixel,suchasintensity,color,etc.Pisthesetofsitesthatoneneedstoassignlabels to. FrequentlyP is set of image pixels.The labelassigned to pixelp ∈ P is denoted D.Cremersetal.(Eds.):EMMCVPR2009,LNCS5681,pp.1–13,2009. (cid:2)c Springer-VerlagBerlinHeidelberg2009 2 O.Veksler byf ,andf isthecollectionofallpixel-labelassignments.ThefirstsuminEq.(1)is p the data term. In the data term,D (f ) is the penaltyfor pixelp to be assigned label p p f .Thedatatermusuallycomesfromtheobserveddata.ThesecondsuminEq.(1)is p thesmoothnessterm,anditusesthepriorknowledgeaboutwhatthelikelylabelingsf shouldbelike.Thesumisoverorderedpixelpairs(p,q) ∈ N. OftenN isthe4or8 connectedgrid,howeverlongerrangeinteractionsare also useful[5]. Withoutloss of generality,weassumethatif(p,q)∈N thenp<q. Any choice for D is easy to handle. The choice of V determines whether the p pq energy function can be efficiently minimized. The V ’s often specify the smooth- pq nessassumptionsonthelabelingf.DifferentchoicesofV ’scorrespondtodifferent pq smoothnessassumptions.AcommonchoiceisthePottsmodel,whichisV (f ,f )= pq p q w ·min{1,|f −f |}.Thecoefficientsw ’scanbedifferentforeachpairofneigh- pq p q pq boring pixels. Potts model penalizes any difference between f and f by the same p q amount.Intuitively,it correspondsto the prior knowledgethat f should be piecewise constant,that is it consists of severalpieces where pixelsinside the same piece share thesamelabel. Anothercommonchoice is V (f ,f ) = w ·min{T,|f −f |a}. If a = 1 the pq p q pq p q modeliscalledatruncatedlinear,andifa=2,itiscalledatruncatedquadratic.These V ’scorrespondtothepiecewisesmoothassumptiononf,thatistheassumptionthat pq f consists of severalpieces, where the labels between neighboringpixels inside each piecevary“smoothly”1.ParameterT iscalledatruncationconstant.Withoutthetrun- cation,thatisifV istheabsolutelinearorquadraticdifference,theenergyinEq.(1) pq canbeoptimizedexactlywithagraphcut[17],butthecorrespondingenergiesarenot discontinuitypreserving.EnergyinEq.(1)isNP-hardtooptimizeifdiscontinuitypre- servingPotts,truncatedlinearorquadraticV ’sareused[2]. pq Recently, Szeliskiet.al. [18] performedan experimentalevaluationof severalopti- mizationmethodspopularforminimizingenergiesinEq.(1):thegraphcutbasedex- pansion and swap algorithms [2], sequential tree-reweighted message passing (TRW-S) [19], and loopy belief propagation (LBP) [20]. They show that for Potts model,bothexpansionandswap algorithmshave an excellentperformance,they find ananswerwithinasmallpercentageoftheglobalminimum.TRW-Sperformsaswell asgraphcuts,buttakessignificantlylongertoconverge.Anadditionalbenefitofgraph cutsoverTRW-Siswhenlongerrangeinteractionsarepresent.Szeliskiet.al.[18]stud- ied only the case when N is the 4-connectedgrid. Kolmogorovand Rother [21] per- formeda comparisonbetween graphcuts and TRW-S when longerrangeinteractions arepresent,andtheyconcludedthatgraphcutsperformsignificantlybetterintermsof energythanTRW-Sinthiscase.ForthetruncatedlinearV ’stheexpansionandswap pq algorithmsstillperformrelativelywell,butforthetruncatedquadraticV theenergy pq valueisnoticeablyworsethanthatofTRW-S. Recently[22]developedanewtypeofmoves,calledtherangemovesforoptimizing energieswithtruncatedconvexpriors.Atruncatedquadraticandlinearareexamplesof truncatedconvexprior.Informally,truncatedconvexpriorscorrespondtoassumingthat f ispiecewisesmooth.Theinsightin[22]isthatbothexpansionandswapalgorithms giveapixelachoiceofonlytwolabels,butforproblemswherepiecewisesmoothness 1Theterm“smoothly”isusedinformallyhere.