Color Image Segmentation using MSNC Algorithm

Color Image Segmentation using MSNC Algorithm

Color Image Segmentation using MSNC Algorithm

Ms. Salve Amrapali Kishanrao

Dept. of CSE

MGMs College of Engg., Nanded.

Mr. Salve Avinash P. Dept. of V&S MSPGCL,HPS ,Yeldari.

Mr. Salve Vilas P. Examination Dept.

SRTM University, Nanded.

Abstract In this paper we developed color image segmentation using fusion of the Mean Shift (MS) and Normalized Cut (Ncut) approach, to measure two disjoint sets. First one is to measure dissimilarity between different groups and second is to measure similarity within a group, which provides effective and robust segmentation regions of a color image. Basically we performed three steps on natural color images; the First step is to preprocess an image by using mean shift algorithm which gives segmented regions. And original characteristics of an image remain same by this method. Second step is to use the segmented regions represented by using bipartite graph structure. Finally, we apply normalized cut method on this graph to partitioning the image. The mean shift method required much time complexity compared to the proposed method because it is directly applied to regions instead of image pixels.

Index Terms Mean Shift (MS), Normalized Cut (NC), Color Image Segmentation, Graph Partitioning and feature space analysis.

1. INTRODUCTION

   Segmentation is process of subdivides (segments) an image into constituent regions or objects. Segmentation is used when we need to automate a particular activity. The automated system is to extract important features from image data like color, shape, texture, pixels, pixel values etc from which description, interpretation, or understanding of the scene can be provided by the machine. Image segmentation algorithms can be classified into three categories first one is feature space analysis, spatial segmentation and graph based segmentation.

   We briefly discussed the first method, the features that are basically used pixels, pixel values, color and texture. To select and calculate the global characteristics of a color image by using a different distance measures method like 4-neighbour, 8-neighbour and Euclidian distances measures. A Euclidian distance measure that ignores the spatial information of an image. The feature samples are handled as vectors to represent feature vectors and our objective is to merge these vectors into the compact but well separated parts or groups. The drawback of feature space analysis [7], [10] is to loss salient features of image. The structure, shape and boundary of region (edges) of an image somewhat changed.

   In spatial segmentation the shape or structure of an object and detailed edge information of an image are not changed and keep as it is, if the feature spaces overlapped. Then the pixels from different or not connected regions of an image may

   grouped together otherwise it will represent well separate segmented regions [5]. We use watershed algorithm [5] for this method. Its output shows very large number of small but similarity segmented regions therefore we need to apply some region merging techniques [5].

   The graph based techniques is the fusion of feature space and spatial segmentation method [7], [8], [10]. Using this method segmented regions are represented by forming weighted graph, where each region or image pixel is represented as a node or vertex of a graph. The weight of each edge connecting two pixels or regions they are grouped together into the same segmented regions. We apply cut based method to minimized boundaries between two different regions [11], [12]. The drawback of minimum cut, the weight of cut is directly proportional to the number of edges and the minimum cut should not gives always good segmentation. The Shi and Malik [9] proposed segmentation approach to avoid drawback of minimum cut. To apply normalized cut for solving Eigen vector and Eigen values [11].We solve an approximate version of the MinNcut problem by converting it into a generalized eigenvector problem. The disadvantage of normalized cut is to required more space and time complexity. It has only bipartition the graph and problems with the texture images.

   To overcome these entire problems we applied the fusion of Mean Shift and Normalized cuts method. First we apply mean shift segmentation method to segment different regions [4] and then select these regions as a nodes in graph structure of an image plane and finally to apply Normalized cut method to separate these regions.

   Segmentation process is a lack of smooth and continuous development of different regions and it also reduction in time of execution. It contain number of vertices, edges and weighted edges i.e. G= (V,E,W). This algorithm will represent more effective because the number of segmented regions is much smaller than that of the image pixels. The superiority of the proposed method is examined and demonstrated through a large number of experiments on color images because color image carries much more information compared to gray scale images.

