Topics

Level-set method – Math

9 February 2018

The Level-Set (LS) method is a very versatile and extensible method for tracking propagating interfaces in a wide variety of settings, such as burning flames, ocean waves, and material boundaries.

The method has been firstly introduced by Osher and Sethian in 1988 for tracking the curvature-dependent evolving interfaces in the setting of Hamilton-Jacobi equations.

It has become very popular and it is currently used in many engineering applications, like image segmentation, fluid-dynamics, and computational physics.

The idea

The idea beyond the method is quite simple but powerful at the same time.

Suppose we are given an evolving $(d − 1)$-dimensional front embedded in $\mathbb{R}^d$ transported by a known velocity vector field $\mathbf{v}\,\colon \mathbb{R}^d \to \mathbb{R}^d$.

For example, just think of a fire-front propagating in a wildland: the fire-front is a 1-dimensional interface moving in a 2-dimensional wildland.

By the LS method, the evolving front is described, tracked, or recovered (whatever you like) by the level-set $0$ of a scalar hypersurface $\varphi \, \colon \mathbb{R}^+ \times \mathbb{R}^d \to \mathbb{R}$ called the level-set function.

I'm talking about something like this:

Responsive image

where the initial propagating front is the circle $\{(x_1,x_2)\in \mathbb{R}^2 \; : \; x_1^2 + x_2^2 = r^2,\; r > 0 \}$ and the corresponding level-set function is $\varphi(0,x_1,x_2) = \sqrt{x_1^2 + x_2^2} - r$ (on the left).

More details

Let $\Sigma_0$ be a bounded closed front (or surface) at initial time $t = 0$ and let $\Omega_0$ be the domain strictly contained in $\Sigma_0$, that is, $\Sigma_0 = \partial \Omega_0$.

Let $\mathbf{x} \in \mathbb{R}^d$. Define the following level-set function $\varphi \, \colon \mathbb{R}^+ \times \mathbb{R}^d \to \mathbb{R}$ such that \[ \text{for all $t\geq 0$}, \quad \begin{cases} \varphi(t,\mathbf{x}) > 0, & \quad \mathbf{x} \notin \overline{\Omega_t}, \\ \varphi(t,\mathbf{x}) = 0, & \quad \mathbf{x} \in \Sigma_t, \\ \varphi(t,\mathbf{x}) < 0, & \quad \mathbf{x} \in \Omega_t. \end{cases} \] In this way, the front is recovered by looking at the level-set $0$ of $\varphi$, that is \[ \Sigma_t = \{ \mathbf{x} \in \mathbb{R}^d \,:\,\varphi(t,\mathbf{x}) = 0 \},\quad\text{for all $t\geq 0$}. \]

The level-set equation

Our task it to track the evolution of the front $\Sigma_t$, as soon as $t >0$, under the action of a velocity field $\mathbf{v}$, so that $\Sigma_t = \partial \Omega_t$.

