Talk:Level-set method

Derivation

Could somebody add a section that explains how to derive the level set equation? In Osher's book it is just given, as if it were obvious. But it's not obvious to me.Singularitarian 08:53, 11 July 2007 (UTC)

I guess you mean the Hamilton-Jacobi equation for the level set function:

$\phi _{t}=v|\nabla \phi |.$

This is easiest to check when $\phi$ is a linear function in one variable, $\phi (x)=mx+b.$ For $m>0,$ moving the $x$-intercept to the right by $v\Delta t$ is the same thing as moving the line down by $mv\Delta t,$ which then easily implies the above equation. The general case is done in the same way for each point $x$ on the zero level set. Let me know if you'd like more details. Oleg Alexandrov (talk) 14:46, 11 July 2007 (UTC)

Well, I hope this is what you want. Supose that

$\Gamma (t=0):\quad \phi ({\vec {r}},t=0)=0$

is the curve you have at $t=0$. So, the level set method say that this identity holds for any time, so there's $\phi$ that satisfy

$\Gamma (t):\,\,\phi ({\vec {r}},t)=0$

for every $t$ in your domain. Take its derivatives with respect to time,

$\phi _{t}+\nabla \phi ({\vec {r}})\cdot {\dot {\vec {r}}}(t)=0$ ,

and then you get your Level Set equation. Hamilton-Jacobi equation is a particularly case of this: if the $\nabla \phi ({\vec {r}})$ has no second order derivatives in space, so we have the the Hamilton-Jacobi equation. (And I hope my English don´t confuse you too much) Do you work with this method? Thschiavo 13:24, 27 July 2007 (UTC)

Sign convention?

Both of Osher's and Sethian's books (given in the references section) give level set function values as negative inside the curve and positive outside. Osher does so explicitly on page 5 (a circle shown with phi < 0 inside and phi > 0 outside) whereas Sethian's plots on page 8 do so implicitly. I would argue that their sign convention trumps whatever was used as the basis for this article, but I don't want to be the one who has to recreate all of the pretty graphs if a change is made. WokYai 17:56, 16 October 2007 (UTC)

Indeed. Changing Oleg's matlab script that generated the picture should not be so hard. Jmath666 (talk) 19:29, 29 November 2009 (UTC)

Missing definitions

The level set method [...] is a numerical technique for tracking interfaces and shapes.

• what is meant with tracking?
• What is an interface?

Thanks, --Abdull (talk) 21:33, 2 July 2008 (UTC)

An interface is a boundary between things. Tracking, means following the interface as it moves. Oleg Alexandrov (talk) 03:58, 3 July 2008 (UTC)

Request for clarification

While I certainly appreciate the hard work that knowledgeable authors put into pages such as this, I'd like to request clarification of some basic ambiguities which make this article difficult to understand.

First, what do the individual words "zero" "level" and "set" refer to? At the moment, one might guess that "set" refers to the set of points in the boundary of either gamma or phi. "level" perhaps means "at the z level of a particular intersecting plane (in the case of a 2-variable phi, as in the example). And "zero" perhaps refers to the intersecting plane having a z-value of zero. Is this right?

If we are sticking with the example in which z = phi(x,y), is "level set" simply synonymous with "surface of phi"?

