K-means & Image Segmentation - Computerphile

Key Takeaways

So we're going to talk about sort of an entry- level um clustering approach called CINS. Now C means comes up a lot in other fields. So machine learning uses C means quite a lot. It's what we call an unsupervised clustering method. Often what you have is a situation where you have some training data but you already know what it is and then you try and teach a network to find the same thing again. So we've got labeled training data. In K means what we've got is just some data and we say split that into three please. I'll start by showing a very simple overview here of how K means works. If we imagine we've got some some data that's grouped up. So I'm going to draw some X's here and some X's here. So if we wanted to split this data up, we have no idea about this data. To my eye, it looks like there are two clusters here, right? Partly because I cheated and drew two clusters, but you know, so if we were giving this data which is in two dimensions to a machine and said cluster this into two, what would it do? Basically is a question. There's lots of different approaches. K means is just one of these approaches that I'm going to show you today. Is K like just a variable or is Yeah, K is a variable we we input at the beginning. So if it's two, we're going to split this into two. If it's five, we're going to split this into five, which would kind of be oversplitting this arguably, but it depends. When images come in, then you might imagine splitting it into 256. So we can turn it into a 256 color palette image as an example. Okay, so the the number of K is very much dependent on the situation you're looking at. So how do we do this? Well, what we do is we have K averages for this data. So, K means, that's how it works. So, I've got myself a couple of squares of paper here that I'm going to use as my mean position. So, I'm going to have this as mean position one and this is mean position two. Now, if I was to calculate the mean position of all of this data, this one is going to be somewhere in the middle. And what K means is going to do is partition this into two and then calculate the means and then repartition it based on those means and try and iteratively work out where the the ideal means should be. So let's start number one over here and let's start number two over here. We want to partition this data into these groups. It's probably going to put a partition somewhere around here and maybe this is going to be in group two. So these these will be decided, you know, depending on which they're nearest to. And so that's our initial segmentation which is pretty poor because it's put a line straight through the middle of this data and it's no it's not really any good but it's a start. And so then what we do is we say right we've got all of these in group one. So what is the actual average position of these? And maybe this one's in group one as well. So it maybe moves just down there a little bit. Just just tweaks a little bit. Now this one has got quite a lot of these in it. So it's just going to come up a little bit. So that's step one, right? So we partition them into these two means and then we move the means a little bit based on how these new partitions have formed. For now, let's assume we've picked one and two at random. We might talk a bit about how you initialize them in in a minute. But for step two, we do the exactly the same thing again. So we say, well, now look, the data's changed somewhat. Okay, so I'm going to use my green pen now. So maybe these ones are now closest to one and these ones are now closest to two. So we're getting there. Okay. So then we reclassify them and we recmp compute the means again and two comes up here and one comes a bit down here and then we do it again and two comes over here and one comes over here and gradually we settle on the optimal mean position for our groups. Okay. And then what that finally means is we put a big nice line between these two bits of data. Okay, which is exactly what we wanted. Is it possible they could get it completely wrong? Good question. Yes. Um, so absolutely. Right. So if I was if I was putting in one and two at random. So for example, if I put one and two over here, okay, you might imagine a situation where if we're drawing a line down like this, they're kind of evenly distributed. There's no real pull either way and they just kind of get stuck there. Okay, so that could happen, right? So often what we might do is run C means a few times with different starting positions and then pick the best one. Okay, pick the best one as in each of the ones in this cluster are nearer to one than they would be in this situation. What we sometimes do is instead of picking these at random because, you know, if we put it over here, that's not hugely helpful. It's just going to take longer to uh converge on a solution. What we sometimes do is pick two points as our starting positions. So, I could pick a point here and a point here. Now, that's not going to necessarily completely solve the problem. You know, if you pick really bad points, that might be a problem, but on average, it's going to work out okay. Okay, there are other there are other initialization methods like C means plus+ and things like this that you can read about that do slightly more complex things. Um but the very general idea is we have an initial guess at how to separate our data. We separate it and then recalculate the centers of those regions and then we repeat that process to try and converge on a good separation. And Cayman is very effective. You know, it's simple, really simple. Two steps basically. Move these points into one of the two classes and then recmp compute the means and just do that over and over again. Now, this is two dimensional data X and Y. But there's no reason it couldn't be three or four or five dimensional data, right? Which I can't draw a fivedimensional don't know what that's called, but you know, a fivedimensional object here on the paper, right? I could barely draw a threedimensional one. So, but in an in an image, of course, we've usually got three dimensions, RG and B. So what we have is we have one mean for the red position and one mean for the blue position and one mean for the green position and we're trying to move around these in this color space trying to find what of the dominant colors. So k means on an image will not only tell you uh which pixels belong to which of the three classes or four classes or five classes. It'll also tell you what's the average color of those classes. Um so then we can simplify our image. So if you wanted to compress an image for example and change it to say 16 colors, right? Then you would just split it into K clusters where K is 16 and then those dominant colors are what you're going to pick and it will look kind of like the original image. Not great, but um you know people are used to seeing compressed images like this, you know, on the internet. So let's look at some images and see what it does. You could pick any initial image to do this. To my eye there's maybe three or four dominant colors here. There's green, obviously, blue, and black. and to a lesser extent white I suppose because of these clouds or gray. What we will do is we will pick three um pixels at random. Okay. And they will be the initial values for our means. Okay. So let's imagine I'm splitting this image into three because I think maybe they're three dominant colors. So I pick I have three means instead of just number one I have a two and a three. They get started at random uh with random RGB values and I cluster the whole image into those regions. One, two, or three. Um, then I recomp compute these mean values and I cluster again. And I recmp compute the mean values and I cluster again. And this is what happens on this image for a K of three. So we've got the black or very dark green down here, light green and gray blue sky. So that's has done exactly what we hoped it would do. Okay, it's split the image into three. If we start to increase the amount of classes, we can slowly start to improve the image and maybe start to get towards what the original image actually looked like. This is eight classes. You can see that now we're starting to see what we were looking at before. There's now a difference between the cloud and the sky and quite a lot of difference now on these bushes here. Okay. And as we go up, it gets better and better. Now we're on 256 colors. We've had a problem here of some of these have been put into a weird cluster, but that's just what happens sometimes with K means. So you reinitialize it. But you can see that actually the sky is now looking quite a lot like it did originally because we've got lots of different colors that we can represent it. In terms of image processing, we might segment this image to try and find the dominant objects. In this image, it's not hugely helpful because even in um even with a few classes, we've got objects all over the place. We can't, for example, pick out the trees particularly well because the trees are the same color as a grass and the same color as this these bushes here. So, doesn't really help us, but it depends on the image you're using. Um, if there was a red bus and nothing else in the image was red, we could pick that class out nicely. So, it depends on the situation going forward. There are much more complicated segmentation approaches. So things like super pixels that we can talk about another time that try and group coherent regions of the image locally. Um so they're bringing spatial information into it as well which makes a lot more sense because our bus isn't going to be distributed in the red throughout the image. It's going to be in a box. So we can start to look for things like that. I did this particular implementation in mat lab because mat lab can do this in about five six lines of code. We can make that available in the comments. So if you want to see the mat lab code that does this, it uses the inbuilt cayins function of mat lab. So I didn't have to work too hard to get it to work. And if you have haven't got a mat lab license, octave will also do this using the same code. So you can have a go.