Modified K – Medoids Algorithm for Image Segmentation

Modified K – Medoids Algorithm for Image Segmentation

Modified K – Medoids Algorithm for Image Segmentation

Amit Yerpude, Dr. Sipi Dubey

Rungta College of Engg. & Tech.

Bhilai, Chhattishgarh,India

ABSTRACT K medoid a lgorith m is not suitable for large amount of dataset such as color images , because it requires setting each value as a medoid even if its frequency (i.e. number of pixe ls of same intensity) is very low. As the color image has number of different intensities to set as medoids it needs more time for calcu lation. The other ma jor dra wback of e xisting algorithm is to find the optima l nu mber of iterations, in our e xpe rimental result we show that how number of iterat ions play an important role to find the best optima l solution. To overcome this disadvantages this paper gives a modified K Medoids algorith m by using histogram equalization technique. To prove the effic iency of this new algorith m we provide various experimental results over different images with comparison of the existing algorith m.

Keywords Colour image segmentation, Histogram equalization, Old K Medoids clustering algorithm, Modified K Medoids clustering algorithm.

1. INT RODUCTION

   The main goal of image segmentation [1] [2] is domain independent partitioning of an image into a set of disjoint regions. Various clustering techniques [3] are used for image segmentation. In paper [4] [5] authors use K Medoids clustering technique for image segmentation, the main drawback of K Medoid clustering is it takes large amount of time for seg mentation which is highly dependent on the number of iteration. In this paper we discussed a modified K Medoids clustering algorith m which reduces the time without compro mising the effectiveness of the algorithm.

   The paper is organized as follows. In section II, a brief knowledge about histogram equalization technique is provided. In section III, we give the basic strategy of clustering using existing K medoids algorithm. In section IV, we introduce our new modified algorith m for image segmentation. In section V, the results of our experiment are listed and the conclusion is covered in section VI.

2. HIST OGRAM EQUALIZATION

   The concept of histogram equalization [6] is to spread otherwise cluttered frequencies more evenly over the length of the histogram. Frequencies that lie c lose together will dramat ically be stretched out. These respective areas of the

   image that first had little fluctuation will appear grainy and rig id, thereby revealing otherwise unseen details.

   A histogram equalization algorith m will determine the ideal number of t imes each frequency should appear in the image and, theoretically, re-plot the histogram appropriately.

   The ideal number of pixe ls per frequency i is the total number of pixe ls in the image divided by the total number of possible image frequencies N. The algorith m counts the frequencies fro m 0 to N and shifts as many pixe l frequencies into that position as long as this number of pixe ls is less than or equal to a certain delimite r that increases linearly to the frequency. If a p ixe l frequency doesnt fit, it is pushed to the right along the horizontal a xis until a place is found.

3. EXIST ING K MEDOIDS CLUST ERING ALGORITHM

   [5] [7] clustering algorith ms is to find k clusters in n objects by first arbitrarily finding a representative object (the Medoids) for each cluster. Each re ma ining object is c lustered with the Medoid to which it is the most simila r. K-Medoids method uses representative objects as reference points instead of taking the mean value of the objects in each cluster. The algorith m ta kes the input parameter k, the number of c lusters to be partitioned among a set of n objects. A typical K- Medoids algorithm for partit ioning based on Medoid or central objects is as follows:

   K: The number of c lusters

   D: A data set containing n objects

   A set of K clusters that minimizes the sum of the dissimila rit ies of all the objects to their nearest medoid.

   Assign each remaining object to the cluster with the nearest medoid;

   Randomly select a non medoid object Orandom;

   Co mpute the total points S of swap point Oj with Orandom

   if S < 0 then swap Oj with Orandom to form the new set of k medoid

   Until no change;

   The algorithm atte mpts to determine k partitions for n objects. After an initial random selection of k medoids, the algorithm repeatedly tries to ma ke a better choice of medoids.

4. MODIFIED K MEDOIDS CLUST ERING ALGORITHM

   K: The number of segments D: An images

   A segmented image that min imizes the sum of the dissimila rit ies of all the pixe ls to their nearest medoid.

   Convert image into gray scale; Equalize histogram;

   Store the equalized intensities into an array;

   Fig. 5.1.1 (Original Image) Fig. 5.1.2 (segmented

   image with 50 iterat ions)

   Select rando mly K medoids fro m a rray; Re move the selected medoids fro m array; Segment image using this medoids;

   Ca lculate the total cost T and store medoids and cost;

   Randomly select a non medoid Orandom fro m array and re move it fro m a rray ;

   Assign each remain ing pixe l to the seg ment with the

   nearest medoid;

   Co mpute the new total cost Tnew of swap point Oj with Orandom

   if Tnew < T then swap Oj with Orandom to form the new set of k medoid

   Until array is not empty;

