java.lang.Object
- java.lang.Thread
- - gov.nih.mipav.model.algorithms.AlgorithmBase
  - - gov.nih.mipav.model.algorithms.AlgorithmGVF

All Implemented Interfaces:

AlgorithmInterface, java.awt.event.ActionListener, java.awt.event.WindowListener, java.lang.Runnable, java.util.EventListener
```
public class AlgorithmGVF
extends AlgorithmBase
implements AlgorithmInterface
```
Snake-like algorithm derivative using BSplines. The algorithm is supplied a polygon (VOI - contour) and that polygon is allowed to evolve to edge of the object generated by calculating the the gradient vector field. The user/programmer supplies the sigmas (scales) at which to calculate the edge map f = |grad(Gsigma(x,y)*I(x,y))|
2 iterative processes are used. The first calculates the gradient vector field. The gradient of the edge map is used to initialize the iterative equation for the gradient vector field. In the second iterative process which calculates the boundary, the point is moved by the gradient vector field

This original GVF algorithm has:
u[i] += mu*del2(u[i]) - Math.sqrt(fx[i]*fx[i] + fy[i]*fy[i])*(u[i] - fx[i]);
v[i] += mu*del2(v[i]) - Math.sqrt(fx[i]*fx[i] + fy[i]*fy[i])*(v[i] - fy[i]);
This program uses the generalized GVF algorithm with:
du/dt = g(|grad f|)del2xy(u) - h(|grad f|)*(u - fx) dv/dt = g(|grad f|)del2xy(v) - h(|grad f|)*(v - fy) g[i] = Math.exp(-(fx[i]*fx[i] + fy[i]*fy[i])/(k*k))
h[i] = 1 - g[i] du/dt = u(i,j,n+1) - u(i,j,n)/(delta t) del2xy(u) = (1/((delta x)(delta y)))* (u(i+1,j,n) + u(i,j+1,n) + u(i-1,j,n) + u(i,j-1,n) - 4u(i,j,n) = del2(u)/((delta x)*(delta y)) u(i,j,n+1) = u(i,j,n) + g(|grad f|)*(delta t)/((delta x)*(delta y)) * del2(u) - (1 - g(|grad f|)*(u - fx)*delta t Letting detla x = 1, delta y = 1, and delta t = 0.25: u[i] += 0.25f*(g[i]*del2(u[i]) - (1 - g[i])*(u[i] - fx[i]));
v[i] += 0.25f*(g[i]*del2(v[i]) - (1 - g[i])*(v[i] - fy[i]));
Stability for the original GVF algorithm requires mu <= 0.25f and stability for the generalized GVF algorithm requires that delta t <= (delta x * delta y)/(4 * gmax) = 1/4. For 3D: delta t <= (delta x * delta y * delta z)/(6* gmax) = 1/6.

A large scale slows the snake and causes the snake to conform to large scale structure. A small sigma value causes the snake to conform to the small scale structure is therefore more sensitive to noise. The three-dimensional version is really a two-and-half dimensional algorithm where resultant contour in a slice is projected into the adjacent slice and is used as an initialization to the evolution in the new slice.

Useful references on gradient vector field:
1.) "Gradient Vector Flow: A New External Force For Snakes", Chenyang Xu and Jerry L. Prince, IEEE Proc. Conf. on Comp. Vis. Patt. Recog. (CVPR'97), pp. 66- 71.
2.) "Snakes, Shapes, and Gradient Vector Flow", Chenyang Xu and Jerry L. Prince, IEEE Transactions on Image Processing, March, 1998, pp. 359-369.
3.) "Generalized gradient vector flow external forces for active contours", Chenyang Xu and Jerry Prince, Signal Processing, 71(2), December, 1998, pp. 131-139.
4.) "Gradient Vector Flow Deformable Models", Handbook of Medical Imaging, ChenYang Xu and Jerry Prince, edited by I. Bankman, Academic Press, 2000, pp. 159-169.
5.) "Image Segmentation Using Deformable Models", Handbook of Medical Imaging -- Volume 2: Medical Imaging and Analysis, Chenyang Xu, Dzung Pham, and Jerry Prince, edited by J.M. Fitzpatrick and M. Sonka, SPIE Press, May, 2000, pp. 129-174.
More information on gradient vector field can be found at Chenyang Xu's homepage at http://iacl.ece.jhu.edu/~chenyang

