Image Segmentation Using Gray-Scale Morphology and Marker-Controlled Watershed Transformation

K. Parvati,¹ B. S. Prakasa Rao,² and M. Mariya Das³

¹Department of Electronics and Communication Engineering (ECE), Jagannath Institute for Technology and Management (JITM), Parlakhemundi, Gajapati 761 211, Orissa, India
²Department of Geo-Engineering, Andhra University, Visakhapatnam 530 003, India
³Department of Instrument Technology, Andhra University, Visakhapatnam 530 003, India

Sourse of information: http://www.hindawi.com/journals/ddns/2008/384346.html

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.

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 the x 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 of f by b, denoted by , is defined as

(2.1)
where Df and Db are the domains of f and b, respectively.

Gray-scale erosion, denoted by is defined as

(2.2)
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)
where and 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 image f by a structuring element b, denoted by is defined as

(2.4)
and closing can be defined as

(2.5)

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)
where n is scale and bi denotes the group of square structuring elements where sizes are 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 image I, 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

Let be the two images defined on the same domain and . The reconstruction of I from J, denoted as , is obtained by iterating elementary geodesic dilations of J under I until stability is reached,

(3.1)
where can be obtained by iterating an elementary geodesic dilation and the geodesic dilation is defined as

(3.2)
(b is the flat structuring element of size I and stands for pointwise minimum).

3.2.2. Erosion-Based Gray-Scale Reconstruction

Let be two gray-scale images defined on the same domain and . The reconstruction of I from J, denoted as , is obtained by iterating elementary geodesic erosions of J above I until stability is reached,

(3.3)
where can be obtained by iterating n elementary geodesic dilation and the geodesic dilation is defined as

(3.4)
(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.


Figure 1: (Top) original images and (below) their respective gradients.

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.


Figure 2: (Top) erosion-based reconstruction applied on gradient images. (Below) dilation-based reconstruction applied on top images.

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 Figure 3.


Figure 3: Foreground markers (objects).

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 Figures 4 and 5.


Figure 4: Background objects.


Figure 5: Final segmented images.

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 Figures 1(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.


Figure 6: Standard watershed segmentation on the gradient images of Figure 1.

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.

Acknowledgments

The authors thank the Department of Geo-Engineering, Andhra University for providing the high-resolution satellite data. The MR images are downloaded from Google.com/images.

References

1. J. Serra, Mathematical Morphology, vol. 1, Academic Press, London, UK, 1982.

2. J. Serra, Image Analysis and Mathematical Morphology, Academic Press, London, UK, 1982.

3. C. R. Giardina and E. R. Dougherty, Morphological Methods in Image and Signal Processing, Prentice-Hall, Upper Saddle River, NJ, USA, 1988.

4. R. C. Gonzalez and R. E. Woods, Digital Image Processing, Prentice-Hall, Upper Saddle River, NJ, USA, 2nd edition, 2002.

5. J. Crespo, J. Serra, and R. W. Schafer, “Theoretical aspects of morphological filters by reconstruction,” Signal Processing, vol. 47, no. 2, pp. 201–225, 1995.

6. J. Serra, “Connectivity on complete lattices,” Journal of Mathematical Imaging and Vision, vol. 9, no. 3, pp. 231–251, 1998.

7. J. Serra and P. Salembier, “Connected operators and pyramids,” in Image Algebra and Morphological Image Processing IV, vol. 2030 of Proceedings of SPIE, pp. 65–76, San Diego, Calif, USA, July 1993.

8. L. Vincent and P. Soille, “Watersheds in digital spaces: an efficient algorithm based on immersion simulations,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 6, pp. 583–598, 1991.

9. H. Digabel and C. Lantuéjoul, “Iterative algorithms,” in Proceedings of the 2nd European Symposium on Quantitative Analysis of Microstructures in Materials Sciences, Biology and Medicine, pp. 85–99, Caen, France, October 1977.

10. L. Vincent, “Morphological grayscale reconstruction in image analysis: applications and efficient algorithms,” IEEE Transactions on Image Processing, vol. 2, no. 2, pp. 176–201, 1993.

11. D. Wang, “A multiscale gradient algorithm for image segmentation using watersheds,” Pattern Recognition, vol. 30, no. 12, pp. 2043–2052, 1997.