5. EXPERIMENTAL RESULT

   The proposed approach is evaluated using different real images. In our experimental result Figure 5.1.1, 5.2.1 and 5.3.1areoriginal images. Each image is segmentized five times with different number o f iterat ion i.e. 50, 100, 150, 200 and 250, using e xisting K- Medoids clustering algorith m.

   Table 5.1 and table 5.2 shows the time required and cost calculated respectively. Figure 5.4 gives the knowledge that the time required for segmentation is highly dependent on the number of iteration, as the number of iteration increases the required time is also increased but figure 5.5 shows that even though the number of iteration increases, the cost or the intercluster similarity is not change drastically.

   Figure 5.1.7, 5.2.7 and 5.3.7 a re the segmented output images by using our modified K- Medoids clustering algorith m. Table

   5.3 and 5.4 shows the difference in time required and cost between existing and modified algorithm.

   Fig. 5.1.3 (segmented image with 100 iterations)

   Fig. 5.1.5 (segmented image with 200 iterations)

   Fig. 5.1.7 (segmented image using new algorith m)

   Fig. 5.1.4 (segmented image with 150 iterations)

   Fig. 5.1.6 (segmented image with 250 iterations)

   Fig. 5.1.1 (Original image) Fig. 5.1.2 (segmented

   image with 50 iterat ions)

   Fig. 5.1.3 (segmented image with 100 iterations)

   Fig. 5.1.4 (segmented image with 150 iterations)

   Fig. 5.1.3 (segmented image with 100 iterations)

   Fig. 5.1.4 (segmented image with 150 iterations)

   Fig. 5.1.5 (segmented image with 200 iterations)

   Fig. 5.1.6 (segmented image with 250 iterations)

   Fig. 5.1.5 (segmented image with 200 iterations)

   Fig. 5.1.7 (segmented image using new algorith m)

   Fig. 5.1.6 (segmented image with 250 iterations)

   Fig. 5.1.7 (segmented image using new algorith m)

   13.77

   TIME (IN SECONDS)
   ITERATION	LENA.JPG	IMAGES TIGER.JPG	SEA.JPG
   256	7.08	24.58
   200	6.23	21.92	12.31
   150	5.41	19.60	10.93
   100	4.69	17.57	9.56
   50	3.94	15.01	8.18

   Fig. 5.1.1 (Original image) Fig. 5.1.2 (segmented

   image with 50 iterat ions)

   30.00

   20.00

   10.00

   0.00

   256 200 150 100 50

   LENA.JPG TIGER.JPG SEA.JPG

   Fig. 5.4 (Graph for Time required for iterat ion)

   COST(DISSIMILARITY B/W PIXELS)
   ITERATION	LENA.JPG	IMAGES TIGER.JPG	SEA.JPG
   256	663.45	2420.22	771.16
   200	656.02	2447.26	790.70
   150	650.26	2474.94	827.31
   100	672.74	2434.17	791.38
   50	658.77	2448.44	840.49

   IMAGES	COST(DISTANCE)
   	OLD(Avg.)	NEW	DIFF(%)
   LENA.JPG	660.24	664.37	-0.62
   TIGER.JPG	2445.01	2439.69	0.22
   SEA.JPG	804.21	787.83	2.08

   3000.00

   2000.00

   1000.00

   0.00

   256 200 150 100 50

   LENA.JPG TIGER.JPG SEA.JPG

   2500.00

   2000.00

   1500.00

   1000.00

   500.00

   0.00

   COST(DISTANCE)

   OLD

   COST(DISTANCE) NEW

   Fig 5.5 (Graph for Cost / Dissimila rity b/w p ixe ls)

   Fig. 5.7 (Diffe rence of cost between Existing and Modified K

   Medoids algorithm)

   3.00

   2.00

   1.00

   IMAGES	TIME (SECONDS)
   	OLD(Avg.)	NEW	DIFF(%)
   LENA.JPG	5.47	4.40	24.32
   TIGER.JPG	19.74	16.71	18.15
   SEA.JPG	10.95	9.10	20.30

   0.00

   -1.00

   COST DIFF(%)

   20.00

   15.00

   10.00

   5.00

   0.00

   TIME (SECONDS) OLD

   TIME (SECONDS)

   NEW

   Fig. 5.8 (Deviation in cost calculation in diffe rent images)

6. CONCLUSION AND FUTURE WORK

   In this paper we suggest an imp roved K Medoids clustering algorith m for image segmentation. Va rious e xperimental data are d iscussed in section V. Table 5.3 and table 5.4 shows the comparison between the K medoids and our modified a lgorith m. The graph on fig. 5.7 shows that the

   Fig. 5.6(Graph for d iffe rence of time required between Existing and Modified K Medoids algorith m)

   30.00

   20.00

   new algorith m gives better time saving strategy up to nearly

   25% . It shows that algorithm is useful for images containing large nu mber of pixe ls (e.g. Tiger.jpg 642*340).Graph on fig

   5.8 shows that the new algorith m work efficiently without

   affecting a large difference in interc luster simila rity, some time it is more than the original a lgorith m but it is very less

   10.00

   0.00

   Fig. 5.7 (Time ga in in Percentage)

   TIME (SECONDS) DIFF(%)

   (less than 1%). Ou r future work incorporates the further

   improve ment of the algorithm which reduces the time and increases the intercluser simila rity.

7. REFERENCES

1. S.Pradeesh Hosea, S. Ranichandra, and T.K.P.Ra jagopal, "Color Image Seg mentation An Approach," Color Image Segmentation An Approach, vol. 2, no. 3, March 2011.

2. R. Ra jesh N. Senthilku maran, "A Note on Image Segmentation Techniques," International J. of Recent Trends in Engineering and Technology, vol. 3, no. 2, May 2010.

3. Osama Abu Abbas, "Comparisions Between Data Clustering Algorithms," The International Arab Journal of Information Technology, vol. 5, no. 3, p. 320, July 2008.

4. Amit Yerpude and Dr. Sipi Dubey, "Colour image segmentation using K Medoids Clustering," Int.J.Computer Techology & Applications, vol. Vo l 3 (1), pp. 152-154, January 2012.

5. Amit Yerpude and Dr. Sip i Dubey, "Robust Method for Noisy Image Seg mentation," IJCSET, vol. 2, no. 2, pp. 891-895, February 2012.

6. Bhawna Mittal, Sheetal Ga rg Ra jesh Ga rg, "Histogram Equalization Techniques For Image Enhancement," IJECT, vo l. 2, no. 1, pp. 107 – 111, March 2011.

7. T. Ve lmurugan and T. Santhanam, "Co mputational Co mple xity between K-Means and K-Medoids Clustering Algorith ms," Journal of Computer Science, vol. 6, no. 3, 2010.