Labelisation watershed

labelisation_watershed(graph, edge_weights)

Watershed cut of the given edge weighted graph.

labelisation_seeded_watershed(graph, ...[, ...])

Seeded watershed cut on an edge weighted graph.
labelisation_watershed(graph, edge_weights)[source]

Watershed cut of the given edge weighted graph.

The definition and algorithm used are described in:

J. Cousty, G. Bertrand, L. Najman and M. Couprie. Watershed cuts: minimum spanning forests, and the drop of water principle. IEEE Trans. on Pattern Analysis and Machine Intelligence, 31(8): 1362-1374, 2009.

The watershed cut is represented by a labelisation of the graph vertices.

Complexity:

This algorithm has a linear runtime complexity \(\mathcal{O}(n)\) with \(n\) the number of edges in the graph.

Parameters:

  • graph – input graph

  • edge_weights – Weights on the edges of the graph

Returns:

A labelisation of the graph vertices

labelisation_seeded_watershed(graph, edge_weights, vertex_seeds, background_label=0)[source]

Seeded watershed cut on an edge weighted graph. Seeds and associated labels are given in vertex_seeds. A vertex \(v\), such that \(vertex\_seeds(v)\neq background\_label\) is a seed with associated label \(vertex\_seeds(v)\).

The label of a vertex of the graph is then defined equal to the label of the closest seed in the edge weighted graph for the min-max distance. If several such seeds exist (eg. on a plateus between two seeds), an arbitrary and consistent choice is made ensuring that:

  • each flat zone of level \(k\) of the final labelling contains at least one seed with the label \(k\); and

  • each seed is contained in a flat zone whose level is equal to the seed label.

Complexity:

This algorithm has a runtime complexity in \(\mathcal{O}(n \log n)\) with \(n\) the number of edges in the graph.

Parameters:

  • graph – Input graph

  • edge_weights – Weights on the edges of the graph

  • vertex_seeds – Seeds with integer label values on the vertices of the graph

  • background_label – Vertices whose values are equal to background_label (default 0) in vertex_seeds are not considered as seeds

Returns:

A labelisation of the graph vertices