BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Efficient Multi-dimensional Parametric Mincuts for Constrained MAP
  Inference - Kyomin Jung\, KAIST
DTSTART:20130802T100000Z
DTEND:20130802T110000Z
UID:TALK46507@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:Energy minimization algorithms\, such as graph cuts\, enable t
 he computation of the MAP solution under certain probabilistic models such
  as Markov random fields. However\, for many computer vision problems\, th
 e MAP solution under the model is not the ground truth solution. In many p
 roblem scenarios\, the system has access to certain statistics of the grou
 nd truth. For instance\, in image segmentation\, the area and boundary len
 gth of the object may be known. In these cases\, we want to estimate the m
 ost probable solution that is consistent with such statistics\, i.e.\, sat
 isfies certain equality or inequality constraints.\nIn this work\, we prop
 ose novel algorithms for inferring the Maximum a Posteriori (MAP) solution
  of discrete pairwise random field models under multiple constraints. We s
 how how this constrained discrete optimization problem can be formulated a
 s a multi-dimensional parametric mincut problem via its Lagrangian dual\, 
 and prove that our algorithm isolates all constraint instances for which t
 he problem can be solved exactly. These multiple solutions enable us to ev
 en deal with `soft constraints' (higher order penalty functions). Moreover
 \, we propose practical variants of our algorithm to solve problems with h
 ard constraints. We also show how our method can be applied to solve vario
 us constrained discrete optimization problems such as submodular minimizat
 ion and shortest path computation. We demonstrate the efficacy of our algo
 rithms on the foreground/background image segmentation problem\, and show 
 that it produces impressive segmentation results with less error\, and run
 s more than 10 times faster than the state-of-the-art LP relaxation based 
 approaches.\nThis is a joint work with Yongsub Lim and Pushmeet Kohli.\n
LOCATION:Microsoft Research Ltd\, 21 Station Road\, Cambridge\, CB1 2FB
END:VEVENT
END:VCALENDAR