Thursday, February 3, 2005
Graph Cut Algorithms for Computer Vision and Medical Imaging
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.