See Also:

GenerateGaussian

Nested Class Summary
- Nested classes/interfaces inherited from class java.lang.Thread
  java.lang.Thread.State, java.lang.Thread.UncaughtExceptionHandler

Field Summary

Fields
Modifier and Type	Field	Description
`private int`	`boundaryIterations`	Maximum iterations to generate new boundary.
`private boolean`	`do25D`	Only applies to 3D, if true do slice by slice.
`private float[]`	`expGvfBuffer`	DOCUMENT ME!
`private int[]`	`extents`	DOCUMENT ME!
`private float[]`	`fx`	DOCUMENT ME!
`private float[]`	`fy`	DOCUMENT ME!
`private float[]`	`fz`	DOCUMENT ME!
`private float[]`	`gVal`	DOCUMENT ME!
`private float[]`	`gvfBuffer`	DOCUMENT ME!
`private int`	`gvfIterations`	Maximum iterations to generate generalized gradient vector field.
`private float[]`	`GxData`	Storage location of the first derivative of the Gaussian in the X direction.
`private float[]`	`GyData`	Storage location of the first derivative of the Gaussian in the Y direction.
`private float[]`	`GzData`	Storage location of the first derivative of the Gaussian in the Z direction.
`private int[]`	`kExtents`	Dimensionality of the kernel.
`private float`	`kValue`	In the paper "Generalized gradient vector flow external forces for active contours" by Chenyang Xu and Jerry Prince values of 0.05, 0.15, and 0.2 were used for k.
`private int`	`length`	DOCUMENT ME!
`private float[]`	`outputBuffer`
`private boolean`	`propagationFlag`	If true propagate the contour to an adjacent slice.
`private VOI`	`resultVOI`	The resultant polygon and the evolution has completed.
`private float[]`	`sigmas`	Standard deviations of the gaussian used to calculate the kernels.
`private VOI`	`srcVOI`	The initial VOI to initialize the evolution process.
`private int`	`stSlice`	Starting slice to evolve contour.
`private float[]`	`uVal`	DOCUMENT ME!
`private float[]`	`vVal`	DOCUMENT ME!
`private float[]`	`wVal`	DOCUMENT ME!
`private int`	`xDim`	DOCUMENT ME!
`private int`	`yDim`	DOCUMENT ME!
`private int`	`zDim`	DOCUMENT ME!

Fields inherited from class gov.nih.mipav.model.algorithms.AlgorithmBase
destFlag, destImage, image25D, mask, maxProgressValue, minProgressValue, multiThreadingEnabled, nthreads, progress, progressModulus, progressStep, runningInSeparateThread, separable, srcImage, threadStopped

Fields inherited from class java.lang.Thread
MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY

Constructor Summary

Constructors
Constructor	Description
`AlgorithmGVF(ModelImage destImage, ModelImage srcImg, float[] sigmas, int gvfIterations, int boundaryIterations, float k, VOI srcVOI, boolean do25D)`	Creates a new AlgorithmGVF object.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`void`	`algorithmPerformed(AlgorithmBase algorithm)`	Called after an algorithm this listener is registered to exits (maybe successfully, maybe not).
`private void`	`calc25D()`	Prepares the data and runs the algorithm for a 3D image on a slice by slice basis.
`private void`	`calc2D()`	Prepares the data and runs the algorithm for a 2D image.
`private void`	`calc3D()`	Prepares the data and runs the algorithm for a 3D image.
`private void`	`calcGVF(int sliceNum, float[] imgBuffer)`	Calculate GVF from image buffer.
`private void`	`calcGVF3D(float[] imgBuffer)`	Calculate GVF from 3D image buffer.
`private void`	`cleanup()`	Sets the structures to null.
`private double`	`distance(int x1, int x2, int y1, int y2)`	Calculates the distance between two points.
`void`	`finalize()`	Prepares this class for destruction.
`private static float`	`getBilinear(int i, float dx, float dy, int[] iExtents, float[] image)`	Performs bilinear interpolation of image data.
`VOI`	`getResultVOI()`	Accessor that returns the resultant VOI.
`private void`	`makeKernels2D()`	Makes 2D derivative kernels to be used in the calculation of the gradient magnitude.
`private void`	`makeKernels3D()`	Makes 3D derivative kernels to be used in the calculation of the gradient magnitude.
`void`	`runAlgorithm()`	Starts the snake algorithm.
`private void`	`runSnake(float[] xPoints, float[] yPoints, float[] zPoints, float[] u, float[] v, VOIBase resultContour)`	Actual function that evolves the boundary.
`private void`	`runSnake(float[] xPoints, float[] yPoints, float[] u, float[] v, java.awt.Polygon resultGon)`	Actual function that evolves the boundary.
`private void`	`setPoints(float[] xPoints, float[] yPoints, float[] zPoints, VOIBase contour)`	Takes the polygon and forms two special arrays for use in the Bspline.
`private void`	`setPoints(float[] xPoints, float[] yPoints, java.awt.Polygon gon)`	Takes the polygon and forms two special arrarys for use in the Bspline.
`void`	`setPropagation(boolean flag)`	Sets the propagation flag.

