Package gov.nih.mipav.model.algorithms

Class AlgorithmPowellOptBase

java.lang.Object

java.lang.Thread

gov.nih.mipav.model.algorithms.AlgorithmBase

gov.nih.mipav.model.algorithms.AlgorithmPowellOptBase

All Implemented Interfaces:

de.jtem.numericalMethods.calculus.function.RealFunctionOfSeveralVariables, java.awt.event.ActionListener, java.awt.event.WindowListener, java.lang.Runnable, java.util.EventListener

Direct Known Subclasses:

AlgorithmPowellOpt2D, AlgorithmPowellOpt3D

public abstract class AlgorithmPowellOptBase
extends AlgorithmBase
implements de.jtem.numericalMethods.calculus.function.RealFunctionOfSeveralVariables

Powell's Method

Runs Powell's method. Powell's method is a way to find minimums without finding derivatives. Basically, it starts at some point P in N-dimensional space, proceeds in a direction, and minimizes along that line using a 1-dimensional minimization method. It continues like this until the point has moved by less than the tolerance. It starts with the initial point defined in the constructor and initial directions of (1 0 ... 0) (0 1 0 ... ) ..., the basis vectors. At the end, "point" is the best point found and functionAtBest is the value at "point".

This is an abstract class which contains many of the basic functions needed to run Powell's method. 2D and 3D versions extend this version.

This optimization technique is based on FLIRT. FLIRT stands for FMRIB's Linear Image Registration Tool. For more information on FLIRT, visit their homepage at http://www.fmrib.ox.ac.uk/fsl/flirt/. Their main paper is:

Jenkinson, M. and Smith, S. (2001a).
A global optimisation method for robust affine registration of brain images.
Medical Image Analysis, 5(2):143-156.

Version:

0.1 Oct 1, 2001, 0.2 March 27, 2008

Author:

Neva Cherniavsky, Hailong Wang, Ph.D

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
protected AlgorithmOptimizeFunctionBase	costFunction	Cost function called to measure cost - 1D.
protected int	dof	Degrees of freedom.
protected TransMatrixd	fromOrigin	The transformation matrix from the origin of the input image.
protected int	maxIterations	The maximum number of iterations the optimization allows.
protected boolean	parallelPowell	The flag for parallel powell's method
protected AlgorithmBase	parent	Parent algorithm that called this optimization.
protected boolean	pathRecorded	The flag to indicate whether the searching path need to be recorded.
protected java.util.Hashtable<java.lang.Long,java.util.Vector<java.util.Vector<WildMagic.LibFoundation.Mathematics.Vector3d>>>	paths	Store the paths for every thread.
protected Vectornd[]	points	Array used to hold the initial points, final points and costs
(package private) double[]	savedStartPoint	The different searches change the number of variables in the transformation matrix that change.
private static double	TINY	Used to prevent division by zero.
protected double[]	tolerance	Array of tolerances for each dimension.
protected TransMatrixd	toOrigin	The transformation matrix to the origin of the input image.
protected boolean	useJTEM	When true, JTEM Powell.search is used, otherwise, JTEM BrentOnline.search is used.

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
AlgorithmPowellOptBase(AlgorithmBase parentAlgo, int degreeOfFreedom, AlgorithmOptimizeFunctionBase costFunc, double[] tols, int maxIter)	Constructs a new algorithm with the given centers of mass (needed for setting the transformations), the given cost function (which was constructed with the proper images), the initial point we're looking at, and some tolerance within that point to look for the minimum.

Method Summary

