# 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