Methods inherited from class gov.nih.mipav.model.algorithms.AlgorithmBase
actionPerformed, addListener, addProgressChangeListener, calculateImageSize, calculatePrincipleAxis, computeElapsedTime, computeElapsedTime, convertIntoFloat, delinkProgressToAlgorithm, delinkProgressToAlgorithmMulti, displayError, errorCleanUp, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, generateProgressValues, getDestImage, getElapsedTime, getMask, getMaxProgressValue, getMinProgressValue, getNumberOfThreads, getProgress, getProgressChangeListener, getProgressChangeListeners, getProgressModulus, getProgressStep, getProgressValues, getSrcImage, isCompleted, isImage25D, isMultiThreadingEnabled, isRunningInSeparateThread, isThreadStopped, linkProgressToAlgorithm, linkProgressToAlgorithm, makeProgress, notifyListeners, removeListener, removeProgressChangeListener, run, setCompleted, setImage25D, setMask, setMaxProgressValue, setMinProgressValue, setMultiThreadingEnabled, setNumberOfThreads, setProgress, setProgressModulus, setProgressStep, setProgressValues, setProgressValues, setRunningInSeparateThread, setSrcImage, setStartTime, setThreadStopped, startMethod, windowActivated, windowClosed, windowClosing, windowDeactivated, windowDeiconified, windowIconified, windowOpened

Methods inherited from class java.lang.Thread
activeCount, checkAccess, clone, countStackFrames, currentThread, dumpStack, enumerate, getAllStackTraces, getContextClassLoader, getDefaultUncaughtExceptionHandler, getId, getName, getPriority, getStackTrace, getState, getThreadGroup, getUncaughtExceptionHandler, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, join, join, join, onSpinWait, resume, setContextClassLoader, setDaemon, setDefaultUncaughtExceptionHandler, setName, setPriority, setUncaughtExceptionHandler, sleep, sleep, start, stop, suspend, toString, yield

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Field Detail
  - boundaryIterations
```
private int boundaryIterations
```
    Maximum iterations to generate new boundary.
  - do25D
```
private boolean do25D
```
    Only applies to 3D, if true do slice by slice.
  - expGvfBuffer
```
private float[] expGvfBuffer
```
    DOCUMENT ME!
  - extents
```
private int[] extents
```
    DOCUMENT ME!
  - fx
```
private float[] fx
```
    DOCUMENT ME!
  - fy
```
private float[] fy
```
    DOCUMENT ME!
  - fz
```
private float[] fz
```
    DOCUMENT ME!
  - gVal
```
private float[] gVal
```
    DOCUMENT ME!
  - gvfBuffer
```
private float[] gvfBuffer
```
    DOCUMENT ME!
  - gvfIterations
```
private int gvfIterations
```
    Maximum iterations to generate generalized gradient vector field.
  - GxData
```
private float[] GxData
```
    Storage location of the first derivative of the Gaussian in the X direction.
  - GyData
```
private float[] GyData
```
    Storage location of the first derivative of the Gaussian in the Y direction.
  - GzData
```
private float[] GzData
```
    Storage location of the first derivative of the Gaussian in the Z direction.
  - kExtents
```
private int[] kExtents
```
    Dimensionality of the kernel.
  - kValue
