# A Novel Model of Image Segmentation Based on Watershed Algorithm

Authors: Ali Abdullah Yahya; Jieqing Tan; Min Hu
Journal: Advances in Multimedia
 (2013)

---

## Abstract

A novel model of image segmentation based on watershed method is proposed in this paper. To prevent the oversegmentation of traditional watershed, our proposed algorithm
has five stages. Firstly, the morphological reconstruction is applied to smooth the flat area
and preserve the edge of the image. Secondly, multiscale morphological gradient is
used to avoid the thickening and merging of
the edges. Thirdly, for contrast enhancement,
the top/bottom hat transformation is used.
Fourthly, the morphological gradient of an image is modified by imposing regional minima
at the location of both the internal and the external markers. Finally, a weighted function is
used to combine the top/bottom hat transformation algorithm and the markers algorithm
to get the new algorithm. The experimental results show the superiority of the new algorithm
in terms of suppression over-segmentation.


---

## Body

## 1. Introduction

A segmentation divides an image into its constituent regions or objects, and the segmentation must be stopped when the objects of interest in an application have been isolated [1]. Image segmentation is based on three principal concepts: edge detection, thresholding, and region growing. The most common one is thresholding. Thresholding has a high speed of operation and ease of implementation. However its performance is relatively limited since image pixels with the same gray level value will invariably be segmented into the same class [2]. Segmentation by morphological watersheds [3–10] embodies many of the concepts of the other three approaches, which produces more stable segmentation results, as well as providing simple framework. A simple watershed transformation causes oversegmentation [11]. In order to prevent this oversegmentation, the watershed method passed through several stages of evolution. The original watershed method was developed by Lantuejoul [12] and was widely described together with its applications by Beucher and Meyer [13]. The authors in [3] used FIFO queues to extend the original evolution with gray scale images [11]. Shafarenko et al. [14] applied FIFO to color images. In this paper we enhance the contrast of the gradient image by top/bottom hat transformation, modify the result of the enhancement by imposing regional minima at the locations of both the internal and the external markers, combine the top/bottom hat transformation algorithm and the markers algorithm by using suitable weight function, and subject the combination to the watershed algorithm. The new algorithm has a capability to prevent oversegmentation of the simple watershed segmentation algorithm. The other particularity of the proposed algorithm is insensitivity to noise.


## 2. Proposed Algorithm

In the proposed algorithm we clean up the image by morphology reconstruction, avoid the thickening and merging of the edges by the multiscale gradient, enhance the contrast of the gradient image by top/bottom hat transformation, modify the enhanced image by internal and external markers, and subject the image combination (top/bottom image with marker image) to watershed segmentation algorithm.


### 2.1. Morphological Reconstruction

Reconstruction is a morphological transformation involving two images and a structuring element. The first image is called marker and the second is called mask. Morphological image processing contains two fundamental operations: erosion and dilation. Dilation and erosion are operations that thicken and thin the objects in the image, respectively. The dilation and erosion of the imagef by structuring element B with f and B as sets in Z×Z, denoted by f⊕B and f⊖B, respectively, are defined as follows:
(1)(f⊕B)(x,y)=max{f(x-x1,y-y1)+B(x1,y1)∣(x-x1,y-y1)∈Z,(x1,y1)∈Z},(f⊖B)(x,y)=min{f(x+x1,y+y1)-B(x1,y1)∣(x+x1,y+y1)∈Z,(x1,y1)∈Z}.
The opening of image f by structuring element B is defined as follows:
(2)ϑ(f)=f∘B=(f⊖B)⊕B.
The closing of image f by structuring element B is defined as follows:
(3)θ(f)=f•B=(f⊕B)⊖B.To smooth the imagef by reconstruction operator, we use the following equation:
(4)R(f)=β(θl,(f⊕B)),0≤l≤n,
where β is reconstruction operator, θl is reference image which is obtained by closing the image f, l times, and n is the size of the structure element B [4].


### 2.2. Multiscale Morphological Gradient

