Lab: Segmentation

CSC 295 - Computer Vision - Weinman



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

Deliverables

Extra Credit

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/CSC295/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.

A. Set Up

  1. Start by assigning a small value for K.
    K = 3;
  2. 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.
  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.
  4. Your cluster centers can be interpreted as an image colormap that can be used by the commands
    image(X);
    colormap(map);
    Use this 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.
  5. Save the image.
  6. How do the colors of your initial clusters compare to those in the image? Are any of them close in hue? Brightness? Other considerations?

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 minimimum distance from each pixel. The entire operation can be vectorized in Matlab, but it is somewhat space intensive. We will focus on vectorizing the operation over the pixels, and looping (gasp!) over the K clusters.
  1. Create an MN×1 vector for holding the cluster assignments.
  2. 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).
  3. For now, let's find the distance to the cluster k=1. In order to find the difference between every pixel's color channels and the cluster efficiently (in Matlab at least), use bsxfun (just as you did in the feature matching lab).
  4. Calculate the MN×1 vector of (squared Euclidean) distances between the cluster center and the data.
  5. Use a vectorized comparison to find all the pixels (rows) whose distance to this cluster is less than the closest cluster so far.
  6. Assign the current cluster to those indices.
  7. Update the new closest distance for those indices.
  8. Wrap the computations from (B.3-B.7) in a for loop over the K clusters.
  9. 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:
    L = updateAssignments( X, C );
  10. Use reshape on your MN×1 assignment vector so that it is M×N.
  11. Use image(X) to display the labels using the cluster centers as the color map and save the result.
  12. 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.
  1. Begin a function that takes a data matrix, the current cluster assignments, and K as its input, returning (updated) cluster centers as its result:
    C = updateCenters( X, L, K );
  2. Inside a for loop over your K clusters ...
  3. 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).
  4. Repeat the process of (A.4-A.5) with your updated cluster centers.
  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.
  1. 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).
    [L, C] = imkmeans( X, K )
    Note that you should not call it simply kmeans, because Matlab already has a built-in function by this name.
  2. Start your function by reshaping the image into a data matrix (cf. A.2), and creating an initial set of clusters (cf. A.3).
  3. Given these cluster centers, calculate an initial assignment for the pixels in your data matrix.
  4. 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.
  5. If all your new assignments as the same as the previous ones (see all), then you can quit the loop (see break).
  6. 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.
  1. Apply your function for a variety of K values: 3, 5, 7, 10, and save the resulting images (displayed using the technique of (B.11). Since K-means is a local search method, it may not converge upon a satisfactory solution. If that is so, make note of it and re-run the algorithm.
  2. Display and save at least three interesting clusters from among your results. Note you can visualize this easily by doing something like
    imshow( (L==k)+1 , [ 0 0 0 ; C(k,:)]);
    so that the cluster is colored appropriately, but everything else is black.
  3. 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?

Extra Credit

Extend your segmentation/clustering function so that it uses more than just color information. Note that because the Euclidean distance between the data is used, any additional features you introduce are going to have to be scaled so that they make an appropriate contribution to the distance measurement.

Acknowledgments

The superior.jpg image was taken by Jerod Weinman at Grand Marais, MN and is Copyright 2006, licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.
Copyright © 2010, 2012 Jerod Weinman.
ccbyncsa.png
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.