Information Technology Reference
In-Depth Information
[
]
…
). Then, the geodesic influence zone
B
(
i
∈
1,
,
k
partitioned in
k
connected sets
()
iz
B
B
within
D
of the set
is computed as:
Di
(
)
{
}
[
] {}
()
(
)
iz
B=p D|j
∈∀∈…
1
k
/
id p,B<d p,B
:
,
(2)
Di
D
i
D
j
dpB
(, ) min
=
dpq
(,)
D
dpq
as the minimum path among all
(,)
where
with
D
i
D
qB
∈
i
paths within
D
between
p
and
q
.
The union of the geodesic influence zones of the connected components B
i
,
()
IZ
B
, is computed as follows:
D
k
()
∑
( )
IZ
B=
iz
(3)
D
D
i
i=
1
The Watershed Transform by immersion is defined by the following recursion:
()
{
}
X=pD| f
∈
p=h
=
T
h
min
h
min
min
(4)
(
)
X=MIN
∪
Z
X,
hh,h
∈
[
)
h+
1
h+
1
T
h
min
max
h+
1
T
,
h
TpDf
=∈
{
|
(
ph
)
≤
},
where
is the set of pixels with grey-level
smaller than or equal to h, and MIN
h
is the union of all the regional minima at level h
.
The watershed line of
D
is then the complement of
defined as
h
X
in
D
.
The Vincent-Soille algorithm, which does not strictly implement equation (4) (for
details see below and [8]), consists of two steps:
max
1.
The pixels of the input image are sorted in increasing order of grey values.
2.
A Flooding step is done, level after level, starting from level hmin and terminating
at level hmax. For every gray value, breadth-first-search is done to determine the
label (label of existing basin, new label or watershed label) to be ascribed to the
pixel.
The location of regional minima is important for segmentation by Watershed
Transform. To extract the objects of interest in the image, the minima should not lie
along the border line of the objects (see Fig. 4 and Fig. 5). On the contrary, regional
maxima should be located on the border lines. To correctly identify the minima far
from the border lines, in practice the gradient image of the original image is used as
an input image for the Watershed Transformation (compare Fig. 5 and Fig. 6).
The Watershed Transform is also dependent on the connectivity. For example, the
gradient image in Fig. 4 has three regional minima if 4-connectedness is used, but
only one minimum if 8-connectedness is used. In the following, we always use 4-
connectedness.
An advantage of the Vincent-Soille algorithm is that it runs in linear running time
respectively to the number of pixels of the input image (if the used sorting algorithm
Search WWH ::
Custom Search