Hello, and welcome back. We just spent a couple of videos talking about edges, and how important it is to compute edges in order to obtain image segmentation. In this video, we are going to present Otsu's method. Otsu, basically looks at the histogram of the image. It looks at the pixel values and looks at the property that in order to maintain segments, we need kind of uniform pixel values. So it's not looking at edges, it's looking at the regions inside the segments that we want to segment out the objects that we want to object out. Let's look at the basic underlying idea behind Otsu what motivates this algorithm, and then we're going to explain how it works. If we look at this image of a finger print. Let, we plot the histogram, and the histogram is what's called bimodal. A lot of pixels values are here, which is basically a lot of the fingerprint. And a lot of pixel values are here, which is basically the background. Very clear, two modes in the histogram. So this is a multi-modal histogram. And the basic idea is that if we threshold here, we can obtain a very simple segmentation, which has separated the fingerprint marks from the background by a simple threshold because we have these bimodal distribution. Otsu, it's going to help us to find basically the threshold in an automatic fashion. Now of course, not all the time images are as nicely distributed as this one. Let us look at this very simple example. Here we have a binary image, so we have still bimodal distribution, but just to the other functions. If we add a little bit of noise, then we're going to still get, so this is Gaussian noise, we're still going to get two modalities. And Otsu it's going to be able to, without any problem, Otsu's method is going to be able to segment this out with no problem, it's going to find the threshold. Now if we add much more noise, the variance is about five times going from here to here. Now the histogram, is much more distributed. We don't have this multi-modality and Otsu is not going to. Otsu's method is going to, not going to be able to find a nice threshold. I haven't explained to you the method yet. But if we apply the method to this image, because of this distribution, this is what we are going to get. We are not going to be able to segment it out. But of course, at this time, fifth week in image processing. We're not really scared of noise. We see a noisy image, we can denoise it. If we denoise, we might be able to get back in this case, we get back to this bimodal distribution and then Otsu's Automatic threshold algorithm is going to be able to segment it back. So it's a very powerful technique as we're going to see. This is a simple image to illustrate the idea. So what is the method trying to do? The method is trying to find a threshold such that the in class variability is very small, so we want to find a threshold here such that the variance on each one of the classes is as small as possible so the class is as compact as possible. And the methods start from the histogram, there is no spacial relationship here. So we lost the special relationship. So regions that have similar pixel values but are in completely different positions in the image. Will kind of be, merged in the histogram and then Otsu's algorithm is going to treat them as the same. So, we're going to see later on how algorithms that take into account this special relationship between the pixels, but this doesn't. The basic idea is very simple. We need to minimize the weighted within class variants. We have seen two classes and we need to minimize the weighted within class variants. So what's that class variants is defined here. T is going to be the threshold. That's the threshold that we are looking for it's going to be if we have a regular image somebody between zero and 255, and this is the value we're trying to minimize for and let me define each one of these variables here, although they are pretty clear. So this is basically the probability of each one of the classes. P is what we get from the histogram. We start from the histogram. We have a probability for every pixel value. So we compute the histogram and we normalize it, so it's a probability, as we have taught, a few weeks before. And then we have, we go from one to T. That's where we put the threshold, or from T plus one to the end of the, the largest pixel value to 55. And then we get the probability for class one, the probability for class two. Then, we simply get the means for class one and for class two, and then we also get the variance for class one, and the variance for class two. And in such a way, we obtain the weighted within class variance, which is here and that's what we wang to minimize. Once again, this measurement, basically, it has the compactness of the classes. If we put the threshold in the wrong place, there's going to be large variance for one of the classes, and we don't want that. So, that's what we need to optimize. That's what Otsu's algorithm does. Now. How to implement this? One way is extremely trivial. You just try. You go for T equals zero you compute this, not hard. And then you compute this value. You do the same thing for one, two, everything up to 255. You remember which one was the lowest. You keep that threshold, and you're done. That by itself would already be very fast. Very efficient, very fast. If you do some algebra, you can actually find out very simple algebra. Just plug in the formulas from the previous slide here, and you can find out that this, which is the total, variance of the image, is basically the sum, of the within class, and the between class variance. Now, this is of course constant, it doesn't depend on the threshold, the image is just one image and the variance of that image is constant. So we want to minimize this, this is constant, this is equivalent to maximizing this. Now the probabilities and the means basically are very, very easy to update as we move the threshold in a very simple recursive formula. Which is you know, add one more, add one more when we are moving the threshold. So basically, this can be computed very efficiently in a recursive fashion as we go from let's say, T plus ten, to eleven, twelve, thirteen. We basically keep adding here and then, very fast, we compute. We once again run from zero to 255 on the Ts. The difference is that, computing this cannot be done explicitly in a recursive fashion, but this can be done explicitly in a recursive fashion where the T1 plus one depends on the T in a very simple formula. It just, you know means and probabilities very simple. You keep adding and you get to the result. So very simple either if you just do direct computation or if you use the recursive computation, you run through all the possible values of T. You pick the one that either minimizes these, or maximizes these, and you're done. So, before I show you some examples inside MATLAB, I want to tell you something. If you have a non-uniform background like in this image, then Otsu is not going to help. Otsu's algorithm is not going to help because you may have a binary distribution. Like we draw here, but then because of the bias of the background, this will not be basic binary bimodal type of distribution. So I just explained you how to do Otsu's algorithm in the whole image. You can also do it in blocks of the image, to try to get rid of the problem with basically a non-uniform background. And then you're going to get a different threshold for every single one of the region. Or if you want, you can actually do what's called a moving window. You can just do it here. Sorry, let me just get the pen. You do it here, then you do it in a narrow window like this, and then you basically do it in a narrow window like this. And then you can, for example if you want, you can average the thresholds that you get in the overlapping windows. Or you can create a function of the thresholds. So once again, as in many of the algorithms that I have explained, there's the underlying concept, which is to separate the images to minimize that within variance that we just explained. Now that concept you can implement in many different fashions in the whole image in blocks, overlapping blocks, non-overlapping blocks. You know, there, there's a lot of art and basically depending on the application, what to apply. Once you do it, for example, as here. If you do it globally, let me just erase the annotation so it's easier. If you do Otsu in the whole image, this is what you're going to get, this is very dark. So you got confused with the letters in the distribution and in the optimization and then it basically the threshold put it together with the letters and the writing has been it's basically gone. Now if you do it with a moving window, you get this beautiful resolve back. Once again extremely, extremely simple all of what we are doing is to segment out the letters here we're computing thresholds we move a window we just move regions. We move it and we are completing thresholds with the formulas that I just explained to you. Now let's see an application of this running inside MATLAB. In order to illustrate Otsu's method in side MATLAB the first thing we have to do always is to load the image. So here we have, we are loading the image, this is the separation. The next operation is what actually does the complication of the optimal threshold. The Otsu's algorithm that we just described. That's this operation in MATLAB, that it gives us the level, it gives us the value of the optimal threshold. And then we are basically going to threshold the image following that value. So, let's see the results of all these operations. We have link here, and let me just move the window so we can observe them better. This is the image, this is the histogram. Now you're an expert in Otsu's method. So the moment you see this histogram, you say wow, that's great. I can do a pretty decent job if I just compute that optimal threshold that should be around here. And that's a result of threshold in the image, with that optimal threshold. Looks pretty nice, remember no special information. So for example, you might be able to see a few pixels here that were included as part of the background. Of course, without any type of smoothing, you will get read and get a very, very nice white object inside here. Here things are a bit different and that's because as you see this part of the coin is relatively dark, almost as dark as the background, or basically as dark as the background. And that's why it was included as part of the background. Situation might have been different if we do Otsu's method in a local window or some other variant of Otsu's method. But the idea is very clear for most of the image, wish a, which, with a simple threshold we get a very nice segmentation. And that threshold we don't need to specify by hand, Otsu's method automatically computes for us. So let's go back to the slides and we'll finish this video, thank you. In this video we have seen another classical standard, very simple and very powerful image segmentation algorithm. Unfortunately, not all the images are easy enough for Otsu or segment or for the half transform to segment and we're going to need more advanced techniques to be able to handle them. And that's going to be the topic of the future videos in this week. I'm looking forward to seeing you then and to having a lot of fun and I hope that you are having to. Thank you.
