0:00

Hello and welcome back. Now we are going to be talking about

curve evolution. This is the concept that is going to

bring us to the understanding of active contours as we have seen in the previous

week. And as we have talked in the previous

videos as well. So what is curve evolution?

Very, very simple concept. The basic idea is that as we see here we

have a curve. And that every point we have a velocity

that defines how that curve is moving, and that's represented by this equation.

So it's a partial differential equation. If I'm going to write it in explicit

form, it's going to say the derivative of the curve, remember the curve is

parameterized by a parameter p. The derivative of the curve in time.

So the curve is changing in time, is equal to certain velocity.

And the velocity is again, at the given point.

And the velocity might be changing in time.

So this is the complete equation. It's a partial differential equation and

we write in shorter form as here we know that, that the subscripts represent

derivatives. So at every point we're moving the curve.

So at some time we're going to have this curve.

A bit later we might have a curve. Like here, and then a bit later we might

have maybe a curve like this, depending on the velocity at every single point.

And as we're going to see, this type of deformations of curves, remember, curves

are boundaries of shapes. This type of deformations will bring us

some very, very interesting. Movements inside images and inside

videos. So let us see a few properties of this

and also a few examples that will illustrate the importance of this

concept. The first important property is the

following. We have a velocity at every point that's

a deformation velocity. Now that velocity can be decomposed of

course, into the component that is normal to the curve, perpendicular to the curve.

We have defined normal as N tangents so we a vector we decompose it into it's

normal and tangent components. It turns out that this tension component

does not change the shape of the curve, so it's not relevant.

So that's written here. This is the general equation that we

have, but we basically project the velocity towards the normal direction.

And with a, only that projection and we move in the normal direction.

So basically from the geometric point of view, the most general deformation is a

deformation in the normal direction to the curve.

You can add velocities in the tangential direction.

They just don't change the shape. Remember the tangent is the velocity you

are travelling the curve. So adding these terms, it's kind of

changing the velocity the things are moving but they're moving along the

curve. They are not really deforming the shape.

Of the curves. So often we are going to just write curve

evolution as deformations in the normal direction.

That's all what we care. Sometimes, for convenience, if you want,

you can add tangential components. You can add them as you wish to add them,

because they don't deform the curve. For example, if I have a motion like

this, CT. Equal some function in the tangent

direction. So, no normal component.

These, does not change the shape of the curve at all.

Its only like, making a lot of effort, around the curve, but not changing the

curve at all. So the general, the formations are in the

normal direction. Lets just talk about more about that, and

lets just see a few examples. By the way, these properties, not very

hard to prove, and you can do that as an exercise, if you wish to do so.

So, the first one that we want to talk is what's called curvature motion.

So, the deformation. In the normal direction is proportional

to the curvature at that point. Before I tell you what basically that

type of deformation is doing to the curve, let's just look a bit more.

Remember that the second derivative of the curve.

When we take the derivative with respect to the Euclidian arc length is this.

So the second derivative of the curve, we know, is a vector perpendicular to the

curve. And the magnitude of that vector is the

curvature. So this deformation, is like the first

derivative in time equal second derivative according to arc length.

For those that are familiar a bit more with differential equations, this is

like. What's called the heat flow based very

geometric because of this arc length. So in explicit form, this says that dC.

Dt is equal to the second derivative of C.

According to the arc length. Okay?

it's a very interesting. Deformation of curves.

And what it does, it basically first of all, is Euclidean invariant.

Curvature is Euclidean invariant, meaning it's invariant to rotations and

translations and the normal is also Euclidean invariant.

So if you do a rotation and translation or an Euclidean transform and.

First you do the deformation and you do the deformation here.

Also here. Along the way of the deformation, the

curves are related by exactly the same rotation and translation.

So you start from two, from a curve, you rotate it.

You start the form in both, according to this motion.

And any time you stop, the same rotation and translation relates the deformed

curve. That will happen as long as you use.

Properties which are invariant to rotation and translation.

