Beyond Trees: MRF Inference via Outer-Planar Decomposition

Speaker  Dhruv Batra

Host  Larry Zitnick

Affiliation  Carnegie Mellon University

Duration  00:48:53

Date recorded  14 December 2009

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)
©2009 Microsoft Corporation. All rights reserved.
> Beyond Trees: MRF Inference via Outer-Planar Decomposition