Seminar report: Active Contour Models

By : Li Huang (ID:01552457)&Erdong Cheng(ID:00272027) 159.731 Machine Vision

------

Seminar report : Active Contour Models
(Snakes)

By : Li Huang (ID : 01552457)

Erdong Cheng (ID : 00272027)

1 Introduction

Active contours or snakes are computer-generated curves that move within images to find object boundaries. They are often used in computer vision and image analysis to detect and locate objects, and to describe their shape. For example, a snake might be used edge detection, corner detection, motion tracking, and stereo matching; one might be used to find the outline of an organ in a medical image; or one might be used to automatically identify characters on a postal letter.

1.1 What is a Snake?

The concept of snakewas first introduced in1988 [9] and has later been developed by different researchers. A snake is an energy-minimizing spline guided by external constraint forces and influenced by image forces that pull it toward feature such as lines and edges. Snake are active contour models: they lock onto nearby edges, localizing them accurately. Scale-space continuation can be used to enlarge the capture region surrounding a feature. Snakes provide a unified account of a number of visual problems, including detection of edges, lines, and subjective contours; motion tracking; and stereo matching.

1.2Applications

  • Actor driven facial animation.

  • Traffic monitoring – time to collision.

  • Medical Diagnosis.

1.3 Procedure

1.3.1. Initialization

Place the snake near the contour of interest

• Discrete initialisation => Control points (e.g. spline)

• Enough control points

1.3.2 Evolution

Snake shape and location affected by forces iteratively

• Internal forces

• Image forces

• External constraint forces

Internal contour forces

Make the snake tend to be more continuous and smooth

Image forces

Draws the contour towards the closest image edges.

External forces

Force the snake in some a priori known direction or shape.

2Basic Snake Behaviour

The basic snake model is a controlled continuity spline under the influence of image forces and external constraint forces. The internal spline forces serve to impose a piecewise smoothness constraint. The image forces push the snake toward salient image feature like lines, edges, and subjective contours. The external constraint forces are responsible for putting the snake near the desired local minimum. These forces can, for example, come from a user interface, automatic attentional mechanisms, or high-level interpretations.

Representing the position of a snake parametrically by v(s) = (x(s), y(s)), To obtain the best fit between the snake and the object, we minimise the energy. Specifically, a snake is defined as

Where represent the internal energy of the spline due to bending,gives rise to the image forces, and gives rise to the external constraint forces.

External and image forces which determine the snake

2.1Internal Energy

The internal energy provides a smoothness constraint. This can be further defined as

The spline energy is compose of a first-order term controlled by α(s) and a second-order term controlled by β(s). The first-order term makes the snake act like a membrane and the second-order term makes it act like a thin plate. Adjusting the weights α(s) and β(s) controls the relative importance of the membrane and thin-plate terms. If β(s) = 0 then the function is discontinuous in its tangent, i.e. it may develop a corner at that point. If α(s) = β(s) = 0 then this also allows a break in the contour, a positional discontinuity.

called Continuity Force (minimize the distance between points)

called Curvature Force (enforce smoothness and avoid oscillation of the snake)

2.2Image Forces

In order to make snakes useful for early vision we need energy functionals that attract them to salient features in images. In this section, we present three different energy functionals which attract a snake to lines, edges, and terminations. The total image energy can be expressed as a weighted combination of the three energy functionals.

By adjusting the weights, a wide range of snake behavior can be created.

2.2.1 Line Functional

The simplest useful image functional is the image intensity itself. If we set

then depending on the sign of , the snake will be attracted either to light lines or dark lines. Subject to its other constraints, the snake will try to align itself with the lightest or darkest nearby contour.

2.2.2Edge Functional

Finding edges in an image can also be done with a very simple energy functional. If we set . then the snake is attracted to contour with large image gradients. An example of the use of this functional is shown in figure. In the upper left, a user has placed two snakes on the edges of the pear and potato. He has then pulled part of the snake off the pear with a spring. The remaining pictures show what happens when he lets go. The snake snaps back rapidly to the boundary of the pear.