Now this motion does some very beautiful things to curves.

And the basic idea. And this has been proven, a number of

times. But was first proved by Grayson some time

ago. Then you take any curve.

Think about any curve that is not self intersecting.

So that's called a simple curve. That's actually the boundary of a shape.

You take any cure, you deform with these. And the curve becomes convex.

It just opens up. It just gets very smoothly into a convex

shape. Once it convex, if you keep going, starts

rounding. And basically, it ends in what's called a

round point. So it actually will vanish, it will keep

shrinking. Basically we keep going inside

proportional to the curvature. And at the end, it would look like a

round point. So if you dilate it all the time.

If you just make the area constant all the time, you will see this becoming

round and round. So what you see is that no matter how

crazy and how difficult your shape is. As long as it doesn't self-intersect.

And basically, it just opens up, so it's becoming smoother and smoother, until it

becomes a circle. Remember, the circle has constant

curvature. So this is basically going from a very

crazy curve. It might be a curve that does a lot like

this. As much as you want, and then smoothly.

Is becoming, just nicer, so it's actualizing regularizing the curve.

And if you wait all the way, it becomes round.

Constant curvature. If you remember, the heat flow takes

heat, no matter the distribution of the heat, at the end becomes constant in the

room. This, no matter what the curvature is all

around, at the end it becomes constant. It becomes one over the radius.

How much it takes it to get to here? We're going to know that in a couple of

minutes. Don't worry, this is a very simple

property to prove how long it takes for the curve to completely collapse into

this round point. Before we do that, let's do a couple of

additional examples. Now that was the Euclidean case.

What about the fine case? The fine case turns out to be this

function. This is the Euclidean curvature.

Where do we get it from? We are going to do, let me just write it

here for a second. We are going to do the same as we did

before. But now.

According to the affine arc length. Now remember when you take second

derivative according to the affine arc length, you are not necessarily

perpendicular to your curve. But, we know that the tangential

component does not matter. So you have to project it.

And we already saw before, in one of the previous videos, that the projection of

the fine normal, the second derivative, into the Euclidean normal, is kappa to

the one third. Is the curvature to the one third.

So. These two equations, are from the

geometric point of view, equivalent. They are absolutely the same equation.

But these has motion in the tangent direction, that is not relevant, so once

we project it, to the normal direction, we get this beautiful equation.

Looks like a Uclidian, that has a magic exponent, that makes it a fine invariant,

that means. That if I take a shape and I do an affine

transform of that shape and now I evolve. Both of them, then all the time I can

relate them by exactly the same a fine transform.

So this is a fine invariant. So I can be doing smoothing in a fine

regularization cleaning my curve in a fine variant fashion meaning invariant to

tilts of the camera. When we are under the assumptions that

the fine model is a good model, as we discussed before.

And now, you can also prove a number of interesting properties.

Similarly to the Euclidian case, what happens here is that the curve, no matter

how crazy it is, it becomes. Convex again and then it goes into an

ellipse. It doesn't go into a circle.

We are in a fine domain. Circles and ellipses are the same in the

fine domain because a, a circle within a fine transform goes into an ellipse.

Moreover, the lips has constant. Affine curvature.

Remember this mu that we discussed. That is the affine curvature.

So as in the Euclidean case, we start from something that might have a crazy

affine curvature. Slowly, the, this crazy or this very

change in the affine curvature is deforming towards constant affine

curvature. And that's why this is called the affine

heat flow. It's taking curvature that is very non

uniform and it's making it uniform at the end.

So that's another very interesting motion.

They're clearly an undefined. They're both kind of cleaning the curves,

meaning, cleaning the shapes. Now, not every motion does that.

If we take the simplest of the motions, constant speed in the normal direction,

just at every point, move a step. I don't care the curvature, about the

curvature of my curve. I just move a step at every single point.

Now. This is a very important equation.

It's the question that creates offsets. You're creating a curve which is parallel

to the previous curve. You can move inwards or you can do minus

here and move outwards. So you're creating another curve that is

