BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Microsoft Research Machine Learning and Perception
Seminars
SUMMARY:Efficient Multi-dimensional Parametric Mincuts for
Constrained MAP Inference - Kyomin Jung\, KAIST
DTSTART;TZID=Europe/London:20130802T110000
DTEND;TZID=Europe/London:20130802T120000
UID:TALK46507AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/46507
DESCRIPTION:Energy minimization algorithms\, such as graph cut
s\, enable the computation of the MAP solution und
er certain probabilistic models such as Markov ran
dom fields. However\, for many computer vision pro
blems\, the MAP solution under the model is not th
e ground truth solution. In many problem scenarios
\, the system has access to certain statistics of
the ground truth. For instance\, in image segmenta
tion\, 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 wit
h such statistics\, i.e.\, satisfies certain equal
ity or inequality constraints.\nIn 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 p
roblem can be formulated as a multi-dimensional pa
rametric mincut problem via its Lagrangian dual\,
and prove that our algorithm isolates all constrai
nt instances for which the problem can be solved e
xactly. These multiple solutions enable us to even
deal with `soft constraints' (higher order penalt
y functions). Moreover\, we propose practical vari
ants of our algorithm to solve problems with hard
constraints. We also show how our method can be ap
plied to solve various constrained discrete optimi
zation problems such as submodular minimization an
d shortest path computation. We demonstrate the ef
ficacy of our algorithms on the foreground/backgro
und image segmentation problem\, and show that it
produces impressive segmentation results with less
error\, and runs more than 10 times faster than t
he state-of-the-art LP relaxation based approaches
.\nThis is a joint work with Yongsub Lim and Pushm
eet Kohli.\n
LOCATION:Microsoft Research Ltd\, 21 Station Road\, Cambrid
ge\, CB1 2FB
CONTACT:Microsoft Research Cambridge Talks Admins
END:VEVENT
END:VCALENDAR