Abstract:

Image segmentation 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 problem is
modeled as minimization of deviation penalty, from the captured colors
of the pixels, and separation penalty, which is associated with two
adjacent images having different colors.

We describe a very efficient and best possible polynomial time algorithm
for the problem.  This algorithm 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.

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