Gradient vector flow

Gradient vector flow (GVF), a computer vision framework introduced by Chenyang Xu and Jerry L. Prince , is the vector field that is produced by a process that smooths and diffuses an input vector field, and is usually used to create a vector field that points to object edges from a distance. It's widely used in object tracking, shape recognition, segmentation, and edge detection. In particular, it's commonly used in conjunction with active contour model.

Results from Gradient Vector Flow algorithm applied to 3-D Metasphere data

Background

Finding objects or homogeneous regions in images is a process known as image segmentation. In many applications, the locations of object edges can be estimated using local operators that yield a new image called an edge map. The edge map can then be used to guide a deformable model, sometimes called an active contour or a snake, so that it passes through the edge map in a smooth way, therefore defining the object itself.

A common way to encourage a deformable model to move toward the edge map is to take the spatial gradient of the edge map, yielding a vector field. Since the edge map has its highest intensities directly on the edge and drops to zero away from the edge, these gradient vectors provide directions for the active contour to move. When the gradient vectors are zero, the active contour will not move, and this is the correct behavior when the contour rests on the peak of the edge map itself. However, because the edge itself is defined by local operators, these gradient vectors will also be zero far away from the edge and therefore the active contour will not move toward the edge when initialized far away from the edge.

Gradient vector flow (GVF) is the process that spatially extends the edge map gradient vectors, yielding a new vector field that contains information about the location of object edges throughout the entire image domain. GVF is defined as a diffusion process operating on the components of the input vector field. It is designed to balance the fidelity of the original vector field, so it is not changed too much, with a regularization that is intended to produce a smooth field on its output.

Although GVF was designed originally for the purpose of segmenting objects using active contours attracted to edges, it has been since adapted and used for many alternative purposes. Some newer purposes including defining a continuous medial axis representation, regularizing image anisotropic diffusion algorithms, finding the centers of ribbon-like objects, constructing graphs for optimal surface segmentations, creating a shape prior, and much more.

Theory

The theory of GVF was originally described in. Let $\textstyle f(x,y)$ be an edge map defined on the image domain. For uniformity of results, it is important to restrict the edge map intensities to lie between 0 and 1, and by convention $\textstyle f(x,y)$ takes on larger values (close to 1) on the object edges. The gradient vector flow (GVF) field is given by the vector field $\textstyle \mathbf {v} (x,y)=[u(x,y),v(x,y)]$ that minimizes the energy functional

$${\mathcal {E}}=\iint _{\mathbb {R} ^{2}}|\nabla f|^{2}|\mathbf {v} -\nabla f|^{2}+\mu (u_{x}^{2}+u_{y}^{2}+v_{x}^{2}+v_{y}^{2})\,dx\,dy\,.$$

1

In this equation, subscripts denote partial derivatives and the gradient of the edge map is given by the vector field $\textstyle \nabla f=(f_{x},f_{y})$. Figure 1 shows an edge map, the gradient of the (slightly blurred) edge map, and the GVF field generated by minimizing $\textstyle {\mathcal {E}}$.

Fig. 1. An edge map (left) describes the boundary of an object. The gradient of the (slightly blurred) edge map (center) points towards the boundary, but is very local. The gradient vector flow (GVF) field (right) also points towards the boundary, but has a much larger capture range.

Equation 1 is a variational formulation that has both a data term and a regularization term. The first term in the integrand is the data term. It encourages the solution $\textstyle \mathbf {v}$ to closely agree with the gradients of the edge map since that will make $\textstyle \mathbf {v} -\nabla f$ small. However, this only needs to happen when the edge map gradients are large since $\textstyle \mathbf {v} -\nabla f$ is multiplied by the square of the length of these gradients. The second term in the integrand is a regularization term. It encourages the spatial variations in the components of the solution to be small by penalizing the sum of all the partial derivatives of $\textstyle \mathbf {v}$. As is customary in these types of variational formulations, there is a regularization parameter $\textstyle \mu >0$ that must be specified by the user in order to trade off the influence of each of the two terms. If $\textstyle \mu$ is large, for example, then the resulting field will be very smooth and may not agree as well with the underlying edge gradients.

Theoretical Solution. Finding $\textstyle \mathbf {v} (x,y)$ to minimize Equation 1 requires the use of calculus of variations since $\textstyle \mathbf {v} (x,y)$ is a function, not a variable. Accordingly, the Euler equations, which provide the necessary conditions for $\textstyle \mathbf {v}$ to be a solution can be found by calculus of variations, yielding

$$\mu \nabla ^{2}u-(u-f_{x})(f_{x}^{2}+f_{y}^{2})=0\,,$$ 2a

$$\mu \nabla ^{2}v-(v-f_{x})(f_{x}^{2}+f_{y}^{2})=0\,,$$ 2b

where $\textstyle \nabla ^{2}$ is the Laplacian operator. It is instructive to examine the form of the equations in (2). Each is a partial differential equation that the components $u$ and $v$ of $\mathbf {v}$ must satisfy. If the magnitude of the edge gradient is small, then the solution of each equation is guided entirely by Laplace's equation, for example $\textstyle \nabla ^{2}u=0$, which will produce a smooth scalar field entirely dependent on its boundary conditions. The boundary conditions are effectively provided by the locations in the image where the magnitude of the edge gradient is large, where the solution is driven to agree more with the edge gradients.

Related Concepts

• Deformable models
• Active contour model
• Snakes: Active Contours, CVOnline
• Edge detection