David Tolliver, Robert T. Collins and Simon Baker
"Multilevel Spectral Partitioning for Efficient Image Segmentation and Tracking,"
IEEE Workshop on Applications of Computer Vision, Beckenridge CO, Jan 2005, pp 414-420.
An efficient multilevel method for solving normalized cut
image segmentation problems is presented. The method
uses the lattice geometry of images to define a set of coarsened
graph partitioning problems. This problem hierarchy
provides a framework for rapidly estimating the eigenvectors
of normalized graph Laplacians. Within this framework,
a coarse solution obtained with a standard eigensolver
is propagated to increasingly fine problem instances
and refined using subspace iterations. Results are presented
for image segmentation and tracking problems. The computational
cost of the multilevel method is an order of magnitude
lower than current sampling techniques and results in
more stable image segmentations.
Click here for
full paper (243023 bytes, pdf).