@article {Lempitsky2012,
	title = {Branch-and-mincut: Global optimization for image segmentation with high-level priors},
	journal = {Journal of Mathematical Imaging and Vision},
	volume = {44},
	number = {3},
	year = {2012},
	pages = {315{\textendash}329},
	abstract = {Efficient global optimization techniques such as graph cut exist for energies corresponding to binary image segmentation from low-level cues. However, introducing a high-level prior such as a shape prior or a color-distribution prior into the segmentation process typically results in an energy that is much harder to optimize. The main contribution of the paper is a new global optimization framework for a wide class of such energies. The framework is built upon two powerful techniques: graph cut and branch-and-bound. These techniques are unified through the derivation of lower bounds on the energies. Being computable via graph cut, these bounds are used to prune branches within a branchand-bound search. We demonstrate that the new framework can compute globally optimal segmentations for a variety of segmentation scenarios in a reasonable time on a modern CPU. These scenarios include unsupervised segmentation of an object undergoing 3D pose change, category-specific shape segmentation, and the segmentation under intensity/color priors defined by Chan-Vese and GrabCut functionals. {\textcopyright} Springer Science+Business Media, LLC 2011.},
	keywords = {Branch-and-bound, Global optimization, Graph Cuts, Image segmentation, Shape priors},
	issn = {09249907},
	doi = {10.1007/s10851-012-0328-0},
	author = {Lempitsky, Victor and Blake, Andrew and Carsten Rother}
}
@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}
}
@conference {Gulshan2010,
	title = {Geodesic star convexity for interactive image segmentation},
	booktitle = {Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition},
	year = {2010},
	pages = {3129{\textendash}3136},
	abstract = {In this paper we introduce a new shape constraint for interactive image segmentation. It is an extension of Veksler{\textquoteright}s [25] star-convexity prior, in two ways: from a single star to multiple stars and from Euclidean rays to Geodesic paths. Global minima of the energy function are obtained subject to these new constraints. We also introduce Geodesic Forests, which exploit the structure of shortest paths in implementing the extended constraints. The star-convexity prior is used here in an interactive setting and this is demonstrated in a practical system. The system is evaluated by means of a "robot user" to measure the amount of interaction required in a precise way. We also introduce a new and harder dataset which augments the existing Grabcut dataset [1] with images and ground truth taken from the PASCAL VOC segmentation challenge [7]. {\textcopyright}2010 IEEE.},
	isbn = {9781424469840},
	issn = {10636919},
	doi = {10.1109/CVPR.2010.5540073},
	author = {Gulshan, Varun and Carsten Rother and Criminisi, Antonio and Blake, Andrew and Zisserman, Andrew}
}
@conference {Gehler2008,
	title = {Bayesian color constancy revisited},
	booktitle = {26th IEEE Conference on Computer Vision and Pattern Recognition, CVPR},
	year = {2008},
	abstract = {Computational color constancy is the task of estimating the true reflectances of visible surfaces in an image. In this paper we follow a line of research that assumes uniform illumination of a scene, and that the principal step in estimating reflectances is the estimation of the scene illuminant. We review recent approaches to illuminant estimation, firstly those based on formulae for normalisation of the reflectance distribution in an image - so-called grey-world algorithms, and those based on a Bayesian formulation of image formation. In evaluating these previous approaches we introduce a new tool in the form of a database of 568 high-quality, indoor and outdoor images, accurately labelled with illuminant, and preserved in their raw form, free of correction or normalisation. This has enabled us to establish several properties experimentally. Firstly automatic selection of grey-world algorithms according to image properties is not nearly so effective as has been thought. Secondly, it is shown that Bayesian illuminant estimation is significantly improved by the improved accuracy of priors for illuminant and reflectance that are obtained from the new dataset. {\textcopyright}2008 IEEE.},
	isbn = {9781424422432},
	doi = {10.1109/CVPR.2008.4587765},
	author = {Gehler, Peter Vincent and Carsten Rother and Blake, Andrew and Minka, Tom and Sharp, Toby}
}
@conference {Lempitsky2008b,
	title = {Image segmentation by branch-and-mincut},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	volume = {5305 LNCS},
	number = {PART 4},
	year = {2008},
	pages = {15{\textendash}29},
	abstract = {Efficient global optimization techniques such as graph cut exist for energies corresponding to binary image segmentation from low-level cues. However, introducing a high-level prior such as a shape prior or a color-distribution prior into the segmentation process typically results in an energy that is much harder to optimize. The main contribution of the paper is a new global optimization framework for a wide class of such energies. The framework is built upon two powerful techniques: graph cut and branch-and-bound. These techniques are unified through the derivation of lower bounds on the energies. Being computable via graph cut, these bounds are used to prune branches within a branch-and-bound search. We demonstrate that the new framework can compute globally optimal segmentations for a variety of segmentation scenarios in a reasonable time on a modern CPU. These scenarios include unsupervised segmentation of an object undergoing 3D pose change, category-specific shape segmentation, and the segmentation under intensity/color priors defined by Chan-Vese and GrabCut functionals. {\textcopyright} 2008 Springer Berlin Heidelberg.},
	isbn = {3540886923},
	issn = {03029743},
	doi = {10.1007/978-3-540-88693-8-2},
	author = {Lempitsky, Victor and Blake, Andrew and Carsten Rother}
}
@conference {Lempitsky2008a,
	title = {Image segmentation by branch-and-mincut},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	volume = {5305 LNCS},
	number = {PART 4},
	year = {2008},
	pages = {15{\textendash}29},
	abstract = {Efficient global optimization techniques such as graph cut exist for energies corresponding to binary image segmentation from low-level cues. However, introducing a high-level prior such as a shape prior or a color-distribution prior into the segmentation process typically results in an energy that is much harder to optimize. The main contribution of the paper is a new global optimization framework for a wide class of such energies. The framework is built upon two powerful techniques: graph cut and branch-and-bound. These techniques are unified through the derivation of lower bounds on the energies. Being computable via graph cut, these bounds are used to prune branches within a branch-and-bound search. We demonstrate that the new framework can compute globally optimal segmentations for a variety of segmentation scenarios in a reasonable time on a modern CPU. These scenarios include unsupervised segmentation of an object undergoing 3D pose change, category-specific shape segmentation, and the segmentation under intensity/color priors defined by Chan-Vese and GrabCut functionals. {\textcopyright} 2008 Springer Berlin Heidelberg.},
	isbn = {3540886923},
	issn = {03029743},
	doi = {10.1007/978-3-540-88693-8-2},
	author = {Lempitsky, Victor and Blake, Andrew and Carsten Rother}
}
@conference {Lempitsky2007,
	title = {LogCut - Efficient graph cut optimization for markov random fields},
	booktitle = {Proceedings of the IEEE International Conference on Computer Vision},
	year = {2007},
	abstract = {Markov Random Fields (MRFs) are ubiquitous in low-level computer vision. In this paper, we propose a new approach to the optimization of multi-labeled MRFs. Similarly to α-expansion it is based on iterative application of binary graph cut. However, the number of binary graph cuts required to compute a labelling grows only logarithmically with the size of label space, instead of linearly. We demonstrate that for applications such as optical flow, image restoration, and high resolution stereo, this gives an order of magnitude speed-up, for comparable energies. Iterations are performed by "fusion" of solutions, done with QPBO which is related to graph cut but can deal with non-submodularity. At convergence, the method achieves optima on a par with the best competitors, and sometimes even exceeds them. {\textcopyright}2007 IEEE.},
	doi = {10.1109/ICCV.2007.4408907},
	author = {Lempitsky, Victor and Carsten Rother and Blake, Andrew}
}
@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}
}
@article {Kolmogorov2006,
	title = {Probabilistic fusion of stereo with color and contrast for bilayer segmentation},
	journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
	volume = {28},
	number = {9},
	year = {2006},
	pages = {1480{\textendash}1492},
	abstract = {This paper describes models and algorithms for the real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from color/contrast or from stereo alone is known to be error-prone. Here, color, contrast, and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, Layered Dynamic Programming (LDP), solves stereo in an extended six-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive color model that is learned on-the-fly and stereo disparities are obtained by dynamic programming. The second algorithm, Layered Graph Cut (LGC), does not directly solve stereo. Instead, the stereo match likelihood is marginalized over disparities to evaluate foreground and background hypotheses and then fused with a contrast-sensitive color model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar performance, substantially better than either stereo or color/contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output. {\textcopyright} 2006 IEEE.},
	keywords = {3D/stereo scene analysis, Computer vision, Dynamic programming, Image processing and computer vision, Parameter learning},
	issn = {01628828},
	doi = {10.1109/TPAMI.2006.193},
	url = {http://research.microsoft.com/vision/cambridge},
	author = {Kolmogorov, Vladimir and Criminisi, Antonio and Blake, Andrew and Cross, Geoffrey and Carsten Rother}
}
@conference {Rother2005,
	title = {Digital tapestry [automatic image synthesis]},
	booktitle = {Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on},
	volume = {1},
	year = {2005},
	pages = {589{\textendash}596},
	abstract = {This paper addresses the novel problem of automatically synthesizing an output image from a large collection of different input images. The synthesized image, called a digital tapestry, can be viewed as a visual summary or a virtual {\textquoteright}thumbnail{\textquoteright} of all the images in the input collection. The problem of creating the tapestry is cast as a multi-class labeling problem such that each region in the tapestry is constructed from input image blocks that are salient and such that neighboring blocks satisfy spatial compatibility. This is formulated using a Markov random field and optimized via the graph cut based expansion move algorithm. The standard expansion move algorithm can only handle energies with metric terms, while our energy contains non-metric (soft and hard) constraints. Therefore we propose two novel contributions. First, we extend the expansion move algorithm for energy functions with non-metric hard constraints. Secondly, we modify it for functions with "almost" metric soft terms, and show that it gives good results in practice. The proposed framework was tested on several consumer photograph collections, and the results are presented.},
	isbn = {0-7695-2372-2},
	doi = {10.1109/CVPR.2005.130},
	url = {http://research.microsoft.com/ http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=1467321\%5Cnhttp://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1467321},
	author = {Carsten Rother and Kumar, Sanjiv and Kolmogorov, Vladimir and Blake, Andrew}
}
@conference {Rother2004,
	title = {"GrabCut" - Interactive foreground extraction using iterated graph cuts},
	booktitle = {ACM Transactions on Graphics},
	volume = {23},
	number = {3},
	year = {2004},
	pages = {309{\textendash}314},
	abstract = {The problem of efficient, interactive foreground/background segmentation in still images is of great practical importance in image editing. Classical image segmentation tools use either texture (colour) information, e.g. Magic Wand, or edge (contrast) information, e.g. Intelligent Scissors. Recently, an approach based on optimization by graph-cut has been developed which successfully combines both types of information. In this paper we extend the graph-cut approach in three respects. First, we have developed a more powerful, iterative version of the optimisation. Secondly, the power of the iterative algorithm is used to simplify substantially the user interaction needed for a given quality of result. Thirdly, a robust algorithm for "border matting" has been developed to estimate simultaneously the alpha-matte around an object boundary and the colours of foreground pixels. We show that for moderately difficult examples the proposed method outperforms competitive tools.},
	keywords = {Alpha Matting, Foreground extraction, Graph Cuts, Image Editing, Interactive Image Segmentation},
	issn = {07300301},
	doi = {10.1145/1015706.1015720},
	author = {Carsten Rother and Kolmogorov, Vladimir and Blake, Andrew}
}
