Thursday, February 3, 2005
4:15 pm
B17 Upson Hall

Computer Science
Spring 2005

Ramin Zabih
Cornell University

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.

Various parts of this talk describe joint work with Yuri Boykov, Vladimir Kolmogorov, Ashish Raj and Olga Veksler.