Big picture

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 hand in. You can assume that the grader will link the files into the directory that you anbd in so you do not need to turn those in. You need to provide a report with images and explanations, and code that displays those images when it is run.

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/fall11/ua_cs_only/assignments/sunset.tiff .
         /cs/www/classes/cs477/fall11/ua_cs_only/assignments/tiger-1.tiff .
         /cs/www/classes/cs477/fall11/ua_cs_only/assignments/tiger-2.tiff .

   For visualizing the segmentations, 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.

   Hand in code to generate the segmentations (6 total), and put the original and segmented images (with captions) into your PDF report (+).

2. Add k*X and k*Y to your feature vector, where (X,Y) are the coordinates of the pixel, and k is constant that you can play with. If k is zero, then you would have the same as before. For at least one image, try several values including k=1 and k=10. Do the results make sense? You may have to push k higher to have a significant effect.

   Add a brief report of what you did in your PDF with some result images (+), any code, and some segmented images. Your report should explain the result of varying k.

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

   (If you use only one image for expermenting, don't use the sunset iamge, as it does not have much texture).

   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 alone, and 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 that K-means is sensitive to the range of your data, and so you will want to scale your features accordingly.

   Describe what you did and what you found, together with some images, in your PDF report (+). The code you hand in should generate the images in your report and display them.

Hand in your code for generating and displaying your segmentations, and your PDF report on what you did that includes the resulting images.

The beginning of your report should contain any "meta" issues such skipped questions, or how to run your code if it is not a Matlab program called hw7.m that does everything. It should be possible to grade the assignment based on the report, with running the code needed only to investigate problems or check that the code can create the images in the report.

If you are working in C/C++, please provide an executable called hw7.bin.linux and/or hw7.bin.mac, so that I can run it even if your code does not compile,

How to submit work

Next assignment