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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Boros, E., Hammer, P.L.: Pseudo-boolean optimization. Discrete Applied Mathematics 123 (2002)
Kolmogorov, V., Rother, C.: Minimizing nonsubmodular functions with graph cuts-a review. TPAMI 29, 1274–1279 (2007); Earlier version appears as technical report MSR-TR-2006-100
Boros, E., Hammer, P., Sun, R., Tavares, G.: A max-flow approach to improved lower bounds for quadratic 0 − 1 minimization. Discrete Optimization 5, 501–529 (2008); Also appeared as 2006 RUTCOR technical report
Rother, C., Kolmogorov, V., Lempitsky, V., Szummer, M.: Optimizing binary MRFs via extended roof duality. In: CVPR (2007)
Woodford, O., Torr, P., Reid, I., Fitzgibbon, A.: Global stereo reconstruction under second-order smoothness priors. TPAMI 31, 2115–2128 (2009)
Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., Rother, C.: A comparative study of energy minimization methods for Markov Random Fields. TPAMI 30, 1068–1080 (2008)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? TPAMI 26, 147–159 (2004)
Boros, E., Hammer, P.: A max-flow approach to improved roof-duality in quadratic 0 − 1 minimization. Technical report, RUTCOR (1989)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. TPAMI 23, 1222–1239 (2001)
Hammer, P., Rudeanu, S.: Boolean Methods in Operations Research and Related Areas. Springer (1968)
Hammer, P.: Some network flow problems solved with pseudo-boolean programming. Operations Research 13, 388–399 (1965)
Hammer, P.L., Hansen, P., Simeone, B.: Roof duality, complementation and persistency in quadratic 0-1 optimization. Mathematical Programming 28, 121–155 (1984)
Feige, U., Goemans, M.: Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In: 3rd Israel Symposium on the Theory of Computing Systems, p. 182 (1995)
Zaslavsky, T.: Signed graphs. Discrete Applied Mathematics 4, 47–74 (1982)
Harary, F.: On the notion of balance of a signed graph. Michigan Mathematical Journal 2, 143–146 (1953)
Hammer, P.L.: Pseudo-boolean remarks on balanced graphs. International Series of Numerical Mathematics 36, 69–78 (1977)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42, 1115–1145 (1995)
Garey, M., Johnson, D.: Computers and Intractability. W. H. Freeman and Company (1979)
Wainwright, M.J., Jordan, M.I.: Graphical Models, Exponential Families, and Variational Inference. Now Publishers Inc., Hanover (2008)
Lipton, R., Tarjan, R.: Applications of a planar separator theorem. SIAM Journal on Computing, 615–627 (1980)
Karger, D.R., Srebro, N.: Learning markov networks: maximum bounded tree-width graphs. In: SODA, pp. 392–401 (2001)
Shahaf, D., Chechetka, A., Guestrin, C.: Learning thin junction trees via graph cuts. In: Artificial Intelligence and Statistics, AISTATS (2009)
Mooij, J.M.: libDAI: A free & open source C++ library for Discrete Approximate Inference in graphical models. Journal of Machine Learning Research 11 (August 2010)
Raj, A., Zabih, R.: A graph cut algorithm for generalized image deconvolution. In: International Conference on Computer Vision, ICCV (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fix, A., Chen, J., Boros, E., Zabih, R. (2012). Approximate MRF Inference Using Bounded Treewidth Subgraphs. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds) Computer Vision – ECCV 2012. ECCV 2012. Lecture Notes in Computer Science, vol 7572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33718-5_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-33718-5_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33717-8
Online ISBN: 978-3-642-33718-5
eBook Packages: Computer ScienceComputer Science (R0)