@conference {Vicente2010,
	title = {Cosegmentation revisited: Models and optimization},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	volume = {6312 LNCS},
	number = {PART 2},
	year = {2010},
	pages = {465{\textendash}479},
	abstract = {The problem of cosegmentation consists of segmenting the same object (or objects of the same class) in two or more distinct images. Recently a number of different models have been proposed for this problem. However, no comparison of such models and corresponding optimization techniques has been done so far. We analyze three existing models: the L1 norm model of Rother et al. [1], the L2 norm model of Mukherjee et al. [2] and the "reward" model of Hochbaum and Singh [3]. We also study a new model, which is a straightforward extension of the Boykov-Jolly model for single image segmentation [4]. In terms of optimization, we use a Dual Decomposition (DD) technique in addition to optimization methods in [1,2]. Experiments show a significant improvement of DD over published methods. Our main conclusion, however, is that the new model is the best overall because it: (i) has fewest parameters; (ii) is most robust in practice, and (iii) can be optimized well with an efficient EM-style procedure. {\textcopyright} 2010 Springer-Verlag.},
	isbn = {3642155510},
	issn = {16113349},
	doi = {10.1007/978-3-642-15552-9_34},
	author = {Vicente, Sara and Kolmogorov, Vladimir and Carsten Rother}
}
@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}
}
@conference {Kolmogorov2006a,
	title = {Comparison of energy minimization algorithms for highly connected graphs},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	volume = {3952 LNCS},
	year = {2006},
	pages = {1{\textendash}15},
	abstract = {Algorithms for discrete energy minimization play a fundamental role for low-level vision. Known techniques include graph cuts, belief propagation (BP) and recently introduced tree-reweighted message passing (TRW). So far, the standard benchmark for their comparison has been a 4-connected grid-graph arising in pixel-labelling stereo. This minimization problem, however, has been largely solved: recent work shows that for many scenes TRW finds the global optimum. Furthermore, it is known that a 4-connecled grid-graph is a poor stereo model since it does not take occlusions into account. We propose the problem of stereo with occlusions as a new test bed for minimization algorithms. This is a more challenging graph since it has much larger connectivity, and it also serves as a better stereo model. An attractive feature of this problem is that increased connectivity does not result in increased complexity of message passing algorithms. Indeed, one contribution of this paper is to show that sophisticated implementations of BP and TRW have the same time and memory complexity as that of 4-connecled grid-graph stereo. The main conclusion of our experimental study is that for our problem graph cut outperforms both TRW and BP considerably. TRW achieves consistently a lower energy than BP. However, as connectivity increases the speed of convergence of TRW becomes slower. Unlike 4-connected grids, the difference between the energy of the best optimization method and the lower bound of TRW appears significant. This shows the hardness of the problem and motivates future research. {\textcopyright} Springer-Verlag Berlin Heidelberg 2006.},
	isbn = {3540338349},
	issn = {16113349},
	doi = {10.1007/11744047_1},
	author = {Kolmogorov, Vladimir and Carsten Rother}
}
@conference {Kolmogorov2006b,
	title = {Comparison of energy minimization algorithms for highly connected graphs},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	volume = {3952 LNCS},
	year = {2006},
	pages = {1{\textendash}15},
	abstract = {Algorithms for discrete energy minimization play a fundamental role for low-level vision. Known techniques include graph cuts, belief propagation (BP) and recently introduced tree-reweighted message passing (TRW). So far, the standard benchmark for their comparison has been a 4-connected grid-graph arising in pixel-labelling stereo. This minimization problem, however, has been largely solved: recent work shows that for many scenes TRW finds the global optimum. Furthermore, it is known that a 4-connecled grid-graph is a poor stereo model since it does not take occlusions into account. We propose the problem of stereo with occlusions as a new test bed for minimization algorithms. This is a more challenging graph since it has much larger connectivity, and it also serves as a better stereo model. An attractive feature of this problem is that increased connectivity does not result in increased complexity of message passing algorithms. Indeed, one contribution of this paper is to show that sophisticated implementations of BP and TRW have the same time and memory complexity as that of 4-connecled grid-graph stereo. The main conclusion of our experimental study is that for our problem graph cut outperforms both TRW and BP considerably. TRW achieves consistently a lower energy than BP. However, as connectivity increases the speed of convergence of TRW becomes slower. Unlike 4-connected grids, the difference between the energy of the best optimization method and the lower bound of TRW appears significant. This shows the hardness of the problem and motivates future research. {\textcopyright} Springer-Verlag Berlin Heidelberg 2006.},
	isbn = {3540338349},
	issn = {16113349},
	doi = {10.1007/11744047_1},
	author = {Kolmogorov, Vladimir and Carsten Rother}
}
@conference {Rother2006,
	title = {Cosegmentation of image pairs by histogram matching - Incorporating a global constraint into MRFs},
	booktitle = {Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition},
	volume = {1},
	year = {2006},
	pages = {994{\textendash}1000},
	abstract = {We introduce the term cosegmentation which denotes the task of segmenting simultaneously the common parts of an image pair. A generative model for cosegmentation is presented. Inference in the model leads to minimizing an energy with an MRF term encoding spatial coherency and a global constraint which attempts to match the appearance histograms of the common parts. This energy has not been proposed previously and its optimization is challenging and NP-hard. For this problem a novel optimization scheme which we call trust region graph cuts is presented. We demonstrate that this framework has the potential to improve a wide range of research: Object driven image retrieval, video tracking and segmentation, and interactive image editing. The power of the framework lies in its generality, the common part can be a rigid/non-rigid object (or scene), observed from different viewpoints or even similar objects of the same class. {\textcopyright} 2006 IEEE.},
	isbn = {0769525970},
	issn = {10636919},
	doi = {10.1109/CVPR.2006.91},
	url = {http://research.microsoft.com/vision/cambridge/},
	author = {Carsten Rother and Kolmogorov, Vladimir and Minka, Tom and Blake, Andrew}
}
