Image Segmentation Using MCWS Algorithm

Image Segmentation Using MCWS Algorithm

Ms.K.Kavi Niranjana Ms.M.Kalpana Devi Ms.L.Mary Marshaline

Department of MCA Department of MCA Department of MCA

SRIT SRIT SRIT

Abstract

This paper presents a new approach for image segmentation by applying Marker Controlled Watershed Algorithm (MCWS). This segmentation process includes a new mechanism for segmenting the elements of high-resolution images in order to improve precision and reduce computation time. The system applies Marker Controlled Watershed Algorithm to the image segmentation. Separating objects in an image is one of the more difficult image processing operations. The watershed transform is applied to this problem. The watershed transform finds "catchment basins" and "watershed ridge lines" in an image by treating it as a surface where light pixels are high and dark pixels are low. This paper evaluates the proposed approach for image segmentation by comparing with Pillar – K means algorithm and involving RGB color space. The experimental results clarify the effectiveness of our approach to improve the segmentation quality in aspects of precision and computational time.

Keywords

Image segmentation, MCWS algorithm RGB Color Space.

I. INTRODUCTION

The image segmentation is an effort to classify similar colors of image in the same group. It clusters colors into several groups based on the closeness of color intensities inside an image. The objective of the image segmentation is to extract the dominant colors. The image segmentation is very important to simplify an information extraction from images, such as color, texture, shape, and structure. The applications of image segmentation are diversely in many fields such as image compression, image retrieval, object detection, image enhancement, and medical image processing. Several approaches have been already introduced for image segmentation. The most popular method for image segmentation is Hierarchical clustering. It is widely applied for image segmentation. Many researches used Gaussian

Mixture Model with its variant Expectation Maximization.

This paper proposes a new approach for image segmentation that utilizes MCWS to optimize the result from pillar K means algorithm. The Pillar algorithm performs the pillars placement which should be located as far as possible from each other to withstand against the pressure distribution of a roof, as identical to the number of centroids amongst the data distribution. It designates the initial centroids positions by calculating the accumulated distance metric between each data point and all previous centroids, and then selects data points which have the maximum distance as new initial centroids. Here the accuracy may fail in case of longer distance. Considering this as a disadvantage MCWS approach is being implemented. The segmentation process by our approach includes a new mechanism for clustering the elements of high-resolution images in order to improve precision and reduce computation time.

1. MARKER CONTROLLED WATERSHED SEGMENTATION ALGORITHM

   Good result of watershed segmentation entirely relay on the image contrast. Image contrast may be degraded during image acquisition. Watershed algorithm can generate over segmentation or under segmentation on badly contrast images. So to avoid this, Watershed Algorithm is enhanced with the control over the Marks of the boundaries. Thus this proposed method is called as Marker Controlled Watershed Algorithm. The Marker Controlled controls the boundary from under segmentation, over segmentation. Separating touching objects in an image is one of the more difficult image processing operations. The Marker Controlled Watershed algorithm is applied to this problem. The watershed transform finds "catchment basins" and "watershed ridge lines" in an image by treating it as a surface where light pixels are high and dark pixels are low. Segmentation using the watershed transforms works well if you can identify, or "mark," foreground objects and background locations.

