# Synopsis

Prototype:
y = watershedCut(f, offsets)
Description:
The watershedCut function implements the watershed cut transform. It implements the algorithm proposed by Cousty et al. [CoustyPAMI2009a] using work images to keep data of sets. Previously to the algorithm itself, the weighted graph is built in a single pass.
Definition:
WC-WT
Exploration:
Depth-First

# Algorithm

Algoritmo 1: Watershed Cut

# References

 [CoustyPAMI2009a] J. Cousty, G. Bertrand, L. Najman, and M. Couprie, ``Watershed cuts: Minimum spanning forests and the drop of water principle,'' IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 8, pp. 1362–1374, 2009.

# Source Code

``` 1 from ipdp.common import *
2
3 # constants
5 IN_SET = -1
6
7 def watershedCut(im, offsets):
8
9     # initialise variables
10     ws = wsImage(im)
11     N, im, lab, D = ws.begin(offsets)
12
13     basins = 0
14
15     max_value = max(im) + 1
16
17     # build the graph
18     graph = dict() # use a dict
19     for p in D:
20
22         fminus = max_value
23         edges = [] # create the edges
24         for q in N(p):
25             m = max(im[p], im[q])
26             edges.append({'w': m, 'index': q})
27             if m < fminus: # minimize the fminus value of the vertex
28                 fminus = m
29
30         graph[p] = {'fminus': fminus, 'edges': edges} # append the edges and fminus dict to the graph
31
32     # iterate on the graph/label image
33     for p in D:
35             # make a stream on the pixel
36             L,label = stream(p, graph, lab)
37             # generate a new label if necessary
38             if label == -1:
39                 basins += 1
40                 label = basins
41             # set the found/generated label on the set
42             for q in L:
43                 lab[q] = label
44
45
46     # crop and return the labeled image
47     return ws.end()
48
49
50 # define the stream function
51 def stream(p, graph, lab):
52     L = [p]
53     Li = [p]
54     lab[p] = IN_SET # mark for signalizing the pixel is in the set
55
56     while len(Li) > 0:
57         u = Li.pop()
59         fminus = graph[u]['fminus']
60         edges = graph[u]['edges']
61
63             edge_found = False
64             for e in edges:
65                 v = e['index']
66                 w = e['w']
67                 if lab[v] != IN_SET and w == fminus:
68                     edge_found = True
69                     break
70
71             if not edge_found:
72                 break
73