%% K Means Clustering
% Your job is to implement a simple k-means clustering algorithm to segment images by color. Note that Matlab has a built-in kmeans function, which you cannot use; it’s your job to implement this.
% Start by using the Command Window to navigate to the folder where you stored this script and the photo. MATLAB uses simple Linux folder commands like pwd and cd.
% Run each section (Live Editor > Run Section) to see the output to the right. You'll need to fill in some of the code, specifically the 2 steps of the algorithm.

clear all
clc

% You can change the image later if you want.
% From https://www.rose-hulman.edu/admissions-and-aid/financial-aid/financial-aid-basics/cost-and-financial-aid/loans-grants-and-scholarships.html
img = imread('WhiteChapel.jpg');
imshow(img);

% Convert to doubles in range [0,1]
img = double(img)/255;

% Shrink it a lot for debugging. Later you can drop it down to a smaller power of 2.
scale = 128
img = imresize(img, 1/scale);
% Then show it big and pixelated for debugging
imshow(pixelate(img,scale))

% Initialization:

% Set up random number generator with the fixed seed 17 for debugging.
% You can comment out that line later to make it pseudorandom.
rng('default')
rng(17)

% How many means
k = 7;

% In this k-by-3 matrix, each row is a mean RGB color.
means = rand(k,3);

% This is a mask to hold labels. Each location will store which of the 
% k means that the pixel in that location is closest to (which 
% row in the means matrix). Initializing it to ones instead of zeros just
% lets the starting code run without crashing. The labels will get
% overwritten by the body of the algorithm anyway.
labels = ones(size(img, 1), size(img, 2));

% The body of the algorithm:
%

% I hardcoded the number of iterations. You can change this as you like.
% You could also test for convergence.

for iter = 1:5
    % Implement the two steps in the k-means algorithm.
    
    
    % TODO 1. For each pixel, find distance to each cluster mean and 
    % store which cluster it belongs to in "labels"
    
    
    
    % TODO 2. Then recalculate the means of each cluster, also using "labels"
    % so you know which pixels are in each cluster.
  
    
    
    % Show results as we go, just for fun. You can comment it out if you
    % like.
    displayLabels(img, labels, means, scale)
    
end

%

% Display the final answer
displayLabels(img, labels, means, scale)

% Once you finish, then try:
% Using different values of k (one that is far too low, like 2-3, one big enough to capture most of the main colors in the image, and one more in the middle). Note how it changes.
% Using a smaller value of "scale" to get a higher resolution image.
% Using a different image of your choosing that shows off the algorithm.
%% Great job. Show this off to someone!
%
% These helper functions are used in the above code. Functions need to go at the bottom of the script which is why they are here. You shouldn't need to modify them, but may do so if you like.
%

function out = pixelate(img, scale)
[nr,nc,nchannels] = size(img);
out = zeros(nr*scale, nc*scale, nchannels);
for r = 1:nr
    for c = 1:nc
        pixel = img(r,c,:);
        replicatedPixel = repmat(pixel, [scale, scale, 1]);
        % size(replicatedPixel);
        out((r-1)*scale+1:r*scale, (c-1)*scale+1:c*scale, :) = replicatedPixel;
    end
end
end


function displayLabels(img, labels, means, scale)
% This function creates a color image, where each position is colored
% with the mean color it is closest to.
labelImg = zeros(size(img));
for r = 1:size(img,1)
    for c = 1:size(img,2)
        labelImg(r,c,:) = means(labels(r,c),:);
    end
end
figure; imshow(pixelate(labelImg,scale))
end