Usually we use the gradient magnitude to preprocess a gray-scale image before using the watershed transformation for segmentation. Dilation and erosion can be used in combination with image subtraction to obtain the morphological gradient imageG(f) of the smoothed image R(f) as follows:
(5)G(f)=(R(f)⊕Bi)-(R(f)⊖Bi),
where Bi is a structuring element (SE) of size (2i+1)×(2i+1).The regions in an image are thickened and shrunk by dilation and erosion, respectively. Subtracting erosion from dilation will emphasize the boundaries between regions; in other words, the effect of the subtraction operation is enhancing the edges. Consequently it prevents merging them. For multiscale gradient imageMG(f), we use a multiscale gradient algorithm first proposed by Wang [16]:
(6)MG(f)=1n∑i=1n‍[G(f)⊖Bi-1].When we subject the multiscale gradient image to watershed segmentation algorithm, it is inevitable that there are so many watershed ridge lines that do not correspond to objects in which we are interested, that is, oversegmentation. Dilated multiscale gradient imageMG(f) with a structuring element B can reduce this oversegmentation. Therefore the final gradient image LG(f) can be expressed as follows:
(7)LG(f)=β[MG(f),(MG(f)⊕B)].


### 2.3. Top/Bottom Hat Transformation

The main goal of the top and bottom hats transforms is to lighten objects on a dark background and darken objects on a light background, respectively [17]. As a result the contrast of the image will be enhanced.Top-hat transformation [18, 19] of a final gradient image LG(f) is defined as follows:
(8)T(LG(f))=LG(f)-(LG(f)∘B).Bottom-hat transformation of a final gradient imageLG(f) is defined as follows:
(9)B(LG(f))=(LG(f)•B)-LG(f).In this paper we use top/bottom hat transformationH(f) to enhance the contrast of the final gradient image LG(f), which contributes to reduce oversegmentation that is produced by subjecting the final gradient image to the watershed segmentation algorithm.


### 2.4. Markers Extraction

Objecting a gradient image directly to the watershed segmentation algorithm can lead to oversegmentation due to noise and other local irregularities of the gradient. The ideal method to prevent this oversegmentation is based on the concept of markers whose aim is to pinpoint regions that are homogeneous in terms of texture, color, and intensity and then merge them to get relatively accurate segmentation. Internal markersI(f) are inside each of the objects of interest, whilst external markers E(f) are contained within the background. These markers are used to modify the gradient image using minima imposition technique. This technique will modify the image wherefore regional minima takes place only in marked location. The image obtained by marker image M(f) is a binary image such that a pixel belonging to homogeneous region will be marker (made black), otherwise it will be white. The concept of markers is a good method for avoiding oversegmentation. Nevertheless in this method some objects will leave without marks, which means that the final segmentation will miss these objects.


### 2.5. A Combined Algorithm

