A survey of PDE methods for image segmentation

Matt Hancock — Florida State University — Department of Mathematics

Image segmentation

Not in this talk

  • Simple intensity based methods
    • Thresholding
    • Region growing
    • Clustering
  • Edge-based
    • Watershed
  • Statistical methods
    • Active shape, active appearance models
    • Pixel / voxel - wise Classification
    • Markov random fields
  • etc ...

Basic idea of PDEs for segmentation

  • A curve on the image evolves according to some PDE.
  • At equilibrium, the curve represents the boundary of segmentation.


  • Ability to capture "true" segmentation
  • Free parameter choices
  • Stability
  • Smoothness
  • Topology

A simple model

  • Segment with parametric curve: $\displaystyle \begin{bmatrix} x(s,t) & y(s,t) \end{bmatrix}^T $
  • Curve velocity is in the direction of the outward normal, and has magnitude proportional to image pixel values: $$ \begin{bmatrix} x_t \\ y_t \end{bmatrix} = \hat{I}(x,y) \mathbf{n}(s,t) = \frac{\hat{I}(x,y)}{\sqrt{x_s^2 + y_s^2}}\begin{bmatrix} y_s \\ -x_s \end{bmatrix} $$
  • $\hat{I}(x,y) = S(G*I)(x,y; \sigma, \beta)$ is the image convolved with a gaussian filter with parameter $\sigma$ and processed with a sigmoidal filter with parameter, $\beta$.
  • Approximate PDE with finite differences.

Spiculated lung nodule from LIDC dataset

It works!

Sort of...


  • Sensitive to parameters of gaussian and sigmoidal filter.
  • Time step size? Curve parameter discretization?
  • How do we know when to stop evolving the curve?
  • Curve can't adapt to holes

Active contours (snakes) [1]

  • Again, segment via a parametrically defined curve, $\mathbf{c}(s)$.
  • Energy minimization principle: $$J[\mathbf{c}] = \int E[\mathbf{c}] ds = \int \left( E_{\text{int}}[\mathbf{c}] + E_{\text{ext}}[\mathbf{c}] \right) ds$$
  • Desired curve is $\displaystyle\text{arg}\min_{\mathbf{c}}J[\mathbf{c}]$.

[1]: Kass et. al. Snakes: Active contour models. International journal of computer vision. 1988

Active contours

  • Typically,$$E_{\text{int}}[\mathbf{c}] = \frac{1}{2}\left( \alpha ||\mathbf{c}'||^2 + \beta ||\mathbf{c}''||^2 \right) $$
  • and, $$E_{\text{ext}}[\mathbf{c}] = -\frac{\gamma}{2} ||\nabla (G*I)(\mathbf{c};\sigma)||^2$$
  • $\alpha,\beta,\gamma,\sigma$ are all free parameters

Minimizing the energy functional

  • Euler-Lagrange equations yield: $$\nabla E_{\text{ext}} - \alpha \mathbf{c}'' + \beta \mathbf{c}^{(4)} = 0 \tag{1}$$
  • Introduce "time" variable, set $(1) := F(t)$.
  • Set $\frac{\partial \mathbf{c}}{\partial t} = F(t)$, and discretize in $s$ and $t$ using finite differences.
  • At equilibrium, the Euler-Lagrange equations are satisfied.

It works!

Sort of...


  • Needs good initialization.
  • So many free parameters! How to set them?
  • Can't adapt to holes (without additional bookkeeping).

Level Sets [2]

  • Segmenting contour is the zero level set of an evolving surface: $$ \mathbf{c}(t) = \{\mathbf{x} \; | \; \psi(\mathbf{x},t) = 0 \}$$

[2]: Malladi, Sethian, Vemuri. Shape Modelling with Front Propagation: A level set approach. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1995

Motion of the surface

  • $\mathbf{x}(t)$ on contour $\Leftrightarrow \psi(\mathbf{x}(t), t) = 0$
  • $\mathbf{x}(t)$ moves normal to $\mathbf{c}(t)$ and $||\mathbf{x}_t|| = F(\mathbf{x}(t))$
  • So, $$\psi_t + F(\mathbf{x}) ||\nabla \psi|| = 0$$ governs the motion of the surface, and its implicitly defined contour.

Controlling the speed

  • Speed is governed by a combination of image attributes and by the geometry of the curve
  • Let $F = F_A + F_G$
  • Often, $$\begin{align*} F_A &= F_A( ||\nabla (G * I)(\mathbf{x};\sigma)|| ) \\ F_G &= F_G(K) \end{align*}$$


  • Contours easily split and merge.
  • No conceptual differences in extending to 3 dimensions.


  • Same as other methods: stability, parameter setting, etc...

Other PDE methods not discussed

  • Caselles, Vicent, Ron Kimmel, and Guillermo Sapiro. "Geodesic active contours." International journal of computer vision 1997
  • Vese, Luminita A., and Tony F. Chan. "A multiphase level set framework for image segmentation using the Mumford and Shah model." International journal of computer vision 2002
  • Álvarez, Luis, et al. "Morphological snakes." Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010.

... this is the last slide