@conference {Kohli2008,
	title = {On partial optimality in multi-label MRFs},
	booktitle = {Proceedings of the 25th International Conference on Machine Learning},
	year = {2008},
	pages = {480{\textendash}487},
	abstract = {We consider the problem of optimizing multilabel MRFs, which is in general NP-hard and ubiquitous in low-level computer vision. One approach for its solution is to formulate it as an integer linear programming and relax the integrality constraints. The approach we consider in this paper is to first convert the multi-label MRF into an equivalent binary-label MRF and then to relax it. The resulting relaxation can be efficiently solved using a maximum flow algorithm. Its solution provides us with a partially optimal labelling of the binary variables. This partial labelling is then easily transferred to the multi-label problem. We study the theoretical properties of the new relaxation and compare it with the standard one. Specifically, we compare tightness, and characterize a subclass of problems where the two relaxations coincide. We propose several combined algorithms based on the technique and demonstrate their performance on challenging computer vision problems. Copyright 2008 by the author(s)/owner(s).},
	isbn = {9781605582054},
	doi = {10.1145/1390156.1390217},
	author = {Kohli, Pushmeet and Shekhovtsov, Alexander and Carsten Rother and Kolmogorov, Vladimir and Torr, Philip}
}
@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}
}
