gov.nih.mipav.model.algorithms.AlgorithmAGVF

All Implemented Interfaces:: AlgorithmInterface, ActionListener, WindowListener, Runnable, EventListener

Direct Known Subclasses:: AlgorithmCellTrackingAGVF

public class AlgorithmAGVF extends AlgorithmBase implements AlgorithmInterface

Snake-like algorithm deriviative. The algorithm is supplied a polygon (VOI - contour) and that polygon is allowed to evolve to the edge of the object generated by calculating 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 invalid input: '<'= 0.25f and stability for the generalized GVF algorithm requires that delta t invalid input: '<'= (delta x * delta y)/(4 * gmax) = 1/4. For 3D: delta t invalid input: '<'= (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 the 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:

Nested Class Summary

Nested classes/interfaces inherited from class java.lang.Thread
Thread.Builder, Thread.State, Thread.UncaughtExceptionHandler
Field Summary

Fields

Modifier and Type

Field

Description

protected 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!

protected 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 float

smoothness

DOCUMENT ME!

private VOI

srcVOI

The initial VOI to initialize the evolution process.

private int

stSlice

DOCUMENT ME!

private float[]

uVal

DOCUMENT ME!

private float[]

vVal

DOCUMENT ME!

private float[]

wVal

DOCUMENT ME!

protected int

xDim

DOCUMENT ME!

protected int

yDim

DOCUMENT ME!

protected 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

AlgorithmAGVF(ModelImage resultImage, ModelImage srcImg, float[] sigmas, int gvfIterations, int boundaryIterations, float k, float smoothness, VOI srcVOI, boolean do25D)

Creates a new AlgorithmAGVF object.
Method Summary

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.

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.

protected Vector<WildMagic.LibFoundation.Mathematics.Vector2f>

cleanLine(float[] xPts, float[] yPts)

Removes points (vectors) that form sharp angles (i.e. smoothes boudnary) Also adds points separated by some distance and removes adjacent points

private Vector<WildMagic.LibFoundation.Mathematics.Vector3f>

cleanLine(float[] xPts, float[] yPts, float[] zPts)

protected void

cleanup()

Sets structures to null.

private double

distance(float x1, float x2, float y1, float y2)

Calculates the euclidian distance between two points.

void

finalize()

Prepares this class for destruction.

protected static float

getBilinear(int i, float dx, float dy, int[] iExtents, float[] image)

Performs bilinear interpolation of image data.

VOI

getResultVOI()

Returns the resultant VOI.

private void

makeKernels2D()

Makes 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.

protected void

runSnake(float[] xPoints, float[] yPoints, float[] zPoints, float[] u, float[] v, VOIBase resultContour)

Actual function that evolves the boundary.

protected void

runSnake(float[] xPoints, float[] yPoints, float[] u, float[] v, 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 arrarys for use in runSnake.

private void

setPoints(float[] xPoints, float[] yPoints, Polygon gon)

Takes the polygon and forms two special arrarys for use in runSnake.

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, isVirtual, join, join, join, join, ofPlatform, ofVirtual, onSpinWait, resume, setContextClassLoader, setDaemon, setDefaultUncaughtExceptionHandler, setName, setPriority, setUncaughtExceptionHandler, sleep, sleep, sleep, start, startVirtualThread, stop, suspend, threadId, toString, yield

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

Field Details
- boundaryIterations
  
  protected int boundaryIterations
  
  Maximum iterations to generate new boundary.
- extents
  
  protected int[] extents
  
  DOCUMENT ME!
- xDim
  
  protected int xDim
  
  DOCUMENT ME!
- yDim
  
  protected int yDim
  
  DOCUMENT ME!
- zDim
  
  protected int zDim
  
  DOCUMENT ME!
- do25D
  
  private boolean do25D
  
  Only applies to 3D, if true do slice by slice.
- expGvfBuffer
  
  private float[] expGvfBuffer
  
  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.
- smoothness
  
  private float smoothness
  
  DOCUMENT ME!
- srcVOI
  
  private VOI srcVOI
  
  The initial VOI to initialize the evolution process.
- stSlice
  
  private int stSlice
  
  DOCUMENT ME!
- uVal
  
  private float[] uVal
  
  DOCUMENT ME!
- vVal
  
  private float[] vVal
  
  DOCUMENT ME!
- wVal
  
  private float[] wVal
  
  DOCUMENT ME!
- outputBuffer
  
  private float[] outputBuffer
Constructor Details
- AlgorithmAGVF
  
  public AlgorithmAGVF(ModelImage resultImage, ModelImage srcImg, float[] sigmas, int gvfIterations, int boundaryIterations, float k, float smoothness, VOI srcVOI, boolean do25D)
  
  Creates a new AlgorithmAGVF object.
  
  Parameters:
  
  resultImage - 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
  
  smoothness - DOCUMENT ME!
  
  srcVOI - VOI that is to be evolved
  
  do25D - only applies to 3D, if true do slice by slice
Method Details
- finalize
  
  public void finalize()
  
  Prepares this class for destruction.
  
  Overrides:
  
  finalize in class AlgorithmBase
- getResultVOI
  
  public VOI getResultVOI()
  
  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
  
  protected 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!
- cleanLine
  
  protected Vector<WildMagic.LibFoundation.Mathematics.Vector2f> cleanLine(float[] xPts, float[] yPts)
  
  Removes points (vectors) that form sharp angles (i.e. smoothes boudnary) Also adds points separated by some distance and removes adjacent points
  
  Parameters:
  
  xPts - x coords of points that define a contour
  
  yPts - y coords of points that define a contour
  
  Returns:
  
  DOCUMENT ME!
- cleanLine
  
  private Vector<WildMagic.LibFoundation.Mathematics.Vector3f> cleanLine(float[] xPts, float[] yPts, float[] zPts)
- cleanup
  
  protected void cleanup()
  
  Sets structures to null.
- runSnake
  
  protected void runSnake(float[] xPoints, float[] yPoints, float[] u, float[] v, Polygon resultGon)
  
  Actual function that evolves the boundary.
  
  Parameters:
  
  xPoints - x coordinates that describe the contour
  
  yPoints - y coordinates that describe the contour
  
  u - x component of the GVF
  
  v - y component of the GVF
  
  resultGon - resultant polygon
- runSnake
  
  protected 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 - x component of the GVF
  
  v - y component of the GVF
  
  resultGon - resultant polygon
- calc25D
  
  private void calc25D()
  
  Prepares the data and runs the algorithm for a 3D image.
- 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!
- distance
  
  private double distance(float x1, float x2, float y1, float y2)
  
  Calculates the euclidian distance between two points.
  
  Parameters:
  
  x1 - first x coord.
  
  x2 - seconde x coord.
  
  y1 - first y1 coord.
  
  y2 - seconde y2 coord.
  
  Returns:
  
  DOCUMENT ME!
- makeKernels2D
  
  private void makeKernels2D()
  
  Makes 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.
- setPoints
  
  private void setPoints(float[] xPoints, float[] yPoints, Polygon gon)
  
  Takes the polygon and forms two special arrarys for use in runSnake.
  
  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 arrarys for use in runSnake.
  
  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 AlgorithmAGVF

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 Details

boundaryIterations

extents

xDim

yDim

zDim

do25D

expGvfBuffer

fx

fy

fz

gVal

gvfBuffer

gvfIterations

GxData

GyData

GzData

kExtents

kValue

length

propagationFlag

resultVOI

sigmas

smoothness

srcVOI

stSlice

uVal

vVal

wVal

outputBuffer

Constructor Details

AlgorithmAGVF

Method Details

finalize

getResultVOI

runAlgorithm

setPropagation

getBilinear

cleanLine

cleanLine

cleanup

runSnake

runSnake

calc25D

calc2D

calc3D

calcGVF

calcGVF3D

distance

makeKernels2D

makeKernels3D

setPoints

setPoints

algorithmPerformed