Gradient vector flow explained

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

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 anactive 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 containsinformation about the location of object edges throughout the entire image domain. GVF is defined as a diffusion process operating on thecomponents 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 sinceadapted and used for many alternative purposes. Some newer purposes including defining a continuous medial axis representation,^[3] regularizing image anisotropic diffusion algorithms,^[4] finding the centers of ribbon-like objects,^[5] constructing graphs for optimal surface segmentations,^[6] creating a shape prior,^[7] and much more.

Theory

The theory of GVF was originally described by Xu and Prince. Let

style 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 style 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 style v (x,y) = [u(x,y),v(x,y)] that minimizes the energy functionalIn this equation, subscripts denote partial derivatives and the gradient of the edge map is given by the vector field style \nabla f = (f _{x,} f _{y)} . Figure 1 shows an edge map, the gradientof the (slightly blurred) edge map, and the GVF field generated byminimizing style l{E} .

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

style v to closely agree with the gradients of the edge map since that will make style v - \nabla f small. However, this only needs to happen when the edge map gradients are large sincestyle 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 partialderivatives of style v . As is customary in these types of variational formulations, there is a regularization parameter style\mu > 0 that must be specified by the user in order to trade off the influence of each of the two terms. If style\mu is large, for example, then the resulting field will be very smooth and may not agree as wellwith the underlying edge gradients.

Theoretical Solution. Finding

style v (x,y) to minimize Equation 1requires the use of calculus of variations since style v (x,y) is a function, not a variable. Accordingly, the Euler equations, which provide the necessary conditions for style v to be a solution can be found by calculus of variations, yielding where style\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 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 style\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.

Computational Solutions. There are two fundamental ways to compute GVF. First, the energy function

l{E} itself (1) can be directly discretized and minimized, for example, by gradient descent. Second, the partial differential equations in (2) can be discretized and solved iteratively. The original GVF paper used an iterativeapproach, while later papers introduced considerably faster implementations such as an octree-based method,^[8] a multi-grid method,^[9] and an augmented Lagrangian method.^[10] In addition, very fast GPU implementations have been developed in^{[11] [12]}

Extensions and Advances. GVF is easily extended to higher dimensions. The energy function is readily written in a vector form as which can be solved by gradient descent or by finding and solving itsEuler equation. Figure 2 shows an illustration of a three-dimensional GVF field on the edge map of a simple object (see ^[13]).

The data and regularization terms in the integrand of the GVF functional can also be modified. A modification describedin ,^[14] called generalized gradient vector flow (GGVF) defines two scalar functions and reformulates the energy as While the choices

style g(\nabla f|) = \mu and style h(|\nabla f|) = |\nabla f| ^{2} reduce GGVF to GVF, the alternative choices style g(|\nabla f|) = \exp\{ - |\nabla f|/K\} and style h(\nabla f|) = 1 - g(|\nabla f|) , for K a user-selected constant, can improve the tradeoff between the data term and its regularization in some applications.

The GVF formulation has been further extended to vector-valued images in ^[15] where a weighted structure tensor of a vector-valued image is used. A learning based probabilistic weighted GVF extension was proposed in ^[16] to further improve the segmentation for images with severely cluttered textures or high levels of noise.

The variational formulation of GVF has also been modified in motion GVF (MGVF) to incorporate object motion inan image sequence.^[17] Whereas the diffusion of GVF vectors from a conventional edge map acts in an isotropic manner, the formulation of MGVF incorporates the expected object motion between image frames.

An alternative to GVF called vector field convolution (VFC) provides many of the advantages of GVF, has superior noise robustness, andcan be computed very fast.^[18] The VFC field

style v _{VFC} is defined as the convolution of the edge map f with a vector field kernel k where

Notes and References

