Edges at multiple scales provide complementary grouping cues for image segmentation. These cues are reliable within different ranges. The larger the scale of an edge, the longer range the grouping cues it designates, and the greater impact it has on the final segmentation. A good segmentation respects grouping cues at each scale.

These intuitions are formulated in a graph-theoretic framework, where multiscale edges define pairwise pixel affinity at multiple grids, each captured in one graph. A novel criterion called average cuts of normalized affinity is proposed to evaluate a simultaneous segmentation through all these graphs. Its near-global optima can be solved efficiently.

With a sparse yet complete characterization of pairwise pixel affinity, this graph-cuts approach leads to a hierarchy of coarse to fine segmentations that naturally take care of textured regions and weak contours.