The graph below shows that I have randomly selected a point from the dataset, (the × in the middle of the red circles). Right now this will be the only centroid chosen. I find that the worst case, (the × on far right of the graph). This point is the furthest from the given centroid, therefore it is added as the new centroid. This becomes the second centroid.
Now, suppose we would like to add one more centroid. First, these two centroids will generate a partition. This is denoted using the different colors/patterns: red/circles for those partitioned to the first centroid, and blue/squares for those partitioned to the second.
Then, the greedy algorithm will find which point is the worst case for each cluster. It will pick the worst of these worst points, and this turned out to be the third × that now appears below at the upper right corner of the graph. Previously this point belongs to the second centroid, but now is added as the third centroid.
The green/triangles are those points that are newly divided into the third group.
Similarly we can then find a fourth centroid, (upper left-hand side of the graph). The fourth centroid happens to be the worst point in the previous red cluster.
Once this fourth centroid is added, it again results in a new cluster, shown by the magenta upside down triangles.
Now, let's look at the application to image segmentation, and compare k-means and k-center.
Below is the original color picture containing 368 × 256 pixels. Every pixel is represented by three color components, known as RGB (levels of red, green and blue). We first converted the RGB components into another color space called LUV, which describes a color by luminance, saturation and hue. To segment the image, we take the 3 dimensional color vector for each pixel and apply k-means or k-center clustering to these color vectors. Pixels whose color vectors are clustered into one group will be put grouped as one segmented region.
The images below show the segmentation result obtained by the k-center and k-means algorithm. All the pixels in one segment (i.e., one cluster) are shown by the average color of that cluster. This is why the images appear to be of low resolution. Results of k-means and k-center are quite different. K-means rarely put a small portion of pixels in one cluster, while k-center often does. This is also shown by the previous simulated data set.
segmentation using K-center
segmentation using K-means with LGB initialization
At last, we show segmentation results of k-means using k-center clustering as initialization. This is a small trick which can be helpful for image segmentation. K-center is used to generate the initial prototypes and then k-means was applied afterwards. It seems that k-means combined with k-center initialization gives the best segmentation result.
segmentation by K-means using K-center for initialization
Let's look some scatter plots in order to get a sense of why things work the way they do. Because every pixel is represented by a color vector of three dimensions, the first scatter plot below shows a plot of the U component versus the L component, the second scatter plot shows the V versus the L component. Please note that these scatter plots do not show all the pixels in an image because there are too many pixels and the scatter plots would look quite messy. A small portion of the points are randomly sampled and shown in the scatter plots.
scatter plots for LUV color components with K-center clustering
The red points to the right represent the majority of the pixels, basically everything but the eyes and nose of the dog. The green and blue clusters contain very few points.
K-center tends to generate rather unbalanced clusters because it only cares about the worst case, while k-means is concerned with the total sum of squared distances. K-means tend to break the big mass of data into smaller pieces even if the big mass looks like one cluster.
For example, below are scatter plots showing results of k-means. Again, k-means is not that concerned with the outliers even if they are quite far away.
k-means with LGB initialization.
Below is the result when we use k-means with k-center as an initialization.
k-means with K-center initialization
Below are three sets of paintings. On the left, the original paintings are shown. The middle column is the result of k-means using k-center as initialization; and the right column is the result of k-means using LBG for initialization. K-center for initialization seems to provide better segmentation results. Some small color patches of distinct colors are segmented out by the former, but not the latter.
Comparison of segmentation results: Left: original images, Middle: K-means with k-center initialization, Right: K- means with LGB