Modifier and Type	Method	Description
abstract void	adjustTranslation(TransMatrixd mat, double sample)	Adjust the translation of the transformation matrix by the sample pararmeter.
abstract double[]	constructPoint(double[] defaultPoint, double[] point)	Construct a full transformation vector from the partial transformation vector.
TransMatrixd	convertToMatrix(double[] vector)	Convert a transformation vector to a transformation matrix.
TransMatrixd	convertToMatrix(double[] defaultPoint, double[] point)	Convert a transformation vector to a transformation matrix.
abstract TransMatrixd	convertToMatrix(TransMatrixd toOrigin, TransMatrixd fromOrigin, double[] vector)	Convert a transformation vector to a transformation matrix about the origin.
static double[]	copyPoint(double[] point)	Make a copy of the transformation vector
private void	createTerrain(double[] terrain, double transXFrom, double transXTo, double transXStep, int xstart, int xdim, double transYFrom, double transYTo, double transYStep, int ystart, int ydim, double rotFrom, double rotTo, double rotStep, int zstart, int zdim)
double[]	createTerrain(double transXFrom, double transXTo, double transXStep, double transYFrom, double transYTo, double transYStep, double rotFrom, double rotTo, double rotStep)
void	disposeLocal()	Sets everything to null and prepares this class for destruction.
double	eval(double[] x)
abstract double[]	extractPoint(double[] startPoint)	Extract the partial or full transformation vector from the start transformation vector, which will be optimized.
double	getCost(int index)	Returns the cost for the transformation vector.
TransMatrixd	getFromOrigin()
TransMatrixd	getMatrix(int index)	Obtain the transformation vector and convert to the matrix representation.
abstract TransMatrixd	getMatrix(int index, double sample)	Obtain the transformation vector and convert to the matrix representation, then scale the translation by sample.
int	getMaxIterations()
int	getNumberOfVariables()
double[]	getPoint(int index)	Return the full transformation vector.
double[]	getPoint(int index, double sample)	Obtain the transformation vector and adjust its translation by sample parameters.
Vectornd[]	getPoints()	Return an array of transformation vector.
TransMatrixd	getToOrigin()
boolean	isParallelPowell()
boolean	isPathRecorded()
void	lineMinimization(double[] pt, double[] directions, double[] bestCost)	Minimizes the point along the given vector direction.
double	measureCost(double[] point)	Measure the cost value for the given transformation vector.
double	measureCost(TransMatrixd m)	Measure the cost value for the given transformation matrix.
void	optimize(Vectornd v)	Finds optimal point for the given initial point
void	optimizeBlock(int start, int end)	Optimize several initial points.
void	print(double[] pt, java.lang.String message)	The utility function used to print information.
void	runAlgorithm()	Runs Powell's method.
static double[]	scalePoint(double[] point, double scale)	Scale the point by scale parameter and store it into another vector.
double[]	scalePoint(int index, double scale)	Obtain the transformation vector and make a copy, then scale it by scale parameter.
void	setMaxIterations(int max)	Accessor that sets the maximum number of iterations.
void	setParallelPowell(boolean parallelPowell)
void	setPathRecorded(boolean pathRecorded)
void	setPoints(Vectornd[] points)	Sets the transformation vectors.
void	setUseJTEM(boolean bOn)
abstract void	updatePoint(double[] point, double cost, Vectornd v)	Store the optimal point and cost to v

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

actionPerformed, addListener, addProgressChangeListener, calculateImageSize, calculatePrincipleAxis, computeElapsedTime, computeElapsedTime, convertIntoFloat, delinkProgressToAlgorithm, delinkProgressToAlgorithmMulti, displayError, errorCleanUp, finalize, 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

TINY

private static final double TINY

Used to prevent division by zero.

costFunction

protected AlgorithmOptimizeFunctionBase costFunction

Cost function called to measure cost - 1D.

fromOrigin

protected TransMatrixd fromOrigin

The transformation matrix from the origin of the input image.

maxIterations

protected int maxIterations

The maximum number of iterations the optimization allows.

dof

protected int dof

Degrees of freedom.

parent

protected AlgorithmBase parent

Parent algorithm that called this optimization.

tolerance

protected double[] tolerance

Array of tolerances for each dimension.

toOrigin

protected TransMatrixd toOrigin

The transformation matrix to the origin of the input image.

points

protected Vectornd[] points

Array used to hold the initial points, final points and costs

parallelPowell

protected boolean parallelPowell

The flag for parallel powell's method

useJTEM

protected boolean useJTEM

When true, JTEM Powell.search is used, otherwise, JTEM BrentOnline.search is used.

paths

protected java.util.Hashtable<java.lang.Long,java.util.Vector<java.util.Vector<WildMagic.LibFoundation.Mathematics.Vector3d>>> paths

Store the paths for every thread.

pathRecorded

protected boolean pathRecorded