2. MEAN SHIFT SEGMENTATION ALGORITHIM

   1. Color Image Segmentation using MS

      The clustering based approach provide robust feature space analysis using mean shift segmentation method[1] which can be applied to smoothing and keep as it is discontinuity characteristics of an image. In this method shape of data clusters are unknown, to know the shape of clusters we apply region merging algorithm. To determine the number of segmented regions is to minimum number of pixels in the region. This algorithm is built on probabilistic intuitions.

      • First we understand mixture models.

      • Then understand mean-shift, we need to understand kernel density estimation[4].

      We consider radically symmetric kernels

      dimensional (d = q + 2) input and the filtered image pixels in the joint spatial-range domain.

      Those regions produced by the mean shift filtering method are nothing but the segmentation and it is actually a merging process performed on a different regions. To select bandwidth parameter h = (hr, hs), to control size of the kernel window which determines the resolution of the mode or pick.

   2. Experimental Results using MS

   An implementation process of mean shift method, we use different color images of size 240×160 in fig.1 first and third column shows original images and then apply mean shift algorithm to set h=(6,8) and m=50 the resultant had displayed in fig. 1 second and fourth column with white contours display the boundaries between the regions.

   satisfying k

   y

   c k , d k

   y 2 where

   constant ck ,d 0

   k y

   0

   c k , d k

   0

   y 2

   dy 1

   (1)

   [ note that k(x) is defined only for x 0 ]. K (y) is a monotonically decreasing function and is referred to as the

   profile of the kernel. Given the function gy ' ky for

   profile, the kernel G(y) is defined as G y c

   g , d

   y 2 For

   n data points yi, i = 1, . . . , n, in the d-dimensional space Rd, the MS is defined

   n y y 2

   g

   g

   y

   y

   as

   i

   i h

   m y

   i 1 y

   h , G

   n y y 2

   g

   g

   i 1

   i

   h

   h

   (2)

   where y is the center of the kernel (window), and h is a bandwidth parameter[3]. Therefore, the Mean Shift is nothing but the difference between the weighted mean, using kernel G is the weights and y as the enter of the kernel (window). The MS method is guaranteed to converge to a nearby point where the estimate has zero gradients [4]. Low-density values of a region has the no interested region in feature space analysis and such a region of interest (ROI) is calculate using mean shift algorithm and it will require large steps.. On the other hand, by using local maxima, the steps require are small thats why feature analysis is more clear. The MS procedure, thus, is an adaptive gradient ascent method [4]. The center position of kernel G can be updated iteratively by

   n x y 2

   1. (b)

   Fig. 1 Test Results of color images. (a) (First column) the original test images. (Second column) the region segmentation by Mean Shift Segmentation. (b) (Third column) the original test images. (Forth column) the region segmentation by Mean Shift Segmentation.

   In the Table No. 1 shows the total region segmentation based on mean shift algorithm and accuracy measure for the same method but the drawback of this method is : 1) Feature space is limited to color. 2)Loose spatial information of segmented regions and 3)Easily gets confused by objects with similar regions.

   Table No.1 Represent number of final segmented regions and time

   i 1

   y i g

   i i

   h

   required to execute Mean Shift Segmentation algorithm.

   x

   Image No.(from top to bottom)		No. of segmented regions using MS method.	Accu racy in %	Execution time in (Sec.)
   As in Fig.1	1	104	75	2.54
   	2	106	77	1.59
   	3	97	70	1.9
   	4	66	65	1.93

   Image No.(from top to bottom)		No. of segmented regions using MS method.	Accu racy in %	Execution time in (Sec.)
   As in Fig.1	1	104	75	2.54
   	2	106	77	1.59
   	3	97	70	1.9
   	4	66	65	1.93

   i 1

   n x

   y 2

   g

   g

   i 1

   i i

   h

   h

   (3)

   Where, the center of initial position of the kernel is denoted by x1 .

   Based on the above procedure, the Mean Shift image filtering algorithm can be obtained. First, an image is represented as a 2-Dimesion lattice of q-dimensional vectors (pixels), where q = 1 for gray-level images, q = 3for color images, and q > 3 for multispectral images. The space of the lattice is known as the spatial domain, while the graph level and the color of spectral information are represented in the range domain. For both domains, the Euclidean distance metric is assumed. Let yi and xi, i = 1..n respectively, be the d-

   III .NORMALIZED CUT METHOD

   A .Normalized Cut Algorithm

   The normalized cut method select image pixel as a node or vertex of graph, distances between two pixels is represent as edge and also calculate weighted edges. To considers segmentation as a graph partitioning problem. The Normalized Cuts algorithm measures the total dissimilarity between the different groups and the total similarity within the groups. To find the optimal solution the splitting points is easily computed by solving a generalized eigenvalue problem[11].

   A graph G = (V, E, W) can be partitioned into two disjoint sets, P, Q. The degree of dissimilarity between these two pieces can be computed as

   Cut ( P , Q )

   w ( x , y )

   x P , y Q

   (4)

   Where, w(x, y) is the similarity between node P and Q. The optimal bipartitioning [8] of a graph is the one that minimizes this cut value [4]. The drawback of minimum cut is not segment proper regions in some cases. Finding the minimum cut is a well-studied problem and there exist efficient algorithms for solving it. However, the minimum cut criteria is favors cutting small sets of common nodes in the graph, and it gives bad partition in some cases. Where assoc (P, y) denotes the total connection from nodes in P to all nodes in the graph, and assoc (Q, y) is similarly defined.

   The normalized cut (Ncut) :

   Fig. 3 Test result of color image with partition class k=4 first column the original test images. Second column the segmentation an edge affinity segmentation. Third column represent final partitioning result using Ncut method. Fourth column partitioning results by directly applying the Ncut method to image pixels an eigenvectors of normalized affinity matrix of graph partitioning results k=4. The size

   Ncut ( P , Q )

   cut ( P , Q )

   Assoc ( P , y )

   cut ( P , Q )

   Assoc (Q , y )

   (5)

   of all images 160*160.

   Unlike the cut criterion that has a bias in favor of cutting small

   sets of nodes, the Ncut criterion is unbiased.

   1. xperimental Results Using NCut Method

      An implementation process of normalized cut method[9], we use different color images of size 160×160.The input image was also obtained from [3]. The Dr. Shis program took 77.6793 seconds for computation, but my program took 22.6640 seconds

      Fig. 2 Show the color original image of size 160*160. Each RGB intensity is normalized to lie within 0 to 255.Subplots (2)-(6) shows the components of partition with Ncut value less than 0.04 Area size

      In the Table No. 2 shows the total region segmentation based on Normalized cut algorithm and accuracy measure for the same method but the drawback of this method is : (1)Huge storage requirement and more execution time .2)Bias towards partitioning into equal segments and 3)Have a problem with textured background.

      Table No.2 Represent number of final segmented regions and time required to execute Normalized cut algorithm.

      Image No.(from top to bottom)		No of segmented region using Ncut method.	Accuracy in (%)	Execution time in (Sec.)
      As in Fig.3	1	3	42	41.969
      	2	3	45	39.922
      	3	6	75	41.078
      	4	6	80	31.906

      VI. PROPOSED APPROACH

      1. Description of the proposed method