```
private float kValue
```
    In the paper "Generalized gradient vector flow external forces for active contours" by Chenyang Xu and Jerry Prince values of 0.05, 0.15, and 0.2 were used for k.
  - length
```
private int length
```
    DOCUMENT ME!
  - propagationFlag
```
private boolean propagationFlag
```
    If true propagate the contour to an adjacent slice.
  - resultVOI
```
private VOI resultVOI
```
    The resultant polygon and the evolution has completed.
  - sigmas
```
private float[] sigmas
```
    Standard deviations of the gaussian used to calculate the kernels.
  - srcVOI
```
private VOI srcVOI
```
    The initial VOI to initialize the evolution process.
  - stSlice
```
private int stSlice
```
    Starting slice to evolve contour.
  - uVal
```
private float[] uVal
```
    DOCUMENT ME!
  - vVal
```
private float[] vVal
```
    DOCUMENT ME!
  - wVal
```
private float[] wVal
```
    DOCUMENT ME!
  - xDim
```
private int xDim
```
    DOCUMENT ME!
  - yDim
```
private int yDim
```
    DOCUMENT ME!
  - zDim
```
private int zDim
```
    DOCUMENT ME!
  - outputBuffer
```
private float[] outputBuffer
```
- Constructor Detail
  - AlgorithmGVF
```
public AlgorithmGVF(ModelImage destImage,
                    ModelImage srcImg,
                    float[] sigmas,
                    int gvfIterations,
                    int boundaryIterations,
                    float k,
                    VOI srcVOI,
                    boolean do25D)
```
    Creates a new AlgorithmGVF object.
    
    Parameters:
    
    destImage - image of GVF field magnitude
    
    srcImg - 2D or 3D source image
    
    sigmas - describe the scale of the gaussian in each dimension
    
    gvfIterations - iterations in calculating GVF field
    
    boundaryIterations - iterations in calculating boundary
    
    k - GVF constant
    
    srcVOI - VOI that is to be evolved
    
    do25D - only applies to 3D, if true do slice by slice
- Method Detail
  - finalize
```
public void finalize()
```
    Prepares this class for destruction.
    
    Overrides:
    
    finalize in class AlgorithmBase
  - getResultVOI
```
public VOI getResultVOI()
```
    Accessor that returns the resultant VOI.
    
    Returns:
    
    resultant VOI that has localized to the boundaries of the object
  - runAlgorithm
```
public void runAlgorithm()
```
    Starts the snake algorithm.
    
    Specified by:
    
    runAlgorithm in class AlgorithmBase
  - setPropagation
```
public void setPropagation(boolean flag)
```
    Sets the propagation flag.
    
    Parameters:
    
    flag - if true result contour from a slice is propagated to the adjacent slice and used to initialize the snake algorithm for that slice. If false the snake algorithm stops after optimizing the boundary in the present slice.
  - getBilinear
```
private static float getBilinear(int i,
                                 float dx,
                                 float dy,
                                 int[] iExtents,
                                 float[] image)
```
    Performs bilinear interpolation of image data.
    
    Parameters:
    
    i - index into image
    
    dx - change in x from integer
    
    dy - change in y from integer
    
    iExtents - dimensions of image
    
    image - image data
    
    Returns:
    
    DOCUMENT ME!
  - calc25D
```
private void calc25D()
```
    Prepares the data and runs the algorithm for a 3D image on a slice by slice basis.
  - calc2D
```
private void calc2D()
```
    Prepares the data and runs the algorithm for a 2D image.
  - calc3D
```
private void calc3D()
```
    Prepares the data and runs the algorithm for a 3D image.
  - calcGVF
```
private void calcGVF(int sliceNum,
                     float[] imgBuffer)
```
    Calculate GVF from image buffer.
    
    Parameters:
    
    sliceNum -
    
    imgBuffer - DOCUMENT ME!
  - calcGVF3D
```
private void calcGVF3D(float[] imgBuffer)
```
    Calculate GVF from 3D image buffer.
    
    Parameters:
    
    imgBuffer - DOCUMENT ME!
  - cleanup
```
private void cleanup()
```
    Sets the structures to null.
  - distance
