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.

Full Paper

Click here for full paper (243023 bytes, pdf).