orderInvariantToboggan

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
  4 MASK = -2
  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 
 13     lab[:] = MASK
 14 
 15     queue = wsQueue()
 16     dist = ws.makeWorkCopy(0)
 17     sliding = dict()
 18 
 19     def resolve(p):
 20         if lab[p] == MASK:
 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 
100                 if lab[u] == MASK:
101                     lab[u] = lab[p]
102                     queue.push(u)
103 
104     # step 4
105     for p in D:
106         resolve(p)
107 
108     return ws.end()