more than 1000.parameter setting:

I 5 .0 , X

6 .0 , r 1 .5

The proposed approach follows following procedure:

• First perform image region segmentation by using Mean Shift Segmentation method.

• Treat these regions as nodes in the image plane to represented graph structure.

• Then apply a graph structure to represent them into nodes, edges then calculate similarity

  weighted matrix

  (D W)y Dy

  • The final step is to apply the Normalized cut method to partition these regions into two disjoint sets.

We have applied the proposed algorithm for the segmentation of a set of color images with natural scenes. In this section, we present the experimental results, indicating the different stages of the method. The contrastive experiment results using the Ncut method implemented by [26] are also presented for comparison. The sizes of all the test images are either 240 × 160 or 160 × 240. The parametrs of the MS segmentation algorithm are set to h = (hr, hs) = (6, 8) and M =

50. With this parameter setting, the number of the regions

produced by the MS algorithm is less than 200 regions (i.e., the RAG has less than 200 nodes) for all the test images we used. Therefore, the dimension of the weight matrix is dramatically reduced from the number of image pixels to the number of regions, and subsequently, the complexity of the graph structure employed for image representation is also reduced. To retain the advantage of the balanced partition of the Ncut method, we use C = 3 to construct the weight matrix WC.

Fig. 4 (a) Original image of size 256*256 .(b)Region Segmented By MS algorithm from top to bottom.(C) the contour images of region merging results (d) final segmented region using Ncut method of partition class k=3 and k=6.

