# Image Segmentation Using Gray-Scale Morphology and Marker-ControlledWatershed Transformation

Authors: K. Parvati; B. S. Prakasa Rao; M. Mariya Das
Journal: Discrete Dynamics in Nature and Society
 (2008)

---

## Abstract

Segmentation, a new method, for color, gray-scale MR medical images, and aerial images, is proposed. The method is based on gray-scale morphology. Edge detection algorithm includes function edge and marker-controlled watershed segmentation. It features the simple algorithm implemented in MATLAB. The watershed segmentation has been proved to be a powerful and fast technique for both contour detection and region-based segmentation. In principle, watershed segmentation depends on ridges to perform a proper segmentation, a property that is often fulfilled in contour detection where the boundaries of the objects are expressed as ridges. For region-based segmentation, it is possible to convert the edges of the objects into ridges by calculating an edge map of the image. Watershed is normally implemented by region growing, based on a set of markers to avoid oversegmentation.


---

## Body

## 1. Introduction and Background

Mathematical morphology
(MM) [1] is a nonlinear branch  of the signal processing field and concerns the
application of set theory concepts to image analysis. Morphology refers to the
study of shapes and structures from a general scientific perspective.
Morphological filters or operators are nonlinear transformations, which modify
geometric features of images. These operators transform the original image into
another image through the iteration with other image of a certain shape and
size which is known as structuring element.A systematic
introduction of theoretical foundations of mathematical morphology, its main
image operations, and their applications can be found in [2–4]. In general,
the structuring element is a set that describes a simple shape that probes an
input image. The basic morphological filters are morphological opening and
morphological closing with structuring elements. These present filters present
several inconveniences in some situations. In general, if undesirable features
are eliminated, the remaining structures will be changed. On the other hand, an
image by reconstruction [5–7] has become a powerful tool that enables us to
eliminate undesirable features without necessarily affecting desirable ones.
From a practical point of view, images by reconstruction are built by means of
a reference image and foreground and background markers. The morphological
image reconstruction-based algorithm used in this paper enables us to obtain the results better than general opening (resp., closing) by reconstruction and to avoid some of the inconveniences.


## 2. Gray-Scale Morphology

The binary morphology can be easily extended to gray-scale
morphology. The only differences result from the definitions of dilation and erosion
because other operations basically depend on them.


### 2.1. Gray-Scale Dilation and Erosion

A
gray-scale image can be considered as a three-dimensional set where the first
two elements are thex and y coordinates of a pixel and the third element is
gray-scale value. It can be also applied to the gray-scale structuring element.
With this concept, gray-scale dilation can be defined as follows.Gray-scale dilation off by b, denoted by f⊕b,
is defined as (2.1)(f⊕b)(s,t)=max{f(s−x,t−y)−b(x,y)(s−x),(t−y)∈Df;(s,y)∈Db}, where Df and Db are  the domains of f and b, respectively.Gray-scale erosion, denoted byfΘb, is defined as (2.2)(fΘb)(s,t)=max{f(s−x,t+y)−b(x,y)(s+x),(t+y)∈Df;(s,y)∈Db}, where Df and Db are the domains of each image or function. Gray-scale dilation and
erosion are duals
with respect to function completion and reflection. That is the relation is (2.3)(fΘb)c(s,t)=(fc⊕b^)(s,t), where fc=−f(x,y) and b^=b(−x,−y); the minimum operator (2.2) will
interrogate a neighborhood with a certain domain and select the smallest pixel
value to become the output value. This has the effect of causing the bright
areas of an image to shrink or erode. Similarly, gray-scale dilation is
performed in (2.1) to select the greatest value in a
neighborhood.


### 2.2. Gray-Scale Opening and Closing

The
opening of a gray imagef by a structuring element b, denoted by f∘b, is defined as (2.4)f∘b=(fΘb)⊕b, and
closing can be defined as (2.5)f•b=(f⊕b)Θb.


