Image segmentation is a key low-level vision process for many tasks in image understanding and applications in image processing. The groups of related pixels produced by a segmentation are expected to reveal some information about the objects in a scene. Many equally valid segmentations exist for most images depending on the context of the segmentation, in particular, the levelof- detail. Segmentation hierarchies can represent different level-of-detail simultaneously. In this paper, we employ the Earth Mover?s Distance (EMD) as a segmentation criterion in a hierarchical colour segmentation algorithm. The use of EMD is motivated by its success in content-based image retrieval based on colour signatures. We also develop a novel evaluation method which looks at the stability of segmentation hierarchies in stereo images. This evaluation method allows us to compare the EMD segmentation criterion with variants and with criterions based on mean colour.