GVF Snake Segmentation

6 min readApr 19, 2021

Introduction

The development of active contour models (snakes) results from the work of Kass et al. and they offer a solution to a variety of tasks in image analysis and machine vision. The active contour model, or snake, is defined as an energy-minimizing spline — the snake’s energy depends on its shape and location within the image. Local minima of this energy then correspond to desired image properties.

Snakes do not solve the entire problem of finding contours in images; rather, they depend on other mechanisms such as interaction with user, interaction with some higher level image understanding process, or information from image data adjacent in time or space. This interaction must specify an approximate shape and starting position for the snake somewhere near the desired contour. A priori as well as image-based information are then used to push the snake toward an appropriate solution. The energy functional which is minimized is a weighted combination of internal and external forces. The internal forces emanate from the shape of the snake, while the external forces come from the image and/or from higher-level image understanding processes.

The snake is defined parametrically as v(s) = [x(s),y(s)], where x(s), y(s) are x, y coordinates along the contour and sϵ[0, 1].

The energy functional to be minimized is written as

where,

E_image is derived from the image data over which the snake lies. It is a weighted combination of three different functional which attract the snake to lines, edges and terminations.

where f(x,y) denotes image gray-levels at image location (x,y) . The sign of w_line specifies whether the snake is attracted to light or dark lines.

The edge-based functional attracts the snake to contours with large image gradients -that is, to locations of strong edges.

Now, line terminations and corners may influence the snake using a weighted energy functional E_term. Let g be a slightly smoothed version of the image f, let φ (x,y) denote the gradient directions along the spline in the smoothed image g. Let
n(x, y) = (cos φ(x, y), sin φ(x, y))
nR(x, y) = (- sin φ(x , y), cos φ(x ,y ))
be unit vectors along and perpendicular to the gradient directions. Then the
curvature of constant-gray-level contours in the smoothed image can be written as

Then, from the calculus of variations, the Euler-Lagrange condition states that the spline v(s) which minimizes E*snakc must satisfy

where E_vs is the partial derivative of E with respect to dv/ds and E_v is the partial derivative of E with respect to v.

Two main limitations common to these approaches are the requirement of snake initialization being close to the desired solution, and difficulties in segmenting concave portions of the boundary. To overcome these problems, gradient vector flow (GVF) fields and their use in snake image segmentation have been reported in literature.

Gradient Vector Flow Snake

In paper, Xu and Prince discussed the shortcomings of the original snake and distance snake from the external force field construction. The external force field, for the original and distance snake, is irrotational and based on the contour points and the closest edge points in the contour points’ normal direction. This limits the deformation into boundary concavities because there is no external force pointing into the concavities inside. GVF snake constructs a new external force field which is not entirely irrotational, which means the new external force points inside in concavities. Additionally, the magnitudes of the external force are the same over the whole image (field), which means a large capture range for the gradient vector flow (GVF) snake.

The GVF snake has a new external force: F(v)= (α(x,y),β(x,y)) and F(v) can be obtained by minimizing the energy functional

Where f is an edge map of the input image I, and μ is a regularization parameter. Using the variational method, F can be found by solving the following Euler equations

Algorithm for Implementation

Getting image, manual selection of initial contour points near to the object of interest for segmentation, formation of ‘Settings’ structure in MATLAB for setting up of parameters, to be used for snake movement, which will take place until that object of interest is segmented.
Run a subroutine through main program where interpolation of initial contour points is done. For this number of desired contour points is specified in the Settings structure.
Movement of snake is determined by the energy variation in the image. Energy comprises of internal energy (contour elasticity, stiffness and balloon forces) and external energy (weighted combination of 3 different energy functional based on attraction towards lines, edges and terminations). Now a contour is said to have minimum energy when it is located across the boundary of object of interest. So, both energy counterparts are first calculated and then the contour for which minimum overall energy exists is the boundary of the object.
External Force Image is developed. It comprises of application of gaussian filters-derivatives to the image, with sigma controlled in Settings. These derivatives are applied in both directions over the image coordinate system. These derivatives are then used with weights of lines, edges and terminations to get the external force image.
Derivative with new sigma (gsigma) is applied over this external energy image to get the gradient of the edge energy image.
The above calculated external force image is then optimised using Gradient Vector Flow (GVF). For this, number of GVF iterations is first specified in Settings and is used to determine how many times the gradient vector field is updated. Laplacian of external force image is done and used in the formula for GVF energy calculation as described in the
literature.
Now, internal forces of the contour is calculated. Internal forces are responsible for elasticity, stiffness and balloon like behaviour of snake. Parameters used are alpha and beta for elasticity and stiffness respectively. They are first order and second order parameters respectively. Gamma is used to weight the balloon force on the contour points.
The position of the contour is updated everytime with the corresponding combined energy of that contour, until the snake movement stops at the point where the overall energy is minimum. This contour determines the boundary of the object to be segmented.
Binary image of segmented object is made and displayed.