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.
