0:00

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.

9:16

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.

12:17

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.