As mentioned above, a multiscale gradient usually leads to oversegmentation, whilst markers extraction leaves some objects without marks. Therefore the combining of these two methods by appropriate weight function can overcome the shortcomings of these two methods. In other words, the combination with proper weight can be expected to segment the objects that are left without marks and at the same time prevent oversegmentation that is caused by multiscale gradient, which can provide more perfect results when we use watershed segmentation algorithm. Considering the characteristics of the multiscale gradient (enhanced by top/bottom hat transformation) method and the markers method, we propose a weight function as follows:(10)λ={I(f)p,ifP∈μ(Piswhite);E(f)p,ifP∈ν(Pisblack),
where P is a pixel at position (i,j), μ is a foreground of the image, and ν is a background of the image. The new algorithm that is obtained by combining the enhanced final gradient image H(f) with marker image M(f) is as follows:
(11)A(f)=λ·M(f)+(1-λ)·H(f).FromA(f) we can expect the following. (i)
In the regions that have large number of segmented regions (oversegmentation) the new algorithm will play good role to control oversegmentation; namely, the new algorithm will highlight the markers methodM(f) since λ is close to 1 in this case.(ii)
In the regions that contain the objects which are left without marks, the new algorithm will play good role to segment these objects; in other words, the new algorithm will highlight the role ofH(f) since λ is close to 0 in this case.


## 2.1. Morphological Reconstruction

Reconstruction is a morphological transformation involving two images and a structuring element. The first image is called marker and the second is called mask. Morphological image processing contains two fundamental operations: erosion and dilation. Dilation and erosion are operations that thicken and thin the objects in the image, respectively. The dilation and erosion of the imagef by structuring element B with f and B as sets in Z×Z, denoted by f⊕B and f⊖B, respectively, are defined as follows:
(1)(f⊕B)(x,y)=max{f(x-x1,y-y1)+B(x1,y1)∣(x-x1,y-y1)∈Z,(x1,y1)∈Z},(f⊖B)(x,y)=min{f(x+x1,y+y1)-B(x1,y1)∣(x+x1,y+y1)∈Z,(x1,y1)∈Z}.
The opening of image f by structuring element B is defined as follows:
(2)ϑ(f)=f∘B=(f⊖B)⊕B.
The closing of image f by structuring element B is defined as follows:
(3)θ(f)=f•B=(f⊕B)⊖B.To smooth the imagef by reconstruction operator, we use the following equation:
(4)R(f)=β(θl,(f⊕B)),0≤l≤n,
where β is reconstruction operator, θl is reference image which is obtained by closing the image f, l times, and n is the size of the structure element B [4].


## 2.2. Multiscale Morphological Gradient

Usually we use the gradient magnitude to preprocess a gray-scale image before using the watershed transformation for segmentation. Dilation and erosion can be used in combination with image subtraction to obtain the morphological gradient imageG(f) of the smoothed image R(f) as follows:
(5)G(f)=(R(f)⊕Bi)-(R(f)⊖Bi),
where Bi is a structuring element (SE) of size (2i+1)×(2i+1).The regions in an image are thickened and shrunk by dilation and erosion, respectively. Subtracting erosion from dilation will emphasize the boundaries between regions; in other words, the effect of the subtraction operation is enhancing the edges. Consequently it prevents merging them. For multiscale gradient imageMG(f), we use a multiscale gradient algorithm first proposed by Wang [16]:
(6)MG(f)=1n∑i=1n‍[G(f)⊖Bi-1].When we subject the multiscale gradient image to watershed segmentation algorithm, it is inevitable that there are so many watershed ridge lines that do not correspond to objects in which we are interested, that is, oversegmentation. Dilated multiscale gradient imageMG(f) with a structuring element B can reduce this oversegmentation. Therefore the final gradient image LG(f) can be expressed as follows:
(7)LG(f)=β[MG(f),(MG(f)⊕B)].


## 2.3. Top/Bottom Hat Transformation

The main goal of the top and bottom hats transforms is to lighten objects on a dark background and darken objects on a light background, respectively [17]. As a result the contrast of the image will be enhanced.Top-hat transformation [18, 19] of a final gradient image LG(f) is defined as follows:
(8)T(LG(f))=LG(f)-(LG(f)∘B).Bottom-hat transformation of a final gradient imageLG(f) is defined as follows:
(9)B(LG(f))=(LG(f)•B)-LG(f).In this paper we use top/bottom hat transformationH(f) to enhance the contrast of the final gradient image LG(f), which contributes to reduce oversegmentation that is produced by subjecting the final gradient image to the watershed segmentation algorithm.


## 2.4. Markers Extraction

Objecting a gradient image directly to the watershed segmentation algorithm can lead to oversegmentation due to noise and other local irregularities of the gradient. The ideal method to prevent this oversegmentation is based on the concept of markers whose aim is to pinpoint regions that are homogeneous in terms of texture, color, and intensity and then merge them to get relatively accurate segmentation. Internal markersI(f) are inside each of the objects of interest, whilst external markers E(f) are contained within the background. These markers are used to modify the gradient image using minima imposition technique. This technique will modify the image wherefore regional minima takes place only in marked location. The image obtained by marker image M(f) is a binary image such that a pixel belonging to homogeneous region will be marker (made black), otherwise it will be white. The concept of markers is a good method for avoiding oversegmentation. Nevertheless in this method some objects will leave without marks, which means that the final segmentation will miss these objects.


## 2.5. A Combined Algorithm

As mentioned above, a multiscale gradient usually leads to oversegmentation, whilst markers extraction leaves some objects without marks. Therefore the combining of these two methods by appropriate weight function can overcome the shortcomings of these two methods. In other words, the combination with proper weight can be expected to segment the objects that are left without marks and at the same time prevent oversegmentation that is caused by multiscale gradient, which can provide more perfect results when we use watershed segmentation algorithm. Considering the characteristics of the multiscale gradient (enhanced by top/bottom hat transformation) method and the markers method, we propose a weight function as follows:(10)λ={I(f)p,ifP∈μ(Piswhite);E(f)p,ifP∈ν(Pisblack),
where P is a pixel at position (i,j), μ is a foreground of the image, and ν is a background of the image. The new algorithm that is obtained by combining the enhanced final gradient image H(f) with marker image M(f) is as follows:
(11)A(f)=λ·M(f)+(1-λ)·H(f).FromA(f) we can expect the following. (i)
In the regions that have large number of segmented regions (oversegmentation) the new algorithm will play good role to control oversegmentation; namely, the new algorithm will highlight the markers methodM(f) since λ is close to 1 in this case.(ii)
In the regions that contain the objects which are left without marks, the new algorithm will play good role to segment these objects; in other words, the new algorithm will highlight the role ofH(f) since λ is close to 0 in this case.


## 3. Experimental Results

To evaluate the proposed algorithm, we select four images as examples. The results of the proposed segmentation algorithm are shown in Figures1, 2, 3, and 4, where in each figure are illustrated, respectively, the original image, the result by traditional watershed algorithm, the result by final multiscale gradient algorithm, the result by the algorithm in [4], the result by the algorithm in [15], and the result by the new algorithm. From Figures 1, 2, 3, and 4 it is obvious to see that the proposed algorithm gives optimal results. The results of the new segmentation algorithm are compared with those of the traditional watershed segmentation algorithm, final multiscale gradient segmentation algorithm, the algorithm in [4], and the algorithm in [15], respectively.From left to right and from top to bottom: original image, result of traditional watershed algorithm, result of final multi-scale gradient algorithm, result of [4] algorithm, result of [15] algorithm, and result of the new algorithm.
(a)
(b)
(c)
(d)
(e)
(f)From left to right and from top to bottom: original image, result of traditional watershed algorithm, result of final multi-scale gradient algorithm, result of [4] algorithm, result of [15] algorithm, and result of the new algorithm.
(a)
(b)
(c)
(d)
(e)
(f)From left to right and from top to bottom: original image, result of traditional watershed algorithm, result of final multi-scale gradient algorithm, result of [4] algorithm, result of [15] algorithm, and result of the new algorithm.
(a)
(b)
(c)
(d)
(e)
(f)From left to right and from top to bottom: original image, result of traditional watershed algorithm, result of final multiscale gradient algorithm, result of [4] algorithm, result of [15] algorithm, and result of the new algorithm.
(a)
(b)
(c)
(d)
(e)
(f)The result of the traditional watershed segmentation algorithm suffers from serious oversegmentation that makes the result virtually useless.Since the final multiscale gradient algorithmLG(f) reduces the effect of the noise, the results look much better than traditional watershed. Nevertheless there are some watershed ridge lines that do not correspond to the objects in which we are interested. The proposed algorithm overcomes the problems of oversegmentation and noise sensitiveness of the traditional watershed segmentation algorithm, so the oversegmentation is almost reduced, and the location of the edges is very accurate.From Figure1, we can see that the watershed ridge lines between the rice grains have completely disappeared in the image that was segmented by the proposed segmentation algorithm and the algorithm in [4], unlike in the cases of traditional watershed segmentation algorithm and final multiscale gradient segmentation algorithm, where we can see many closed and connected regions whose boundaries follow the contours of the image that made the image look very messy, especially in the case of traditional watershed segmentation algorithm. As for the case of the algorithm in [15] the rice grains almost left without marked.From Figures2, 3, and 4 we can find that the traditional watershed, final multiscale gradient, and the algorithms in [4, 15] oversegment the image into peak, pit and saddle regions, which result in many watershed ridge lines that do not correspond to the objects in which we are interested, while only peak and pit, regions appear in the image by the proposed algorithm. From Figures 2, 3, and 4 we see that the traditional watershed, final multiscale gradient, and the algorithms in [4, 15] lead to oversegmentation. Nevertheless the proposed algorithm leads to correct segmentation.Table1 lists the computational costs for different equations for four images. From this table, it can be seen that (11) proposed in our paper takes less computation time than (14) and (2) proposed in [4] and [15], respectively, which means that our proposed algorithm saves more computation time than the other two algorithms; in other words, the proposed algorithm is much economical.Table 1
Computational cost of [4, (14)], [15, (2)], and (11).
Images
[4] model
[15] model
New model
Rice
0.0047 s
0.0146 s
0.0033 s
Fingerprint
0.0054 s
0.0164 s
0.0034 s
Cells
0.0251 s
0.0299 s
0.0126 s
Grass
0.0226 s
0.0294 s
0.0128 s


## 4. Conclusion

To solve the oversegmentation and noise sensitiveness of the simple watershed transform, the new algorithm is proposed in this paper. The proposed segmentation algorithm was implemented for several images and produced very satisfactory results with respect to suppression of oversegmentation. Appropriate weight function is used to combine the enhanced final multiscale gradient algorithm with markers algorithm to get the new algorithm. A combination of these two algorithms can contribute to overcome the oversegmentation and undersegmentation which are caused by enhanced final multiscale gradient algorithm and markers algorithm, respectively. The experimental results show that the new algorithm is superior to the final multiscale gradient algorithm, the algorithm in [4], and the algorithm in [15] in terms of suppression of oversegmentation of traditional segmentation algorithm.



---

*Source: 120798-2013-09-04.xml*