Theory

Consider a curve moving in a plane. Let $\gamma(0)$ be the initial curve. $\gamma(t)$ is obtained by moving $\gamma(0)$ along its normal with a speed $F$ which may depend on the curvature and image gradient. One approach to solving this would be to put marker points and advance their position by approximating the spatial derivatives in the equations of motion. If the curve moves with a constant $F$, that is with no smoothing term, singularities develop in the propagating front (figure 1). If a smoothing term is added, the front is not able to model the sharp corners, see figure 1. What is desired is the entropy satisfying solution obtained as the limit of smooth solutions.

Figure 1: Cosine Curve Propagating with Unit Speed. Figure taken from [5].

The central idea in the level set approach is to represent the front $\gamma(t)$ as the level set {$\psi = 0$} of a higher dimensional function $\psi$. The goal is to produce an equation for the evolving function $\psi({\bf x},t)$ which contains the embedded motion of $\gamma(t)$ as the level set {$\psi = 0$}. Let $\psi({\bf x},t=0)$, where ${\bf x} \in {\bf R}^N$ be defined by

$$\psi({\bf x},t=0) = \pm d$$

The evolution equation turns out to be

$$\psi_t + F\vert\nabla \psi\vert = 0$$ (1)

The velocity $F$ has the form

$$F = k_i(F_0 + F_1(K)$$ (2)

where $k_i$ is the image based term which is used to stop the propagation of the front near places with high image gradient. A typical definition for $k_i$ is

$$k_i(x,y) = e^{-\vert\nabla G_{\sigma}*I(x,y)\vert}$$ (3)

$F_0$ is a constant speed and $F(K)$ is a curvature dependent speed normally defined as

$$F(K) = -\epsilon \cdot K.$$

where $\epsilon$ is a very small constant and $K$ is the curvature.

A more detailed formulation can be found in [3].

There are several advantages of such a formulation as described in [3]. First, the function $\psi$ is always smooth and non-intersecting , even though the corresponding contour (level set 0), may change topology, break, merge and form sharp corners as $\psi$ evolves.

Secondly, a discrete numerical approximation to the equation can be obtained. Replacing the derivatives by difference operators in equation 1 we get

$$\frac{\psi_{ij}^{n+1} - \psi_{ij}^n}{\delta t} + (F)(\nabla_{ij}\psi_{ij}^n) = 0.$$ (4)

$\nabla_{ij}\psi_{ij}^n$ is the spatial difference operator. The correct operator used is derived using upwind schemes. For the curvature term, the spatial derivate of $\psi$ is taken as the centered difference approximation. If the constant velocity is assumed to be $1$, the spatial derivate of $\psi$ for that term, is approximated using upwind methods and is given by

$$\nabla_{ij}\psi_{ij}^n = (max(D_i^{-x}\psi,0)^2 + min(D_i^{+x}\psi,0)^2 + max(D_j^{-y}\psi,0)^2 + min(D_j^{+y}\psi,0)^2)^{1/2}$$

where $D_i^{+x}$ denotes the forward difference operator and $D_i^{-x}$ denotes the backward difference operator.

Other advantages of this formulation are that curve properties like normal and curvature can be obtained directly from the $\psi$ function and the method is easily extensible to higher dimensions.

The material presented in this section is laid out in more detail in [3,6].