@article {Swoboda2016,
	title = {Partial Optimality by Pruning for MAP-Inference with General Graphical Models},
	journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
	volume = {38},
	number = {7},
	year = {2016},
	month = {jul},
	pages = {1370{\textendash}1382},
	publisher = {IEEE Computer Society},
	abstract = {We consider the energy minimization problem for undirected graphical models, also known as MAP-inference problem for Markov random fields which is NP-hard in general. We propose a novel polynomial time algorithm to obtain a part of its optimal non-relaxed integral solution. Our algorithm is initialized with variables taking integral values in the solution of a convex relaxation of the MAP-inference problem and iteratively prunes those, which do not satisfy our criterion for partial optimality. We show that our pruning strategy is in a certain sense theoretically optimal. Also empirically our method outperforms previous approaches in terms of the number of persistently labelled variables. The method is very general, as it is applicable to models with arbitrary factors of an arbitrary order and can employ any solver for the considered relaxed problem. Our method{\textquoteright}s runtime is determined by the runtime of the convex relaxation solver for the MAP-inference problem.},
	keywords = {energy minimization, Local polytope, MAP-inference, Markov random fields, partial optimality, persistency},
	issn = {01628828},
	doi = {10.1109/TPAMI.2015.2484327},
	author = {Swoboda, Paul and Shekhovtsov, Alexander and Kappes, Jorg Hendrik and Christoph Schn{\"o}rr and Savchynskyy, Bogdan}
}
@article {Lempitsky2010a,
	title = {Fusion moves for markov random field optimization},
	journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
	volume = {32},
	number = {8},
	year = {2010},
	pages = {1392{\textendash}1405},
	abstract = {The efficient application of graph cuts to Markov Random Fields (MRFs) with multiple discrete or continuous labels remains an open question. In this paper, we demonstrate one possible way of achieving this by using graph cuts to combine pairs of suboptimal labelings or solutions. We call this combination process the fusion move. By employing recently developed graph-cut-based algorithms (so-called QPBO-graph cut), the fusion move can efficiently combine two proposal labelings in a theoretically sound way, which is in practice often globally optimal. We demonstrate that fusion moves generalize many previous graph-cut approaches, which allows them to be used as building blocks within a broader variety of optimization schemes than were considered before. In particular, we propose new optimization schemes for computer vision MRFs with applications to image restoration, stereo, and optical flow, among others. Within these schemes the fusion moves are used 1) for the parallelization of MRF optimization into several threads, 2) for fast MRF optimization by combining cheap-to-compute solutions, and 3) for the optimization of highly nonconvex continuous-labeled MRFs with 2D labels. Our final example is a nonvision MRF concerned with cartographic label placement, where fusion moves can be used to improve the performance of a standard inference method (loopy belief propagation). {\textcopyright} 2006 IEEE.},
	keywords = {Combinatorial algorithms, Computer vision, Graph algorithms, Image restoration., Markov random fields, Motion, Stereo},
	issn = {01628828},
	doi = {10.1109/TPAMI.2009.143},
	author = {Lempitsky, Victor and Carsten Rother and Roth, Stefan and Blake, Andrew}
}
@article {Lempitsky2010,
	title = {Fusion moves for markov random field optimization},
	journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
	volume = {32},
	number = {8},
	year = {2010},
	pages = {1392{\textendash}1405},
	abstract = {The efficient application of graph cuts to Markov Random Fields (MRFs) with multiple discrete or continuous labels remains an open question. In this paper, we demonstrate one possible way of achieving this by using graph cuts to combine pairs of suboptimal labelings or solutions. We call this combination process the fusion move. By employing recently developed graph-cut-based algorithms (so-called QPBO-graph cut), the fusion move can efficiently combine two proposal labelings in a theoretically sound way, which is in practice often globally optimal. We demonstrate that fusion moves generalize many previous graph-cut approaches, which allows them to be used as building blocks within a broader variety of optimization schemes than were considered before. In particular, we propose new optimization schemes for computer vision MRFs with applications to image restoration, stereo, and optical flow, among others. Within these schemes the fusion moves are used 1) for the parallelization of MRF optimization into several threads, 2) for fast MRF optimization by combining cheap-to-compute solutions, and 3) for the optimization of highly nonconvex continuous-labeled MRFs with 2D labels. Our final example is a nonvision MRF concerned with cartographic label placement, where fusion moves can be used to improve the performance of a standard inference method (loopy belief propagation). {\textcopyright} 2006 IEEE.},
	keywords = {Combinatorial algorithms, Computer vision, Graph algorithms, Image restoration., Markov random fields, Motion, Stereo},
	issn = {01628828},
	doi = {10.1109/TPAMI.2009.143},
	author = {Lempitsky, Victor and Carsten Rother and Roth, Stefan and Blake, Andrew}
}
@article {Szeliski2008,
	title = {A comparative study of energy minimization methods for Markov random fields with smoothness-based priors},
	journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
	volume = {30},
	number = {6},
	year = {2008},
	pages = {1068{\textendash}1080},
	publisher = {Springer-Verlag},
	abstract = {Among the most exciting advances in early vision has been the development of efficient energy minimization algorithms for pixel-labeling tasks such as depth or texture computation. It has been known for decades that such problems can be elegantly expressed as Markov random fields, yet the resulting energy minimization problems have been widely viewed as intractable. Recently, algorithms such as graph cuts and loopy belief propagation (LBP) have proven to be very powerful: for example, such methods form the basis for almost all the top-performing stereo methods. However, the tradeoffs among different energy minimization algorithms are still not well understood. In this paper we describe a set of energy minimization benchmarks and use them to compare the solution quality and running time of several common energy minimization algorithms. We investigate three promising recent methods graph cuts, LBP, and tree-reweighted message passing in addition to the well-known older iterated conditional modes (ICM) algorithm. Our benchmark problems are drawn from published energy functions used for stereo, image stitching, interactive segmentation, and denoising. We also provide a general-purpose software interface that allows vision researchers to easily switch between optimization methods. Benchmarks, code, images, and results are available at http://vision.middlebury.edu/ MRF/. {\textcopyright} 2008 IEEE.},
	keywords = {Belief propagation, Global optimization, Graph Cuts, Markov random fields, Performance evaluation},
	issn = {01628828},
	doi = {10.1109/TPAMI.2007.70844},
	url = {http://vision.middlebury.edu/MRF.},
	author = {Szeliski, Richard and Zabih, Ramin and Scharstein, Daniel and Veksler, Olga and Kolmogorov, Vladimir and Agarwala, Aseem and Tappen, Marshall and Carsten Rother}
}
@article {Szeliski2008a,
	title = {A comparative study of energy minimization methods for Markov random fields with smoothness-based priors},
	journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
	volume = {30},
	number = {6},
	year = {2008},
	month = {jun},
	pages = {1068{\textendash}1080},
	abstract = {Among the most exciting advances in early vision has been the development of efficient energy minimization algorithms for pixel-labeling tasks such as depth or texture computation. It has been known for decades that such problems can be elegantly expressed as Markov random fields, yet the resulting energy minimization problems have been widely viewed as intractable. Recently, algorithms such as graph cuts and loopy belief propagation (LBP) have proven to be very powerful: for example, such methods form the basis for almost all the top-performing stereo methods. However, the tradeoffs among different energy minimization algorithms are still not well understood. In this paper we describe a set of energy minimization benchmarks and use them to compare the solution quality and running time of several common energy minimization algorithms. We investigate three promising recent methods graph cuts, LBP, and tree-reweighted message passing in addition to the well-known older iterated conditional modes (ICM) algorithm. Our benchmark problems are drawn from published energy functions used for stereo, image stitching, interactive segmentation, and denoising. We also provide a general-purpose software interface that allows vision researchers to easily switch between optimization methods. Benchmarks, code, images, and results are available at http://vision.middlebury.edu/ MRF/. {\textcopyright} 2008 IEEE.},
	keywords = {Belief propagation, Global optimization, Graph Cuts, Markov random fields, Performance evaluation},
	issn = {01628828},
	doi = {10.1109/TPAMI.2007.70844},
	author = {Szeliski, Richard and Zabih, Ramin and Scharstein, Daniel and Veksler, Olga and Kolmogorov, Vladimir and Agarwala, Aseem and Tappen, Marshall and Carsten Rother}
}
@booklet {Kolmogorov2007,
	title = {Minimizing nonsubmodular functions with graph cuts - A review},
	howpublished = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
	volume = {29},
	number = {7},
	year = {2007},
	pages = {1274{\textendash}1279},
	abstract = {Optimization techniques based on graph cuts have become a standard tool for many vision applications. These techniques allow to minimize efficiently certain energy functions corresponding to pairwise Markov Random Fields (MRFs). Currently, there is an accepted view within the computer vision community that graph cuts can only be used for optimizing a limited class of MRF energies (e.g., submodular functions). In this survey, we review some results that show that graph cuts can be applied to a much larger class of energy functions (in particular, nonsubmodular functions). While these results are well-known in the optimization community, to our knowledge they were not used in the context of computer vision and MRF optimization. We demonstrate the relevance of these results to vision on the problem of binary texture restoration. {\textcopyright} 2007 IEEE.},
	keywords = {energy minimization, Markov random fields, Min cut/max flow, Quadratic pseudo-Boolean optimization, Texture restoration},
	issn = {01628828},
	doi = {10.1109/TPAMI.2007.1031},
	author = {Kolmogorov, Vladimir and Carsten Rother}
}
