CSE 455 Autumn 2014: HW3
Color Clustering for Scene Segmentation
Date released: Tuesday, October 14, 2014
Date due: Thursday, October 23, 11:59pm
Download the software you need.
HW3
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
- First implement a basic K-Means Clustering Algorithm (your own
code) using the RGB color space the images come in.
- First with randomly selected cluster seeds
- 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.
- 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.
- 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:
- 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.
- 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.
- You are free to come up with your own ways.
- 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 a grayscale image that shows your clusters.
You should obtain this image as follows:
1. Replace each pixel's value with the number of the cluster to which it has been
assigned.
2. Use the provided autocolor function to transform into something more easily interpretable.
What You Should Turn In
1. All of your code, which
must be well commented so that the grader can compile it to working binaries.
2. Write a brief report on the performance of:
- the basic K-means with a) random seeds, b) sampled seeds, c) seeds
selected using histogram.
- your smart K-means
algorithm
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.
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
- Working k-means Program: 4 points
- Classical algorithm with random seeds (2 point)
- Selecting seeds by sampling(1 point)
- Selecting seeds using the histogram of the image (1 point)
- Working smarter k-means algorithm: 3 points
- Quality of the code (code structure, comments and documentation): 2 points
- Report: 3 points
- Quality of the results: 3 points
Dropbox
Upload your report and code to the homework dropbox HERE. Any modification made after the deadline will not be counted for your grade.
Homework is due on October 23 (Thursday) by 11:59 PM. Please plan your work early. You can submit until October 25 but you will lose 10% of your grade for every late day.
This is a one-person assignment. You may discuss it, but please turn in your own individual work.