unionFind

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
 6 MASK = -2
 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 
17     lab[:] = MASK
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:
42             if lab[r] == MASK:
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