### 2.3. Morphological Gradient

The original image is transformed
into a gradient image, which represents the edge strength of each pixel. A
threshold is applied to classify each pixel to the edge point or nonedge point.Multiscale edge detector. For greater
robustness to noise, a multiscale gradient algorithm can be considered. The
term multiscale means analysis of the image with structuring elements of
different sizes. The combination of the morphological gradients in different scales is insensitive not
only to noise but also to extract various finenesses of the edges. The
applicable multiscale edge detector is introduced in [8] to find the gradient
of the image: (2.6)MG(f)=1n∑i=1n[((f⊕bi)−(fΘbi))⊕bi−1], where n is scale and bi denotes the
group of square structuring elements where sizes are (2i+1)*(2i−1) pixels.


### 2.4. Watershed Transformation

The watersheds concept is one of the
classic tools in the field of topography. It is the line that determines where
a drop of water will fall into particular region. In mathematical morphology, gray-scale
images are considered as topographic relieves. In the topographic
representation of a given imageI,
the intensity value of each pixel stands for the elevation at this point. The
initial concept of  the watersheds transformation as a morphological tool was
introduced by
Digabel and Lantuéjoul [9]. Later, a joint work of Lantuéjoul and Beuche led to
the “immersion” of this original algorithm in order to extend it to the more
general framework of gray-scale images. Later, watersheds were studied by many
other researchers and used in numerous gray-scale segmentation problems. The
efficient algorithm for watersheds suggested by Vincent [8, 10] was
reviewed briefly and used throughout the entire simulation.Oversegmentation is the embedded
problem of watersheds. The transformation makes a number of regions as an
output. This problem comes mostly from the noise and quantization error. To
eliminate the effect of local minima from noise or quantization error in the
final results, first the gradient of the original image is computed as a
preprocessing and then watershed transformation is applied. Noise has a quite
different value relative to its neighbor hence it shows a high gradient value.
Another approach to eliminate noise and error effects is to apply efficient algorithm
as a past processing.


## 2.1. Gray-Scale Dilation and Erosion

A
gray-scale image can be considered as a three-dimensional set where the first
two elements are thex and y coordinates of a pixel and the third element is
gray-scale value. It can be also applied to the gray-scale structuring element.
With this concept, gray-scale dilation can be defined as follows.Gray-scale dilation off by b, denoted by f⊕b,
is defined as (2.1)(f⊕b)(s,t)=max{f(s−x,t−y)−b(x,y)(s−x),(t−y)∈Df;(s,y)∈Db}, where Df and Db are  the domains of f and b, respectively.Gray-scale erosion, denoted byfΘb, is defined as (2.2)(fΘb)(s,t)=max{f(s−x,t+y)−b(x,y)(s+x),(t+y)∈Df;(s,y)∈Db}, where Df and Db are the domains of each image or function. Gray-scale dilation and
erosion are duals
with respect to function completion and reflection. That is the relation is (2.3)(fΘb)c(s,t)=(fc⊕b^)(s,t), where fc=−f(x,y) and b^=b(−x,−y); the minimum operator (2.2) will
interrogate a neighborhood with a certain domain and select the smallest pixel
value to become the output value. This has the effect of causing the bright
areas of an image to shrink or erode. Similarly, gray-scale dilation is
performed in (2.1) to select the greatest value in a
neighborhood.


## 2.2. Gray-Scale Opening and Closing

The
opening of a gray imagef by a structuring element b, denoted by f∘b, is defined as (2.4)f∘b=(fΘb)⊕b, and
closing can be defined as (2.5)f•b=(f⊕b)Θb.


## 2.3. Morphological Gradient

