# Synopsis

Prototype:
y = unionFind(f, offsets)
Description:
The unionFind function implements the watershed transform using a variation of the algorithm of Tarjan [Tarjan1983] for disjoint sets to create connected components of same label. The pixels that do not belong exclusively to any of these groups are watershed pixels. This variation was proposed by Meijster and Roerdink [MeijsterRoerdinkEUSIPCO1998].
Definition:
TD-WT
Exploration:
Depth-First

# Algorithm

Algoritmo 1: Oriented graph construction

Algoritmo 2: Union Find

# References

 [Tarjan1983] Robert Endre Tarjan, Data structures and network algorithms, Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1983.
 [MeijsterRoerdinkEUSIPCO1998] A. Meijster and J. B. T. M. Roerdink, ``A disjoint set algorithm for the watershed transform,'' in Proc. IX European Signal Processing Conf EUSIPCO ’98, 1998, pp. 1665–1668.
 [RoerdinkMeijsterFI2000] J. B. T. M. Roerdink and A. Meijster, ``The watershed transform: definitions, algorithms and parallelization strategies,'' Fundam. Inf., vol. 41, no. 1-2, pp. 187–228, 2000.

# Source Code

``` 1 from ipdp.common import *
2
3 # constants
4 WSHED = 0
5 W = -1
7
8 def unionFind(im, offsets):
9
10     lc = lowerComplete(im, offsets)
11     sln = digraph(lc, offsets)
12
13     # initialise variables
14     ws = wsImage(lc)
15     N, im, lab, D = ws.begin(offsets)
16
18     basins = 1
19
20     def find(p):
21         rep = 0
22         i = 0
23         gamma = sln[p]
24         while i < len(gamma) and rep != W:
25             if gamma[i] != p and gamma[i] != W:
26                 gamma[i] = find(gamma[i])
27
28             if i == 0:
29                 rep = gamma[0]
30             elif gamma[i] != rep:
31                 rep = W
32                 for j in range(len(gamma)):
33                     gamma[j] = W
34             i += 1
35
36         return rep
37
38     for p in D:
39
40         r = find(p)
41         if r != W:
43                 lab[r] = basins
44                 basins += 1
45
46             lab[p] = lab[r]
47         else:
48             lab[p] = WSHED
49
50     return ws.end()
51
52
53
54 def digraph(im, offsets):
55
56     # initialise variables
57     ws = wsImage(im)
58     N, im, lc, D = ws.begin(offsets)
59
60     sln = dict()
61
62     # scan the image
63     for p in D:
64
65         if sln.has_key(p):
66             continue # is part of the minimal plateau
67
68         gamma = list()
69         minvalue = min(im[N(p)])
70         plateau = False
71         for q in N(p):
72
73             if im[q] == minvalue and im[q] < im[p]:
74                 gamma.append(q)
75
76             if im[q] == im[p]:
77                 plateau = True
78
79         if len(gamma) == 0:
80             if plateau:
81                 # minimal plateau
82                 queue = wsQueue()
83                 queue.push(p)
84                 gamma.append(p) # make the first one the representative
85                 while not queue.empty():
86                     q = queue.pop()
87                     for u in N(q):
88
89                         if im[u] == im[p]:
90                             if not sln.has_key(u):
91                                 sln[u] = [p]
92                                 queue.push(u)
93             else:
94                 gamma.append(p) # one-pixel minimum
95
96         sln[p] = gamma
97
98     return sln
```