0:00

Hello, and welcome back. We just finished learning about curve

evolution. There's one thing that is missing that we

need to learn. It's how do we implement curve evolution

in the computer. We saw that curve evolution is important

for example, to regularize curves with curvature motion, but even more important

for active contours. And we need to learn, how do we implement

in that friendly fashion that in a computer we have discrete images.

So, we need to talk about the numerical implementation of that.

one of the areas that has had a tremendous impact in image processing, in

particular, when we talk about PDs in image processing, is level sets methods

and I want to to explain that. And with that, we're going to know how we

implement any type of curve or surface evolution in a computer.

So what is all this theory, all this framework of level sets?

So we have talk about curves and it's going to be the same for surfaces because

it's much easier to present this for curves.

We have talk about curves and curve representations.

And we see that here, we have a curve that is parameterized and remember for

every P, we have basically a different point on the curve.

Now this is not the only way to represent curves.

There's a very different way to represent exactly the same curve that is actually

even more familiar when we are talking about shapes.

And the basic idea is that instead of parameterizing the curve, we're going to

represent the curve by all the points on the plane that hold a certain equation

equal to zero. So let's look at this figure.

We're going to put a coordinate system x and y and then we say every point in the

curve is a point such that phi at that point is equal to zero.

So we have to describe this function phi. And for example we can define the

function to be positive inside and negative outside and one example is to

define this as the distance to the curve for, for of course the distance to the

curve at the curve itself is zero. The distance to the point itself is zero.

So, every point on the curve has zero distance to the curve.

Every point inside has a positive distance, and we define every point

outside to be at negative distance. And that way, we define the function phi.

That the zero set, that's called the zero level set of that function, meaning all

the points in the plain where that function is zero define a curve.

Let's look at a profile of this and we see that here. If I have a function that

is positive inside and negative outside and I cross it with a line, then this is

the profile. We're going from negative tp positive.

So this region is positive. Then we go again outside, so we have

negative again. And we go again inside and we go again

outside. Now which are the points that belong to

the curve. This point, basically, this zero.

This point and this point and this point, every time the profile of five crosses

the zero, that point belongs to the surface.

In that way we are, belongs to a curve sorry or a surface if we are in higher

dimensions. In that case, in that form we are

defining a curve on the plane by all the points that hold this equal to zero.

And these two are just two different representations of exactly the same

curve. This is kind of painting inside the curve

and painting outside the curve in such a way that along the curve that paint is

equal to zero. Now.

With this representation we have compute tangents, normals and curvature.

We need to be able to compute it with this representation, otherwise, we won't

be able to do curve evolution. So let's see how we do that.

And we're going to prove a couple of things.

As we have talked, this week is one of the most theoretical ones.

But we are doing everything self-contained.

So I'm explaining everything inside and I think we are learning a lot of new

concepts. So let us show that basically if we

define the curve as before at the zero level set of the function fee.

The normal is the gradient of phi divided by the magnitude, actually, with a minus.

That's a convention because I want the normal to point inwards.

It's just a convention. And of course the tangent will be this.

It's basically a perpendicular vector. Let's prove that, it's not hard to prove.

So remember, we have the function phi and all the points that belong to the curve

is where phi is equal to zero. So along the curve, phi is not changing.

It's always zero. When I travel the curve, it's always

zero. Then, the derivative of the function

along the curve. Along the arc length.

Because I'm traveling along the curve is equal to zero.

Let's compute that derivative. So I want to take the derivative of this

function. Remember, the function exists all over

the plane, and I'm taking the derivative in the direction of the curve in the,

with the arc length along the curve. Now, we have it here.

This is just the chain rule. Basic calculus.

So if I have to take the derivative according to s.

It's the derivative according to x, x according to s, and the same for the y.

So that's simple calculus. Now, what I wrote here is this inner

product. Remember, the inner product of two

vectors. So I'm going to write it here in case you

don't remember. If I want to multiply two vectors a, b.

I want to do the inner product, let's say with cd is a * c + b Time d.

So this is nothing else, now the inner product of the gradient of phi with the

time chain. Remember, xs, ys is the time chain, is

the unit time chain. We say that a couple of years ago when we

were talking about differential geometry curves of the plane.

And phi x, phi y is just a gradient. So, this is what we have here.

Now this is zero. Okay, we have it here.

Of course this is the zero. So I'm going to go here.

And, of course, I'm allowed to normalize. So here I have proof that the gradient of

the curve is perpendicular to the tangent.

Then I normalize the gradient. So if I have a vector that is

perpendicular to another. Of course, any change in magnitude in the

vector is still perpendicular. In particular I want to basically

normalize it to have unit norm. And then I get this equal to zero.

So if this is perpendicular to the tangent then this is the normal.

So I have a perpendicular, this is the normal.

And now once again, we as a convention put a minus because they, we want if we

have positive and negative we want the gradient to point, to point basically we

want the normal to point inwards. Once again, it's just a convention.

So a very simple proof that basically shows that.

This is the definition of a normal so having phi, I can complete the normal

