watershedCut

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
 4 MASK = -2
 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 
21         lab[p] = MASK # "mask" the image
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:
34         if lab[p] == MASK:
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()
58         breadth_first = True
59         fminus = graph[u]['fminus']
60         edges = graph[u]['edges']
61 
62         while breadth_first:
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 
74             if lab[v] != MASK:
75                 return (L, lab[v])
76             elif graph[v]['fminus'] < fminus:
77                 L.append(v)
78                 lab[v] = IN_SET
79                 Li = [v]
80                 breadth_first = False
81             else:
82                 L.append(v)
83                 lab[v] = IN_SET
84                 Li.append(v)
85 
86     return (L,-1)