Function iacwatershed

Synopse

Watershed by markers using the IFT - Image Forest Transform.

  • y = iacwatershed(f, g, Bc=iasecross(), option='LINES')
    • y: Image
    • f: Image
    • g: Image of markers
    • Bc: Structuring Element (connectivity)
    • option: 'LINES' for the lines dividing regions or 'REGIONS' for a labelled image
 1 from ia870 import iasecross, iaisbinary, ialabel, iasubm, iaero, iabinary
 2 
 3 def iacwatershed(f, g, Bc=iasecross(), option='LINES'):
 4     from ipdp import se2offset
 5 
 6     if iaisbinary(g):
 7         g = ialabel(g, Bc)
 8     offset = se2offset(Bc)
 9     w = ift_m(f, offset, g)
10     if option == 'LINES':
11         w = iasubm(w, iaero(w))
12         w = iabinary(w)
13     return w
14 
15 def ift_m(im, offsets, M):
16 
17     from ipdp import wsImage
18 
19     # initialise variables
20     ws = wsImage(im)
21     N, im, lab, D = ws.begin(offsets)
22 
23     wsM = wsImage(M)
24     NM, imM, labM, DM = wsM.begin(offsets)
25 
26     # make the set
27     Mset = dict()
28     for p in D:
29         if imM[p] > 0:
30             if Mset.has_key(imM[p]):
31                 Mset[imM[p]].append(p)
32             else:
33                 Mset[imM[p]] = [p]
34 
35     ift_k(ws, im, Mset.values(), N, D, lab)
36 
37     return ws.end()
38 
39 # constants
40 MASK = -2
41 
42 def ift_k(ws, im, M, N, D, lab):
43 
44     import numpy as np
45     from ipdp import wsHeapQueue
46 
47     # create the working images
48     done = ws.makeWorkCopy(False)
49     c1 = ws.makeWorkCopy(np.inf)
50     par = ws.makeWorkCopy(MASK)
51 
52     lab[:] = MASK
53 
54     queue = wsHeapQueue()
55 
56     for m in xrange(len(M)):
57         for p in M[m]:
58             #c1[p] = im[p]
59             c1[p] = 0
60             lab[p] = m+1
61             par[p] = p
62             #queue.push(p, im[p])
63             queue.push(p,0)
64     while not queue.empty():
65         p = queue.pop()
66         done[p] = True
67         for q in N(p):
68             if not done[q]:
69                 c = max(c1[p], im[q])
70                 if c < c1[q]:
71                     if c1[q] < np.inf:
72                         if queue.contains(q, c1[q]):
73                             queue.remove(q, c1[q])
74                     c1[q] = c
75                     lab[q] = lab[p]
76                     par[q] = p
77                     queue.push(q, c1[q])

Description

iacwatershed segments the image f on the image of labels y. The labels of y are determined not from regional minima, but from the markers from the image g. The iacwatershed function determines the shortest path from each pixel to a marker, using the IFT algorithm. The implementation of this code is based on algorithm of Lotufo and Falcão. [LotufoFalcaoISMM2000].

WARNING: There is a common mistake related to the marker image g. If this image contains only zeros and ones, but it is not a binary image, the result will be an image with all ones. If the marker image is binary, you have to set this explicitly using the iabinary function.

Examples

Example 1

 1 from ia870 import *
 2 
 3 a = uint8([\
 4     [10,   10,   10,   10,   10,   10,   10],\
 5     [10,    9,    6,   18,    6,    5,   10],\
 6     [10,    9,    6,   18,    6,    8,   10],\
 7     [10,    9,    9,   15,    9,    9,   10],\
 8     [10,    9,    9,   15,   12,   10,   10],\
 9     [10,   10,   10,   10,   10,   10,   10]])
10 
11 b = iacmp(a,'==',uint8(6))
12 print 'b=\n',b * 1
13 
14 print 'ws Lines:\n',iacwatershed(a,b,iasecross()) *1
15 print 'ws Regions:\n',iacwatershed(a,b,iasecross(),'REGIONS')
b=
[[0 0 0 0 0 0 0]
 [0 0 1 0 1 0 0]
 [0 0 1 0 1 0 0]
 [0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0]]
ws Lines:
[[0 0 0 0 1 0 0]
 [0 0 0 0 1 0 0]
 [0 0 0 0 1 0 0]
 [0 0 0 0 1 0 0]
 [0 0 0 0 1 0 0]
 [0 0 0 0 1 0 0]]
ws Regions:
[[1 1 1 1 2 2 2]
 [1 1 1 1 2 2 2]
 [1 1 1 1 2 2 2]
 [1 1 1 1 2 2 2]
 [1 1 1 1 2 2 2]
 [1 1 1 1 2 2 2]]

Example 2

1 f = adreadgray('astablet.tif')
2 grad = iagradm(f)
3 mark = iaregmin(iahmin(grad,35))
4 w = iacwatershed(grad,mark)
5 adshow(grad,'gradient image')
6 adshow(mark,'markers')
7 adshow(w,'watershed from markers by IFT')
8 adshow(iagshow(f,w),'watershed lines over the original image')

gradient image

markers

watershed from markers by IFT

watershed lines over the original image

Equation

Limitations

The structuring elements must be symmetric.

See Also

  • iawatershed - Watershed by connected components
  • iatz - Tie-Zone watershed transform

References

[LotufoFalcaoISMM2000] R. Lotufo and A. Falcão,
``The ordered queue and the optimality of the watershed approaches,'' in Proceedings of the 5th International Symposium on Mathematical Morphology and its Applications to Image and Signal Processing, vol. 18. Kluwer Academic Publishers, June 2000, pp. 341–350.