The original image is transformed
into a gradient image, which represents the edge strength of each pixel. A
threshold is applied to classify each pixel to the edge point or nonedge point.Multiscale edge detector. For greater
robustness to noise, a multiscale gradient algorithm can be considered. The
term multiscale means analysis of the image with structuring elements of
different sizes. The combination of the morphological gradients in different scales is insensitive not
only to noise but also to extract various finenesses of the edges. The
applicable multiscale edge detector is introduced in [8] to find the gradient
of the image: (2.6)MG(f)=1n∑i=1n[((f⊕bi)−(fΘbi))⊕bi−1], where n is scale and bi denotes the
group of square structuring elements where sizes are (2i+1)*(2i−1) pixels.


## 2.4. Watershed Transformation

The watersheds concept is one of the
classic tools in the field of topography. It is the line that determines where
a drop of water will fall into particular region. In mathematical morphology, gray-scale
images are considered as topographic relieves. In the topographic
representation of a given imageI,
the intensity value of each pixel stands for the elevation at this point. The
initial concept of  the watersheds transformation as a morphological tool was
introduced by
Digabel and Lantuéjoul [9]. Later, a joint work of Lantuéjoul and Beuche led to
the “immersion” of this original algorithm in order to extend it to the more
general framework of gray-scale images. Later, watersheds were studied by many
other researchers and used in numerous gray-scale segmentation problems. The
efficient algorithm for watersheds suggested by Vincent [8, 10] was
reviewed briefly and used throughout the entire simulation.Oversegmentation is the embedded
problem of watersheds. The transformation makes a number of regions as an
output. This problem comes mostly from the noise and quantization error. To
eliminate the effect of local minima from noise or quantization error in the
final results, first the gradient of the original image is computed as a
preprocessing and then watershed transformation is applied. Noise has a quite
different value relative to its neighbor hence it shows a high gradient value.
Another approach to eliminate noise and error effects is to apply efficient algorithm
as a past processing.


## 3. Marker-Controlled Watershed Segmentation

### 3.1. Creating Markers

The marker-controlled watershed segmentation
has been shown to be a robust and flexible method for segmentation of objects
with closed contours, where the boundaries are expressed as ridges. The marker
image used for watershed segmentation is a binary image consisting of either
single marker points or larger marker regions, where each connected marker is
placed inside an object of interest.Each initial marker has a one-to-one
relationship to a specific watershed region, thus the number of markers will be
equal to the final number of watershed regions. After segmentation, the
boundaries of the watershed regions are arranged on the desired ridges, thus
separating each object from its neighbors. The markers can be manually or
automatically selected, but high throughput experiments often employ
automatically generated markers to save human time and resources.


### 3.2. Morphological Image Reconstruction

#### 3.2.1. Dilation-Based Gray-Scale Image Reconstruction

LetI,J be the two images defined on the same domain
and J≤I.
The reconstruction of I from J, denoted as γI(rec)(J), is
obtained by iterating elementary
geodesic dilations of J under I until stability is reached, (3.1)γI(rec)(J)=⋃n≥1δ(n)(J), where δ(I)(J) can be obtained by iterating an elementary
geodesic dilation and the geodesic dilation is defined as (3.2)δ(I)(J)=(J⊕b)∩I (b is the flat structuring element of size I and ∩ stands for pointwise minimum).


#### 3.2.2. Erosion-Based Gray-Scale Reconstruction

LetI,J be two gray-scale images defined on the same
domain and J≤I. The reconstruction of I from J, denoted as ϕI(rec)(J),
is obtained by iterating elementary geodesic erosions of J above I until stability is reached, (3.3)ϕI(rec)(J)=⋂n≥1ε(n)(J), where ε(n)(J) can be obtained by iterating n elementary
geodesic dilation and the geodesic dilation is defined as (3.4)ε(I)(J)=(JΘb)∪I, (b is flat structuring element of size I and ∪ stands for pointwise maximum).Local
minima consist of a small number of pixels or have a low contrast with respect
to their neighbors. The procedure to eliminate local minima adopted is in [10, 11]. The morphological reconstruction transformation is well known in the
binary case, where it simply extracts the connected components of an image,
which are “marked” by another image. Extending it to gray-scale reconstruction,
it can accomplish several tasks such as image filtering, domes, and basin
extraction. In this paper, we used improvised image reconstruction algorithm.


