Spectral Rounding & Image Segmentation

David Tolliver
doctoral dissertation, tech. report CMU-RI-TR-06-44, Robotics Institute, Carnegie Mellon University, August, 2006

  • Adobe portable document format (pdf) (7MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

The task of assigning labels to pixels is central to computer vision. In automatic segmentation an algorithm assigns a label to each pixel where labels connote a shared property across pixels (e.g. color, bounding contour, texture). Recent approaches to image segmentation have formulated this labeling task as partitioning a graph derived from the image. We use spectral segmentation to denote the family of algorithms that seek a partitioning by processing the eigenstructure associated with image graphs.

In this thesis we analyze current spectral segmentation algorithms and explain their performance, both practically and theoretically, on the Normalized Cuts (NCut) criterion. Further, we introduce a novel family of spectral graph partitioning methods, spectral rounding, and apply them to image segmentation tasks. Edge separators of a graph are produced by iteratively reweighting the edges until the graph disconnects into the prescribed number of components. At each iteration a small number of eigenvectors with small eigenvalue are computed and used to determine the reweighting. In this way spectral rounding directly produces discrete solutions where as current spectral algorithms must map the continuous eigenvectors to discrete solutions by employing a heuristic geometric separator (e.g. k-means).

We show that spectral rounding compares favorably to current spectral approximations on the NCut criterion in natural image segmentation. Quantitative evaluations are performed on multiple image databases including the Berkeley Segmentation Database. These experiments demonstrate that segmentations with improved NCut value (obtained using the SR-Algorithm) are more highly correlated with human hand-segmentations.

Associated Center(s) / Consortia: Vision and Autonomous Systems Center
Associated Lab(s) / Group(s): Human Identification at a Distance
Number of pages: 116

Text Reference
David Tolliver, "Spectral Rounding & Image Segmentation," doctoral dissertation, tech. report CMU-RI-TR-06-44, Robotics Institute, Carnegie Mellon University, August, 2006

BibTeX Reference
   author = "David Tolliver",
   title = "Spectral Rounding & Image Segmentation",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "August",
   year = "2006",
   number= "CMU-RI-TR-06-44",
   address= "Pittsburgh, PA",