# 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:

# 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
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
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
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]:
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()
```