## 3.1. Creating Markers

The marker-controlled watershed segmentation
has been shown to be a robust and flexible method for segmentation of objects
with closed contours, where the boundaries are expressed as ridges. The marker
image used for watershed segmentation is a binary image consisting of either
single marker points or larger marker regions, where each connected marker is
placed inside an object of interest.Each initial marker has a one-to-one
relationship to a specific watershed region, thus the number of markers will be
equal to the final number of watershed regions. After segmentation, the
boundaries of the watershed regions are arranged on the desired ridges, thus
separating each object from its neighbors. The markers can be manually or
automatically selected, but high throughput experiments often employ
automatically generated markers to save human time and resources.


## 3.2. Morphological Image Reconstruction

### 3.2.1. Dilation-Based Gray-Scale Image Reconstruction

LetI,J be the two images defined on the same domain
and J≤I.
The reconstruction of I from J, denoted as γI(rec)(J), is
obtained by iterating elementary
geodesic dilations of J under I until stability is reached, (3.1)γI(rec)(J)=⋃n≥1δ(n)(J), where δ(I)(J) can be obtained by iterating an elementary
geodesic dilation and the geodesic dilation is defined as (3.2)δ(I)(J)=(J⊕b)∩I (b is the flat structuring element of size I and ∩ stands for pointwise minimum).


### 3.2.2. Erosion-Based Gray-Scale Reconstruction

LetI,J be two gray-scale images defined on the same
domain and J≤I. The reconstruction of I from J, denoted as ϕI(rec)(J),
is obtained by iterating elementary geodesic erosions of J above I until stability is reached, (3.3)ϕI(rec)(J)=⋂n≥1ε(n)(J), where ε(n)(J) can be obtained by iterating n elementary
geodesic dilation and the geodesic dilation is defined as (3.4)ε(I)(J)=(JΘb)∪I, (b is flat structuring element of size I and ∪ stands for pointwise maximum).Local
minima consist of a small number of pixels or have a low contrast with respect
to their neighbors. The procedure to eliminate local minima adopted is in [10, 11]. The morphological reconstruction transformation is well known in the
binary case, where it simply extracts the connected components of an image,
which are “marked” by another image. Extending it to gray-scale reconstruction,
it can accomplish several tasks such as image filtering, domes, and basin
extraction. In this paper, we used improvised image reconstruction algorithm.


## 3.2.1. Dilation-Based Gray-Scale Image Reconstruction

LetI,J be the two images defined on the same domain
and J≤I.
The reconstruction of I from J, denoted as γI(rec)(J), is
obtained by iterating elementary
geodesic dilations of J under I until stability is reached, (3.1)γI(rec)(J)=⋃n≥1δ(n)(J), where δ(I)(J) can be obtained by iterating an elementary
geodesic dilation and the geodesic dilation is defined as (3.2)δ(I)(J)=(J⊕b)∩I (b is the flat structuring element of size I and ∩ stands for pointwise minimum).


## 3.2.2. Erosion-Based Gray-Scale Reconstruction

LetI,J be two gray-scale images defined on the same
domain and J≤I. The reconstruction of I from J, denoted as ϕI(rec)(J),
is obtained by iterating elementary geodesic erosions of J above I until stability is reached, (3.3)ϕI(rec)(J)=⋂n≥1ε(n)(J), where ε(n)(J) can be obtained by iterating n elementary
geodesic dilation and the geodesic dilation is defined as (3.4)ε(I)(J)=(JΘb)∪I, (b is flat structuring element of size I and ∪ stands for pointwise maximum).Local
minima consist of a small number of pixels or have a low contrast with respect
to their neighbors. The procedure to eliminate local minima adopted is in [10, 11]. The morphological reconstruction transformation is well known in the
binary case, where it simply extracts the connected components of an image,
which are “marked” by another image. Extending it to gray-scale reconstruction,
it can accomplish several tasks such as image filtering, domes, and basin
extraction. In this paper, we used improvised image reconstruction algorithm.