1. Xu . C. . Prince . J.L. . Gradient Vector Flow: A New External Force for Snakes . Proc. IEEE Conf. on Comp. Vis. Patt. Recog. (CVPR) . Los Alamitos . Comp. Soc. Press . 66–71 . June 1997 .
2. Snakes, Shapes, and Gradient Vector Flow. IEEE Transactions on Image Processing . 7. 3. 359–369. 1998. Xu . C.. Prince . J.L. .
3. Variational curve skeletons using gradient vector flow . IEEE Transactions on Pattern Analysis and Machine Intelligence . 31. 12. 2257–2274. 2009. Hassouna . M.S.. Farag . A.Y. .
4. GVF-based anisotropic diffusion models . IEEE Transactions on Image Processing . 15 . 6 . 1517–1524 . 2006 . Yu . H. . Chua . C.S. .
5. CRUISE: cortical reconstruction using implicit surface evolution . NeuroImage . 23 . 3 . 997–1012 . 2004 . Han . X. . Pham . D.L. . Tosun . D. . Rettmann . M.E. . Xu . C. . Prince . J.L. . etal .
6. Incorporation of gradient vector flow field in a multimodal graph-theoretic approach for segmenting the internal limiting membrane from glaucomatous optic nerve head-centered SD-OCT volumes . Computerized Medical Imaging and Graphics . 55 . 87–94 . 2017 . Miri . M.S. . Robles . V.A. . Abràmoff . M.D. . Kwon . Y.H. . Garvin . M.K..
7. Optimal multi-object segmentation with novel gradient vector flow based shape priors . Computerized Medical Imaging and Graphics . 69 . 96–111 . 2018 . Elsevier . Bai . J. . Shah . A. . Wu . X..
8. Silhouette and stereo fusion for 3D object modeling . Computer Vision and Image Understanding . 96 . 3 . 367–392 . 2004 . Elsevier . C. H. . Esteban . F. . Schmitt.
9. Fast numerical scheme for gradient vector flow computation using a multigrid method . IET Image Processing . 2007 . 1 . 48–55 . 1 . X. . Han . C. . Xu . J.L. . Prince.
10. Fast gradient vector flow computation based on augmented Lagrangian method . Ren . D. . Zuo . W. . Zhao . X. . Lin . Z. . Zhang . D. . Pattern Recognition Letters . 34 . 2 . 219–225 . 2013 . Elsevier.
11. Real-time gradient vector flow on GPUs using OpenCL . Smistad . E. . Elster . A.C. . Lindseth . F. . Journal of Real-Time Image Processing . 10 . 1 . 67–74 . 2015 . Springer.
12. Multigrid gradient vector flow computation on the GPU . Smistad . E. . Lindseth . F. . Journal of Real-Time Image Processing . 12 . 3 . 593–601 . 2016 . Springer.
13. Book: C. . Xu . X. . Han . J.L. . Prince . Gradient Vector Flow Deformable Models . Handbook of Medical Image Processing and Analysis . Academic Press . 2008 . Isaac Bankman . 181–194 . 2nd .
14. C. . Xu . J.L. . Prince . Generalized gradient vector flow external forces for active contours . Signal Processing . 1998 . 71 . 131–139 . 2.
15. Variational segmentation of vector-valued images with gradient vector flow . IEEE Transactions on Image Processing . 23 . 11 . 4773–4785 . 2014 . Jaouen . V. . Gonzalez . P. . Stute . S. . Guilloteau . D. . Chalon . S. . etal.
16. Phase-based probabilistic active contour for nerve detection in ultrasound images for regional anesthesia . Computers in Biology and Medicine . 52 . 88–95 . 2014 . Hafiane . A. . Vieyres . P. . Delbos . A..
17. Motion gradient vector flow: An external force for tracking rolling leukocytes with shape and size constrained active contours . IEEE Transactions on Medical Imaging . 2004 . 23 . 1466–1478 . 12 . Ray . N. . Acton . S.T..
18. Active contour external force using vector field convolution for image segmentation . IEEE Transactions on Image Processing . 2007 . 16 . 2096–2106 . 8 . Li . B. . Acton . S.T..