# Synopsis

Prototype:
y = chainCode(f, offsets)
Description:
The chainCode function implements the watershed transform calculating paths of input and output for each pixel using a variation of the well known chain codes. These paths are then processed to group pixels into catchment basins. This algorithm was proposed by Sun, Yang and Ren. [SunYangRenPRL2005]
Definition:
LC-WT
Exploration:
Depth-First

# Algorithm

Algoritmo 1: Chain Code Watershed

# References

 [SunYangRenPRL2005] H. Sun, J. Yang, and M. Ren, ``A fast watershed algorithm based on chain code and its application in image segmentation,'' Pattern Recognition Letters, vol. 26, no. 9, pp. 1266–1274, 2005.

# Source Code

```  1 from ipdp.common import *
2
3 # constants
4 MASK = -2
5
6 def chainCode(im, offsets):
7
8     # initialise variables
9     ws = wsImage(im)
10     N, im, lab, D = ws.begin(offsets)
11
12     wout = ws.makeWorkCopy(MASK)
13     win = ws.makeWorkCopy(0)
14     basins = 1
15     queue = wsQueue()
16     stack = wsStack()
17
18     def pointOut(p,q):
19         # finds the offset
20         c = q - p
21         # query the neighbourhood for the offset
22         idx = ws.neighbour.query(c)
23         if idx == -1:
25         return idx
26
27     def pointIn(p,q):
28         idx = pointOut(q,p)
29         return 1 << idx
30
31     # step 1
32     for p in D:
33
34         minvalue = min(im[N(p)])
35         minpx = None
36
37         for q in N(p):
38
39             if im[q] < im[p] and im[q] == minvalue:
40                 minpx = q
41
42         if not minpx is None:
43             wout[p] = pointOut(p, minpx)
44             win[minpx] |= pointIn(p, minpx)
45
46     # step 2
47     for p in D:
48         if wout[p] == MASK:
49             continue
50
51         for q in N(p):
52
53             if wout[q] == MASK and im[q] == im[p]:
54                 queue.push(p)
55                 break
56
57     while not queue.empty():
58         p = queue.pop()
59         for q in N(p):
60
61             if im[p] == im[q] and wout[q] == MASK:
62                 wout[q] = pointOut(q, p)
63                 win[p] |= pointIn(q, p)
64                 queue.push(q)
65
66     # step 3
67     for p in D:
68         if wout[p] != MASK:
69             continue
70
71         for q in N(p):
72             if im[q] != im[p]:
73                 continue
74
75             wout[q] = pointOut(q, p)
76             win[p] |= pointIn(q, p)
77             stack.push(q)
78
79         while not stack.empty():
80             u = stack.pop()
81             for v in N(u):
82
83                 if im[u] == im[v] and wout[v] == MASK and v != p:
84                     wout[v] = pointOut(v, u)
85                     win[u] |= pointIn(v, u)
86                     stack.push(v)
87
88     # step 4
89     for p in D:
90         if wout[p] != MASK:
91             continue
92
93         stack.push(p)
94         while not stack.empty():
95             u = stack.pop()
96             lab[u] = basins
97             for v in N(u):
98
99                 # checks if v is in in-list of u
100                 if pointIn(v,u) & win[u] > 0:
101                     lab[v] = basins
102                     stack.push(v)
103
104         basins += 1
105
106     return ws.end()
```