2.2.3Termination Functional

The termination functional allows terminations (i.e. free ends of lines) or corners to attract the snake. (Consider the perception of illusory contours.). In order to find terminations of line segments and contours, we use the curvature of level lines in a slightly smoothed image. Let be a slightly smoothed

version of the image. Let be the gradient angle and let

and be unit vectors along and perpendicular to the gradient direction . Then the curvature of the level contour in C( x, y) can be written

By combining and we can create a snake that is attracted to edges or terminations. Figure shows an example of such a snake exposed to a standard subjective contour.

Right: Standard subjective contour illusion.

Left: Edge/termination snake in equilibrium on the subjective contour

Above left: Dynamic subjective contour illusion. (Sequence is left to right, top to bottom. Above Right: Snake attracted to edges and terminations. As moving horizontal line slides to the right, the snake bends until it falls off the lines. Bringing the line close enough makes the snake reattach.

2.3 External Forces

The external energy function attracts the deformable contour to interesting features, such as object boundaries, in an image. Any energy expression that accomplishes this attraction can be considered for use.

Image gradient and intensity are obvious (and easy) characteristics to look at (another could be object size or shape). Therefore, the following external energy function is investigated:

where is an expression that attracts the contour to high or low intensity regions and is an energy term that moves the contour towards edges. Again, the constants, and , are provided to adjust the relative weights of the terms.

Image Intensity Energy

Each element in the intensity energy matrix, is assigned the intensity value of the corresponding image point in the neighborhood of :

Then, if is positive, the contour is attracted to regions of low intensity and vice-versa.

Image Gradient Energy

The image gradient energy function attracts the deformable contour to edges in the image. An energy expression proportional to the gradient magnitude will attract the contour to any edge:

When active contours are used to find object boundaries, an energy expression that discriminates between edges of adjacent objects is desirable. The key to such an expression is that the gradients at the edges of the objects have different directions. Further, the direction of the gradient at the object's edge should be similar to the direction of the unit normal of the contour. This situation is illustrated in Figure .


Figure : An example of the movement of a deformable contour due to gradient energy. Because the gradient direction at the edge of the object of interest is similar to the outward unit normal direction of the contour, the active contour algorithm moves the snake point from to even though the gradient magnitudes at both points are similar.

The value for each element in the directional gradient energy matrix, , can therefore be defined by a dot product between the unit normal of the deformable contour and the image gradient:

where is the unit normal of the contour at point .

3 advantages and disadvantages of snakes

Snakes have several advantages over classical feature extraction techniques:

  • They can be controlled interactively by using appropriately placed springs and volcanoes.
  • They are easy to manipulate because the external image forces behave in an intuitive manner.
  • They are autonomous and self-adapting in their search for a minimal energy state.
  • They can be made sensitive to image scale by incorporating Gaussian smoothing in the image energy function.
  • They are relatively insensitive to noise and other ambiguities in the images because the integral operator is an inherent noise filter.
  • They can be used to track dynamic objects in temporal as well as the spatial dimensions.

Snakes are not without their drawbacks, chief among which are the following:

  • They can often get stuck in local minima states; this may be overcome by using simulated annealing techniques at the expense of longer computation times.
  • They often overlook minute features in the process of minimizing the energy over the entire path of their contours.
  • Their accuracy is governed by the convergence criteria used in the energy minimization technique; higher accuracies require tighter convergence criteria and hence, longer computation times.

3Conclusion

  • Low-level” feature detection processes are effective up to a point but cannot be expected to retrieve entire geometric structures.
  • Snakes are becoming increasingly effective.

–Edges, lines, and contours can all be found by essentially the same mechanism.

–Motion tracking and stereo matching can be done in the same framework.

References:

Page 1 of 10