K-Smallest Spanning Tree Segmentations

Real-world images often admit many different segmentations that have nearly the same quality according to the underlying energy function. The diversity of these solutions may be a powerful uncertainty indicator. We provide the crucial prerequisite in the context of seeded segmentation with minimum spanning trees (i.e. edge-weighted watersheds). Specifically, we show how to efficiently enumerate the k smallest spanning trees that result in different segmentations; and we prove that solutions are indeed found in the correct order. Experiments show that about half of the trees considered by our algorithm represent unique segmentations. This redundancy is orders of magnitude lower than can be achieved by just enumerating the k-smallest MSTs, making the algorithm viable in practice.