orderInvariantImmersion

Synopsis

Prototype:
y = orderInvariantImmersion(f, offsets)
Description:
The orderInvariantImmersion function implements the watershed transform by immersion. That is similar to simulating a flooding, however the order invariance ensures unique solutions. This algorithm was proposed by Lin et al. [LinIP2006].
Definition:
TD-WT
Exploration:
Breadth-First

Algorithm

Algoritmo 1: Order Invariant Immersion

References

[LinIP2006]Y. Lin, Y. Tsai, Y. Hung, and Z. Shih, ``Comparison between immersion-based and toboggan-based watershed image segmentation,'' IEEE Transactions on Image Processing, vol. 15, no. 3, pp. 632–640, 2006.

Source Code

 1 from ipdp.common import *
 2 
 3 #constants
 4 MASK = -2
 5 RIDGE = 0
 6 
 7 def orderInvariantImmersion(im, offsets):
 8 
 9     # initialise variables
10     ws = wsImage(im)
11     N, im, lab, D = ws.begin(offsets)
12 
13     dist = ws.makeWorkCopy(0)
14 
15     lab[:] = MASK
16     basins = 1
17 
18     queue = wsQueue()
19 
20     # "sorting"
21     levels = dict()
22     for p in D:
23 
24         if levels.has_key(im[p]):
25             levels[im[p]].append(p)
26         else:
27             levels[im[p]] = [p]
28 
29     # watershed
30     H = sorted(levels.keys())
31     for h in H:
32         # step 1
33         for p in levels[h]:
34 
35             hmin = min(im[N(p)])
36             if h > hmin:
37                 S = list()
38                 single_label = True
39                 alfa = None
40                 for q in N(p):
41                     if im[q] != hmin:
42                         continue
43 
44                     S.append(q)
45 
46                 dmin = min(dist[S])
47                 for q in S:
48                     if dist[q] != dmin:
49                         continue
50 
51                     if alfa is None:
52                         alfa = lab[q]
53                     else:
54                         if alfa != lab[q]:
55                             single_label = False
56 
57 
58                 if single_label:
59                     lab[p] = alfa
60                 else:
61                     lab[p] = RIDGE
62                 queue.push(p)
63                 dist[p] = 0
64 
65         # step 2
66         while not queue.empty():
67             p = queue.pop()
68             d = dist[p] + 1
69             for q in N(p):
70                 if im[q] != h:
71                     continue
72 
73                 if lab[q] == MASK:
74                     lab[q] = lab[p]
75                     dist[q] = d
76                     queue.push(q)
77                 elif lab[p] != lab[q] and dist[q] == d:
78                     lab[q] = RIDGE
79 
80         # step 3
81         for p in levels[h]:
82             if lab[p] != MASK:
83                 continue
84 
85             lab[p] = basins
86             basins += 1
87             queue.push(p)
88             while not queue.empty():
89                 q = queue.pop()
90                 for u in N(q):
91                     if im[u] != h or lab[u] != MASK:
92                         continue
93 
94                     lab[u] = lab[p]
95                     queue.push(u)
96 
97     return ws.end()