DIP Lecture 12b: Snakes, active contours, and level sets

okay so today's lecture is kind of continuing on the concept of image segmentation okay and the specific thing we're talking about today is called snakes also known as active contours at the end we'll talk about briefly what are called level sets and so the philosophy behind this material is that you know everything we talked about so far in terms of segmentation has really been at the pixel by pixel level right we threshold and we get a set of pixels right or we do you know graph cut we get a set of pixels right but as humans you know our natural inclination is more about kind of like you know if I told you to isolate something an image you probably wouldn't click on pixel by pixel you'd probably draw like a freehand contour around the object right you think about things in terms of shapes right and so that's the philosophy today is instead of talking about like pixel level segmentation we're going to talk about kind of curve level segmentation and the curve is going to be the key concept that we kind of talked about today and so you know the idea is to segment using kind of curves not pixels and so to whet your appetite let's just kind of do an example to show where we're going right so again I'm going to use the same app that I used before in the last lecture this image segment or in MATLAB which I think is in the most recent versions of MATLAB so gotta load up an image and let's suppose that I'm gonna use this guy and actually before I do this I guess maybe because this is a color image maybe I should RGB degrade this first actually so I feel like the option that I want is not there okay so let's go back to my guy here so this image signature I can oops just happen here I can load stuff from the workspace instead of loading it from a file which is kind of nice okay actually this looks exactly the same maybe I could have done it before sorry okay so what I'm gonna do is first I'm gonna draw freehand to say okay you know this is kind of like what I want to outline my hand right all right now where's my my segment er here now here we go I just had to open the window a little more okay so thumb goes like what's called active contours and I'm just going to you know don't worry about the magic numbers here for the moment I'm just gonna see what happens let's just set this to be 300 and I'm gonna evolve what you're gonna see is that this kind of freehand curve I drew is shrinking inwards towards the boundaries of my hand and eventually as it goes on and on it's going to kind of snap around the contours kind of like a rubber band except the rubber band is going inside the nooks and crannies so it's not just like a convex shape it's actually going all the way inside right so the question is how does this work right how is this contour drawn to the edges of my hand and how is it finished doing this that's what we're going to talk about today but I just wanted to give you a little bit of a flavor of what we're doing before I go into the math of how it works right the math is a little more complicated that's we're going to talk about most of the lecture you can see that here it's an iterative process and eventually I guess I don't know if I had enough iterations it's gonna crawl all the way inside my fingers and do a good job it has to take so this is where it stops if I got maybe 50 more iterations it would have gone that way right so this is called the snake because it basically is like this kind of closed contour that slithers inwards towards the stuff that it wants okay so this is where we're going but what does this be and how does it get there right so if I go back to my notes kind of the idea is we want a segmentation curve that you know the most important thing is number one it conforms to image edges but at the same time I also don't want this snake to be too you know jaggedy too pixelated right so the other kind of thing is that we want you know something that's kind of a smoothly varying curve versus I guess I'd say lots of jagged nooks and crannies to use a technical term right so kind of like the idea is that there's this tension between wanting to really go tightly around the edges but also not wanting the curve to be like you know super jaggedy pixelated right I want to have this kind of like nice rubber banding thing and of course there's a trade-off between these two things as I'll talk about in lecture here and so the idea which you kind of saw in the MATLAB demo is that you know to kind of draw this in a very sketchy way so here's my hand so first the user draws should be closest up the user draws some sort of an initial contour and then iteration by iteration the snake kind of you know conforms to the object of interest until eventually it snaps kind of tightly around the object so this is definitely a iterative process and the idea is that either I set the number of iterations that I'm willing to go this far or I basically keep the snake going until it doesn't move anymore okay so basically we need to kind of specify to make this work what do we consider to be a good curve right we need a cost function that tells us how good a curve is okay and so first of all we have to talk about how do we describe a curve okay so first if I talk about what are called snakes okay so snakes this this kind of came into vogue maybe in the late 80s early 90s again probably before many of you were born but still at the time it was like a pretty exciting idea as a young child that was anyway so basically a snake are basically what I call a parametric representation of a curve so for example what I mean by that is that I have a function of X and a function of Y and a parameter s that goes between zero and one continuously right and the idea is that as we change s smoothly I trace out a closed contour in the plane okay so for example let's look at how we would make a circle right so for example I could say something like the x coordinate and the y coordinate are our cosine 2 pi s our sine 2 pi s s going from 0 to 1 if I think about what that traces out so an S equals 0 I'm at our x cosine 0 is 1 so that's our and our sine 0 is 0 right this is like s equals 0 now as I go around the circle right so for example s equals 1/4 says that I met PI over 2 right so this is going to be s equals 1/4 s equals 1/2 s equals 3/4 and by the time I get back to s equals 1 I'm back over here and so the curve that I trace out is this nice circle pretty circular and so this is a lot cleaner a representation then if I had to do this in like plot Y as a function of X right so this is kind of a nicer way to think about things versus something like you know if I want to represent this like a Cartesian thing I'd have to do it like this and I have two functions I have to piece together to make the whole shape right so this is like a nice way of doing things and you could imagine that this also allows me to kind of trace out an arbitrary closed curve that might otherwise be a huge pain to represent with Cartesian coordinates right so you could imagine a curve that I could kind of go like this and as s is changing I can kind of go around and around as long as it comes back to the place it started you know that's something that would be a you know freak show to try to represent like Y as a function of X and have all these pieces right so with s just ranging from 0 to 1 I trace out my curve ok so this is the way we're gonna represent our closed curves today ok and I am gonna assume that everything that we're going to do is a closed contour it is possible to have kind of like an open contour like an arc that is conforming to the edge of some object but conventionally when we think about the snake stuff we think about this as a closed group okay so any questions about the setup so far ok so now also the other going to say is that really we're going to assume that everything here is in continuous time and continuous space right so as I change s I am moving this contour around I'm also going to assume that the x and y values are continuous values right so forget about the pixel grid for the moment I'm going to assume everything is nice and continuous right and I will talk a little bit briefly about what happens when you have pixels and so on but for the moment it's much much easier to do a theory when everything is just like you know continuous time ok so what I want to do is I wanted to find a what's called an energy for this curve right and then I'm going to try to evolve the curve drive the curve to have minimum energy ok and this energy intuitively should reflect how good is the snake for a given image right so let's talk about this so now we want to define an energy function so let's call that e of C so C is my curve he is energy that matches our intuition about what a good curve is and then what's going to happen is that the curve will iteratively evolve and every step is going to reduce and hopefully minimize this energy function so again kind of like what you might imagine that a well so suppose I've got a convex object it's kind of like what you might imagine that a rubber band would do if I kind of stretched it around the object and I let it go and you saw through our band snap to the contour it's like that except it takes a lot more time than the program actually would right so what I'm going to do is I am going to decompose this energy in two parts okay I'm going to say the energy function has what's called an internal part and an external part so the internal part is something that only depends on the shape right so this depends only on the shape of the curve so the idea is that independent of the image just how nice is this curve right and this is going to encapsulate our idea that cur should not be too squiggly too Wiggly right so this is kind of saying how good is a curve in general okay and then I balance that out with a function that depends on the image intensities for example the edges in the image right so here I'm trading off how good is the curve on its own and how well does it fit with the image edges and as you can imagine there's kind of a you know a parameter that I can use to say which one do I think is more important okay okay so now I'm going to talk about what makes a kind of a good curve from each of these perspectives okay so let's talk about the internal one first the one that just depends on the shape okay so all things being equal so let's talk about e internal so all things being equal I kind of want a shape that is more like this than a shape that is like this right so something that is nicely smooth and varying and doesn't have lots of ins and outs okay and so if you think about this like a rubber band again the idea is that we want shapes that kind of minimize the energy of the curve like how much energy is required to keep the curve in that state right so again think about you know your rubber band is just sitting on your desk it takes zero energy to just stay there and has like a nice round shape now you try to squeeze it into some sort of weirdo shape it's gonna be like super stretched and there's going to be a lot of tension and it takes a lot of energy to maintain that tension right this is like the super hand-wavy way of thinking about it right so you know I think about you know relaxed shapes have lower energy and you know bendy twisty shapes have more energy so I want to kind of make sure that all things being equal I have low energy okay so those of you that are more physics inclined than I am can think about this in terms of actual tension right actual energy right I'm not a physics guy but basically it Maps exactly on to the concept of how much energy there is inside a physical object like imagine that you've got like a metal hoop that's very flexible that you could you know suppose you've got like you know pegs on a board you've got this bendy metal hoop and you're either you could thread the metal hoop around the pegs that would like have this kind of internal tension or you just put on the table that would have a very low energy right so again you could compute all that stuff for a physics perspective but here we're kind of thinking about for like a math perspective so we kind of you know like the idea actually since this is energy I kind of want to get the sense that this should have lower energy than that right and so how do i encapsulate this mathematically okay so this kind of idea let's just say this is encapsulated by an energy like so let me write this down first and then I'll talk about what each of the terms means that's integral okay so one of these terms mean right so these both again have like kind of physics based interpretations but my hand-wavy interpretation is that you know this term here kind of refers to how stretchy the curve is right how you know how much how much tension that curve is under and so this is kind of related to if you're a physicist the elastic energy of the curve so let's just say here that you know a low value of the derivative means this is not too stretchy basically this kind of keeps points on the curve together as a function of s right what that means is that as I travel around the curve going from like s equals zero s equals 0.05 of 0.1 and so on I don't want the distribution of those points around the curve to be too non-uniform right in some sense ideally I kind of want to be taking an equal step in arc length of the curve for every little increment to test that I go so I don't want the I don't want the points on the curve to be bunched up like you know this right as I take uniform steps in s I don't want to have to be like having a bunch of points that are close together and then a bunch of points that are far apart that kind of in means that the curve is it kind of means as I move my dot along the curve that it's traveling at perhaps wildly different speeds right and we know that derivative is gonna relate to the speed right so that's the very hand wavy way of thinking about this this part is basically saying that if I want a low double derivative what that means is that the curve is not too bendy this is really technical meaning that having a term like this basically keeps points on the curve from kind of oscillating and that's going to kind of prevent me from being in this state right so the double derivative of the curve is kind of related to basically the curvature right meaning you know at every point instantaneously I can think about what is the kind of so again temperature is a concept that you probably have not come across in calculus but if you took like a differential geometry of course you do about curvature basically the idea is like you know what is the radius of the circle that sits adjacent to the curve right and so that could be negative or positive depending whether I'm inside or outside the curve you can imagine that you know in a curve like this as I roll this little circle around the curve it's changing radius to match the nooks and crannies of my shape right whereas here I can imagine that I have basically very little change as I roll this circle around the interior the curve because there's not a lot of little you know inlets and islands for this curve to have to negotiate right so this basically is our intuition that I don't want to have lots of squiggles in my curve right so I think that's good enough for this intuition right so basically this says not too stretchy this says not too bendy okay and you know both of these terms are important because you know just the shape by itself doesn't necessarily tell me for example where the point is along the curve I could have different parameterizations of the curve that you know trace out the same path but go along that path of different speeds right so I kind of have to know not only what is the actual shape that I get which is related to the curvature but also I also have to know how fast the point is going around you know as a function of s okay all right so all this is just to say this my intuition for well-behaved curves slowly pause and ask any questions about this okay that's the hard part the easier part is what makes the curve conform what question no no all right you're good okay slide bar okay so now the next ocean is what makes the curve good externally right so now we need to kind of make the curve fit with image edges okay well okay I guess I gave away the show right so what makes the curve good for segmenting an image well I have this notion that the final curve should basically lie right on top of strong edges in the image right so in some sense here's an obvious choice for that want to write this down first let's talk about why this is good so now the image finally comes into play and when you write this a little bit more explicitly so here what I've got is I've got my image which I'm going to assume is grayscale and then at every point along the curve s that corresponds to a point X Y in the plane and then I evaluate the image in tents all right I felt like the image gradient at that point and I integrate around the curve adding up all those grades right so let me be a little more explicit to say this is like the integral let's write down what exactly this this number is this would be saying I take the X derivative at the point X of s Y of s and then I guess I square that and then so the base is like the gradient magnitude at each point on the curve and then I integrate that number as I go around the curve and I have a negative here right so let's think of what this means so the intuition here is that I want this energy to be really low when I've got edges right so let's suppose that there's no edge at a given point right that means that the gradient is zero we know that from before and that means that at that point this number inside let's call this you know ffs this number will be zero right so when I get you know when I'm in the middle of some flat region nothing's happening right if I have a big edge then my gradient magnitude is going to be big and then this number here is gonna be some you know big negative number which means that that edge is gonna make the cost function overall have lower energy right so again I was a little bit well I didn't lie to you but basically you know they said this energy can be negative right and here you can see that it's got to be negative because either it's zero when nothing is happening or when I have edges it just gets pulled more and more negative right so overall if I take the internal energy plus the external energy I could get some negative numbers so it's okay that's no big deal but just to know that the energy is not like non negative it's actually going quite negative okay but this is the kind of intuition is that I want the snake to be attracted to edges okay okay so pause and ask any questions about this does it make sense alright so as we're gonna see in just a couple minutes there are better ways of thinking about this okay so I'm gonna show that actually this is kind of like while a good idea it doesn't always work so well in practice we'll talk about why that is but let me talk now about okay so let's come back to you know my cost function right my cost function is basically saying okay I told you something about this so I'll tell you what something about that now I need to minimize this right that's the whole point is that every step I want to make that number smaller so now the next question is so now how to minimize this whoops well this is something that is probably no offense beyond most of you at the moment right because this requires a little bit of what's called variational calculus right so you guys are used to kind of like measuring you know you've got differentiate a function set equals zero that's the way I minimize with respect to that parameter right that's how I find the X minimum that does something right so that there's no sweat and you can do that in calculus you do that multiple dimensions but this is a little bit different this is like minimizing a function of a whole curve all at once right so that's something that probably you've never done before right and if you look in the book in Gonzalez and woods there's a whole chapter that you know I'd say that 50 pages that chapter taken up with the details of how exactly you do this minimization right so important stuff good stuff but this is like a one lecture overview I'm not going to go into the details this what I will say is some high points right so let's just say first of all it requires what's called variational calculus so if you were a math major you might know something about this but ultimately the other thing is that obviously to make this work for the real world with digital images we have to kind of get out of the mathy world and come down to the pixelated world right so let me just say a few words about how this works in practice right so in practice for digital images we basically solve the problem by creating a curve C of two parameters s Mt we're SMT are both discreet so the S part is basically the amount that I'm traveling along the curve right so for example let's suppose I've got my initial curve this is what my my human drew so maybe this is you know the curve at s equals zero and this is the curve at whoops see sorry this is the curve at s equals one and this is the curve at s equals two dot dot dot so all I'm doing basically is I'm approximating the curve by a set of points around the contour and let's say I've got you know K minus 1 points okay right so these are now going to be an ordered set of points X I Y I in the plane okay which could also be you know actual pixel values although I think that even in implementations you're gonna leave these to be continuous numbers right but that is that you know instead of having this curve I'm instead approximating the curve by a set of connect-the-dots line segments right and obviously the more you know higher K is the you know more smooth and fluid that curve can be right so if K is like 10 you're stuck with basically a 10 sided polygon trying to crunch around your image if K is like 100 maybe you don't even notice that there's little line segments connecting the dots right so we have to make the problem discrete in that way okay and then the T part is basically this temporal evolution of the curve remember in the very first demo you saw that I had a elastic shape that was step by step click by click matching the shape of my hand right so here basically then we step this curve as a function of you know say I've got this then I step by curve to the next time step by and this is this is very hand wavy taking a step along the gradient of e right something like you know how do I do numerical differentiation right so any of you have taken like kind of an optimization course and you're talking about how do you actually you know how does MATLAB actually minimize a function well I look at the point that I'm at I look at where the gradient is the gradient points in the direction of the greatest amount of change and I take a little step along the gradient I look where I am I take other stuff that's called gradient descent right and so that's like the standard way that you do numerical optimization and the same idea here right except instead of taking a step in a you know you know in one dimension I'm taking a step in here you know one way I think about this is that now I've kind of parameterize the problem by K to D locations right so there's actually kind of like you can imagine a big 2 K by 1 vector is defining the curve shape at every point in time and that makes the life a little bit easier you can imagine that now I'm going to take a derivative in this 2 K dimensional world and that's actually the way that it happens under the hood but I'm not going to talk about this too much let me just say this directly which is that you know in practice this results in a kind of like 2 K by 2 K linear system solved at each step at each iteration and you know this linear system this big block of numbers has to do with a bunch of X&Y derivatives in multiple directions relative points and you know as you can imagine I've already got in the internal force I've already got like first and second derivatives just to measure the energy function if I go take a derivative of that then I'm actually gonna have like third and fourth derivatives it gets to be like very messy at least you have to do some bookkeeping to keep track of what the actual values are but you know if you're interested the details are in the book and so you know this is just basically a bunch of finite differences let's just say that and then the result is that the curve will kind of you know inch along until the points around the boundary stop changing and let me just say that if you're gonna do this yourself there is a lot of bookkeeping to do which by which I mean for example lots of bookkeeping behind the scenes just to give you one example kind of what I mean by that is that you know suppose that I have a curve at time t minus 1 and as a function of s I find that my points around this curve are kind of non-uniform right so maybe what I want to do before going to the next step is to actually maybe better if I just use a different color here I can find my pencil so maybe will be better would be to say okay before I go on to the next iteration I'm going to resample these points to be equally spaced along the perimeter right so that my curve is ultimately more well-behaved so you can imagine I could you know do things like I could change the spacing of the points I could even make me change on the fly the number of points like if I discover that you know I could add some points in regions that I found had high curvature to kind of force the curve to go a little bit further in so there's lots of stuff that happens under the hood to make a good curve evolution algorithm work right when you're living in the continuous time world you have to worry about any of this stuff right but when you're living in MATLAB world you have to worry about this kind of thing and so I will put this under the category of kind of important but tedious ok so let's take a look at how this works ok so now I have to remember what my commands are here let's see here do I have an explorer window open no not you what was the yeah I want a file explorer file explorer no go away I closed the wrong one good good stuff alright tries again ok so I guess I have a function call or a thing called basic snake so let's try this and this is something that I found on the MATLAB what do you call it so let's give credit where credit is due so if I search for MATLAB snake no not snake game right so here this is the function that I'm just showing you here MATLAB central file exchange ok so just to give credit and so let's do this so this is going to be like very simple outline of something so here all I'm going to do is I'm going to draw some initial points around the boundary and then I'm going to start my snake evolving and it come on red point come on and eventually this thing will snap around the circle like so right and took me it's still kind of adjusting minorly it took me 1 and 3 3 iterations to do that and you can see there's a whole bunch of parameters here like you know gradient weight which is kind of like the yell it's just the curvature weight which is kind of like I guess I have something that see I'm sorry continuity weight curvature weight gradient weight are like the three weights on the terms of the snake right there are two internal terms and one external term has two at the edge and by tuning those numbers I could probably get you know more attention paid to the edges or less attention paid to the edges right and there's a bunch of other parameters so yeah it looks great right so but this of course is like a super simple example right but well okay let's also try what would happen if I started from inside the snake or inside circle oh not so good my thing disappears right so that's not so great what happens if I were to do something like this where I'm a little bit off from oh here so here you know I'm kind of doing okay and actually this is a okay I guess it never really get this guy to slide over to the edge of the circle right and so and certainly if I started like you know entirely outside of the shape then it never finds it right so basic idea is sound right so let's lest we forget how will it work the first time let's just look at this you know this was like the best case right so you know it does work right but it doesn't work all the time right and of course we want something that's gonna be more robust and of course in real digital image processing the shapes that we want to segment are a lot more complicated than this right definitely not black and white so what's going wrong here okay and actually before we start let's just try okay what would we do with a real image so let's go to let's see where did I put that okay maybe I have to close out of here dress again how about this one that I showed earlier so let's draw some points around this guy mmm that's so great right this is where it ends up so again and this shouldn't be too much of a problem right because I got such strong edges between my hand and the black book that I mean why is it having such a problem so problem is that the image gradient part is not strong enough to pull the snake in right so if I think about it if I go back to my looking back to my notes right the external part here is basically just saying you know if I am right on top of the really strong edge then life is good right but you know what's the problem the problem is that suppose that I kind of have a situation like this which is kind of like what I had before so I've got a say a dark shape on a light background and I initialize my points like this like I kind of did in that example well what's happening right gradient here is great right everything is going to basically be kind of pulling you know things into the boundary right when I'm right near the edge but out here in the middle of nowhere the grained is zero right I'm in a flat region and there's zero gradient and so the snake is not inclined to do anything right at most what you saw in that example was that the snake is kind of forced to contract right so the natural inclination in the absence of any image edges is to minimize the internal energy right so the internal energy is basically saying hey you know I want you to make this as small as possible there oh if there are no gradients anywhere that all I'm doing is minimizing this and the effect of that is going to be basically pulling the nodes closer and closer together until as you saw in some cases the curve just vanishes right then everything is great everything is so in place that all these ruins are zero and everything is good right so that kind of thing will force the snake to collapse right and you saw that in the example with the circle so the problem with the basic snake which comes from the way that we defined this external energy is that you know the contour never kind of sees strong edges that are far away so that's not good and actually let us say there are multiple problems the other problem that you can imagine is that you know if I have any noise the image at all that will create you know many kind of small gradients and then the snake kind of gets hung up on those right so we need to find a way to fix these problems okay one idea that you that you could do which is something that does work a little bit is you can imagine that I could blur the image and then try running the snake right and hopefully that would do a better job and so you need your time not going to do that you can do the experiment yourself but you can show that life works a little bit better if I blur the image what that means is that instead of having hard gradients only in one place I have kind of like you know so say this is my hard edge if I make this softer that means that I'm going to kind of spread out the gradients in a wider band around that hard edge and that depends on for example the variants of like a Gaussian blur that I would use and then I can attract the snake a little bit more further away than it was before right but it's still not going to be good enough in a case like this where the initial boundary is far away and I need to kind of pull in from a distance okay so the solution does which is pretty slick is what's called gradient vector flow okay so the solution to this problem or yeah it doesn't fully solve it but this mitigates the problem let's just say it's called gradient vector flow sometimes you see that called gvf okay so the idea here is that instead of using exactly the image gradient we instead make kind of a new gradient field that is nonzero everywhere so even in flat regions the image it's going to be pulling the snake inwards two gradients that are strong further inwards right so the idea is that instead of using exactly the image gradient we create a new vector field over the image plane so let's call it V of XY so there's an X component and there's a Y component and let's call E the edge map of the image which is kind of like you know the magnitude of the gradient okay so now what I want to do is I wanted to find this new V that is equal to gradient stuff where there is a gradient and outside the gradient is kind of pulling inwards right so let me start a new piece paper so V is defined to minimize now I got double integral all right so let me write this down first and then I will explain what it means here it is acai from the audience it's not that bad gradients okay so we were like getting it to write this down so let's unpack this for a second right this basically is saying that here this is basically the magnitude of the edge map right how much gradient action is there okay and this is basically saying how similar is the thing that I'm creating to the thing that I want okay so what this is saying is that when I'm in a really edgy region then the V that I create just kind of agrees with what's going on with the edges right so the high priority is when this is big then this has to be small which means I have to push you know V to be similar to the E in the right you know in the places where there are edges this here is basically saying okay well suppose that this number is small then this term takes over this is what I would say is the smoothness of V so this is like saying that okay suppose this part doesn't matter then this part is basically trying to make the V that I create very nice and smoothly right whereas if I just looked at the edge map there would be like this kind of sharp step between where I am locally and then far far away I step down to zero right so what I want to do is I want to kind of smooth that transition out so that even far away from the edge I have like this nice kind of smooth transition towards the edge and I'll show you an example this that will make this a little bit more clear and this here is kind of like a tuning parameter that kind of trades off how smooth the vector field is versus how close it is to the edges so let me just kind of again recap what I just said the intuition is that if this is big that means that the gradient is large and then the V is gonna follow this edge gradient faithfully if this is small then the gradient is small and then V is just going to kind of follows it's going to kind of follow along to be as smooth as possible and then this mu trades off kind of how smooth I am versus how faithful I am just like in real life okay so this works a lot better than the previous case since now the strong image edges are going to kind of diffuse out to the to the rest of the image so let me just show an example of that to make it clear what we're talking about here so I'm going to go back to my MATLAB and again if you look in file exchange for gradient vector floor gvf you're gonna find a package that was written actually by one of our RPI alumni chuan Wang and so let me just show you what we get here so so I just kind of wrote a little wrapper around these functions I think that I just called it my snake I guess I commented a bunch of stuff out but let's see here I thought I had any function yes snake hand okay so it's thinking oh this is not what I want sorry well let's say let's see what happens here this is still not quite what I want okay this this is not what I want actually this is getting better but you can see that something is wrong this is someone else's implementation of the gradient vector flow and I can see this isn't working actually because if i zoom in it has a little bit of what I want in the sense that you can see that now there are gradient vectors everywhere but for some reasons implementation is not good because the the zero points of this thing are like not along the boundaries of my hand okay so forget I showed you this and let me back let me stop this crazy thing so what was my thing let's try I have a function called Pangea okay better okay so what do we have now this is the same thing I had before and if i zoom in on my hand I can see that actually you know there are little vectors that are pushing the gradient from these places that would normally not basically 0 gradient towards the edge right so I've kind of diffused the influence of this edge outwards and so you can see that this is going to pull the curve basically the little arrow says which way is the curve going to go if it's sitting here okay and I can try to make this a little bit more clear I believe that I made a version of this that makes the arrows little bit bigger right so here you can I really see that I get a little bit confusing but if we zoom in like there are big arrow is pointing from the outside in and then big arrow is pointing from the inside out that's basically gonna say that I'm gonna push my curve inwards or outwards depending on where things are at and so now let's try seeing how this works so this guy is built into MATLAB in this image segment or so if you go to image segment or and I load up this image so let's again draw my initial curve whoops I guess in MATLAB I have to hold down the button okay so now I'm going to go into active contours say edge based and evolve this no this is way too late let's see if this works okay things are shrinking and I can see that even though the curves started far away from the edges of my hand it is slowly being pulled in to my fingers right and here I'm about halfway through so it has more to go but when it gets to the edges of my fingers it's going to pull in and stop right now here you can see actually again this curve is kind of dumb right doesn't know that it's looking for my hand for example and so here you can see on my sleeve it's caught by the edges that are on little patterns on my sleeve right so if it encounters a strong edge on the way to you know what we would consider to be the hand it's going to get caught up right so certainly if this hand was on a you know checkerboard tablecloth then things would would go wrong and in fact I'm not sure whether this will fail bullets just see I had a different version of this image that I took on like a woodgrain so a couple things that you should know about this so one thing is that there is a you know kind of a time penalty for bigger images right oh okay so let's try what happens here let's try again it's going to complain because this is grayscale so let me just try hand again there's no reason why this stuff wouldn't work on color images is just the implementation doesn't always accept it oh forgot to M read sorry okay so this image is actually pretty big 12 24 by 16 32 and so I'm actually gonna resize this image to be quite a bit smaller just for the purposes of demonstration now it's 306 by 408 so now let's see if I can run this example here no not you image segment or I guess I still have one of these open alright so let's try loading oops I guess I'd this is my workspace yes alright so I have this woodgrain image and I'm curious to know how well this will work I don't really know but I assume that things are not going to work so well active contours edgy based all right see what happens see here I feel like things are you know not like totally going in the right direction like for example things that are I think that what's going to happen is that you know here since the wood grain at the table is kind of like parallel or I'm sorry perpendicular to the contour it's okay the contours getting sucked in along those relatively constant intensity lines but here I think we're gonna have problems where basically since there are strong edges in the table the you know great vector flow is gonna just get caught on those edges and it's gonna have a hard time just jumping over the hump right so I think even if we were to let this go for longer and longer we would have you know not such great success okay so you know the gradient vector flow is not like a silver bullet but it works a lot better than just like regular edges okay alright so there are two more things that I talked about before I do that let me just stop and ask if there any questions or comments oh okay question number one [Music] so method seems slow and that's true so I don't know what the complexity is off the top my head it certainly depends on the number of points that I have and also it depends on you know whenever you do a numerical optimization there's this kind of notion of like step size right so when I take a step along the gradient how big should that step be and so I think that what you can see here is that you know first of all the number of points around the contour is probably pretty high because this is a pretty fine detailed contour so it's solving a relatively large system and number two its chewing in only a very few pixels if that at every iteration right so it's gonna take me a long time to get to the answers so somewhat depends on number of points so it depends on number of steps right or size of the step but is slow I mean it's not gonna be like a snap your fingers and think how it goes so something like graph cuts for example is much faster you saw that I was able to do graph cuts that interactive rates last lecture right so this is definitely anything where you have kind of like this discretization of a continuous time like partial differential equation is inevitably gonna be a little bit slower for sure and if you wanted to I mean I'm not even sure whether or not like if I look in the MATLAB help I'm kind of wondering I think it's called active contour I'm wondering whether there's even like any sort of a graphical like if you have a GPU I'll go any faster no I don't think so so yeah I mean yes it can be slow okay all right so how would you dis realize the contour right so that's a little tricky right so I mean definitely most active counter stuff assumes that you get that initial contour from somewhere right now you could be very crude about it you could just say okay I'm gonna draw a you know so one one example right okay threshold the image very aggressively I'm gonna get the centroid of those points so say I'm looking for a bright object on dark background I could find the center of that bright object and I could draw a circle whose radius is the width of that threshold of thing times some factor and then I let that circle contract until it snaps around the object right so you could do something sending automated like that but a lot of times when people talk about snakes the contours kind of the initial contour is assumed to come from somewhere right and it may not necessarily be automatic could be human generated oh yeah that's tricky right to figure out what the I mean obviously if you want to put this into a fully automated system you don't have some person who's you know clicking on stuff right you could imagine that for example say so I did a lot of work with medical imaging long ago and so there are rooms full of you know interns and radiologists who are basically you know looking at CT scans and having to very precisely outline things right so you can imagine that'd be much easier on them if all they had to do was kind of like drag a bounding box around the object and then have this thing snap to it and drag another bounding box as opposed to having to click manually around the contour right so it's not that unreasonable to think that there's some human in the loop when you're doing this that's a good question yes could you go inside the object and expand out the answer is yes and that's the name it's called the balloon force and so I'm not gonna talk about that today but yes there are ways to do that and I guess I was a little bit breezy about again all the details right so for example when I first showed you that circle example the black circle on the white Bragg I tried a bunch of stuff right what if it's totally outside the curve what if it's totally inside the curve whether it's overlapping the curve in those cases you need something that will pull from inside as well as out and kind of force the snake to blow up so I don't wanna do that right now because I'm not sure whether it will work on a my examples but yes there are considerations for making sure the snake expands outwards places where it starts inside the contour yeah other questions are coming okay so there is kind of one more cool idea that I want to introduce to you that makes life a little bit easier so let's recall the first example that I did which was I had the choice here edge based or region based right so let's try this region based thing whatever this region based thing is it seems like it's doing better and faster right so that's good although in this case it seems like it's also kind of chewing into my hand which is not great but let's observe a couple things right first of all this is you know regardless of how good the segmentation is it's also like picking up this other stuff here right like picking up the little figures on my sleeve that are disconnected from the hand right and so clearly this thing is not necessarily evolving a closed curve it's evolving I mean it's if they're like multiple closed curves here there's the one around my hand there's a one around these guys there's no one around these guys right so what's happening there so it turns out that there are a lot of segmentation problems so you know for all the stuff I just talked about let me just say that snakes are generally as I define them a huge pain to work with right partially because you are explicitly defining the contour of the object by a closed curve right and you have to keep track of like where are the points on this curve and do I have enough points and so on and so let's just say that snakes defined as a set of points around the contour I mean I'm not gonna sugarcoat it they can be a pain I mean when when snakes were first introduced like people like oh this is pretty cool and so you know for a while there was a lot of work on these kinds of contrabass things and then it was observed you know so but there are some problems right part of it is that you know keeping track of the number of points around the contour kind of the point distribution around the contour is a pain it can be tough to get the points to kind of probe into concave areas right so you kind of saw that you know in the case of my hand the thing that took the longest time was pushing the contour into the narrow places between my fingers right the odds the outside part was fine but getting in those looks and crannies took some effort right and that could be a pain when you know you're forced to distribute the points evenly around the contour and somebody's points have to really probe inwards to these places right they could bunch up in the wrong places and stuff like that the other thing is that a snake as defined can never wrap around multiple objects at once right so for example suppose that I was a biologist and I wanted to segment a bunch of cells on a plate all of which had basically the same intensity to you know foreground to background difference right seems like I should be able to do this but I don't want to have to number one you know either I'd have to initialize a bunch of contours and let each of these you know shrink down by themselves which could be a pain in that figure how many of these do I need if I use a single snake the best that I could hope for would probably be something that would snap around the outer boundary of the objects without you know there's no way that it could get these objects to be separated and also a snake can't do holes right so suppose that I had an object like a doughnut that had a hole inside right I could segment this with a snake and I get the outside but I wouldn't be able to get the inner boundary which may be something that I care about right so say it's like some sort of a machine part okay so to solve these problems namely you know so it's definitely the one about keeping track of all this stuff and also you know it's nice to be able to segment multiple objects and objects with holes and have like a single thing that will do all that at once for you right the solution is what's called a level set approach and this is a pretty slick idea so and I would say that fundamentally if you're doing snake active contour type of stuff now you're going to be doing with levels that's not with the things I showed you earlier right so the idea is that instead of parameterizing the curve by a set of ordered points what i do is i discretize the whole image plane so I've got these XY coordinates and I define what's called a level set function feet okay and so instead of evolving a curve I'm evolving this function over the plane so evolve this entire function and then the key idea is that the pixels where this function equals zero implicitly define the object that we care about which could have you know multiple objects could have holes and so on so let me kind of do a better job of sketching this for you so the idea here is that the curve that I get at the end of the day is the set of places where this level set function equals zero so for example let's suppose that I have [Music] let's suppose I have this function of x and y okay so this basically anywhere that I have x and y I can define this function right and if I set this function equal zero that means that I have x squared plus twice you know this that means I'm implicitly getting this circle of radius R right so to draw it a different way this is kind of like saying that this function over the XY plane looks like you know some shape like this and if I look at where this shape intersects this is like saying I look at this this axis here this is like saying that this point here is like Z equals zero I look and see what do I get in the XY plane I get the outline of this thing right and so in a way I can imagine that I have a function that has like you know a shape like this and want to intersect it I could get this and this or I can have a shape that looks like this and when I intersect it I could get like a shape that has a hole in it right and multiple shapes so this is a kind of a slick idea because as I evolved this function actually the function can be changing all the time and I can actually change the topology of what it is I'm finding on the fly so instead of saying oh all of a sudden I discovered I have two objects is that one object I have to go back and change my snake stuff entirely here the function just changes and I just discover what my objects are right which is kind of neat and so a good choice for this fee is what's called the signed distance function so for example all I'm saying is that you know in the XY plane this is like saying the places on the curve have a value of exactly zero places that are inside the curve have a negative value places that are outside the curve have a positive value and I can kind of think about this like a kind of a an image and so let me make this a little more concrete in MATLAB right so I made a little example as I want to do so here I have here I have a object that has a complicated boundary right it's got the outside of the R and it's got a hole right and so here is a little demo I made that shows that on the Left I have a 3d function you can see is this colored thing right and it's a function of x and y and when I intersect this with my Z equals zero plane it hits the curve in oops I guess I'm upside down it hits the curve in exactly the places that trace out the R and as I change the level of the function it hits this you know as I change the level of the plane for example I could say okay where is this function equal to 20 I get kind of the outside of the R and then as I move this down I can start getting the hole and as I move it down even further I get you know disconnected pieces and then I get nothing right so this is the idea is that this one function can encapsulate though come back this one function basically encapsulates the shape of the R with a single function of x and y right which is pretty slick and so it is that instead of you know evolving this complicated our contour instead I'm going to evolve the colored function here and look at the cross section of it as e equals zero over time right so that's the idea and so the basically idea is that evolving this level set function is kind of mathematically better-behaved let's just say right so now I'm basically going to have a function XY T and again I'm going to at every step of T try and make this function a little bit better right although I will say that you know there are many picky details to make this work and I can't talk about them in five minutes so but this is the idea is that this kind of school of thought came from fluid dynamics actually so if any of you are like Becky's this is kind of like a fluid dynamics idea of how do I evolve the front of changing like how do I evolve a wave front right but this works pretty well and then at the end I use what I would call like an isosurface algorithm to extract you know the final segmentation so again like if any of you have taken like computer graphics or something like that you maybe came across this thing if there are lots of functions to say okay find a place where this function equals zero right marching cubes is an example of such a algorithm okay and this is evident this even goes to 3d right so you can imagine that if I wanted to segment the surface of a 3d object then I go up one more dimension right so then I have a function of a 3d space and the place where I have that 3d function equals zero well outline a cool 2d surface right so there are these one level up ways to do level sets so let me just say that everything I talked about with respective snakes can be done with level sets I can kind of use the same types of internal external forces except that everything is done on this one dimension up function instead of on the image plane okay so I'm not going to go into the details of that you can again look in gonzales and woods for some where the nitty-gritty but this is the kind of a cool thing this is what matlab will do in terms of trying to evolve a function I think if you if you watch what those contours are a lot of times they're not actually a single closed contour so I pause and ask any questions about this one more thing I have to say last thing I just say is that you know final comment is that everything we've talked about today so far has been what I call edge based right which you know kind of stands to reason we've talked a lot about edges and stuff so far in this class but you know what if there aren't really strong edges so in the absence of edges or at the absence it's not the way you spell absence a sense of strong edges we can use a region based formulation and actually this will even work when I have you know strong edges - the idea here is that instead of trying to push the curve on to the edges of an object I could just generally say that I want a curve that separates the image plane into an inside and an outside and this is my curve right and then the energy of my curve could be defined as something like I have some number that says over the pixels on the inside I want these I want the standard deviation of those pixels to be small and around the outside I want the standard deviation of those pixels to be small so this is kind of like you know this is like the external part and then I could have something that says also I want the curve to be short or you know this is like a kind of an internal force and then I could have another term that basically encourages the curve to shrink right this is called the Chen si or Qian visa I'm not sure how to pronounce it right so the nice thing about this is that it doesn't force the image to have to have strong edges you can imagine that I have an image that was kind of fuzzy and it would still work pretty well and so if you go to matlab's image signature and you ask for region based as we did here that's what's going on here so if you look here it says region based active contour developed by Qian BC so that's what's happening and just as a final thing before we go let's just see how we do with more complicated images so like here see how well this is gonna work so here's a case where I've got a really complicated interior and a blurry exterior so let's see how we do here so this is the region based algorithm Oh No so it's kind of coming around the boundaries of some of these objects but then it's also somehow flipping out on the the outer boundary so maybe not so great here unfortunately the way that this you know the way that this image segment is designed you don't really have a lot of direct access to the underlying parameters so I think honestly you could probably get this kind of thing to work but given the timing let's just see freehand if this works so here here's another example where even though the zebra is really stripy I wonder whether the region based algorithm will work on this yeah this looks like it's going okay right so you can imagine that fundamentally the interior distribution of the zebra is black and white and the exterior distribution is green and even though there's lots and lots of edges all over the place here this region based algorithm is still able to do pretty well because it's trying to basically maximize the difference in distributions between what's inside the curve what's outside the curve as long as there's green grass inside the curve it's advantageous for the algorithm to push those pixels on the other side because that matches more with the outer distribution so you can actually see that this works pretty well so I'm glad that this example seemed to go OK at this point I could say I'm happy with the segmentation of course it's still taking a while to dig into the interior legs of the zebra but externally things look pretty good okay so any last questions or comments all right that's it so thanks for listening and

Channel: Rich Radke

Views: 28,221

Keywords: rich radke, radke, rpi, snakes, active contours, segmentation, image segmentation, level sets, chan vese, gvf snake, gradient vector flow

Id: RJEMDkhVgqQ

Length: 81min 2sec (4862 seconds)

Published: Thu Mar 08 2018