parallel. It is equal distance all the time.

And basically if you keep going you get another equal distance and then you get

another equal distance here and so on depending how far you go.

Remember this is a differential equation in time.

You can stop or you can keep going. Now this curve is obtained by doing this

deformation, but is also obtained in the following fashion.

You, draw a circle centered on the curve and with a given radius.

And then for every point you draw a circle with exactly the same radius.

And then you take the envelope. Of that circle and that gives you this.

Constant motion deformation. And that's related to what's called

Huygens principle in physics. That's how waves propagate, basically

when they don't have obstructions. So, if you had, maybe you did this

experiment in physics, where you where you basically propagate waves and that's

what this constant motion does for the Huygens principal.

So maybe you knew that the... So this is a wave.

And maybe you knew the Huggins principle basically is the one that governs the

motion of the waves without any obstructions.

So that's just nothing else than this type of curve evolution.

So, this kind of revolution is important in image processing, but it also explains

a lot of very interesting physical phenomena.

Constant motion. Now this constant motion is very

interesting. For example, it can actually change the

topology of a curve. If you start from this curve.

And then you move with constant velocity, after awhile the curve splits in two.

This cannot happen in the curvature motion for Euclidean or affine that we

saw. The curve stays simple, stays smooth.

Here actually it can split into pieces, it's like the waves can split into

pieces. There are even more things happening, if

you start with a smooth curve and you move inwards after awhile these sides

will collapse. They don't have a curvature term here so

they don't have any way to understand that the curvature is becoming very, very

high. It's going to collapse.

It's going to get to a corner. Corner has infinite curvature.

Just you, really turn very fast. That's a no, because there is no

curvature term here. So after some time it will basically

collapse and it will create what are called shocks.

And we know that from waves. When waves are coming, they can collapse.

And they can create these shocks. This doesn't happen with curvature

motions for the fine or Euclidean case. The curve stays smooth all the time.

It will never collapse. The constant flow creates this collapse.

So we have the both extremes. The constant flow can change topology.

Can collapse things. Can create corners.

Now. The curvature regularizes discrete

corners so maybe it sharpens shapes, so we have both motions depending on what we

want to do in the image processing arena. Now once we have this type of.

Curvature motions. And I'm basically going to write them

here again, so you remember them. We have the constant flow.

No speed here, or speed equal one. The curvature flow Euclidan, and the fine

flow. The constant motion can split curves, can

do. Can do shocks, can do corners.

That gradient one regularizes everything into a circle and affine regularizes

everything into an ellipse. Which ellipse?

We don't know, we have fine space. All ellipses are the same.

Now, we can write a lot of properties of these deformation, and those are just

interesting curiosity, sometimes, they are very useful for image processing,

sometimes, they are just nice things, one of the things, we are going to see is,

when does these curve in the Uchlion case collapses, and this is just some

calculus, so its not very hard to do. But if you take a certain deformation, so

remember we only consider the normal deformation, and with velocity with speed

V. So for example how is the length

changing, and deforming the curve. What's happening to the length of curve?

So we have to take the derivative of the length.

And this is. The definition of the length of curve, so

it's the interval all around the curve. That's the symbol with the circle there

as you go all around the curve, we're talking about closed curves, in this

case. So you go all around the curve and this

is the function of basically the length. Now I have to put the derivative inside

and we have already seen that we take the derivative of the first component.

* the second + the second * the first. These are symmetric.

So that's why we get these two here and then we get here and we're going to have

to reverse the order here of derivatives. And instead of c derivative with respect

to p and then t, we're going to reverse that.

So it's a bit of calculus and we get at the end these expressions.

So this is the expression that governs the change of length.

And we're going to see an example in a second for different v's.

We can do the same for area. We basically, instead of inner product,

we take the outer product or the determinant.

We have already seen that. We take basically the two vectors.

And we take the determinant of that matrix.

And that computes area. We can also look at the change of

basically curvature. And these are the questions.

Again, I don't want to take too much time to do the whole derivation.

