Progressive multigrid eigensolvers for multiscale spectral segmentation

We reexamine the role of multiscale cues in image seg-mentation using an architecture that constructs a globally coherent scale-space output representation. This charac-teristic is in contrast to many existing works on bottom-up segmentation, which prematurely compress information into a single scale. The architecture is a standard extension of Normalized Cuts from an image plane to an image pyramid, with cross-scale constraints enforcing consistency in the so-lution while allowing emergence of coarse-to-fine detail. We observe that multiscale processing, in addition to im-proving segmentation quality, offers a route by which to speed computation. We make a significant algorithmic ad-vance in the form of a custom multigrid eigensolver for con-strained Angular Embedding problems possessing coarse-to-fine structure. Multiscale Normalized Cuts is a special case. Our solver builds atop recent results on randomized matrix approximation, using a novel interpolation opera-tion to mold its computational strategy according to cross-scale constraints in the problem definition. Applying our solver to multiscale segmentation problems demonstrates speedup by more than an order of magnitude. This speedup is at the algorithmic level and carries over to any imple-mentation target. 1