Image Segmentation using Spectral Rounding

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.