They're not very hard. And.

They appear in the book, for example, that, that I mentioned, but here we have

the. General formulas of the change of length,

area and curvature. This is actually a very interesting

formula. It's basically, in some cases, it's

called a reaction diffusion equation. It's the same type of equations that

people use to model how, basically, patterns in the skin, patterns in the

zebra are created. It has kind of a diffusion term.

And it has kind of a shock term here for certain types of V.

So let's just pick some examples and see what happens for different V's, for.

Example for V equal one, the constant motion.

So for the constant motion we have V equal one, and then the change of length

we put here, V equal one. So it's the integral all around the curve

from zero to L. Now.

There is integral of the curvature around a closed curve, it's always equal to two

Pi, that's basic fundamental theorem in differential geometry.

And that basically says that the length is changing at constant rate.

The length is changing so the derivative of the length is changing at constant

length. And that, if you.

Integrate that, it tells you. When, are you starting to see.

Crazy things happening, as we're going to see in a second.

So, the time. That things change.

So you can either. Write it as a function of the, initial

length or as a function of time. You get it here.

The are is basically, this was the general formula, that V=1, and basically

we have the integral from zero to L of one, that's L.

So, the area is changing proportional to the length.

Now, the length is changing. So, this is not constant.

This is constant, this is not constant. The area is changing, proportional to the

length. The curvature.

This was the general formula. And we have the, then the derivative is

equal to the curvature^2. Because V is constant.

So second derivative vanishes. Now you can solve this equation of

derivative of curvature according to time equal curvature^2.

You solve it, and you get this equation. And look what happens here.

This, basically, the curvature blocks. It becomes infinity.

When t is one over the curvature at the original curve.

Remember, we say that things can create shocks.

Basically, the waves are coming, and boom, they collapse.

And that's basically very high curvature, infinite curvature.

When that happens, when this term is zero.

When is that happening? When t is one over the initial curvature

at this point. One over curvature is radius.

So you know exactly when are you expecting a shock to happen.

When are you expecting these waves from both sides to collapse?

You go around your initial, initial curve.

And you say, where do I have, basically, my curvature?

Of this form. When is that going to happen?

When is this curvature going to become infinity, because it's collapsing from

both sides. Oh, at time one over the curvature.

The larger the curvature, the shorter the time it will become a shock.

So if you have something which is already almost, almost a corner very fast, it

will become a shock. So from these equations, you understand

the. Overall behavior of that.

You can, of course, do that also for the curvature flow for the Euclidean case and

once again you plug in the same equations and in this case.

This is the general formula of the area. Now, the velocity now is curvature.

So you integrate, again, the integral of the curvature is constant.

So you get that in the constant motion, the length was changing at constant rate.

In the Uclindian motion, the area in the Uclidian curvature motion, the area is

changing at constant rate. And then, I can solve for these, and I

can tell youi exactly, when is the curve collapsing, It is collapsing at time,

which is the initial area, divided by two party.

So you look at your initial area, you divide by two pi and say, at this time my

whole curve will become a point. Remember this motion.

Collapses everything to a point that all the way smooth in contrast with a

constant motion. Here everything is smooth.

It just gets cleaner and cleaner and it goes into a round point.

At when exactly at this time. So that's why these formulas are

important to understand how the length is changing, how the area is changing, or

even hos the curvature is changing. So these are really, really interesting

properties. We can do the same for the fine case, and

you get this formulas, there is no kind of, very.

Clean way to solve this type of integrals.

So you just get these formulas. There's no constant basically things

here, although you can make an interpretation of some of the things as

constants but let's just not discuss about that in this moment.

So basically we have properties of these motions.

Now. One of the motions, so these are

curvature motions, constant motions. The active contours we talk about

basically are these type of deformations. Nothing else in that.

And then I'll just give you one example of active contour's velocity and when we

learn in one of the next videos, calculus of variations, after that we're going to

be able to derive this motion in a more formal way, but even now I can write it

down and explain it to you. So this is V.

