Labelisation watershed¶

Watershed cut of the given edge weighted 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): 13621374, 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 minmax 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) invertex_seeds
are not considered as seeds
 Returns
A labelisation of the graph vertices