Efficient cut-based image segmentation techniques

Dorit Hochbaum
University of California, Berkeley (UC Berkeley)

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".

Back to Graph Cuts and Related Discrete or Continuous Optimization Problems