Global–local optimizations by hierarchical cuts and climbing energies

• Theoretical results on partition selection from, hierarchies of segmentations.
• Framework: input image, hierarchy of segmentations, positive energy, optimization.
• Optimization by parent–child class comparisons, children composition laws.
• Dynamic programs, segmentation results on Berkeley database, indigenous dataset.
• Euclidean formulation, partial optimization, equivalence with max-flow.

Hierarchical segmentation is a multi-scale analysis of an image and provides a series of simplifying nested partitions. Such a hierarchy is rarely an end by itself and requires external criteria or heuristics to solve problems of image segmentation, texture extraction and semantic image labelling. In this theoretical paper we introduce a novel framework: hierarchical cuts, to formulate optimization problems on hierarchies of segmentations. Second we provide the three important notions of h-increasing, singular, and scale increasing energies, necessary to solve the global combinatorial optimization problem of partition selection and which results in linear time dynamic programs. Common families of such energies are summarized, and also a method to generate new ones is described. Finally we demonstrate the application of this framework on problems of image segmentation and texture enhancement.