Efficient algorithms for watershed image segmentation on graphs

Playing with Kruskal: algorithms for flat and hierarchical watershed cuts

Computer Vision and Pattern Recognition

Summary

Segmenting images into meaningful parts is important for many uses, but it can be complex. The authors explain how watershed methods, which are connected to well-known graph algorithms like minimum spanning trees, can help break images into segments reliably. They bring together various ways to compute these watershed segmentations, including hierarchical and supervised versions, in one clear guide. This makes it easier for people building image analysis tools to understand and use these techniques.

What this means in practice

  • For computer vision engineers: Create clear and reliable image part boundaries by following a complete set of watershed segmentation algorithms for different scenarios.
  • For medical image analysts: Improve detection of anatomical structures by applying hierarchical watershed methods with various seed placement strategies explained in the paper.

A survey. It maps existing work.

Authors

Jean Cousty, Laurent Najman, Benjamin Perret, Deise Santana Maia

Abstract

In the framework of edge-weighted graphs, watersheds have proven to be linked to well-known optimization problems, as Minimum Spanning Tree, which allowed the design of efficient algorithms for computing (hierarchical) watershed segmentations. In the present article, after reviewing the literature related to watershed segmentation, we present a detailed end-to-end pipeline of algorithms to compute (hierarchical) watershed segmentations, starting from the computation of graph-based image representations, up to the computation of connected components of the final (hierarchical) segmentation. We consider the several variations of watersheds, including their supervised and unsupervised versions, and the various ways of computing seeds, to name a few. For the first time, we bring together all these watershed notions and algorithms in a compact and understandable way. We aim at providing a reference for those interested in employing and reimplementing the watershed segmentation framework for their task at hand.