This assignment will help you understand solving problems using the iterative chicken-and-egg approach, and in particular, the k-means algorithm for clustering. Clustering will be applied to image segmentation, and you will experiment with different feature vectors.

You can do this assignment in either Matlab or C/C++.

Information for those working in C/C++ who want to use my libraries.

Assignment specification

This assignment has three parts, the first two being required for undergrads and grads.

To simplify things, you should hard code the file names in the version of your program that you give to the TA. Please attempt to give the TA a self contained set of files. You should provide a README explaining, at a minimum, how to run any programs that you have provided. When the TA runs your program(s), the images requested below should appear. You are asked to hand them in as well, to simplify grading.

1. Implement K-means clustering. You should make K easy to set. At every iteration you must print out the value of the objective function (which should go down). Recall that the objective function is the sum of the squared errors from the mean of the assigned cluster. Use your implementation to segment the following three images based on color taken as a 3D vector, using k=5 and k=10.

         /cs/www/classes/cs477/spring06/ua_cs_only/assignments/sunset.tiff .
         /cs/www/classes/cs477/spring06/ua_cs_only/assignments/tiger-1.tiff .
         /cs/www/classes/cs477/spring06/ua_cs_only/assignments/tiger-2.tiff .

   Hand in any code, and some segmented images. For simplicity, you can simply set each segment to its mean color. You could spice it up adding region borders. One way to do so is to make any pixel that is not surrounded by pixels from the same cluster a distinctive color.

2. Add s*(x,y) to your feature vector, where s is constant. If s is zero, then you would have the same as before. For at least one image, try several values including s=1 and s=10. Do the results make sense?

   Hand in a brief report of what you did, any code, and some segmented images.

3. Required for grad students only (modest extra credit for ugrads).

   Construct some texture features from a black and white version of the image (R+G+B). Do with using your ability to find horizontal and vertical edges at various blurring sigmas. Consider a window size, W, centered on each image pixel in turn. Compute the mean squared response of some filters over the pixels of W, for some sigmas. This will result in a feature vector that captures some notion of texture for the location of W.

   Explore using this feature vector together with the full color (RGB), and using only brightness instead (R+G+B), and with and without the spatial location feature in the previous question, for some choices for W. For more interesting results, you may want to apply the scaling trick to the color / brightness features. You do not need to try everything with everything. However, it is a good exercise to organize your experimentation so you can efficiently study the effects of various choices.

   Don't forget about the possibility of scale effects!

   Hand in a brief report of what you did, what you learned (do the results make sense?), any code, and some segmented images.

To hand in the above, use the turnin program available on lectura (turnin key is cs477_hw7). Hand in your code, some representative images, and explanation of what you are handing in and what you did in the README, including your comments regarding the effect of adding (x,y) with increasing weight.