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.