# Synopsis

Prototype:
y = dijkstraMoore(f, offsets)
Description:
The dijkstraMoore function implements the watershed transform based on shortest path forests using the algorithm of Dijkstra-Moore and a path cost function of summation. Also, this algorithm requires the input image f has no plateaus. This algorithm was proposed by Meyer [MeyerSP1994] and correct by Roerdink and Meijster [RoerdinkMeijsterFI2000] to generate the watershed pixels.
Definition:
TD-WT
Exploration:

# Algorithm

Algoritmo 1: Dijkstra-Moore

# References

 [MeyerSP1994] F. Meyer, ``Topographic distance and watershed lines,'' Signal Processing, vol. 38, no. 1, pp. 113–125, 1994.
 [RoerdinkMeijsterFI2000] J. B. T. M. Roerdink and A. Meijster, ``The watershed transform: definitions, algorithms and parallelization strategies,'' Fundam. Inf., vol. 41, no. 1-2, pp. 187–228, 2000.

# Source Code

``` 1 from ipdp.common import *
2
3 # constants
5 WSHED = 0
6
7 def dijkstraMoore(im, offsets):
8
9     # initialise variables
10     lc = lowerComplete(im, offsets)
11     ws = wsImage(lc)
12     N, im, lab, D = ws.begin(offsets)
13
14     # find minima
15     M = findMinima(im, N, D)
16
17     def cost(p, q):
18         LSp = im[p] - min(im[N(p)])
19         LSq = im[q] - min(im[N(q)])
20         if im[p] > im[q]:
21             return LSp
22         elif im[q] > im[p]:
23             return LSq
24         else:
25             return (LSp + LSq)/2.0
26
28     dist = ws.makeWorkCopy(inf)
29
30     for m in xrange(len(M)):
31         for p in M[m]:
32             lab[p] = m+1
33             dist[p] = im[p]
34
35     # make the domain object a set
36     D = list(D)
37
38     while len(D) > 0:
39         p = dist.argmin()
40
41         D.remove(p)
42         for q in N(p):
43
44             c = cost(p,q)
45             if dist[p] + c < dist[q] and lab[q] == MASK:
46                 dist[q] = dist[p] + c
47                 lab[q] = lab[p]
48             elif dist[p] + c == dist[q] and lab[q] != lab[p]:
49                 lab[q] = WSHED
50
51
52         dist[p] = inf
53
54     return ws.end()
```