Thresholding scheme & level set method

MBO scheme

The evolution of mean curvature flow has many different schemes and algorithms that approximate it and converge in the limit (often the time step goes to zero and in the case of discretization, the number of points goes to infinity) to the continuous evolution. A special scheme is the thresholding scheme of Merriman, Bence and Osher which is also called MBO scheme. It uses the reaction-diffusion character, which can also be seen in the approximation using the Allan-Cahn equation. This algorithm is based on the perspective of the manifolds as boundaries of sets and uses an iterated two-step procedure. Let \(\chi\) be the characteristic function of a set. Then the first step is a convolution with a kernel \(K*\chi\). Usually, the heat kernel \(G_h\) is used. In \(\mathbb{R}^d\), we have the explicit formula

\[G_h(x,y)=\frac{1}{\sqrt{4\pi t}^d}e^{-\frac{|x-y|^2}{4t}}.\]

The second step is a thresholding step at the critical value \(\frac{1}{2}\) (the midpoint between the two values of \(\chi\)). Thus, we have the evolution:

\[\chi^{n+1}={1\!\!1}_{\{K*\chi^n\geq \frac{1}{2}\}}.\]

Figure 6. One step of the MBO scheme.

An example evolution is shown in Figure 6.

We start with the discrete set of three balls. The second image shows the diffused function where the values are indicated by the gray value. Finally, we obtain the third image through the threshold. In the limit of zero time step size, this scheme converges to the mean curvature flow.

Level set method

The idea behind the level set method is to obtain the sets as the sub level sets of a given function. E.g.

\[\chi={1\!\!1}_{\{g<q\}}.\]

for some \(q\in\mathbb{R}\). We now want to study the level set equation of mean curvature flow

\[\begin{split}\begin{cases}\partial_t u(t,x)=|\nabla u|\nabla\cdot \left(\frac{\nabla u}{|\nabla u|}\right),\\ u(0,x)=g.\end{cases}\end{split}\]

This evolution implies that the level sets of \(u\) evolve by mean curvature flow. This can be seen by the facts that \(\nabla\cdot \left(\frac{\nabla u}{|\nabla u|}\right)\) is the divergence of the normal and thus represents the mean curvature while \(\frac{\partial_t u}{|\nabla u|}\) represents the negative normal velocity. One could also derive this PDE by a Lagrangian specification calculation for a point which follows a levelset of \(u\) that evolves by MCF. Another useful fact is that

\[|\nabla u|\nabla\cdot \left(\frac{\nabla u}{|\nabla u|}\right)=\Delta u-\frac{\nabla u}{|\nabla u|}\cdot \nabla^2 u\frac{\nabla u}{|\nabla u|}\]

is the level set Laplacian. An important part of this level set formulation is the maximum principle. It is necessary that the (sub) level sets are ordered. By this principle they remain ordered and a level set wise evolution is possible.

To be precise, we will consider the viscosity solution of this equation which generalizes this flow in a unique maximal way.

Median filter

In this subsection, we will sketch how the MBO scheme is generalized to the level set formulation and where the medians appear.

It can be seen that the thresholding scheme solves the following minimization problem

\[\chi^{n+1}\in\text{argmin}\left\{\int\limits_{\mathbb{R}^d}\int\limits_{\mathbb{R}^d}K(x,y)|\chi(x)-\chi^n(y)|\text{d}y\text{d}x\right\}.\]

One could also minimize over each point \(x\) individually. If we assume that the sets are the sub level sets of a function \(u\) and integrate over all values, we get

\[u^{n+1}\in\text{argmin}\left\{\int\limits_{\mathbb{R}^d}\int\limits_{B_r(x)}|u(x)-u^n(y)|\text{d}y\text{d}x\right\}.\]

Here we have inserted the special kernel of a local ball. This minimization problem is solved by the median, i.e. the value that has the same amount of points/values above it as below it. The problems are equivalent to solve (for almost every level set) as the function which is constructed from the value wise minimizers is a viable candidate.

The advantages of this formulation include the viscosity solution as a general solution concept and more general topologies for convergence. Moreover, it turns out to be easier to make statements about the function than about general level sets.