Function iawatershed - Watershed transform based on connected components

Synopse

Watershed transform by connected components.

  • y = iawatershed(f, Bc=iasecross(), option='LINES')
    • y: Image
    • f: Image
    • Bc: Structuring Element (connectivity)
    • option: 'LINES' for the lines dividing regions or 'REGIONS' for a labelled image
001. from ia870 import iasecross, iasubm, iaero, iabinary
002. 
003. def iawatershed(f, Bc=iasecross(), option='LINES'):
004.     from ipdp import se2offset
005. 
006.     offset = se2offset(Bc)
007.     w = connectedComponents(f, offset)
008.     if option == 'LINES':
009.         w = iasubm(w, iaero(w))
010.         w = iabinary(w)
011.     return w
012. 
013. # constants
014. MASK = -2
015. PLATEAU = -1
016. 
017. def connectedComponents(im, offsets):
018. 
019.     from ipdp import wsImage
020.     from ipdp import wsQueue
021. 
022.     # initialise variables
023.     ws = wsImage(im)
024.     N, im, lab, D = ws.begin(offsets)
025. 
026.     lab[:] = MASK
027.     adr = ws.makeWorkCopy(0)
028. 
029.     queue = wsQueue()
030. 
031.     def find(p):
032.         q = p
033.         while adr[q] != q:
034.             q = adr[q]
035.         u = p
036.         while adr[u] != q:
037.             v = adr[u]
038.             adr[u] = q
039.             u = v
040.         return q
041. 
042.     # step 1
043.     for p in D:
044. 
045.         q = p
046.         for u in N(p):
047. 
048.             if im[u] < im[q]:
049.                 q = u
050. 
051.         if q != p:
052.             adr[p] = q
053.         else:
054.             adr[p] = PLATEAU
055. 
056.     # step 2
057.     for p in D:
058.         if adr[p] != PLATEAU:
059.             continue
060. 
061.         for q in N(p):
062.             if adr[q] == PLATEAU or im[q] != im[p]:
063.                 continue
064. 
065.             queue.push(q)
066. 
067.     while not queue.empty():
068.         p = queue.pop()
069.         for q in N(p):
070.             if adr[q] != PLATEAU or im[q] != im[p]:
071.                 continue
072. 
073.             adr[q] = p
074.             queue.push(q)
075. 
076.     # step 3
077.     for p in D:
078.         if adr[p] != PLATEAU:
079.             continue
080. 
081.         adr[p] = p
082. 
083.         for q in N(p):
084.             if q > p or im[q] != im[p]:
085.                 continue
086. 
087.             u = find(p)
088.             v = find(q)
089.             adr[u] = adr[v] = min(u,v)
090. 
091.     # step 4
092.     basins = 1
093.     for p in D:
094. 
095.         r = find(p)
096.         adr[p] = r
097.         if lab[r] == MASK:
098.             lab[r] = basins
099.             basins += 1
100.         lab[p] = lab[r]
101. 
102.     return ws.end()

Description

iawatershed segments the image f on the image of labels y. The labels of y form connected components, and receive values greater than 1. The label 0 is not used, as is generally associated with watershed pixels on the context of the watershed transform. The neighbourhood for the algorithm is defined by structuring element Bc. The implementation of this code is based on algorithm of Bieniek and Moga [BieniekMogaISMM1998], [BieniekMogaPR2000].

Examples

Example 1

1. import ia870 as MT
2. 
3. f = adreadgray('astablet.tif')
4. grad = MT.iagradm(f)
5. w = MT.iawatershed(grad, MT.iasebox())
6. wr = MT.iawatershed(grad, MT.iasebox(), 'REGIONS')
7. adshow(grad, 'gradient')
8. adshow(w, 'watershed LINES')
9. adshow(MT.iaglblshow(wr), 'watershed REGIONS')

gradient

watershed LINES

watershed REGIONS

Equation

with the regional minima and the labelled output

Limitations

The structuring element must be symmetric.

See Also

References

[BieniekMogaISMM1998] A. Bieniek and A. Moga,
``A connected component approach to the watershed segmentation,'' in ISMM '98: Proceedings of the fourth international symposium on Mathematical morphology and its applications to image and signal processing. Norwell, MA, USA: Kluwer Academic Publishers, 1998, pp. 215–222.
[BieniekMogaPR2000] A. Bieniek and A. Moga,
``An efficient watershed algorithm based on connected components,'' Pattern Recognition, vol. 33, no. 6, pp. 907–916, 2000.