Digital image processing: p040- Otsus Segmentation with Demo

hello and welcome back which is spend 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 Otto's method also basically looks at the histogram of the image it looks at the pixel values and looks at the property that in order to obtain 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 segment out let's look at the basic underlying idea behind also what motivates this algorithm and then we're going to explain how it works if we look at this image of a fingerprint let we plot the Instagram and the Instagram is what's called by model 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 multimodal histogram and the basic idea is that if we threshold here we can obtain a very simple segmentation we just separate the fingerprint marks from the background by a simple threshold because we have this bimodal distribution also is 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 two Delta functions if we add a little bit of noise then we're going to still get so this is Gaussian noise we are still going to get two modalities and also is going to be able to without any problem otto's method is going to be able to segment this out with no problem is going to find the threshold now if we had much more noise the variance is about five times gone from here to here now the histogram is much more distributed we don't have this multi-modality also is not going to authors method is gonna 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 are not really scared of noise we see a nice image we can be noise it if we'd annoys we might be able to get back in this case we get back to this bimodal distribution and then also 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 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 thresher 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 method starts from the Instagram there is no special 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 merge in the Instagram and then also the algorithm is going to treat them as the same so we're going to see later on other algorithms that take into account the spatial relationship between the pixels that this doesn't the basic idea is very simple we need to minimize the weighted within class variance we assume two classes and we need to minimize the weighting within class variance so what's that class variance is defined here t is going to be the Thresher that's the Thresher we are looking for it's going to be if we have a regular image it's going to some value between 0 and 255 and this is the value we are 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 Instagram 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 1 to T that's what we put the threshold or front t plus 1 to the end of the the largest pixel value 255 and then we get the probability for class 1 the probability for class 2 then we simply get the means for class 1 and 4 plus 2 and then we also get the variance for class 1 and the variance for class 2 and in such a way we obtain the weighted within class variance which is here and that's what we want to minimize once again this measurement basic give us 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 Otto's algorithm does now how to implement this one way is extremely trivial you just try you go for T equals 0 you compute this not hard and then you compute this value you do the same for 1 to everything up to 255 you remember which one was the slope their lowest you keep that Thresher and you're done that by itself will 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 these which is the total variance of the image is basically the sum of the width in class and between class variants 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 probability 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 as one more add one more when we are moving the threshold so basically these can be computed very efficiently in a recursive fashion as we go from let's say T equal 10 to 11 12 13 with AC keep adding here and then very fast we compute we once again run from 0 to 255 on the t's the difference is that computing these cannot be done explicitly in a recursive fashion that these can be done explicitly in a recursive fashion where the T plus 1 depends on the T in a very simple formula which as you know means and probabilities very simple you keep you keep adding and you get to the result so very simple either if you just the 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 also is not going to help also cyber rhythm is not going to help because you might have a binary distribution we draw here but then because of the bias of the background this will not be a basic binary by model type of distribution so I just explain you how to do Otto's algorithm in the Hall limit 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 threshers that you get in the overlapping windows or you can create a function of the threshold so once again as in many of the other algorithms that I have explained there's the underlying concept which is to separate the images to minimize that with invariance 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'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 also in the whole image this is when you're going to get this is very dark so I got confused with the letters in the distribution and in the optimization and then basically the threshold put it together with the letters and the writing has B it's basically gone now if you do it with a moving window you get this beautiful result back once you can extremely extremely simple all what we are doing is to cement out the letters here we are completing thresholds we move a window which is smooth 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 these running inside market in order to illustrate Otto's method inside 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 this operation the next operation is what actually does the computation of the optimal threshold the otto's algorithm that we just described that this operation in MATLAB that it gives us the level gives us the value of the optimal threshold and then we are basically going to Thresh all the image following that value so let's see the results of all these operations we have been here and let me just move the windows so we can observe them better this is the image this is the Instagram now your expert in artists method so the moment you see the sister can you say wow that's great I can do a pretty decent job if I just complete that optimal Thresher that should be around here and that's the 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 rid and will 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 direct as the background and that's why it was included as part of the background situation might have been different if we do all Sue's method in a lot a window or some other variant of otto's method but the idea is very clear for most of the image we said which with a simple threshold we get a very nice segmentation and that threshold we don't need to specify by hand otto's method automatically computed for us so let's go back to the slide and we 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 also to 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 in them and having a lot of fun and I hope that you are having - thank you

Channel: Alan Saberi

Views: 23,687

Rating: 4.939394 out of 5

Keywords: Photography, Alireza Saberi, Ali Saberi, AlirSaberi, Alan Sberi, Digital image processing, DIP

Id: GuqBJ4W7_58

Length: 14min 26sec (866 seconds)

Published: Sat Mar 16 2013