(Note that the sentence "This function is called a level set function" might refer back to either gamma or phi, so doesn't help us.)

Moving on, "The Level set method" section promised that a more technical definition will become quite accessible. That's presumably what we're going to get to in the "The level set equation" section, however...

1. The title suggests that "THE level set equation" is about to be shown. Either it's not there, or that's an alternate name for the HJE. Yet HJE, as described here, is a means of describing the *motion* of a zero level set, not the zero level set itself.

2. How does the notation used here for HJE relate to the notation on the wikipedia Hamilton-Jacobi_equation page? What's the intended interpretation of the vertical bars? http://en.wikipedia.org/wiki/Vertical_bar

3. What's the interpretation of "t" in this equation, relative to the example? Does it correspond to z?

4. What is to be made of the intro sentence: "If the zero level set moves in the normal direction to itself with a speed v, this movement can be represented by..."?

Which direction is "normal to itself"? Does this mean normal to the z=0 plane? Or is it referring to each point in gamma moving within the z=0 plane, normal to the tangent at that point (loosely speaking "radially")?

I'm leaning towards this sentence actually referring to the "vertical" movement of phi, relative to the z=0 plane. Ie: movement and velocity of phi rather than movement of the *zero* level set per se... but I'm not sure.

5. OK, now we're discussing "numerical solution of the level set equation". What does this refer to? (Still suffering from not knowing whether "THE level set equation" is HJE or not.) Get values for gamma by applying phi to particular values of z (or t?) (or apply z=0 to some "vertical" position of phi)? Or solve the HJE, and if so how do these relate?

6. But, says the article, finite difference methods "fail quickly". Why do they fail? Qualitatively, what approach is needed to avoid whatever that failure is?

I'm guessing that HJE is a method for calculating incremental changes in gamma by making incremental changes in phi (or z position of phi), which conceptually could be integrated to calculate gamma at any value of z (or t?).... and that this suffers from the usual problem of this kind of strategy... that what works for small differences might encounter difficulty in integrating up to large changes. But again I'm not sure from this discussion.

At any rate, by this point in the article, we've been told that (a) using level set method is "very easy" and (b) the approach "requires sophisticated techniques" and "is questionable".

In short, the more technical discussion seems incomplete, and not coherent with the introduction.

Gwideman (talk) 04:56, 29 November 2009 (UTC)

First, what do the individual words "zero" "level" and "set" refer to? At the moment, one might guess that "set" refers to the set of points in the boundary of either gamma or phi. "level" perhaps means "at the z level of a particular intersecting plane (in the case of a 2-variable phi, as in the example). And "zero" perhaps refers to the intersecting plane having a z-value of zero. Is this right?

That should be clear by mid-page.

If we are sticking with the example in which z = phi(x,y), is "level set" simply synonymous with "surface of phi"?

No. That would be the set of all (x,y,z) such that z = phi(x,y).

1. The title suggests that "THE level set equation" is about to be shown. Either it's not there, or that's an alternate name for the HJE. Yet HJE, as described here, is a means of describing the *motion* of a zero level set, not the zero level set itself.

I have reworded that.

2. How does the notation used here for HJE relate to the notation on the wikipedia Hamilton-Jacobi_equation page? What's the intended interpretation of the vertical bars? http://en.wikipedia.org/wiki/Vertical_bar

It does not. The Hamilton-Jacobi_equation has quite a different setting. Can't have everything. Maybe later. Explained bars, this is customary notation in PDEs.

3. What's the interpretation of "t" in this equation, relative to the example? Does it correspond to z?

Time, added.

4. What is to be made of the intro sentence: "If the zero level set moves in the normal direction to itself with a speed v, this movement can be represented by..."?

Which direction is "normal to itself"? Does this mean normal to the z=0 plane? Or is it referring to each point in gamma moving within the z=0 plane, normal to the tangent at that point (loosely speaking "radially")?

Normal means orthogonal to tangent. "to itself" is redundant, deleted, made clear what moves.

6. But, says the article, finite difference methods "fail quickly". Why do they fail? Qualitatively, what approach is needed to avoid whatever that failure is?

They do. Too complicated to explain here. You need to go the references to see what is going on.

I'm guessing that HJE is a method for calculating incremental changes in gamma by making incremental changes in phi (or z position of phi), which conceptually could be integrated to calculate gamma at any value of z (or t?).... and that this suffers from the usual problem of this kind of strategy... that what works for small differences might encounter difficulty in integrating up to large changes. But again I'm not sure from this discussion.

Correct. Except It's the hyperbolic character of the level set equation. For more common parabolic problems(say, for the heat equation or viscous fluid flows) numerical integration does not present a difficulty, but here it does. This is a similar situation as in finite difference methods for systems of conservation laws such as inviscid flows. Basically, in such as system, information flows in one direction only, along characteristics, and the solution may develop shocks. This is clearly not good for finite differences, which rely on the solution being smooth. (Corrected/added Jmath666 (talk) 06:57, 29 November 2009 (UTC))

At any rate, by this point in the article, we've been told that (a) using level set method is "very easy" and (b) the approach "requires sophisticated techniques" and "is questionable".

Indeed. It is conceptually easy but numerically questionable.

In short, the more technical discussion seems incomplete, and not coherent with the introduction.

Yes, the intro is a bit too optimistic. Thanks for helpful comments! Jmath666 (talk) 06:39, 29 November 2009 (UTC)

Cool! Thanks Jmath666 for the improvements, they do indeed help. Could you comment on a couple of these items further? In the discussion comments I ask:

If we are sticking with the example in which z = phi(x,y), is "level set" simply synonymous with "surface of phi"?

And you reply:

No. That would be the set of all (x,y,z) such that z = phi(x,y).

... In which I _think_ you're saying that "surface of phi" is not the level set. Yet the article currently says "the red surface is the graph of a level set function phi". It seems to me that the red surface is z = phi(x,y), and that this is the level set... or is there some subtle point I'm missing?

OK, next point. What is the relationship between t and z in this example? I am assuming that t is the parameter for selecting a particular "state" of curve gamma... but that looks to be parallel to a particular value of z (or at least a particular z positioning of phi, if gamma is the intersection of phi and z=0).

Thanks for your comments. Gwideman (talk) 12:54, 30 November 2009 (UTC)

1. I am sorry that's how one would normally write it. (Even if I did not write that sentence.) Equivalent but awkward: "The red surface is the graph of phi. phi is called a level set function." 2. There is no relation between t and z. t is the time and z is the vertical dimension. 3. Gamma is indeed the intersection of the graph of phi and the plane z=0. Thanks for working on this - it is so easy to for us to forget that if you do not already know it's harder to understand. Jmath666 (talk) 01:15, 1 December 2009 (UTC)

I see now what you mean. In the example in the picture the surface (the graph of phi) sinks with increasing t and Gamma shrinks. Well that just happens in this case. It can be just as easily the opposite. Jmath666 (talk) 01:22, 1 December 2009 (UTC)

Thanks again for the answer. Regarding time t: Presumably "t" is completely unrelated to any notion of time in the real world, it is simply a parameter by which to characterize the progression of shapes that gamma can take on, right? And the point of the level set method is to address awkward gammas where to directly state gamma as a function of t is too difficult; that is the set of (x,y) values at t is too difficult to determine directly. Hence we instead proceed to try to find a function z=phi(t,x,y), and take the intersection of this with z=0 to find the set of (x,y) values of gamma at t.

This generalizes to more dimensions, with the general idea being that the shape of phi changes as t progresses. As it happens, for two-variable-plus-time phi(t,x,y), phi can actually be a fixed shape, with progression over time being just translation in the z direction, as illustrated in the figure. Hence the simple relationship between z and t in the example. However, this is only one possible progression of phi... it could instead perform a more complicated combination of shape and position progression and achieve the same progression of gamma.

If I got all that right, it would be helpful for the article to describe explicitly the central role of t in the example, where it's currently not mentioned -- specifically reconciling this t with the parameter described in the intro. Indeed, is it really correct for the intro to say "without having to parameterize these objects"? The method does appear to achieve a parametrization of the objects, just indirectly. Thanks for the discussion. Gwideman (talk) 15:46, 1 December 2009 (UTC)

In applications, t is often the real time. By parametrization, one usually means using some fixed set of functions that are combined by means of a collection of real numbers called parameters. For example, if you have a polynomial function, the coefficients of the polynomial would be the parameters. In this sense, t is not a parametrization of Gamma. Otherwise, you got it right. Yes the article could use some expanding and clarification and it is a bit convoluted. Maybe I should work on it more at some point... thanks again for showing the weak points. Jmath666 (talk) 08:10, 2 December 2009 (UTC)

Hmmm, on more reading I'm less happy with my understanding than I was. But, I've ordered a couple of books, so there's hope. Anyhow, thanks for the comments, and maybe we'll convene again at some later time. Gwideman (talk) 14:33, 4 December 2009 (UTC)

Besides the books by Osher & Fedkiw and Sethian, the review article, "The Level Set Methods for Fluid Interfaces", by Sethian and Smereka is very readable and provide an overview of the method. Salih (talk) 16:56, 4 December 2009 (UTC)

Thanks for the reference Gwideman (talk) 11:48, 9 December 2009 (UTC)

Comment on symbols and type styles

As a side note, for those encountering "level sets" for the first time, the choice of symbols might be challenging. Given that this article needs to distinguish less than ten different entities, is there really a need to stretch over two different alphabets and so many different type style combinations? It would be helpful to indicate how much of this variation is intended to convey something important, and how much is simply sticking to convention.

For example, what is the significance of using greek letters, and these particular greek letters, in this example? Are they reandomly chosen, or does their particular choice, and type style, signify something that's important to understand? Why upper-case greek non-italic for one function, and lower-case greek script italic for the other function? Or perhaps it's just customary, and if so that could be explained. I point out that if readers didn't already know that the phi symbol used here happens to be a rather "scripty" version of the italic and lower-case phi, they would not figure it out from wikipedia page:

http://en.wikipedia.org/wiki/Greek_letters_used_in_mathematics,_science,_and_engineering

... and lacking that knowledge would find it difficult to even verbalize what they were reading. Gwideman (talk) 04:57, 29 November 2009 (UTC)

It is customary. Upper case $\Gamma$ is the common notation for a curve or the boundary of a domain in numerical analysis and PDEs. $\Gamma$ is not a function, which is perhaps why it is not lowercase. Lowercase $\phi ,\varphi$, or $\psi$ for the level set function happens to be the notation used by all the references (as well as all the level set papers I can remember). No particular reason. It could be any other symbol, really. Well, not quite in an applied paper where this methods gets used... there is a lot of notation that has an established meaning and you want to avoid those otherwise it turns counterintuitive. For example, x, y, z are coordinates... f is right-hand-side... u,v are usually velocities... a, b, c are coefficients... $\alpha ,\beta ,\gamma$ are usually coefficients too... $\delta ,\epsilon$ are something small... and so on. So pretty soon not much is left. I am sorry if the use of a greek letter looks like a hindrance. I do not think the particular choice of font (scripty or not) matters, that's just how it happens be here. Jmath666 (talk) 05:49, 29 November 2009 (UTC)