K-means & Image Segmentation - Computerphile

K-means sorts data based on averages. Dr Mike Pound explains how it works.

Dr. Mike's Code:
% This script is the one mentioned during the Computerphile Image
% Segmentation video. I chose matlab because it's a popular tool for
% quickly prototyping things. Matlab licenses are pricey, if you don't have
% one (or, like me, work for an organisation that does) try Octave as a
% good free alternative. This code should work in Octave too.

% Load in an input image

% In matlab, K-means operates on a 2D array, where each sample is one row,
% and the features are the columns. We can use the reshape function to turn
% the image into this format, where each pixel is one row, and R,G and B
% are the columns. We are turning a W,H,3 image into W*H,3

% We also cast to a double array, because K-means requires it in matlab
imflat = double(reshape(im, size(im,1) * size(im,2), 3));

% I specify that initialisation shuold sample points at
% random, rather than anything complex like kmeans++ initialisation.
% Kmeans++ takes a long time if you are using 256 classes.

% Perform k-means. This function returns the class IDs assigned to each
% pixel, and in this case we also want the mean values for each class -
% what colour is each class. This can take a long time if the value for K
% is large, I've used the sampling start strategy to speed things up.

% While KMeans is running, it will show you the iteration count, and the
% number of pixels that have changed class since last iteration. This
% number should get lower and lower, as the means settle on appropriate
% values. For large K, it's unlikely that we will ever reach zero movement
% (convergence) within 150 iterations.
K = 3
[kIDs, kC] = kmeans(imflat, K, 'Display', 'iter', 'MaxIter', 150, 'Start', 'sample');

% Matlab can output paletted images, that is, grayscale images where the
% colours are stored in a separate array. This array is kC, and kIDs are
% the grayscale indices.
colormap = kC / 256; % Scale 0-1, since this is what matlab wants

% Reshape kIDs back into the original image shape
imout = reshape(uint8(kIDs), size(im,1), size(im,2));

% Save file out, you need to subtract 1 from the image classes, since once
% stored in the file the values should go from 0-255, not 1-256 like matlab
% would do.

This video was filmed and edited by Sean Riley.

[YingwuUsagiri]

Mike is seriously one of my favourites. He's not old-timey so he doesn't clash with Brailsford nor Mr Heartbleed but he's still very technical and it seems like his knowledge is extremely diverse. From imagery to coding to hacking to password stuff (etc. etc.).

[qwertyman]

his neuralnet and learning explanations, as a collective, blow my mind.

[parlaparolequimestco]

I love the video of Dr Mike pound, he explains well and he's entertaining :)

[michaels]

bro, ive seen so many videos of smart people try to explain concepts like this and none have come close to how simple and clear you explain it. you've clearly mastered what you are interested in. mucho respecto de los angeles

[rian]

just found this, a week of lecture done in just over 8 minutes. absolutely great explanations from Dr Mike Pound, clear and sound

[jonnypanteloni]

I just want to thank Mike Pound and Sean for putting this whole thing together. This has fostered creativity in computers for me and encouraged me to explore more about computers.
I wouldn't really come here for a classroom, but this sort of short educational video format is really cool!

[-beee-]

This finally helped me understand why K-means is relevant in ML and image recognition. Thank you!

[JohnMichaelson]

Something very similar is used in remote sensing for vegetation classification and analysis with multi-band imagery. Train the software on the color and IR signature returns of known vegetation and surface types in a portion of an image and it merrily classifies all the rest.

[dvdreb]

You should do a separate channel for this guy

[TheMeyerchris]

By far the best contributor to Computerphile imho. Not that the others are bad, but every video with this dude is gold.

[mybigbeak]

This was really clear, and I can see lots of uses for learning this. It makes me want to have a go at writing the k-means method myself.

[lokeshpal]

Was looking for the explanation only but stayed around because things kept on getting interesting. Nice video.

[MrDubidubidubidu]

You are the best. I don't know if you already have, but I really hope you go into teaching, your explanations are always crystal clear.

[lewisb]

I'm still confused, but I love listening to Dr Pound! :D

[dolfinsbizou]

My god, I've been like "There isn't any computer science channels on Youtube" for so much time, and today I just discover your channel (thanks to e-penser, a French youtuber, who presented your channel in his last video) with this video that speaks of kmeans, a clustering algorithm I used in a recent research internship for my studies. :o

[Jorgepg]

Dr. Mike is amazing at explaining and seems to know a whole lot. Many thanks for the code! Would be great if it was given more often so that we can easily try things at home! :)

[azmfhqzafarhan]

I haven't ever seen such an explanation about anything on the internet!

[x]

Wow, this totally helps me understand the photoshop magic wand tool, the reason why Star Craft Brood Wars looks the way it does when it gets compressed, and so much more. The implications of this algorithm go so far in common application. Man I love computer science @_@

[juweinert]

Yep - super pixel segmentation would be AWESOME! Please do it! :)

[eck]

Just wow! Cool stuff, thank you. This helped me to understand it much better. Real life examples helps a lot a well!