Beyond Trees: MRF Inference via Outer-Planar Decomposition


December 14, 2009


Dhruv Batra


Carnegie Mellon University


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 (eg trees via BP), or approximate inference algorithms (eg Loopy BP and Tree-reweighted message passing).

I will first present a unifying perspective of these approximate techniques – called “Decomposition Methods”. These are methods that decompose the given problem over a graph into tractable subproblems over subgraphs and then employ message passing over these subgraphs to get a global solution. This provides a new way of thinking about BP and TRW as successive steps in a hierarchy of decomposition methods. Using this framework, we take the first step towards extending this hierarchy beyond trees. We leverage a new class of graphs amenable to exact inference, called outer-planar graphs, and propose an approximate inference algorithm called Outer- Planar Decomposition (OPD). OPD is a strict generalization of BP and TRW, and contains both of them as special cases. Our experiments show that this extension beyond trees is indeed very powerful – OPD outperforms current state- of-art inference methods on hard non-submodular synthetic problems and is competitive on real vision applications.

  • Joint work with Andrew Gallagher (Eastman Kodak), Devi Parikh (TTI-C) and Tsuhan Chen (Cornell, CMU) (* Unpublished work)


Dhruv Batra

Dhruv Batra is a Ph.D. student at Carnegie Mellon University. For the past one year, he has been a visiting student at Cornell. His research interests include computer vision and machine learning. Specifically, his thesis focus is on learning and inference in CRFs, with applications to vision problems like interactive co-segmentation and semantic object segmentation