Progressive Multigrid Eigensolvers for Multiscale Spectral Segmentation

TitleProgressive Multigrid Eigensolvers for Multiscale Spectral Segmentation
Publication TypeConference Paper
Year of Publication2013
AuthorsMaire, M., & Yu S. X.
Other Numbers3621

We reexamine the role of multiscale cues in image segmentation using an architecture that constructs a globallycoherent scale-space output representation. This characteristic is in contrast to many existing works on bottom-upsegmentation, which prematurely compress information intoa single scale. The architecture is a standard extension ofNormalized Cuts from an image plane to an image pyramid,with cross-scale constraints enforcing consistency in the solution while allowing emergence of coarse-to-fine detail.We observe that multiscale processing, in addition to improving segmentation quality, offers a route by which tospeed computation. We make a significant algorithmic advance in the form of a custom multigrid eigensolver for constrained Angular Embedding problems possessing coarse-to-fine structure. Multiscale Normalized Cuts is a specialcase. Our solver builds atop recent results on randomizedmatrix approximation, using a novel interpolation operation to mold its computational strategy according to cross-scale constraints in the problem definition. Applying oursolver to multiscale segmentation problems demonstratesspeedup by more than an order of magnitude. This speedupis at the algorithmic level and carries over to any implementation target.


This work was partially supported by funding provided to ICSI through National Science Foundation CAREER award IIS : 1257700 (“Art and Vision: Scene Layout from Pictorial Cues”). Additional support was provided through ONR MURI N00014-10-1-0933 and ARO/JPL-NASA Stennis NAS7.03001. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the National Science Foundation or any other funder.

Bibliographic Notes

Proceedings of the International Conference on Computer Vision 2013 (ICCV 2013), Sydney, Australia

Abbreviated Authors

M. Maire and S. X. Yu

ICSI Research Group


ICSI Publication Type

Article in conference proceedings