# Synopsis

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

# Algorithm

Algoritmo 1: Order Invariant Toboggan

# 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 orderInvariantToboggan(im, offsets):
8
9     # initialise variables
10     ws = wsImage(im)
11     N, im, lab, D = ws.begin(offsets)
12
14
15     queue = wsQueue()
16     dist = ws.makeWorkCopy(0)
17     sliding = dict()
18
19     def resolve(p):
21
22             S = sliding[p]
23
24             for q in S:
25                 resolve(q)
26
27             single_label = True
28             alfa = None
29
30             dmin = min(dist[S])
31
32             # identifies unique label on S
33             for u in S:
34                 if dist[u] != dmin:
35                     continue
36
37                 if alfa is None:
38                     alfa = lab[u]
39                 else:
40                     if alfa != lab[u]:
41                         single_label = False
42
43
44             if single_label:
45                 lab[p] = alfa
46             else:
47                 lab[p] = RIDGE
48
49     # step 1
50     for p in D:
51
52         h = im[p]
53         hmin = min(im[N(p)])
54
55         if h > hmin:
56             S = list()
57             for q in N(p):
58                 if im[q] != hmin:
59                     continue
60                 S.append(q)
61             sliding[p] = S
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         h = im[p]
70
71         for q in N(p):
72             if im[q] != h:
73                 continue
74
75             if not sliding.has_key(q):
76                 sliding[q] = [p]
77                 dist[q] = d
78                 queue.push(q)
79             elif dist[q] == d:
80                 sliding[q].append(p)
81
82     # step 3
83     basins = 1
84     for p in D:
85         if sliding.has_key(p) or lab[p] != MASK:
86             continue
87
88         lab[p] = basins
89         basins += 1
90
91         queue.push(p)
92         h = im[p]
93
94         while not queue.empty():
95             q = queue.pop()
96             for u in N(q):
97                 if im[u] != h:
98                     continue
99