2. EXPERIMENTAL RESULTS OF K-MEANS

   1. K-Means Clustering

      The k-means algorithm assigns each point to the cluster whose center (also called centroid) is nearest. The center is the average of all the points in the cluster.

      The algorithm steps are:

      Step 1: Choose the number of clusters, k.

      Step 2: Randomly generate k clusters and determine the cluster centers, or directly generate k random points as cluster centers.

      Step 3: Assign each point to the nearest cluster center.

      Step 4: Recompute the new cluster centers.

      Step 5: Repeat the two previous steps until some convergence criterion is met (usually that the assignment hasn't changed).

      The main advantages of this algorithm are its simplicity and speed which allows it to run on large datasets. Its disadvantage is that it does not yield the same result with each run, since the resulting clusters depend on the initial random assignments. It minimizes intra-cluster variance, but does not ensure that the result has a global minimum of variance. Considering the unstable output as a disadvantage,

      MCWS is implemented in image segmentation.

   2. Output of K-Means Clustering

      (a)

      (b) (c)

      Fig. 1 Visual Comparison of K-Means Image Segmentation

      (a) Original Image (b) Clustering the objects (c) Clustering the background.

3. PROPOSED APPROACH

1. Basic Theory of Marker Controlled Watershed Segmentation

   Segmentation using the watershed transforms works well with identifying marks on the foreground objects and background locations. Marker-controlled watershed segmentation follows this basic procedure:

   1. Compute a segmentation function. This is an image whose dark regions are the objects you are trying to segment.

   2. Compute foreground markers. These are connected blobs of pixels within each of the objects.

   3. Compute background markers. These are pixels that are not part of any object.

   4. Modify the segmentation function so that it only has minima at the foreground and background marker locations.

   5. Compute the watershed transform of the modified segmentation function.

   All these procedure is summarized into several steps that are proposed as follows.

   The algorithm steps are:

   Step 1: Read in the color image and convert it to grayscale

   Step 2: Use the gradient magnitude as the segmentation function

   Step 3: Mark the foreground objects

   Step 4: Compute background markers

   Step 5: Compute the watershed transform of the segmentation function.

   Step 6: Visualize the result.

2. EXPERIMENTAL RESULTS OF MCWS

   1. (b)

(c) (d)

(e) (f)

Fig. 2 Visual Comparison of MCWS Image Segmentation

Fig. 2 Visual Comparison of MCWS Image Segmentation

(a) Original Image (b) Image with disk structuring

(c) Eroding the grayscale (d) RGB imposed on the image.

(e) Optimized Object Clustering

Fig. 2 (a) is the original image and it is converted into gray scale which has been taken for the experimental research. Fig. 2 (b) it is the disk structured image. Morphological structuring element is created with a flat structured element such as disk. Morphological operations run much faster when the structuring element uses approximations than when it does not. However, structuring elements that do not use approximations are not suitable for computation.

ig.2 (c) This image erodes the gray scale with respect to the predefined properties of the structuring elements. Fig. 2 (d) the image returned by watershed is

stored in the form of matrix and is converted into a RGB image for visualizing the region.

Fig. 2 (e) after converting into RGB image, the colors of the object which does not resemble the background color is clustered and optimized. Fig. 2 (f) the background and the color of the object which resembles the background color are clustered and optimized.

1. CONCLUSION

   In this paper, we have presented a new approach for image segmentation using MCWS algorithm. The system applies MCWS to cluster and optimize the image. The K means algorithm does not yield the same result with each run, since the resulting clusters depend on the initial random assignments. It minimizes intra-cluster variance, but does not ensure that the result has a global minimum of variance. The output of the K means algorithm does not generate a clear cluster. Hence, MCWS algorithm is implemented for the same problem and the result is shown as an optimized image. This algorithm is able to optimize the clustering for image segmentation in aspects of precision and computation time. A series of experiments involving four different color spaces with variance constraint and execution time were conducted. The experimental results show that our proposed approach for image segmentation using Marker controlled Watershed Segmentation algorithm is able to improve the precision and enhance the quality of image segmentation in all color spaces. It also performed the computational time as fast as K-means and kept the high quality of results.

2. REFERENCES

1. Ali Ridho Barakbah and Yasushi Kiyoki, A New Approach for Image Segmentation using Pillar-Kmeans Algorithm, World Academy of Science, Engineering and Technology 59 2009

2. K. Atsushi, N. Masayuki, K-Means Algorithm Using Texture Directionality for Natural Image Segmentation, IEICE technical report. Image engineering, 97 (467), pp.17-22, 1998.

[3]. S. Ray, R.H. Turi, Determination of number of clusters in K-means clustering and application in colthe image segmentation, Proc. 4th ICAPRDT, pp. 137-143, 1999. [4]. B. Kövesi, J.M. Boucher, S. Saoudi, Stochastic K-means algorithm for vector quantization, Pattern Recognition Letters, Vol. 22, pp. 603-610, 2001.

[5]. Y. Gdalyahu, D. Weinshall, M. Wermen, Self-Organizationin Vision: Stochastic clustering for Image Segmentation, Perceptual Grouping, and Image database Organization, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23, No. 12, pp. 1053-1074, 2001.

[6]. B. Wei, Y. Liu, Y. Pan, Using Hybrid Knowledge Engineering and Image Processing in Color Virtual Restoration of Ancient Murals, IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 5, 2003. [7]. M. Luo, Y.F. Ma, H.J. Zhang, A Spatial Constrained K-Means Approach to Image Segmentation, Proc. the 2003

Joint Conference of the Fourth International Conference on Information, Communications and Signal Processing and the Fourth Pacific Rim Conference on Multimedia, Vol. 2, pp. 738-742, 2003.

[8] Y.M. Cheung, k*-Means: A new generalized k-means clustering algorithm, Pattern Recognition Letters, Vol. 24, pp. 2883-2893, 2003.

[9]. Beucher S, Meyer F: The morphological approach to segmentation: The watershed transformation. In: Mathematical Morphology in Image

Processing. E. Dougherty (ed). Marcel Dekker, New York, 1992.

[10]. Garbay C, Chassery J-M, Brugal G: An interactive region-growing process for cell image segmentation based on local color similarity and global shape criteria. Anal Quant Cytol Histol 8:2534, 1986.

[11]. Vincent L: Morphological grayscale reconstruction in image analysis: Applications and efficient algorithms. IEEE Trans Image Proc 2:176 201, 1993.

[12]. J.L. Marroquin, F. Girosi, Some Extensions of the K-Means Algorithm for Image Segmentation and Pattern Classification, Technical Report, MIT Artificial Intelligence Laboratory, 1993.

[13]. Qixiang Ye Wen Gao Wei Zeng, Color Image Segmentation Using Density-based Clustering IEEE – ICASSP 2003.

[14]. Jiawei Han, Micheline Kamber, Data Mining Concepts and Techniques, Morgan Kaufmann Publishers, Chapter 8, pp. 363- 364, 2001.

[15] James D. Foley, Andries van Dam, Steven K. Feiner and John F. Hughes, Computer Graphics: Principles and Practice, 2nd ed., Reading, Mass, Addison-Wesley, 1990.

[17] M. Miyahara and Y. Yoshida, Mathematical Transform of (R, G, B) Color Data to Munsell (H, V, C) Color Data, SPIE Visual Communications and Image Processing, vol. 1001, pp. 650-65, 1988.

[18]. K. Barnard, P. Duygulu, and D. forsyth, Clustering Art, Conference on Computer Vision and Pattern Recognition, Hawaii, pp. 434-441, 2001.

[19]. Malik Sikandar Hayat Khiyal, Aihab Khan, and Amna Bibi, Modified Watershed Algorithm for Segmentation of 2D Images, Issues in Informing Science and Information Technology ,Volume 6, 2009.

[20]. Hsiesh, F-Y. (2006). A study of watershed transform on image segmentation and data classification. Doctoral Dissertation, National Central University, Computer science and Information Engineering.