|
In this talk we present a new image segmentation algorithm, Spectral
Rounding (SR), and a fast solver. The combination is used for
segmenting 2D and 3D images. Applying SR to the Berkeley data base of
human segmented images, and medical examples such as tumors in
mammograms and 3D retinal scans gives robust quality segmentations.
When used with our fast solver SR is nearly nearly time.
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 important 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 (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.
|