[理学]ICCV07_tutorial_yuri_Discrete Optimization Methods on Computer Vision.ppt

Disclaimer Can not possibly cover all discrete optimization methods widely used in computer vision in the last 30 years We mainly concentrate on Discrete energy minimization methods that can be applied to Markov Random Fields with binary or n-labels applicable to a wide spectrum of problems in vision Methods motivated by LP relaxations good bounds on the solutions Discrete Optimization Methods in Computer Vision Part I: basic overview of graph cuts binary labeling a few basic examples energy optimization submodularity (discrete view) continuous functionals (geometric view) posterior MRF energy (statistical view) extensions to multi-label problems interactions: convex, robust, metric move-based optimization 2D Graph cut shortest path on a graph Graph cuts for optimal boundary detection(BJ, ICCV’01) Standard minimum s-t cuts algorithms Optimal boundary in 2D Optimal boundary in 3D Graph cuts applied to multi-view reconstruction Adding regional properties(BJ, ICCV’01) Adding regional properties(BJ, ICCV’01) Adding regional properties(BJ, ICCV’01) Adding regional properties(BJ, ICCV’01) Iterative learning of regional color-models GMMRF cuts (Blake et al., ECCV04) Grab-cut (Rother et al., SIGGRAPH 04) At least three ways to look atenergy of graph cuts I: Binary submodular energy II: Approximating continuous surface functionals III: Posterior energy (MAP-MRF) Simple example of energy binary object segmentation Graph cuts for minimization of submodular binary energies I Characterization of binary energies that can be globally minimized by s-t graph cuts [BorosHummer, 2002, KZ 2004] Non-submodular cases can be addressed with some optimality guarantees, e.g. QPBO algorithm (see BorosHummer, 2002, Tavares et al. 06, Rother et al. 07) Graph cuts for minimization of continuous surface functionals II One extension using parametric max-flow methods optimization of ratio functionals In 2D can use DP [Cox et