What we have here is b. So this equation looks very long, but

it's nothing else than a deformation with a certain velocity in the normal

direction. Now what are the terms inside here?

So this curve. Is basically going to deform with a

certain velocity. Now what are these terms?

Here's the curvature. No problem.

We know it. Here's the normal.

Here's the normal. What's g?

G is, for example, is a function that depends on the image, and, for example,

one over the gradient of the image. Now, why do we need this function?

Let's say that this function was not here.

Let's just leave aside this term for a second.

Let's assume that this function was never here, so we have city equal K, kappa,

curvature, collapses to a point. I don't want that.

I want this red curve here. Basically, to stop, basically, add the

boundaries of the shapes. I don't want it to collapse to a point.

So how do I do that? I make it stop at high gradients.

So if g is proportional to one over the gradient of the image.

Then, let's say that I have a very strong boundary.

The gradient is very high. Let's assume it's infinity.

And then G is zero. So the curvature's trying to collapse,

collapse, but it gets multiplied by zero and then stops, say, hey, I cannot move

any more. I need to stop.

There is no more velocity. And that's why you have this term here.

Now. We never have ideal shapes.

So this derivative of G. Remember, G is one over derivative of the

image. For example, the gradient, or any other

type of function. You take another derivative of that to

make that stopping term even stronger, even when there are no perfect edges.

That this will not be zero. You basically create that potential

valley by taking the second derivative, and of course that doesn't have to be in

the normal direction, so you have to project without that.

Every time we have something that's not in the normal direction, we have to

project it to the normal direction. So this is almost nothing else than

curvature motion. So, a simplified version of active

counters is this. Its curvature motion.

In the normal direction multiplied by G. G is a function of your image, it's the

one that tells stop when you get to very high gradients and this second term just

made that stopping even stronger. So here it is, we saw active counters in

the previous week and now we have been talking about differential geometry and

we have been talking about. Curvature, curve motions and how things

deform, why, one of the reasons is to get to active counters, you're an expert now

in differential geometry, you're an expert now in.

Curve evolution, curve the formation. So here it is.

You could have to sign this. If I give you five minutes to say, define

this sign of curve evolution motion that will get you active contours.

Many of you, most of you probably would have come with this solution.

Just deform it smoothly, move towards the objects.

But when you get to the objects, stop. And then people have done many different

variations of these. But this is the underlying concept.

You can add some constant motion. That helps you to move faster, but be

very careful you can get shocks and you can you keep moving.

So always you have to have turns that depend on the image, not just depend on

the curve, depend on the image. So it makes you stop.

And you can basically go wide and do very, very interesting things in Curve

evolution to get to active contours. Now remember, we know how to define these

properties also for surfaces. So we could do that for surfaces as well

and basically, here is just an example of a surface.

So these are snapshots of a surface that started basically from here.

And it deform, it deform, it deform and it is covered inside.

They were basically two rings basically touching each other.

And this motion is nothing else than the motion I just wrote for you but now in

surface domain and here, this was an ideal object, white and black, so the

gradient was very strong and one of the, over the gradient was very weak.

So basically when I did the surface evolution, dS, dt equal let's say, one of

the curvatures and, can be the Gaussian, can be the mean.

Yeah we could discuss more about that, what curvature exactly to put here.

The normal direction, that would basically move, move, move and then we

have G, that basically you say, we'll say, when you get to a very, very high

gradients, stop. And so this is just a ve, artificial

example. We're going to see more examples of

active contours later on now that we're becoming experts in this curve evolution

and differential geometry and this is just, as I say, snapshots of this

evolution. So a lot of very interesting mathematical

tools. That give us, active counters, which is

one of the most useful techniques for doing image segmentation, as we have seen

many examples last week and as we're going to keep looking at more examples.

So now we're experts on curve evolution. And I'm looking forward to seeing you in

the next video when we're going to keep learning, keep building the tools that

will let us understand everything about these active counters and this type of

deformation as well as some of the material coming later on.

Thank you very much and see you in the next video.