chainCode

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:
 24             raise Exception("Neighbour not found")
 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()