Progressive Multigrid Eigensolvers for Multiscale Spectral Segmentation

Michael Maire, Stella X. YuICCV 2013 · OpenReview

Abstract

We reexamine the role of multiscale cues in image segmentation using an architecture that constructs a globally coherent scale-space output representation. This characteristic 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 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 to speed 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. Our solver builds atop recent results on randomized matrix approximation, using a novel interpolation operation 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.

Introduction

Spectral clustering, particularly the Normalized Cuts algorithm, remains a cornerstone of image segmentation due to its ability to capture global image structure. However, its widespread adoption is hindered by the immense computational cost of solving large-scale eigenvalue problems. Traditional approaches often attempt to mitigate this by compressing multiscale information—such as fine textures and coarse shapes—into a single affinity matrix. This "premature compression" frequently results in a loss of fine detail or a failure to maintain global coherence.

Maire and Yu (ICCV 2013) propose that the multiscale representation should be preserved throughout the entire clustering process. They introduce a "progressive multigrid eigensolver" that leverages an image pyramid to solve spectral segmentation problems up to 31x faster while simultaneously improving segmentation quality.

Comparison of multigrid, multirange, and multiscale problem structures.

The Progressive Multigrid Approach

The core innovation lies in treating the solver and the multiscale problem definition as partners. Instead of a single graph, the method utilizes an image pyramid where affinities are defined within each scale. Explicit constraints ($U$) tie pixels at coarse scales to their corresponding blocks at finer scales, ensuring consistency across the pyramid. This architecture is designed for constrained Angular Embedding (AE) problems, a generalization of Normalized Cuts.

The solver follows a coarse-to-fine strategy. It begins at the coarsest level, reaches convergence, and then uses a novel interpolation operator ($\Phi_{U_s}$) to initialize the solution at the next finer level. This operator is derived directly from the problem's own constraints, allowing for a near-perfect initialization that significantly reduces the iterations needed at high resolutions.

Transformation from a standard multiscale representation to a progressive multigrid multiscale architecture.

Key Algorithmic Components

  • Multiscale Problem Definition: Uses an image pyramid with cross-scale constraints to enforce global coherence while allowing fine-grained details to emerge.
  • Randomized Subspace Iteration: Moves away from traditional Lanczos solvers in favor of randomized matrix approximations, which are more naturally parallelizable and robust.
  • Constraint-Guided Interpolation: The "secret sauce" that uses the problem's structural constraints to guide the solver between grid levels efficiently.

Experimental Results

The method was evaluated on the Berkeley Segmentation Dataset (BSDS). The results demonstrate that the progressive multigrid strategy is not only faster but also produces higher-quality contours.

  • Efficiency: The solver achieved an 11x wall-clock speedup on a standard CPU for finding 32 eigenvectors, reducing the time from 12 minutes to 27 seconds. In terms of raw computational operations (diffusion and projection), the speedup reached 31x.
  • Quality: The resulting "Multiscale sPb" (spectral Probability of Boundary) outperformed standard single-scale methods. It successfully identified boundaries in complex, textured regions where single-scale approaches often "hallucinate" edges or lose detail.

Conclusion

By rethinking the relationship between multiscale representations and numerical solvers, this work provides a path toward real-time, high-quality spectral segmentation. The progressive multigrid eigensolver demonstrates that the very constraints that define a robust multiscale problem can be harnessed to accelerate its solution. This framework holds potential for other complex vision tasks, such as simultaneous figure-ground organization and object detection, where global coherence and local detail are equally vital.

Summary updated

Abstract

We reexamine the role of multiscale cues in image segmentation using an architecture that constructs a globally coherent scale-space output representation. This characteristic 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 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 to speed 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 special case. Our solver builds atop recent results on randomized matrix approximation, using a novel interpolation operation 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 implementation target.
BibTeX
@inproceedings{maire2013progressive,
  author = {Michael Maire and Stella X. Yu},
  title = {{Progressive Multigrid Eigensolvers for Multiscale Spectral Segmentation}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  url = {https://openreview.net/forum?id=BJ-iKbzuZr},
}
Figure