with absolutely no problem and of course I can complete the tangent just a

perpendicular vector to it. And we have the first, actually we have

two. The normal and the tangent.

Now let us compute the curvature. And again a very simple computation as we

have here. Just maybe two more steps and we get the

curvature. So what we want to show is that the

curvature, I only have phi, remember the curvature is the second derivative

according to s. So the curvature was cssKN.

equal kN. That's a curvature.

This is, I want to compute. I don't have c.

I have phi. I have c, the curve, the final implicitly

by phi as its zero level set. And I want to prove that it's this

formula. In case you don't remember what div is,

div is a divergence. And the divergence of a vector alpha beta

is basically alpha x + beta y. So it's a scalar.

The first term of the vector, you take the derivative according to the first

coordinate X. The second, according to the second

coordinate, okay?

Let us prove this formula right now. So now, we are basically, are still going

along the zero level set so we still have this relationship.

And let us exploit it now. We are going to compute the second

derivative of phi along the curve with arc length.

We just compute the first one in the previous slide when we're computing the

normal. Now I want to compute the second

derivative. So I have the first derivative and I want

to take one more derivative. Now, once again, this was nothing else

than the gradient in our product with T as we saw the previous one and I have to

take a derivative. Remember derivative of a final product is

the derivative of the first times the second plus the first times derivative of

the second. Now what's the derivative of the tangent?

Second derivative is curvature in a normal direction.

So here it is. Curvature in a normal direction.

So once again, derivative of the first one times inner product with the tangent

and then the first one, inner product with the derivative of the second one,

which is T. But we know that the derivative of T is

kN and this basically is equal to zero. So what we have, so this is equal to

zero, so what we have is that this turn is equal to minus distant and basically I

wrote that here so this turn I can take the curvature outside,

okay? That's not a problem.

It's a scalar. I can take it outside of the inner

product. That's the first thing we do.

Oh, I apologize, there is here a typo, this should be a phi.

Basically a kind of a capital phi, but, I apologize for that typo.

We are going to continue. It's just that very easy to see that

going from here I just made a typo. And we basically have the curvature goes

outside, that's here, then we have this, again here.

And the normal we just saw in the previous slide, is gradient divided by

gradient. So we have curvature here.

Now this product is the gradient square because I'm multiplying this by itself.

So it's the gradient square divided by the gradient that cancel each other and I

get only one gradient. So this turn.

Is here, okay? This term I'm not going to write it down

but by now you're an expert because we're just doing derivatives and chain rule.

If you want to take the derivative of the gradient according to S, remember you

have to take the derivative according to X and then XS plus derivative according

to y, ys. So you do chain rule again and then

you're going to get this expression. This expression is basically this

derivative. And then the tangent once again we have

from the previous one. Now we got this equality here if you now

open this with this definition your going to see that is identical to here.

Times this. And then we got basically the formula for

the curvature of a curve that is represented in implicit form.

Now pay attention this is extremely important this is going to be very

important next when I explain the forming curves in level sets.

I don't need to have the curve I don't know c.

C, it's an implicit fashion define. All I need to know is phi and I take

regular derivatives in each direction, in the Y direction.

We know how to do that. So this is the x direction, this is the y

direction. We know, we just take derivatives as we

have been seeing many times in this class.

This pixel minus this pixel or this pixel minus this pixel when we are taking

derivatives in the Y direction. And we do that a number of times, just

following this formula and we get the curvature.

or we got the normal, or we got the tension, so it's much simpler, I don't

have to go and take derivatives along the curve.

I take derivatives in the grid, basically in the image.

Really, really much simpler. So now we know the curvature, we know the

normals. Do we know how to deform curves?

Let's see about that. So the next step is to learn how to

deform a curve. How to deform phi in such a way that the

boundary, basically, is deforming as I wanted.

So, we have a function that is representing a curve in implicit form.

Okay? We know that the curve that is defined in

this way, it's moving with this velocity. And we ask ourself,

how do I have to change phi for the level set of phi to move according to this

velocity? And it turns out that it is this form.

And I'm going to prove to you here in just a couple of lines.

But before we do that, please pay attention to what's happening here.

The phi is once again, it lives on the image.

It lives on the grid. Every time I'm talking about derivatives,

I'm talking about derivatives on the grid.

So the pixels are moving up or down. There's no derivatives on the curve which

are very difficult to implement. This is like when, we know.

We have seen how to compute a gradient. You know, again this minus this.

We have seen those things. So implementing this is much easier than

implementing this. Let us prove this formula.

So, the basic idea is once again very, very simple.

I'm going to take the derivative of phi according to T,

okay? And this is where I'm going,

I'm going to take the derivative according to T of this side, and the

derivative according to T of this side. Now this side is zero.

It's a constant. So the derivative of this side is also

zero. Here it is.

The derivative here, I wrote it here. And now once again chain rule, and this

is what we have. The derivative of this function of x, y,

t according to t is what I have written here.

So I take the derivatives according to x, than xt plus the derivative according to

y, yt plus derivative according to t. These are partial derivatives.

