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.
