## A survey of PDE methods for image segmentation

Matt Hancock — Florida State University — Department of Mathematics

### 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.

## Issues

• 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.

### Issues

• 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.

### Issues

• 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.