[Colloquium] TTI-C Talk: Dhruv Batra, CMU

[Julia MacGlashan]

When:             *Tuesday, Nov 24 @ 10:30am*

Where:           * TTI-C Conference Room #526*, 6045 S Kenwood Ave

Who:               *Dhruv Batra*, CMU

Title:          *      **Beyond Trees: MRF Inference via Outer-Planar
Decomposition*


A number of computer vision tasks can be formulated as discrete labelling
problems. Markov Random Fields (MRFs) provide natural mathematical
frameworks for modelling and solving these labelling problems. Maximum a
posteriori (MAP) inference in MRFs (or energy minimization) is known to be
NP-hard in general, and thus research has focussed on either finding
efficiently solvable subclasses (such as trees and polytrees via Belief
Propagation), or approximate inference algorithms (such as Loopy Belief
Propagation and Tree-reweighted message passing).

More recently, it has been shown that MAP inference on outer-planar graphs
can be performed by formulating as a max-cut problem in planar graphs. In
this work, we leverage this new class amenable to exact inference, and
propose an approximate inference algorithm called Outer-Planar Decomposition
(OPD). OPD involves ``decomposing'' an arbitrary energy function into energy
functions over outer-planar graphs, and then a message passing algorithm
over these outer-planar graphs. OPD is a strict generalization of
tree-reweighted methods and contains as special cases each of the three TRW
algorithms -- TRW-T, TRW-S and TRW-DD. Our Experiments show that OPD
significantly outperforms current state of art inference methods -- TRW,
QPBO and BP.

Time permitting, I will also briefly talk about my work on interactive
co-segmentation of related images -- present a novel distance metric
algorithm and show a video about of our system presented at the CVPR '09
Demo session. Our recommendation system is able to guide users as to which
image (and where) to scribble next. User studies showed our system is less
cumbersome for users and facilitates quicker segmentation of many related
images, as compared to a baseline set up.

Joint work with Andrew Gallagher (Eastman Kodak) and Devi Parikh (TTI-C)
(* Unpublished work)


Contact:          Greg Shakhnarovich, TTI-C
greg at tti-c.org<nati at tti-c.org><nati at tti-c.org>
  834-2572
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20091117/38482e6f/attachment.htm