gov.nih.mipav.model.algorithms.AlgorithmGVF

All Implemented Interfaces:: AlgorithmInterface, ActionListener, WindowListener, Runnable, 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 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 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

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

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, 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, 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, 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
  
  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 Details
- 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 Details
- 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, 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, 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 Details

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 Details

AlgorithmGVF

Method Details

finalize

getResultVOI

runAlgorithm

setPropagation

getBilinear

calc25D

calc2D

calc3D

calcGVF

calcGVF3D

cleanup

distance

makeKernels2D

makeKernels3D

runSnake

runSnake

setPoints

setPoints

algorithmPerformed