DEFORMABLE MODELS FOR IMAGE SEGMENTATION

Jussi Tohka

Signal Processing Laboratory

Tampere University of Technology

MOTIVATION AND BACKGROUND

A problem is well-posed if

the solution exists
the solution is unique
the solution depends continuously on the data

If even one of these conditions are not satisfied the problem is ill-posed (in the sense of Hadamard). Image segmentation can be seen as an ill-posed inverse problem due to the noise, lack of contrast and boundary discontinuities.
The general idea of solving ill-posed problems is to restore well-posedness of the problem by introducing some constraints, implicit and explicit, to the solution. This is often termed as regularization of the problem and it has close connections to Bayesian estimation.
See an informal example of ill-posed problems and regularization.

DEFORMABLE MODELS

We shall consider following problem:

P1 : Find the contour C_O that surrounds the known object O from an image I.

Note that the exact shape of O is not known. That is, fitting rigid contour models (registration) is not possible. Also location and orientation of O in an image I is unknown.

As said object O does not usually have clear boundary, so straightforward approaches using edge detectors or other local operators would lead to trouble.

In the framework of deformable models and regularization P1 is reformulated as

P2: Find the contour C_Othat minimizes the energy function

where E_imageis energy term that depends on underlying image, E_internal is the regularization term that depends only on the shape of the C, and is the regularization parameter that weights the two energy types.

Above formula captures the essence of deformable models that is quite the same than the idea of Bayesian Maximum A Posteriori (MAP) estimation. Indeed, deformable models can, with suitable assumptions, be put into a probabilistic framework and then it turns out that minimizing the energy of the contour is equivalent with finding the contour that maximizes certain a posteriori probability.

To actually do some computations we have to fix a representation for the arbitrary contour C. There are basically three types of representations available:

Parametrized or explicit: C is defined as a parametrized curve c(s) = (x(s),y(s)), where s varies over a certain interval, say [0,1].

Implicit: C is defined as trough level sets of implicit function i.e.

Discrete: C is just an ordered set of points, which are though to form a polygonal line.

Parametrized representation leads to `snakes' in their traditional formulation. They however rely on user interaction, and as such are not very suitable for fully automated target extraction.

We shall next take a deeper look into discrete representation.

DISCRETE SNAKES

A contour is an ordered set of discrete points on the plane, i.e.

where p_i= (x_i,y_i). If contours are closed index arithmetic is modulo N + 1, i.e. p₀is the successor of p_N.

The energy of each contour is defined point wise

Position of each point p_ican be predicted from the positions of its neighbours p_i-1and p_i+1. The internal energy of p_i is then the squared prediction error

where the simple prediction

is used.

l(C) measures the length of the contour C. Its main function is to yield scale invariant internal energy. The internal energy is usually also translation and rotation invariant.
Image energy at each point pi is related to the properties of image in that particular point. Interesting properties are, for example, intensity of image and intensity change of the image. Assume now that we interested in edges in the image. If the intensity of the image is given by I(p) in each point then

where denotes some edge operator (e.g. Sobel).

ENERGY MINIMIZATION

In order to find the desired contour surrounding the object O we still have to minimize the defined energy. This is not an easy thing to do, because the external energy function is typically highly nonlinear, and we would like to find the global minimum or at least a strong local minimum.
Overall scheme can be iterative:

Make an initial guess C₁ about the energy minimizing contour C_O
Minimize the energy starting from C₁. Call the result C₂.
See if the given convergence criterion is satisfied.

If yes, then set C_O<- C₂.

If no, then make some adjustments, e.g. resolution change, set C₁<- C₂, and go to step 2.

Several methods have been used for minimization, for example greedy-type algorithms, dynamic programming, genetic algorithms, hopfield networks and simulated annealing with (when suitable) different kind of iteration techniques.

CONCLUDING REMARKS

In the web poster deformable models are presented in general terms. There exists quite different types of deformable models and to see that interested reader is referred to survey articles mentioned in the literature part. Only two-dimensional models are reviewed all tough three-dimensional deformable models are widely used in medical image segmentation, for example. While the three-dimensional deformable models are straight-forward generalizations of the two-dimensional ones at the conceptual level, there are some difficulties, which make 3-D models more complex than 2-D ones.
Also we have dealt only with energy-minimizing deformable models. There exists another scheme in which contours are influenced by internal and external forces acting similarly than internal and external energy. These two approaches are, however, related: If the energy function is formulated in terms of the calculus of variations as in the original snake-model then the contour of the minimal energy satisfies the corresponding Euler-Lagrange differential equation, and we get an evolution equation for the contour.

See some nice examples by Xu. These are related to parametric and implicit force based deformable models, but simulations with energy minimizing models are quite similar.

SOME LITERATURE

Last modified 30.10.2000 by Jussi Tohka