Let $\mathbf{x}(t)$ be the position at time $t>0$ of a point of the front $\mathbf{x} \in \Sigma_t$. We require that $\mathbf{x}(t)$ belongs to the level-set $0$ of $\varphi$, that is, $\varphi(t, \mathbf{x}(t)) = 0$ for all $t > 0$. By the chain rule we get \[ \frac{\partial}{\partial t} \varphi(t,\mathbf{x}(t)) + \mathbf{x}'(t) \cdot \nabla \varphi(t, \mathbf{x}(t)) = 0 \qquad \forall \; \mathbf{x} \in \mathbb{R}^d, \; t > 0, \] and since $\mathbf{v}$ supplies the speed of the motion, that is $\mathbf{v} = \mathbf{x}'(t)$, we obtain the level-set equation \[ \frac{\partial}{\partial t} \varphi(t,\mathbf{x}(t)) + \mathbf{v} \cdot \nabla \varphi(t, \mathbf{x}(t)) = 0 \qquad \forall \; \mathbf{x} \in \mathbb{R}^d, \; t > 0, \qquad (1) \] which is nothing but that a transport equation for the level-set function $\varphi$. A suitable initial condition $\varphi_0(\mathbf{x}) = \varphi(0,\mathbf{x})$ at time $t=0$ has to be chosen.

Notice that, of course, the propagation will move all the level-sets of $\varphi$: the level-set $0$ is just a confortable choice.

Responsive image

The level-set equation $(1)$ permits to describe particular movements of the front, for which the velocity field $\mathbf{v}$ is a function of the level-set function $\varphi$ itself, that is, $\mathbf{v} = \mathbf{v}[\varphi](t,\mathbf{x})$.

The most important are motions along the normal direction as well as motions under the (mean) curvature.

Motion along the normal direction

In this case, the velocity field is something like this: \[ \mathbf{v}[\varphi](t,\mathbf{x}) = w(\mathbf{x}) \, \mathbf{\hat{n}}(t,\mathbf{x}) \qquad \qquad (2) \] where $w(\mathbf{x})$ is a scalar function of the point $\mathbf{x}$, and $\mathbf{\hat{n}}(t,\mathbf{x})$ is the exterior unit normal to the level-sets, \[ \mathbf{\hat{n}} = \frac{\nabla \varphi}{|\nabla \varphi|}. \] If we substitute $(2)$ in $(1)$, the level-set equation becomes \[ \frac{\partial}{\partial t} \varphi(t,\mathbf{x}(t)) + w(\mathbf{x}) | \nabla \varphi(t, \mathbf{x}(t)) | = 0 \qquad \forall \; \mathbf{x} \in \mathbb{R}^d, \; t > 0, \qquad (3) \] and it describes the evolution of the front along its normal direction.

It is worth considering the case of a monotone evolution:

  • if $w(\mathbf{x}) > 0$ for every $\mathbf{x}$, we have an outward expansion of the front as shown in figure below on the left ($\Omega_t \subset \Omega_{t+1}$);
  • if $w(\mathbf{x}) < 0$ for every $\mathbf{x}$, we have a contraction of the front as shown in the figure below on the right ($\Omega_{t+1} \subset \Omega_{t}$).
Responsive image

Motion under the mean curvature

In this case, the velocity field is something like this: \[ \mathbf{v}[\varphi](t,\mathbf{x}) = -k(\mathbf{\hat{n}}(t,\mathbf{x})) \, \mathbf{\hat{n}}(t,\mathbf{x}), \qquad \qquad (4) \] where $\mathbf{\hat{n}}(t,\mathbf{x})$ is the exterior normal previously defined in $(3)$, and $k(\mathbf{\hat{n}}(t,\mathbf{x}))$ is the mean curvature of the front defined as \[ k(\mathbf{\hat{n}}(t,\mathbf{x})) = \text{div} (\mathbf{\hat{n}}(t,\mathbf{x})) = \text{div}\left(\frac{\nabla \varphi}{|\nabla \varphi|}\right). \] Here, $\text{div}$ denotes the divergence operator $\text{div}(\mathbf{a}) = \nabla \cdot \mathbf{a}$. Therefore, this is again a motion along the normal direction but the "intensity" of the movement is given by the curvature of the front.

As before, if we substitute $(5)$ in $(1)$, we obtain: \[ \frac{\partial}{\partial t} \varphi(t,\mathbf{x}(t)) - \text{div}\left(\frac{\nabla \varphi}{|\nabla \varphi|}\right)| \nabla \varphi(t, \mathbf{x}(t)) | = 0 \qquad \forall \; \mathbf{x} \in \mathbb{R}^d, \; t > 0. \qquad (5) \]

A typical motion under mean curvature is shown in the picture below.

Responsive image

In the regions of the front such that the curvature $k(\mathbf{n}(t,\mathbf{x})) > 0$, the front will move inward, while on the other hand, where the curvature $k(\mathbf{n}(t,\mathbf{x})) < 0$, the front will move outward.

The result is that, at some point, the front will turn into a circle-type shape for which the curvature is only positive, and therefore, it keeps moving inward until possibly vanishing.