Markov Random Fields (MRFs) are ubiquitous in low-level computer vision. In the first part of the talk I will summarise some of the ways in which we have used graph cut in interactive graphics, stereo video processing and object detection. Then I will discuss a new approach to the optimization of multi-labeled MRFs. Similarly to alpha-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-graph cut which is related to graph-cut but can deal with nonsubmodularity. In practice, our method achieves optima on a par with the best competitors, and sometimes even exceeds them.
Joint work with V. Lempitsky, C. Rother.