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.