Efficient Multi-dimensional Parametric Mincuts for Constrained MAP Inference

Add to your list(s) Download to your calendar using vCal

• Kyomin Jung, KAIST
• Friday 02 August 2013, 11:00-12:00
• Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

This event may be recorded and made available internally or externally via http://research.microsoft.com. Microsoft will own the copyright of any recordings made. If you do not wish to have your image/voice recorded please consider this before attending

Energy minimization algorithms, such as graph cuts, enable the computation of the MAP solution under certain probabilistic models such as Markov random fields. However, for many computer vision problems, the MAP solution under the model is not the ground truth solution. In many problem scenarios, the system has access to certain statistics of the ground truth. For instance, in image segmentation, the area and boundary length of the object may be known. In these cases, we want to estimate the most probable solution that is consistent with such statistics, i.e., satisfies certain equality or inequality constraints. In this work, we propose novel algorithms for inferring the Maximum a Posteriori (MAP) solution of discrete pairwise random field models under multiple constraints. We show how this constrained discrete optimization problem can be formulated as a multi-dimensional parametric mincut problem via its Lagrangian dual, and prove that our algorithm isolates all constraint instances for which the problem can be solved exactly. These multiple solutions enable us to even deal with `soft constraints’ (higher order penalty functions). Moreover, we propose practical variants of our algorithm to solve problems with hard constraints. We also show how our method can be applied to solve various constrained discrete optimization problems such as submodular minimization and shortest path computation. We demonstrate the efficacy of our algorithms on the foreground/background image segmentation problem, and show that it produces impressive segmentation results with less error, and runs more than 10 times faster than the state-of-the-art LP relaxation based approaches. This is a joint work with Yongsub Lim and Pushmeet Kohli.

This talk is part of the Microsoft Research Machine Learning and Perception Seminars series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• ML
• Machine Learning Summary
• Microsoft Research Cambridge, public talks
• Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB
• Microsoft Research Machine Learning and Perception Seminars
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587
• yk373's list

Note that ex-directory lists are not shown.