CAM colloquium - Friday, March 28
3:30 p.m.
655 Rhodes Hall

Speaker: Dorit S. Hochbaum, Haas School of Business and Department of IE&OR
University of California, Berkeley.

 

Title: Efficient cut-based image segmentation techniques

 

Abstract: Segmenting an image is to determine a partition to the salient features of the image and identify them as associated with different types of
objects. This is of particular importance in medical imaging where blur conceals information of critical importance. The MRF presentation
of the problem is formulated as minimization of deviation penalty, from the captured colors of the pixels, and separation penalty, which is
associated with two adjacent pixels having different colors.

We describe a very efficient and best possible polynomial time algorithm for a convex variant of the problem. This algorithm's efficiency enables
its use in an interactive set-up. It is more efficient than most procedures based on spectral techniques, partitioning approaches or heuristic
clustering. We then demonstrate how to apply the procedure for the purpose of de-blurring medical images and identifying structures hidden
by noise.

Time permitting, we will present additional efficient poly time algorithms for several types of ratio cuts that have been believed to be "hard".

Refreshments at 4:30 in 657 Rhodes Hall.