Graph Cut Algorithms for Computer Vision and Medical Imaging
Computational analysis of images involves many difficult optimization problems. Traditionally these problems have been solved with continuous techniques. I will describe a discrete approach that relies on computing the minimum cut on an appropriately constructed graph. I will give an overview of these algorithms, focusing on the situations in which they can be used and the performance guarantees they provide. For some problems these graph cut methods efficiently produce the global minimum, while for others they provide a local minimum in a strong sense. These methods also give strong experimental performance; for example, the majority of the top-ranked vision algorithms for computing stereo depth rely on graph cuts. I will also describe some recent work which has significantly increased the class of problems these methods can solve, at the cost of weakening their performance
guarantees. As a result, it is now possible to apply graph cuts to an important task in medical imaging.