So this is what I have. Okay, now.

This I moved to the other side because I have a zero here and I get minus the

derivative according to t equal to the right hand.

So this part is equal to minus this. This we have seen before,

okay? It's an inner product as we have seen

already at least two times in the previous slides.

So it's the gradient of phi because of this part and this part.

And this xt yt is ct is basically my curve deforming.

So we are here now. We have one more step.

City, I know what it is. VN so I write VN.

It's the motion of my curve exactly what I want.

So, once again the V can come out because it is scalar and I have this.

Now, remember, I want to write everything as a function of phi.

That's the important part, okay?

So, we just saw that the normal is minus the gradient normalized,

okay? So,

here we basically applied that. We replaced minus the normal by the

gradient of phi, normalized, okay?

And this as before is gradient times gradient, that's gradient squared, divide

one gradient, we get one gradient. So this is gradient, this stays, and we

got this and because there's a minus here.

It counts as with the minus here and then we have that this is equal to this, which

is what we wanted to prove. Okay?

So once again, you can look at this, if you want to just you can pause the video

now and look at the proof. There is nothing here but applying the

chain rule, and then writing everything as a function of phi.

That's the important part. we get that when we want to move a curve

according to V in the normal direction. That's obtained by moving feet up and

down, whatever this formula tells us and then we cut.

So you want to go for t equal five, do this for t equal five, find the zero

level set and you got the curve evolution.

So everything now is in implicit form. We have functions defined on the plane

and by moving those functions, we are moving the zero level set and we are

getting curve evolution, for example, we're getting active contours.

Why is this so important? Let me just illustrate a couple of ideas

which I think will help us to illustrate how important this is.

So remember, that sometimes when we deform a curve, the topology can change.

I'm going to ask you, which was the curve motion that produces changes in topology,

that might produce changes in topology? Is it the curvature motion, is it the

fine motion, or is it the constant motion?

We know that and we know that is the normal motion the normal motion can

change topology. Now when the topology of a curve is

changing if you discrotise the curve its very difficult to understand at this

point that was neighbor of this point that was neighbor of this point actually

ended up here. And this one ended up there and now there

not neighbors anymore. They were neighbors once step before, but

because of topological changes they're not anymore.

And numerical analysis is very complicated, when those things happen,

when neighvor things, neighboring things just stop being neighboring things.

It's very, very complicated. Now when we are in this phi function, so

imagine that this gray is the phi, and basically the two planes, the two green.

Light green and dark green are just a different times you are cutting this feed

function. The feed function is moving according to

v gradient v. And all that I have to do is cut and be

surprised if there is a topological change.

I do not have to worry about connectivites.

No worry at all, because I'm working on a grade, as I'm going to show here.

So I don't have to work with particles and discretizer curve.

And remember who is neighboring with whom and how the neighbor, the neighborhood is

changing when there are topological changes.

I don't have to do that. I'm basically working with phi defined on

a grid, as we have it here. This is just another profile.

And phi is changing. Phi t is V.

gradient, gradient phi and that's it.

So we discretize that the same way that we discretized before.

It goes up, it goes down. An example you say, I want to know the

state of the curve evolution right now. You just slice it.

You look at every place where the current phi is equal to zero.

You look at every coordinate or every coordinate here.

If there is topological change or not you have to be aware of that.

And that's the beauty of this and that is how the active counters that we talk at

the end of the previous video is implemented with this where V is that

velocity of active counters so V can be in a simplified fashion G curvature.

Where G was this inverse gradient of the image or some function that makes it

stop. So you want to implement active counters.

All you have to do is phi t equal G curvature times the absolute value of the

gradient. And we know that the curvature, previous

slide, we can also compute as a function of phi.

So everything is a function of this surface that is defined on the grid and

that's the beauty of the level states. It simplifies the whole numerics.

And with it we can implement the curvature motion, constant motion,

constant motion is absolutely trivial. Let me write it here.

Phi t equal gradient phi. So the gradient you might discretize the

same way that we talked before. The pixel on the right minus the pixel on

the center. The pixel on the top minus the pixel on

the center. phi t, you discretize like phi of t + 1 -

phi of t. Any type of time discretization.

We're not discussing a lot of numeric analysis like just relatively standard

numeric analysis that you can use to implement.

Smart numeric analysis but relatively standard instead of having to discretize

a curve. Very, very simple equations for as

complicated as we want curve evolutions, curve motions.

And I prove this only for curves. Happens the same four surfaces and

actually, the formula is exactly the same formula.

But phi is not function in higher dimensions so exactly the same formula.

So, now you have the tools to do active contours.

And we are going to actually see more of active contours later this week in some

of the future videos. But you know curve evolution and you know

how to implement curve evolution, as well.

as I said we are learning a lot of new material and as I say, you can go back

and recheck this video. The proofs are really, really two line

proofs with basic calculus and algebra from very, very relatively simple

calculus and algebra but you don't have to be aware of it. I just explain it to

you during this video and during the previous videos.

So we keep advancing and I'm going to see you again in the next video.

Thank you very much.