 |
    |
Approximate MRF Inference Using Bounded Treewidth Subgraphs
Alexander Fix1, Joyce Chen1, Endre Boros2, and Ramin Zabih1
1Cornell University, Computer Science Department, Ithaca, New York USA
afix@cs.cornell.edu
yuhsin@cs.cornell.edu
rdz@cs.cornell.edu
2Rutgers University, RUTCOR, New Brunswick, New Jersey USA
boros@rci.rutgers.edu
Abstract. Graph cut algorithms [9], commonly used in computer vision, solve a first-order MRF over binary variables. The state of the art for this NP-hard problem is QPBO [1,2], which finds the values for a subset of the variables in the global minimum. While QPBO is very effective overall there are still many difficult problems where it can only label a small subset of the variables. We propose a new approach that, instead of optimizing the original graphical model, instead optimizes a tractable sub-model, defined as an energy function that uses a subset of the pairwise interactions of the original, but for which exact inference can be done efficiently. Our Bounded Treewidth Subgraph (k-BTS) algorithm greedily computes a large weight treewidth-k subgraph of the signed graph, then solves the energy minimization problem for this subgraph by dynamic programming. The edges omitted by our greedy method provide a per-instance lower bound. We demonstrate promising experimental results for binary deconvolution, a challenging problem used to benchmark QPBO [2]: our algorithm performs an order of magnitude better than QPBO or its common variants [4], both in terms of energy and accuracy, and the visual quality of our output is strikingly better as well. We also obtain a significant improvement in energy and accuracy on a stereo benchmark with 2nd order priors [5], although the improvement in visual quality is more modest. Our method’s running time is comparable to QPBO.
LNCS 7572, p. 385 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012