Image Segmentation using Spectral Rounding

In this talk we present a new image segmentation algorithm, Spectral
Rounding (SR), and a fast solver used for segmenting 2D images.  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 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 (voxels).  A related and important first step to finding
eigenvector and of interest on its own 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 represents joint work with Yiannis Koutis and David Tolliver.