# DEFORMABLE MODELS FOR IMAGE SEGMENTATION

Jussi Tohka
Signal Processing Laboratory
Tampere University of Technology

### MOTIVATION AND BACKGROUND

• A problem is well-posed if
1. the solution exists
2. the solution is unique
3. 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 CO  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 CO that minimizes the energy function

where Eimage is energy term that depends on underlying image, Einternal 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 pi = (xi,yi). If contours are closed index arithmetic is modulo N + 1, i.e. p0 is the successor of pN.
• The energy of each contour is defined point wise
• Position of each point pi can be predicted from the positions of its neighbours pi-1 and pi+1. The internal energy of pi 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 C1 about the energy minimizing contour CO
•  Minimize the energy starting from C1. Call the result C2.
•  See if  the given convergence criterion is satisfied.
• If yes, then set CO <- C2.
If no, then make some adjustments, e.g. resolution change, set C1 <- C2, 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.