Lab: Segmentation

CSC 262 - Computer Vision - Weinman

Summary:: You will implement and experiment with the K-means clustering algorithm for color-based image segmentation.

Deliverables

The Matlab script used to make your comparisons and generate your report
(5 points) Initial cluster color image (A.5)
(10 points) Observations of initial cluster centers (A.6)
(5 points) Initial cluster assignments image (B.11)
(10 points) Initial cluster assignment observations (B.12)
(5 points) Updated cluster color image (C.4)
(10 points) Observations of updated cluster centers (C.5)
(15 points) imkmeans, updateAssignments, and updateCenters functions (B,C,D)
(10 points) Image results for various K (E.1)
(10 points) Cluster images (E.2)
(10 points) Overall observations (E.3)
(10 points) Professionalism of write-up

Preparation

Ultimately, you are encouraged to try out your algorithm on whatever colorful image you wish. For now, though, you should use a standard image to get started

: /home/weinman/courses/CSC262/images/superior.jpg

Because you will be doing color-based segmentation, you should not convert this to grayscale, but for calculations, you should convert it to doubles.

Some of the operations will be computationally intensive; you also should downsize this image so that it is not so big and allows you to see the simple color results more easily. While you could do this via a combination of Gaussian blurring and subsampling, Matlab can also do this for you with imresize:

: B = imresize(A, scale, method);

I recommend you start with something that is about 1/20th the size of the original, using bicubic interpolation.

Exercises

Eventually we will be transforming your work into three separate subroutines. Therefore, you are advised to use variable names that are general and informative and to avoid hard-coding any values that can change. (However, image is a function name, so you should avoid using that as a variable!)

A. Set Up

So that your results are repeatable (particularly so your commentary matches your images), initialize the random number generator with a seed value of your choice. (My default is of course always 42.)

rng('default');
rng(42);

Note that as you are adding commentary on the results to your published file, you will need to have rerun the script from the beginning (or the last point at which you set the seed) to see the cumulative effects of all calls to rand (and kin) that will end up in your published report.
Start by assigning a small value for K.

K = 4;
It is often easier to think of K-means as operating on a matrix, where each row is one feature. Your image is currently M×N×3. Use reshape to change this into a data matrix that is MN×3.
We will store the cluster centers in a K×3 matrix. However, these need to be initialized to some value. Because the values in our data matrix are all in the range [0,1], we can simply generate random cluster centers in this range. Use rand to generate such an initial cluster center matrix.
Your cluster centers can be interpreted as an image colormap that can be used by the commands

image(X);
colormap(map);

Use this technique to display the "image" 1:K (which is actually a vector parading as indices into the color map) using your cluster centers as the color map. That is, use

image( 1:K );

to display the palette consisting of the initial cluster centers.
How do the colors of your initial clusters compare to those in the image? Are any of them close in hue? Brightness? Other considerations? How do you think the pixels in the image will be mapped to these clusters?

B. Assigning Clusters

You now have some very arbitrary cluster centers, and our first step is to assign each pixel (now a row in your data matrix) to a cluster. In order assign each pixel to a cluster, we will need to find the cluster center with the minimum distance from each pixel. While the entire operation could be vectorized in Matlab, it is somewhat space intensive. We will focus on vectorizing the operation over the pixels, and looping (gasp!) over the K clusters.

Create an MN×1 vector for holding the cluster assignments.
Create an MN×1 vector for holding the distance to the closest cluster found so far. Initialize this vector so that every entry is infinity (Inf in Matlab).
For now, let's find the distance to the cluster k=1. Start by finding the difference (i.e., using substraction) between every pixel's color channels and this cluster.
Finish calculating the MN×1 vector of (squared Euclidean) distances between the cluster center and the data (i.e., square the differences and sum them).
Use a vectorized comparison to find all the pixels (rows) whose distance to this cluster is less than the distance to the closest cluster so far.
Assign those indices to the current cluster.
Update the new closest distance for those indices.
Wrap the computations from (B.3-B.7) in a for loop over the K clusters.
Finally, generalize all of the statements from Part B into a function that takes your data matrix and the cluster centers as input and returns the assignment vector as its result:
labels = updateAssignments( data, centers );
Use reshape on your MN×1 assignment vector so that it is M×N.
Use imshow(labels, centers) to display the reshaped labels using the cluster centers as the color map.
Briefly comment on the result. Are the colors accurate? Is the image recognizable? In both cases, why or why not?

C. Updating Cluster Centers

Now that you have some cluster assignments, we can assume they are valid and re-calculate the cluster centers. Once again, the easiest way to do this is not to vectorize, but to loop (gasp!) over the clusters. This is simple enough we will do it from the outside in, rather than our usual ground-up style.

Begin a function that takes a data matrix, the current cluster assignments, and K as its input, returning (updated) cluster centers as its result:
centers = updateCenters( data, labels, K );
Inside a for loop over your K clusters ...
- Find the pixels (data matrix rows) who are assigned the current cluster.
- If there are no rows assigned to the current cluster, use a random color for the cluster center, otherwise
- Calculate the mean color of the pixels assigned to the current cluster, and assign the result as the cluster center.
Use your function to update the cluster centers, given your current labeling. Be sure to use the vector version, of the assignments, your reshaped version from (B.10).
Display your updated cluster centers (as in A.5).
How have the colors of the updated clusters changed? Are they any better? Worse? Same?

D. Putting it Together

You now have functions for both updating labels and cluster centers. All that is left to do it tie a pretty bow around them by writing a K-means function.

Begin a function that takes a color image and K, the number of clusters, and returns both the cluster assignments for all the pixels in the image as well as the cluster centers (the colors).

[labels, centers] = imkmeans( data, K )

Note that you should not call it simply kmeans, because Matlab already has a built-in function by this name.
Start your function by reshaping the image into a data matrix (cf. A.3), and creating an initial set of clusters (cf. A.4).
Given these cluster centers, calculate an initial assignment for the pixels in your data matrix.
Add a for loop that iterates up to a fixed maximum number of iterations. Inside your loop,
1. update the cluster centers, given the assignments, and then
2. update the assignments, given the new cluster centers.
If all your new assignments as the same as the previous ones (see all), then you can quit the loop (see break).
After your loop terminates, you should return the assignment vector to matrix form (cf. B.10).

E. Exploring the Results

For your explorations, you may use a slightly larger image, but make sure it's not too big, or else it may take a very long time.

Apply your function for a variety of K values: 3, 5, 7, 10, and show the resulting images (displayed using the technique of (B.11). Because K-means is essentially a hill-climbing local search method, it may not converge upon a satisfactory solution.¹ If that is so, make note of it and re-run the algorithm.
Display and save at least three (hopefully) interesting clusters from among your results. Note you can visualize this easily by doing something like

imshow( (labels==k)+1 , [ 0 0 0 ; centers(k,:) ] );

so that the cluster k is colored appropriately, but everything else is black.
Important: Use of a colormap (as done implicitly above) impacts the figure window, not just one set of axes (i.e., within a subplot).

Alternatively, you may want to "mask" the raw image with something like the following

imshow( img .* (labels==k) );
Comment on the results you have included. How well does the algorithm work for segmenting the image? What works well? Where are the deficiencies? What can you suggest for improvements?

Acknowledgments

This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 4.0 International License.

Footnotes:

¹That is, it takes steps that look locally optimal until every step from where it is looks worse. Applying such a strategy could get you to the top of an anthill (every step is down), rather than the top of Everest.