In this talk we present a new image segmentation algorithm, Spectral
Rounding (SR), and a fast solver used for segmenting 2D images. We will
show it applied to the Berkeley data base of human segmented images, and
medical examples such as tumors in mammograms.

The key idea in SR is to view an image as a 2D mattress of springs. Two
neighboring pixels are connected by a spring where the spring constant
is determined by local similarity in the pixel intensity. Shi and Malik
proposed the fundamental idea of using the fundamental modes of
vibration of this mattress (the eigenvectors) to segment the image. The
straightforward method for partitioning a graph using its eigenvectors,
however, does not seem to work well in practice.

We propose a relaxation method based on eigenvectors for finding these
graph cuts. At each round a few fundamental eigenvectors are computed,
from which the spring constants are updated and these eigenvectors are
recomputed using the new spring constants. Thus the spring constants
are successively readjusted until the mattress disconnects, an image
segmentation.

SR compares favorably with hand-segmented images from the Berkeley
database and the normalized cut metric. We also show convergence in
general and termination for several important cases.

The second issue addressed is fast algorithms for finding the associated
eigenvectors and solving related linear systems. This is a critical
issue because modern 3D medical images may contain a billion nodes
(voxel). A related and important first step to finding eigenvectors,
and of independent interest, is solving 2D and 3D Laplacians. For
instance, Siemens uses Laplacians for their new assisted image
segmentation algorithm. We present the first linear-time algorithm for
2D and more general planar Laplacians.

This is joint work with Yiannis Koutis and David Tolliver.