ECEP 596, Autumn 2019 Homework 2: K means Clustering

DUE: October 24, 2019 (Thursday) 11:59 P.M.

Late date: October 27, 2019 (Sunday) 11:59 P.M. (Late policy: 10% penalty per day)

Total points: 12 (+3 extra credit) 

Before you start:

Download the zip file here.

Please refer to HW1 for instructions on Qt installation, usage and details about working with the QImage class. Pay careful attention to all the instructions.

 

Assignment Description:

For this assignment, you'll be implementing the functionality of the Kmeans program, which allows you to load an image and apply K-means clustering to the images. 

In the project, you should only update the file - "Project2.cpp". The other files like "mainwindow.cpp" and "main.cpp" contain code to execute the application. When you compile and run the "Kmeans" project, a user interface (UI) will appear on the screen. The buttons in the UI will call the corresponding functions in "Project2.cpp". Several of the buttons have already been implemented, including "B/W", "Reset" and "Half size". The implementations of these buttons are also in "Project2.cpp", and should provide helper sample code. 

What to turn in:

To receive credit for the project, you need to turn in HERE the 'Project2.cpp' file and a PDF file (name it as report.pdf) containing the requested images for each task with proper captions. Your code needs to be correct and efficient in terms of speed and/or memory; just getting correct outputs is not enough. Please write necessary comments in your code so that it is easily understandable.

 

FIRST WEEK TASKS: (Oct. 15 - Oct. 20)

Task 1: K-means color clustering with random seeds (6 points)

Implement the function RandomSeedImage(double **image, int num_clusters) to perform K-Means Clustering on a color image with randomly selected initial cluster centers in the RGB color space. "num_clusters" is the number of clusters into which the pixel values in the image are to be clustered. Use "(rand() % 256, rand() % 256, rand() % 256)" as RGB values to create #num_clusters centers, assign each pixel of the image to its closest cluster center and then update the cluster centers with the average of the RGB values of the pixels belonging to that cluster until convergence. Use max iteration # = 100 and L1 distance between pixels, i.e. dist = |Red1 - Red2| + |Green1 - Green2| + |Blue1 - Blue2|. The algorithm converges when the sum of the L1 distances between the new cluster centers and the previous cluster centers is less than epsilon*num_clusters. Choose epsilon = 30 (or anything suitable). Note: Your code should account for the case when a cluster contains 0 pixels during an iteration. Also, since this algorithm is random, you will get different resultant images every time you call the function.

To do: Perform random seeds clustering on "Flower.png" with num_clusters = 4 and save as "task1.png".

 

SECOND WEEK TASKS: (Oct. 20 - Oct. 24)

Task 2: K-means color clustering with pixel seeds (6 points)

Implement the function PixelSeedImage(double **image, int num_clusters) to perform K-Means Clustering on a color image with initial cluster centers sampled from the image itself in the RGB color space. "num_clusters" is the number of clusters into which the pixel values in the image are to be clustered. Choose a pixel and make its RGB values a seed if it is sufficiently different (dist(L1) >= 100) from already-selected seeds. Repeat till you get #num_clusters different seeds. Use max iteration # = 100 and L1 distance between pixels, i.e. dist = |Red1 - Red2| + |Green1 - Green2| + |Blue1 - Blue2|. The algorithm converges when the sum of the L1 distances between the new cluster centers and the previous cluster centers is less than epsilon*num_clusters. Choose epsilon = 30.

To do: Perform pixel seeds clustering on "Flags.png" with num_clusters = 5 and save as "task2.png".

 

EXTRA CREDIT:

Task 3: Histogram K-means implementation (+3 points)