## 4. Method Overview

The developed segmentation method gives a resultant image, whose
foreground and background markers are the objects we are trying to segment. The
method is applicable to gray-scale images. Color images were first converted into gray scale.
Finding the gradient image using multiscale edge detector (2.6) is shown in Figure 1.(Top) original
images and (below) their respective gradients.
(a)(b)(c)(d)Direct application of watershed
transformation on the gradient images producing typically severe segmentation
of the image, because of numerous minima, exists in real (gradient) images due
to inherent noise. One possibility to get rid of the false regions is the so-called
“marker image” to mark those regions that require segmentation, but it is generally
difficult to obtain relevant markers automatically without any interaction by
the user.In this paper, we used simple
algorithm to create foreground and background markers using morphological image
reconstructions. We used erosion-based gray-scale reconstruction (3.3) and (3.4)
followed by dilation-based gray-scale reconstruction (3.1) and (3.2) to trace the
foreground objects  (selecting structuring element as per the desired objects). The results are shown
in Figure 2.(Top) erosion-based
reconstruction applied on gradient images. (Below) dilation-based
reconstruction applied on top images.
(a)(b)(c)(d)Calculating the
regional maxima of these reconstructed images is done to get smooth edge foreground objects.
Later,  we superimposed these markers on the original images as shown in Figure3.Foreground markers (objects).
(a)(b)(c)(d)The background markers are created by
calculating the Euclidean distance of binary version of above superimposed
image. The gradient image is modified by morphological reconstruction with
foreground and background markers. Application of watershed transform gives
final segmented images of desired objects. The final results are shown in Figures4 and 5.Background objects.
(a)(b)(c)(d)Final segmented images.
(a)(b)(c)(d)Algorithm 4.1.
(i)
Read the color image and convert it to gray-scale.(ii)
Develop gradient images using appropriate edge detection function.(iii)
Mark the foreground objects using morphological reconstruction (better than the opening
image with a closing).(iv)
Calculating the regional maxima and minima to obtain the good
forward markers.(v)
Superimpose the foreground marker image on the original image.(vi)
Clean the edges of the markers using edge reconstruction.(vii)
Compute the background markers.(viii)
Compute the watershed transform of the function.


## 5. Experimental Results

The proposed algorithm applied on the MR
medical images (grey, color), aerial image, and a high-resolution satellite
image is shown in
Figures1(a), 1(b), 1(c), and 1(d), respectively. The algorithm is helpful to
segment the objects that touch each other in an image. We extracted
the tumor-like objects from MR brain images. The results are shown in Figures
5(a) and 5(b). From high-resolution satellite images, man-made objects like
buildings have been extracted and shown in Figure 5(c). From an aerial image,
the river network can be extracted as shown in Figure 5(d). The standard watershed segmentation algorithm
is also applied on the gradient images (after imposing local minima). The
results are shown in Figure 6.
The proposed algorithm results gave better identification of desired objects
(tumor, buildings, and river) than the standard algorithm.Standard watershed segmentation on the gradient images of Figure1.
(a)(b)(c)(d)


## 6. Conclusions and Future Work

This study shows  that the proposed watershed by foreground
markers is able to segment real images containing severe irregularities in a
better way than the standard watershed segmentation. The formulation is based
on markers and simple morphology, which easily allows a regularization of the
watersheds, and is a flexible approach for further optimization parameters. The algorithm is
able to segment or extract desired parts of only gray-scale images. The
technique can possibly be merged with advanced techniques like wavelet
transforms to improve the results especially in the case of high-resolution
images.



---

*Source: 384346-2009-01-05.xml*