The flag to indicate whether the searching path need to be recorded.

savedStartPoint

double[] savedStartPoint

The different searches change the number of variables in the transformation matrix that change. This fills in the rest of the 'constant' portion of the matrix.

Constructor Detail

AlgorithmPowellOptBase

public AlgorithmPowellOptBase(AlgorithmBase parentAlgo,
                              int degreeOfFreedom,
                              AlgorithmOptimizeFunctionBase costFunc,
                              double[] tols,
                              int maxIter)

Constructs a new algorithm with the given centers of mass (needed for setting the transformations), the given cost function (which was constructed with the proper images), the initial point we're looking at, and some tolerance within that point to look for the minimum. The initial point contains rotations, translations, scales, and skews.

Parameters:

parentAlgo - DOCUMENT ME!

degreeOfFreedom - Degree of freedom for transformation (must be 3, 4, 6, 7, 9, or 12).

costFunc - Cost function to use.

tols - Tolerance for each dimension (tols.length == degreeOfFreedom).

maxIter - The maximum iterations.

Method Detail

convertToMatrix

public TransMatrixd convertToMatrix(double[] vector)

Convert a transformation vector to a transformation matrix.

Parameters:

vector - a transformation vector.

Returns:

a transformation matrix

convertToMatrix

public abstract TransMatrixd convertToMatrix(TransMatrixd toOrigin,
                                             TransMatrixd fromOrigin,
                                             double[] vector)

Convert a transformation vector to a transformation matrix about the origin.

Parameters:

toOrigin - the matrix translating the origin to some specified point

fromOrigin - the matrix translating the origin back.

vector - a transformation vector.

Returns:

a transformation matrix.

constructPoint

public abstract double[] constructPoint(double[] defaultPoint,
                                        double[] point)

Construct a full transformation vector from the partial transformation vector. For missing values in point, the values in defaultPoint will be used.

Parameters:

defaultPoint - a default full transformation vector.

point - a partial or full transformation vector.

Returns:

a full transformation vector.

convertToMatrix

public final TransMatrixd convertToMatrix(double[] defaultPoint,
                                          double[] point)

Convert a transformation vector to a transformation matrix. For missing values, use the values from defaultPoint.

Parameters:

defaultPoint - a start transformation vector.

point - a transformation vector.

Returns:

a transformation matrix.

extractPoint

public abstract double[] extractPoint(double[] startPoint)

Extract the partial or full transformation vector from the start transformation vector, which will be optimized.

Parameters:

startPoint - the start full transformation vector.

Returns:

the partial or full transformation vector which will be optimized.

getPoint

public double[] getPoint(int index)

Return the full transformation vector.

Parameters:

index - the index of the transformation vector.

Returns:

the full transformation vector.

getPoint

public double[] getPoint(int index,
                         double sample)

Obtain the transformation vector and adjust its translation by sample parameters.

Parameters:

index - the index of transformation vector.

sample - the translation scaling parameter.

Returns:

the translation scaled transformation vector.

getCost

public final double getCost(int index)

Returns the cost for the transformation vector.

Parameters:

index - the index of transformation vector.

Returns:

the cost for the transformation vector.

getMatrix

public final TransMatrixd getMatrix(int index)

Obtain the transformation vector and convert to the matrix representation.

Parameters:

index - the index of transformation vector.

Returns:

the transformation matrix

getMatrix

public abstract TransMatrixd getMatrix(int index,
                                       double sample)

Obtain the transformation vector and convert to the matrix representation, then scale the translation by sample.

Parameters:

index - the index of transformation vector.

sample - the translation scaling parameter.

Returns:

the scaled transformation matrix.

adjustTranslation

public abstract void adjustTranslation(TransMatrixd mat,
                                       double sample)

Adjust the translation of the transformation matrix by the sample pararmeter.

Parameters:

mat - the transformation matrix

sample - the resolution adjusting parameter.

measureCost

public final double measureCost(double[] point)

Measure the cost value for the given transformation vector.

Parameters:

point - a transformation vector.

Returns:

the cost value.

measureCost

public final double measureCost(TransMatrixd m)

Measure the cost value for the given transformation matrix.

Parameters:

m - a transformation matrix.

