hierarchicalQueue

Synopsis

Prototype:
y = hierarchicalQueue(f, offsets)
Description:
The hierarchicalQueue function implements the watershed transform based on priority queues by Beucher and Meyer [BeucherMeyer1993]. The priority queues use a FIFO for tie breaking on each priority. This algorithm does not produce dividing lines.
Definition:
IFT-WT (see [LotufoFalcaoISMM2000])
Exploration:
Breadth-First

Algorithm

Algoritmo 1: Hierarchical Queue

References

[BeucherMeyer1993]S. Beucher and F. Meyer, Mathematical morphology in image processing, ser. Optical Engineering. New York: M. Dekker, 1993, ch. The Morphological Approach to Segmentation: The Watershed Transformation.
[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.

Source Code

 1 from ipdp.common import *
 2 
 3 # constants
 4 MASK = -2
 5 
 6 def hierarchicalQueue(im, offsets):
 7 
 8     # initialise variables
 9     ws = wsImage(im)
10     N, im, lab, D = ws.begin(offsets)
11 
12     lab[:] = MASK
13 
14     # find minima
15     M = findMinima(im, N, D)
16 
17     queue = wsHeapQueue()
18 
19     for m in xrange(len(M)):
20         for p in M[m]:
21             queue.push(p, im[p])
22             lab[p] = m+1
23 
24     while not queue.empty():
25         p = queue.pop()
26         for q in N(p):
27             if lab[q] != MASK:
28                 continue
29 
30             lab[q] = lab[p]
31             queue.push(q, im[q])
32 
33     return ws.end()