connectedComponents

Synopsis

Prototype:
y = connectedComponents(f, offsets)
Description:
The connectedComponents function implements the watershed transform using the algorithm of connected components by Bieniek and Moga [BieniekMogaPR2000]. This algorithm computes the shortest paths using a drop of water simulation. It does not produce watershed pixels.
Definition:
LC-WT
Exploration:
Depth-First

Algorithm

Algoritmo 1: Connected Components

References

[BieniekMogaISMM1998]A. Bieniek and A. Moga, ``A connected component approach to the watershed segmentation,'' in ISMM '98: Proceedings of the fourth international symposium on Mathematical morphology and its applications to image and signal processing. Norwell, MA, USA: Kluwer Academic Publishers, 1998, pp. 215–222.
[BieniekMogaPR2000]A. Bieniek and A. Moga, ``An efficient watershed algorithm based on connected components,'' Pattern Recognition, vol. 33, no. 6, pp. 907–916, 2000.

Source Code

 1 from ipdp.common import *
 2 
 3 # constants
 4 MASK = -2
 5 PLATEAU = -1
 6 
 7 def connectedComponents(im, offsets):
 8 
 9     # initialise variables
10     ws = wsImage(im)
11     N, im, lab, D = ws.begin(offsets)
12 
13     lab[:] = MASK
14     adr = ws.makeWorkCopy(0)
15 
16     queue = wsQueue()
17 
18     def find(p):
19         q = p
20         while adr[q] != q:
21             q = adr[q]
22         u = p
23         while adr[u] != q:
24             v = adr[u]
25             adr[u] = q
26             u = v
27         return q
28 
29     # step 1
30     for p in D:
31 
32         q = p
33         for u in N(p):
34 
35             if im[u] < im[q]:
36                 q = u
37 
38         if q != p:
39             adr[p] = q
40         else:
41             adr[p] = PLATEAU
42 
43     # step 2
44     for p in D:
45         if adr[p] != PLATEAU:
46             continue
47 
48         for q in N(p):
49             if adr[q] == PLATEAU or im[q] != im[p]:
50                 continue
51 
52             queue.push(q)
53 
54     while not queue.empty():
55         p = queue.pop()
56         for q in N(p):
57             if adr[q] != PLATEAU or im[q] != im[p]:
58                 continue
59 
60             adr[q] = p
61             queue.push(q)
62 
63     # step 3
64     for p in D:
65         if adr[p] != PLATEAU:
66             continue
67 
68         adr[p] = p
69 
70         for q in N(p):
71             if q > p or im[q] != im[p]:
72                 continue
73 
74             u = find(p)
75             v = find(q)
76             adr[u] = adr[v] = min(u,v)
77 
78     # step 4
79     basins = 1
80     for p in D:
81 
82         r = find(p)
83         adr[p] = r
84         if lab[r] == MASK:
85             lab[r] = basins
86             basins += 1
87         lab[p] = lab[r]
88 
89     return ws.end()