CSE 455 Autumn 2010: HW3
Color Clustering for Scene Segmentation

Date released:  Monday, October 18, 2010

Date due: Wednesday, October 27, 11:59pm

Download the software you need. Windows zip file; Linux zip file
Download the images you need:
    Scenes

In this assignment, you will segment images by color, using the K-means algorithm and some variants. Here is a picture of high quality results on this assignment.

What You Should Do

  1. First implement a basic K-Means Clustering Algorithm (your own code) using the RGB color space the images come in.
    1. First with randomly selected cluster seeds
    2. Next try sampling pixels from the image to find the seeds. Choose a pixel and make its value a seed if it is sufficiently different from already-selected seeds. Repeat till you get K different seeds.
    3. Next with a method that you develop for selecting the seeds intelligently from the image using its color histogram (again your code). The seed selection should be automatic, given the histogram and the number of seeds to be selected. One way to go is to find the peaks in the color histogram as candidates for seeds.
  2. Now develop and implement a smarter K-Means variant (your own code again) that determines the best value for K by evaluating statistics of the clusters. Some possible methods to try:
    1. You can start from the color histogram, as K is closely related to the number of peaks in the histogram. Not all the peaks are necessary as you want only the dominant ones, so you should pick the ones that occupy a certain fraction of the image in terms of pixels.
    2. You can also try clustering using different Ks, and pick the best one. The metric could be related to the distance between clusters and the variance within each cluster.
    3. You are free to come up with your own ways.

  3. Test each variant of the above on the following scene images and report your results: s03, s06, s08, s09, s12.
        
Your k-means code should output an image that can be used to show your clusters. This can be a grayscale image where each pixel's value is the number of the cluster to which it has been assigned, which the provided autocolor function will transform into something more easily interpretable. It could also be a ppm where each pixel has the mean color of the cluster it was assigned to (this generally makes a prettier picture, but it can be harder to tell the number of clusters), or better yet output both.

What You Should Turn In

1. All of your code, which must be well commented and in text files so that the grader can compile it to working binaries.    
    You should put headers on all your routines with the following information:
2. Write a brief report on the performance of:

You report must clearly describe and explain the algorithms you developed and also include some discussions on failure examples or limitations for your approach; this will shed light on future improvements. It must include output results showing original images and color clusters for the different methods. It can be a Word document or  pdf document. HTML or webpages are not accepted.

Download .doc template for the report (HW3-report.doc). You are free to use other text processing tools like latex etc, however make sure that you have the same sections in your report.

Evaluation

Download grading guidelines here.


Please email your code and report to Alfred (alfredg@cs) in a zip file with your last name as the zip file name e.g. Brown.zip, by Wednesday, October 27, 2010 11.59pm.