An image is segmented into image regions. Each of the image regions is represented by a respective vertex. A graph of the vertices interconnected by edges, each of which has a respective edge weight value, is built. The graph is partitioned into respective disjoint subgraphs based on the edge weight values. The partitioning of one or more of the subgraphs into respective subgraphs is repeated. A partition tree data structure that describes a partitioning hierarchy of parent-child relationships between the subgraphs is produced.