 Open Access
 Total Downloads : 932
 Authors : Amit Yerpude, Dr. Sipi Dubey
 Paper ID : IJERTV1IS3100
 Volume & Issue : Volume 01, Issue 03 (May 2012)
 Published (First Online): 30052012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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.

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.

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, replot 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.

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. KMedoids 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.

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;

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)

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.

REFERENCES

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.

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.

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

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

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

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.

T. Ve lmurugan and T. Santhanam, "Co mputational Co mple xity between KMeans and KMedoids Clustering Algorith ms," Journal of Computer Science, vol. 6, no. 3, 2010.