Returns:

the cost value.

copyPoint

public static final double[] copyPoint(double[] point)

Make a copy of the transformation vector

Parameters:

point - a transformation vector.

Returns:

the copy of the transformation vector.

scalePoint

public static final double[] scalePoint(double[] point,
                                        double scale)

Scale the point by scale parameter and store it into another vector.

Parameters:

point - the transformation vector.

scale - the scale parameter.

Returns:

the scaled transformation vector

scalePoint

public final double[] scalePoint(int index,
                                 double scale)

Obtain the transformation vector and make a copy, then scale it by scale parameter.

Parameters:

index - the index of transformation vector

scale - the scale parameter

Returns:

the new scaled transformation vector.

disposeLocal

public void disposeLocal()

Sets everything to null and prepares this class for destruction.

setMaxIterations

public void setMaxIterations(int max)

Accessor that sets the maximum number of iterations.

Parameters:

max - The max number of iterations.

lineMinimization

public void lineMinimization(double[] pt,
                             double[] directions,
                             double[] bestCost)

Minimizes the point along the given vector direction. Given an initial point and a guess as to how far from that point we should go to look for a minimum.

Parameters:

pt -

directions -

bestCost -

getPoints

public Vectornd[] getPoints()

Return an array of transformation vector. The meanings of those transformation vector are as following: the initial transformation vector: before algorithm is performed the final transformation vector: after algorithm was performed.

Returns:

setPoints

public void setPoints(Vectornd[] points)

Sets the transformation vectors.

Parameters:

points - the transformation vectors.

print

public void print(double[] pt,
                  java.lang.String message)

The utility function used to print information.

Parameters:

pt - a double array.

message - the message

optimize

public void optimize(Vectornd v)

Finds optimal point for the given initial point

Parameters:

v - the initial point

optimizeBlock

public void optimizeBlock(int start,
                          int end)

Optimize several initial points.

Parameters:

start -

end -

runAlgorithm

public void runAlgorithm()

Runs Powell's method. Powell's method is a way to find minimums without finding derivatives. Basically, it starts at some point P in N-dimensional space, proceeds in a direction, and minimizes along that line using golden search. It then resets the point and minimizes again, until the point moves by less than the tolerance. This method starts with the initial point defined in the constructor and initial directions of (1 0 ... 0) (0 1 0 ... ) ..., the basis vectors. At the end, "point" is the best point found and functionAtBest is the value at "point".

Specified by:

runAlgorithm in class AlgorithmBase

isParallelPowell

public boolean isParallelPowell()

setParallelPowell

public void setParallelPowell(boolean parallelPowell)

setUseJTEM

public void setUseJTEM(boolean bOn)

updatePoint

public abstract void updatePoint(double[] point,
                                 double cost,
                                 Vectornd v)

Store the optimal point and cost to v

Parameters:

point - the optimal point.

cost - the optimal cost.

v - the Vectornd variable used by upper level algorithm.

createTerrain

public double[] createTerrain(double transXFrom,
                              double transXTo,
                              double transXStep,
                              double transYFrom,
                              double transYTo,
                              double transYStep,
                              double rotFrom,
                              double rotTo,
                              double rotStep)

createTerrain

private void createTerrain(double[] terrain,
                           double transXFrom,
                           double transXTo,
                           double transXStep,
                           int xstart,
                           int xdim,
                           double transYFrom,
                           double transYTo,
                           double transYStep,
                           int ystart,
                           int ydim,
                           double rotFrom,
                           double rotTo,
                           double rotStep,
                           int zstart,
                           int zdim)

isPathRecorded

public boolean isPathRecorded()

setPathRecorded

public void setPathRecorded(boolean pathRecorded)

getFromOrigin

public TransMatrixd getFromOrigin()

getToOrigin

public TransMatrixd getToOrigin()

getMaxIterations

public int getMaxIterations()

eval

public double eval(double[] x)

Specified by:

eval in interface de.jtem.numericalMethods.calculus.function.RealFunctionOfSeveralVariables

getNumberOfVariables

public int getNumberOfVariables()

Specified by:

getNumberOfVariables in interface de.jtem.numericalMethods.calculus.function.RealFunctionOfSeveralVariables