I'll introduce the Cheeger inequality, a fundamental theoretical result
relating the spectrum of a graph to the cost of various quotient cuts.
Then I'll quickly introduce a few worst case examples and use similar
technology to explain the behavior of spectral image segmentation
algorithms. Finally, I'll introduce a family of partitioning methods,
spectral rounding, and apply them to image segmentation tasks. Spectral
rounding produces edge separators of a graph by iteratively reweighting
the edges until the graph disconnects into the prescribed number of
components. By directly producing discrete solutions we avoid the use
of heuristic geometric separators (e.g. k-means) in obtaining the cut.
Back to the Main Page
Pradeep Ravikumar Last modified: Mon Dec 4 10:15:44 EST 2006