The test examples include three image sets. The results of the first set of examples are shown in Fig. 3(a), where the partitioning class k is three. The results of the second set of examples are shown in Fig. 3(b), where k = 6.

The table no.1 represents total time required for execution of mean shift, normalized cut and contribution method. We conclude the time require for MS, Ncut and contribution is less for small iteration but if we go for more iterations the result should is more accurate.

Table No.3 Execution time Comparison between Contributions, Mean Shift and Normalized Cut methods

In the table No,4 # indicate number of segmentations performed in an image and calculate accuracy for Mean shift, Normalized cut and contribution method and it also represented by graph in fig.5.

Table No. 4 Comparison of accuracy measures by different methods and graph shows comparison between these methods.

Fig. 5 Graph shows the comparison of accuracy measures by different methods and graph shows comparison between these methods.

The results of the third set of examples are shown in Fig. 4 with varying values of k. In each figure, the five columns respectively show, from left to right, the original test image, the resultant image after applying the MS segmentation algorithm, the contour image of the final region partitioning, the original images overlapped with the final partitioning contour, and the partitioning result using the Ncut method.

V. CONCLUSION

In this correspondence, we have developed new fusion for the segmentation of color images. The proposed method should avoid drawbacks of mean shift and normalized cut methods. By

using MS method we segment image to preserve discontinuity characteristics of an image. Then apply normalized cut method on these segmented regions to partition an image into multiple and accurate segmented regions. The proposed method is used to reduction in execution of time and it requires less time complexity. In future proposed method used for real time image segmentation.

ACKNOWLEDGMENT

The written words have an unfortunate tendency to degenerate the feeling of genuine gratitude into a still formality. First of all, I would like to express my deep sense of gratitude and indebtedness towards my guide, Dr. Ms .K. C. Jondhale , Associate Prof., computer science and engineering department for her invaluable guidance, unfailing and inspiring effort for completion of this paper. Last, but not least, I thank my family members, for giving me life in the first place, for educating me with aspects from both arts and sciences, for unconditional support and encouragement to pursue my interests.

REFERENCES

1. D. Comaniciu and P. Meer, Mean shift: A robust approach toward feature space analysis, IEEE Trans. Pattern Anal. Mach. Intell., vol. 24, no. 5, pp. 603619, May 2002.

2. S. Wang and J. M. Siskind, Image segmentation with ratio cut, IEEE Trans. Pattern Anal. Mach. Intell., vol. 25, no. 6, pp. 675690, Jun. 2003.

3. Y. Cheng, Mean shift, mode seeking, and clustering, IEEE Trans. Pattern Anal. Mach. Intell., vol. 17, no. 8, pp. 790799, Aug. 1995.

4. Wenbing tao, Hai Jin, Color image segmentation based on mean shift and normalized cuts, IEEE transaction on system, man, and cybernetics-part-B: cybernetics, vol. 37, no. 5, October 2007.

5. V. Grau, A. U. J. Mewes, M. Alcaniz, R. Kikinis, and S.

   K. Warfield, Improved watershed transform for medical image segmentation using prior information, IEEE Trans. Image Process., vol. 23, no. 4, pp. 447 458, Apr. 2004.

6. S. X. Yu and J. Shi, Multiclass spectral clustering, in

   Proc. Int. Conf. Comput. Vis., 2003, pp. 313319.

7. S. Makrogiannis, G. Economou, and S. Fotopoulos, A region dissimilarity relation that combines feature-space and spatial information for color image segmentation, IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 35, no. 1, pp. 4453, Feb. 2005.

8. Z.-Y.Wu and R. Leahy, An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., vol. 15, no. 11, pp. 11011113, Nov. 1993.

9. J. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 8, pp. 888905, Aug. 2000

10. O. J. Morris, J. Lee, and A. G. Constantinides, Graph theory for image analysis: An approach based on the shortest spanning tree, Proc. Inst. Electr. Eng., F, vol. 133, no. 2, pp. 146152, 1986.

11. Y. Weiss, Segmentation using eigenvectors: A unifying view, in Proc. Int. Conf. Comput. Vis., 1999, pp. 957 982.