```
private double distance(int x1,
                        int x2,
                        int y1,
                        int y2)
```
    Calculates the distance between two points.
    
    Parameters:
    
    x1 - first x coord.
    
    x2 - second x coord.
    
    y1 - first y1 coord.
    
    y2 - second y2 coord.
    
    Returns:
    
    DOCUMENT ME!
  - makeKernels2D
```
private void makeKernels2D()
```
    Makes 2D derivative kernels to be used in the calculation of the gradient magnitude.
  - makeKernels3D
```
private void makeKernels3D()
```
    Makes 3D derivative kernels to be used in the calculation of the gradient magnitude.
  - runSnake
```
private void runSnake(float[] xPoints,
                      float[] yPoints,
                      float[] u,
                      float[] v,
                      java.awt.Polygon resultGon)
```
    Actual function that evolves the boundary.
    
    Parameters:
    
    xPoints - x coordinates that describe the contour
    
    yPoints - y coordinates that describe the contour
    
    u - gradient vector field x component
    
    v - gradient vector field y component
    
    resultGon - resultant polygon energy is too much extra computation to be worth computing energy is given by the sum over 0.5*alpha*|first order derivative|**2 + Eext, where v = -grad(Eext). The first derivative of the curve and Eext would also have to be calculated to obtain the energy.
  - runSnake
```
private void runSnake(float[] xPoints,
                      float[] yPoints,
                      float[] zPoints,
                      float[] u,
                      float[] v,
                      VOIBase resultContour)
```
    Actual function that evolves the boundary.
    
    Parameters:
    
    xPoints - x coordinates that describe the contour
    
    yPoints - y coordinates that describe the contour
    
    u - gradient vector field x component
    
    v - gradient vector field y component
    
    resultGon - resultant polygon energy is too much extra computation to be worth computing energy is given by the sum over 0.5*alpha*|first order derivative|**2 + Eext, where v = -grad(Eext). The first derivative of the curve and Eext would also have to be calculated to obtain the energy.
  - setPoints
```
private void setPoints(float[] xPoints,
                       float[] yPoints,
                       java.awt.Polygon gon)
```
    Takes the polygon and forms two special arrarys for use in the Bspline.
    
    Parameters:
    
    xPoints - storage location of array of x coord. points
    
    yPoints - storage location array of y coord. points
    
    gon - initial polygon
  - setPoints
```
private void setPoints(float[] xPoints,
                       float[] yPoints,
                       float[] zPoints,
                       VOIBase contour)
```
    Takes the polygon and forms two special arrays for use in the Bspline.
    
    Parameters:
    
    xPoints - storage location of array of x coord. points
    
    yPoints - storage location array of y coord. points
    
    gon - initial polygon
  - algorithmPerformed
```
public void algorithmPerformed(AlgorithmBase algorithm)
```
    Description copied from interface: AlgorithmInterface
    
    Called after an algorithm this listener is registered to exits (maybe successfully, maybe not). If the algorithm is run in a separate thread, this call will be made within that thread. If not, this call will be made from that same, shared thread.
    
    Specified by:
    
    algorithmPerformed in interface AlgorithmInterface
    
    Parameters:
    
    algorithm - the algorithm which has just completed

Class AlgorithmGVF

Nested Class Summary

Nested classes/interfaces inherited from class java.lang.Thread

Field Summary

Fields inherited from class gov.nih.mipav.model.algorithms.AlgorithmBase

Fields inherited from class java.lang.Thread

Constructor Summary

Method Summary

Methods inherited from class gov.nih.mipav.model.algorithms.AlgorithmBase

Methods inherited from class java.lang.Thread

Methods inherited from class java.lang.Object

Field Detail

boundaryIterations

do25D

expGvfBuffer

extents

fx

fy

fz

gVal

gvfBuffer

gvfIterations

GxData

GyData

GzData

kExtents

kValue

length

propagationFlag

resultVOI

sigmas

srcVOI

stSlice

uVal

vVal

wVal

xDim

yDim

zDim

outputBuffer

Constructor Detail

AlgorithmGVF

Method Detail

finalize

getResultVOI

runAlgorithm

setPropagation

getBilinear

calc25D

calc2D

calc3D

calcGVF

calcGVF3D

cleanup

distance

makeKernels2D

makeKernels3D

runSnake

runSnake

setPoints

setPoints

algorithmPerformed