hillClimbing

Synopsis

Prototype:
y = hillClimbing(f, offsets)
Description:
The hillClimbing function implements the watershed transform based on image integration from regional minima. 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:
Breadth-First

Algorithm

Algoritmo 1: Hill Climbing

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
 4 WSHED = 0
 5 MASK = -2
 6 
 7 def hillClimbing(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     lab[:] = MASK
15 
16     # find minima
17     M = findMinima(im, N, D)
18 
19     # expands xrange into a list
20     S = list(D)
21 
22     # label minima
23     for m in xrange(len(M)):
24         for p in M[m]:
25             lab[p] = m+1
26             # removes inner pixels from S
27             hmax = max(im[N(p)])
28             if hmax == im[p]:
29                 S.remove(p)
30 
31     Sc = dict()
32     while len(S) > 0:
33         p = S[(im[S]).argmin()]
34         S.remove(p)
35         Sc[p] = True
36 
37         upstream = list()
38         for q in N(p):
39             if im[p] == min(im[N(q)]):
40                 upstream.append(q)
41         for q in upstream:
42             if Sc.has_key(q):
43                 continue
44 
45             if lab[q] == MASK:
46                 lab[q] = lab[p]
47             elif lab[q] != lab[p]:
48                 lab[q] = WSHED
49 
50     return ws.end()