Class AlgorithmFuzzyCMeans
- java.lang.Object
-
- java.lang.Thread
-
- gov.nih.mipav.model.algorithms.AlgorithmBase
-
- gov.nih.mipav.model.algorithms.AlgorithmFuzzyCMeans
-
- All Implemented Interfaces:
java.awt.event.ActionListener
,java.awt.event.WindowListener
,java.lang.Runnable
,java.util.EventListener
public class AlgorithmFuzzyCMeans extends AlgorithmBase
Fuzzy C-Means Segmentation algorithmSegmentation divides an image into distinct classes or types, such as segmenting the brain into 3 tissue types: gray matter, white matter, and cerebrospinal fluid. There are 2 types of segmentation: hard and soft or fuzzy. In hard segmentation a pixel is simply assigned to 1 of the classes. However, often in medical images, there cannot be absolute classification of a pixel because of partial volume effects where multiple tissues contribute to a pixel or voxel causing intensity blurring across boundaries. Fuzzy segmentation allows for the uncertainty in the location of object boundaries. In fuzzy segmentation a membership function exists for each class at every pixel location. At each pixel location a class membership function will have a value of 0 if there is absolutely no chance of that pixel belonging to the class. At each pixel location a class membership function will have a value of 1 if the pixel belongs to the class with absolute certainty. Membership functions can vary from 0 to 1, with the constraint that at any pixel location the sum of the membership functions of all the classes must add up to 1. The fuzzy membership function reflects the similarity between the data value at that pixel and the value of the class centroid. As a pixel data value becomes closer to the class centroid, the class membership function approaches unity.
The fuzzy C-Means algorithm is an unsupervised method; it works without the use of training data. This algorithm, allowing for soft segmentation based on fuzzy set theory, generalizes the K-means algorithm. The technique clusters data by iteratively computing a fuzzy membrship function and mean value estimates for each tissue class. The algorithm works by minimizing the sum over all pixels j and all classes k of: (ujk**q) * ((yj - vk)**2)
nClass = number of classes. ujk is the membership value at pixel location j for class k such that that sum over k from k = 1 to k = nClass for ujk = 1. q is a weighing exponent on each membership value and determines the amount of "fuzziness" of the resulting segmentation. q is required to be greater than 1 and is typically set to 2. yj is the observed single channel image intensity at location j. vk is the centroid of class k.
The user provides initial centroid values or simply uses default evenly spread pixel values generated by:
for (i = 0; i < nClass; i++) centroid[i] = minimum + (maximum - minimum)*(i + 1)/(nClass + 1);
Minimization is achieved by an interative process which:
1.)Computes the membership functions using a current estimate of the centroids.
numerator = (yj - vk)**(-2/(q-1))
denominator = Sum over l from l = 1 to l = nClass of (yj - vl)**(-2/(q-1))
ujk = numerator/denominator for all pixels j and all classes k
2.) Computes the centroids using current estimates of the membership functions.
numerator = sum over all pixels j of (ujk**q) * yj
denominator = sum over all pixels j of (ujk**q)
vk = numerator/denominator for all classes k
The iteration continues until either the user specified maximum number of iterations has occcured or until convergence has been detected. Convergence occurs when all membership functions over all pixel locations j change by less than the tolerance value between 2 iterations. The default maximum iteration number is 100. The default tolerance is 0.01.
The initial dialog asks the user for a signal threshold value. The default value is the image minimum value. In the centroid calculation only those pixels whose values equal or exceed threshold are used in the centroid calculaton. In the hard segmentation pixels whose values are less than threshold or not in a selected VOI if the whole image is not used are set to a segmentation value of 0, meaning that these pixels are outside of the specified classes.
The initial dialog has a checkbox for Boundary noise cropping which is unchecked by default. This function finds the smallest bounding box outside of which all image pixel values are below the image threshold. Values inside the bounding box are copied to a smaller array to save space and calculations are performed with this reduced array. However, these pixels outside the box are restored for the production of the hard and fuzzy segmented images. In the hard and fuzzy segmentation cases values outside the box all have a value of 0. If the cropping checkbox is selected, the user is constrained to select whole image rather than VOI region(s).
There are 3 choices for produced output images:
1.) HARD ONLY
2.) FUZZY ONLY
3.) HARD & FUZZY BOTH
Hard segmentation produces only 1 unsigned byte output image which assigns pixels which do not meet threshold requirements values of 0. The first class is assigned a value of 1, the second class is assigned a pixel value of 2, and so on. The last class has a value of nClass.
Fuzzy segmentation produces 1 image of floating point type for every segmentation class. The values ranges from 0.0 to 1.0. If boundary cropping is used, pixels outside the bounding box are all assigned the value 0.0.
The signal threshold value is entered on the initial dialog and the image centroids are entered on a later dialog.
Image Types:
This algorithm can be applied to 2D and 3D data sets that are not color or COMPLEX.
References: This code is a ported subset of C-code written and kindly provided by Dzung Pham. Note that our code is not the adaptive fuzzy C-means segmentation, which the Dzung Pham code is. Our code is not adaptive - it does not correct intensity inhomogeneities, also known as shading artifacts.
1.) Dzung L. Pham, Chenyang Xu, and Jerry L. Prince, "A Survey of Current Methods in Medical Image Segmentation", Department of Electrical and Computer Engineering, The Johns Hopkins University, Baltimore, Maryland, 21218, Technical Report JHU/ECE 99-01.
2.) Alberto F. Goldszal and Dzung L. Pham, "Volumetric Segmentation", Chapter 12, Academic Press, copyright 2000.
3.) Dzung L. Pham and Jerry L. Prince, "Adaptive Fuzzy Segmentation of Magnetic Resonance Images", IEEE Transactions on Medical Imaging, Vol. 18, No. 9, September, 1999, pp. 737 - 752.
- Version:
- 0.1 June 15, 2000 conversion of Dzung Pham's C code
- See Also:
JDialogFuzzyCMeans
,AlgorithmFuzzyCMeans
,JDialogInitialCentroids
-
-
Field Summary
Fields Modifier and Type Field Description static float
ALPHA
DOCUMENT ME!static int
BOTH_FUZZY_HARD
possible values for segmentation.private float[]
buffer2
DOCUMENT ME!private float[]
centroids
DOCUMENT ME!private int[]
classNumber
DOCUMENT ME!private boolean
cropBackground
DOCUMENT ME!private ModelImage[]
destImage
Fuzzy images require 1 image for each class Hard images 1 image with assigned clusters.private int
destNum
DOCUMENT ME!private double
exponent
1/(qValue - 1).static int
FUZZY_ONLY
DOCUMENT ME!static int
HARD_ONLY
DOCUMENT ME!private int
iterations
DOCUMENT ME!private int
jacobiIters1
jacobiIters1 and jacobiIter2 are only used with gain correction.private int
jacobiIters2
static float
MAX_FLOAT
DOCUMENT ME!private float
maxChange
DOCUMENT ME!private int
maxIter
DOCUMENT ME!private float[]
mems
DOCUMENT ME!private float[]
memsBuffer
DOCUMENT ME!private int
memSize
DOCUMENT ME!private int
nClass
DOCUMENT ME!private int
newSliceSize
DOCUMENT ME!private int
newXDim
DOCUMENT ME!private int
newYDim
DOCUMENT ME!private int
newZDim
DOCUMENT ME!private java.util.BitSet
objMask
DOCUMENT ME!private float[]
oldMember
DOCUMENT ME!private int
oldX
DOCUMENT ME!private int
oldY
DOCUMENT ME!private int
oldZ
DOCUMENT ME!private int
orgSlice
DOCUMENT ME!private int
orgVol
DOCUMENT ME!private int
orgXDim
DOCUMENT ME!private boolean
outputGainField
private boolean
powEIntFlag
DOCUMENT ME!private int
pyramidLevels
pyramidLevels is only used with gain correction.private double
qValue
DOCUMENT ME!private float[]
sCentroids
DOCUMENT ME!private byte[]
segBuffer
DOCUMENT ME!private int
segmentation
DOCUMENT ME!private int
sliceSize
DOCUMENT ME!private float
smooth1
smooth1 and smooth2 are only used with gain field correction.private float
smooth2
private float
threshold
DOCUMENT ME!private float
tolerance
DOCUMENT ME!private boolean[]
unusedCentroids
DOCUMENT ME!private int
volSize
DOCUMENT ME!private boolean
wholeImage
wholeImage is constrained to be true if background cropping is selected.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, image25D, mask, maxProgressValue, minProgressValue, multiThreadingEnabled, nthreads, progress, progressModulus, progressStep, runningInSeparateThread, separable, srcImage, threadStopped
-
-
Constructor Summary
Constructors Constructor Description AlgorithmFuzzyCMeans(ModelImage[] destImg, ModelImage srcImg, int _nClass, int _pyramidLevels, int _jacobiIters1, int _jacobiIters2, float _q, float _smooth1, float _smooth2, boolean _outputGainField, int _segmentation, boolean _cropBackground, float _threshold, int _max_iter, float _tolerance, boolean _wholeImage)
Creates a new AlgorithmFuzzyCMeans object.AlgorithmFuzzyCMeans(ModelImage srcImg, int _nClass, int _pyramidLevels, int _jacobiIters1, int _jacobiIters2, float _q, float _smooth1, float _smooth2, boolean _outputGainField, int _segmentation, boolean _cropBackground, float _threshold, int _max_iter, float _tolerance, boolean _wholeImage)
Creates a new AlgorithmFuzzyCMeans object.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
cleanUp()
Cleans up the memory usage.private void
cMeans2()
DOCUMENT ME!private void
cMeans3()
cMeans3.private void
computeCentroids2D(float[] buffer, float[] centroids, float[] mems)
Determines the centroids of each cluster given fuzzy membership values.private void
computeCentroids3D(float[] buffer)
Determines the centroids of each cluster given fuzzy membership values.private void
computeMemberships2D(float[] buffer, float[] centroids, float[] mems, double exponent)
Determines the membership of each feature vector in each cluster.private void
computeMemberships3D(float[] buffer)
Determines the membership of each feature vector in each cluster.void
finalize()
Prepares this class for destruction.void
runAlgorithm()
Starts the algorithm.void
setCentroids(float[] cent)
Accessor to set the centroids.-
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
-
-
-
-
Field Detail
-
BOTH_FUZZY_HARD
public static final int BOTH_FUZZY_HARD
possible values for segmentation.- See Also:
- Constant Field Values
-
FUZZY_ONLY
public static final int FUZZY_ONLY
DOCUMENT ME!- See Also:
- Constant Field Values
-
HARD_ONLY
public static final int HARD_ONLY
DOCUMENT ME!- See Also:
- Constant Field Values
-
MAX_FLOAT
public static final float MAX_FLOAT
DOCUMENT ME!- See Also:
- Constant Field Values
-
ALPHA
public static final float ALPHA
DOCUMENT ME!- See Also:
- Constant Field Values
-
buffer2
private float[] buffer2
DOCUMENT ME!
-
centroids
private float[] centroids
DOCUMENT ME!
-
classNumber
private int[] classNumber
DOCUMENT ME!
-
cropBackground
private boolean cropBackground
DOCUMENT ME!
-
destImage
private ModelImage[] destImage
Fuzzy images require 1 image for each class Hard images 1 image with assigned clusters.
-
destNum
private int destNum
DOCUMENT ME!
-
exponent
private double exponent
1/(qValue - 1).
-
iterations
private int iterations
DOCUMENT ME!
-
jacobiIters1
private int jacobiIters1
jacobiIters1 and jacobiIter2 are only used with gain correction.
-
jacobiIters2
private int jacobiIters2
-
maxChange
private float maxChange
DOCUMENT ME!
-
maxIter
private int maxIter
DOCUMENT ME!
-
mems
private float[] mems
DOCUMENT ME!
-
memsBuffer
private float[] memsBuffer
DOCUMENT ME!
-
memSize
private int memSize
DOCUMENT ME!
-
nClass
private int nClass
DOCUMENT ME!
-
newSliceSize
private int newSliceSize
DOCUMENT ME!
-
newXDim
private int newXDim
DOCUMENT ME!
-
newYDim
private int newYDim
DOCUMENT ME!
-
newZDim
private int newZDim
DOCUMENT ME!
-
objMask
private java.util.BitSet objMask
DOCUMENT ME!
-
oldMember
private float[] oldMember
DOCUMENT ME!
-
oldX
private int oldX
DOCUMENT ME!
-
oldY
private int oldY
DOCUMENT ME!
-
oldZ
private int oldZ
DOCUMENT ME!
-
orgSlice
private int orgSlice
DOCUMENT ME!
-
orgVol
private int orgVol
DOCUMENT ME!
-
orgXDim
private int orgXDim
DOCUMENT ME!
-
outputGainField
private boolean outputGainField
-
powEIntFlag
private boolean powEIntFlag
DOCUMENT ME!
-
pyramidLevels
private int pyramidLevels
pyramidLevels is only used with gain correction.
-
qValue
private double qValue
DOCUMENT ME!
-
sCentroids
private float[] sCentroids
DOCUMENT ME!
-
segBuffer
private byte[] segBuffer
DOCUMENT ME!
-
segmentation
private int segmentation
DOCUMENT ME!
-
sliceSize
private int sliceSize
DOCUMENT ME!
-
smooth1
private float smooth1
smooth1 and smooth2 are only used with gain field correction.
-
smooth2
private float smooth2
-
threshold
private float threshold
DOCUMENT ME!
-
tolerance
private float tolerance
DOCUMENT ME!
-
unusedCentroids
private boolean[] unusedCentroids
DOCUMENT ME!
-
volSize
private int volSize
DOCUMENT ME!
-
wholeImage
private boolean wholeImage
wholeImage is constrained to be true if background cropping is selected.
-
xDim
private int xDim
DOCUMENT ME!
-
yDim
private int yDim
DOCUMENT ME!
-
zDim
private int zDim
DOCUMENT ME!
-
-
Constructor Detail
-
AlgorithmFuzzyCMeans
public AlgorithmFuzzyCMeans(ModelImage srcImg, int _nClass, int _pyramidLevels, int _jacobiIters1, int _jacobiIters2, float _q, float _smooth1, float _smooth2, boolean _outputGainField, int _segmentation, boolean _cropBackground, float _threshold, int _max_iter, float _tolerance, boolean _wholeImage)
Creates a new AlgorithmFuzzyCMeans object.- Parameters:
srcImg
- source image model_nClass
- number of classes into which the image will be segmented_pyramidLevels
- Not used in the present version of the code_jacobiIters1
- Not used in the present version of the code_jacobiIters2
- Not used in the present version of the code_q
- a weighing exponent on each membership value and determines the amount of "fuzziness" of the resulting segmentation. q is required to be greater than 1 and is typically set to 2._smooth1
- Not used in the present version of the code_smooth2
- Not used in the present version of the code_outputGainField
- Not used in the present version of the code_segmentation
- possible values are hard only, fuzzy only, or both hard and fuzzy_cropBackground
- unchecked by default. This function finds the smallest bounding box outside of which all image pixel values are below the image threshold. Values inside the bounding box are copied to a smaller array to save space and calculations are performed with this reduced array. However, these pixels outside the box are restored for the production of the hard and fuzzy segmented images. In the hard and fuzzy segmentation cases values outside the box all have a value of 0._threshold
- The default value is the image minimum value. In the centroid calculation only those pixels whose values equal or exceed threshold are used in the centroid calculaton. In the hard segmentation pixels whose values are less than threshold or not in a selected VOI if the whole image is not used are set to a segmentation value of 0, meaning that these pixels are outside of the specified classes._max_iter
- Maximum allowed iterations of main program loop_tolerance
- The iteration continues until either the user specified maximum number of iterations has occcured or until convergence has been detected. Convergence occurs when all membership functions over all pixel locations j change byless than the tolerance value between 2 iterations._wholeImage
- If true apply algorithm to the whole image - constrained to be true if background cropping is selected. If false, only apply to VOI regions.
-
AlgorithmFuzzyCMeans
public AlgorithmFuzzyCMeans(ModelImage[] destImg, ModelImage srcImg, int _nClass, int _pyramidLevels, int _jacobiIters1, int _jacobiIters2, float _q, float _smooth1, float _smooth2, boolean _outputGainField, int _segmentation, boolean _cropBackground, float _threshold, int _max_iter, float _tolerance, boolean _wholeImage)
Creates a new AlgorithmFuzzyCMeans object.- Parameters:
destImg
- list of image models where result image is to storedsrcImg
- source image model_nClass
- number of classes into which the image will be segmented_pyramidLevels
- Not used in the present version of the code_jacobiIters1
- Not used in the present version of the code_jacobiIters2
- Not used in the present version of the code_q
- a weighing exponent on each membership value and determines the amount of "fuzziness" of the resulting segmentation. q is required to be greater than 1 and is typically set to 2._smooth1
- Not used in the present version of the code_smooth2
- Not used in the present version of the code_outputGainField
- Not used in the present version of the code_segmentation
- possible values are hard only, fuzzy only, or both hard and fuzzy_cropBackground
- unchecked by default. This function finds the smallest bounding box outside of which all image pixel values are below the image threshold. Values inside the bounding box are copied to a smaller array to save space and calculations are performed with this reduced array. However, these pixels outside the box are restored for the production of the hard and fuzzy segmented images. In the hard and fuzzy segmentation cases values outside the box all have a value of 0._threshold
- The default value is the image minimum value. In the centroid calculation only those pixels whose values equal or exceed threshold are used in the centroid calculaton. In the hard segmentation pixels whose values are less than threshold or not in a selected VOI if the whole image is not used are set to a segmentation value of 0, meaning that these pixels are outside of the specified classes._max_iter
- Maximum allowed iterations of main program loop_tolerance
- The iteration continues until either the user specified maximum number of iterations has occcured or until convergence has been detected. Convergence occurs when all membership functions over all pixel locations j change byless than the tolerance value between 2 iterations._wholeImage
- If true apply algorithm to the whole image - constrained to be true if background cropping is selected. If false, only apply to VOI regions.
-
-
Method Detail
-
finalize
public void finalize()
Prepares this class for destruction.- Overrides:
finalize
in classAlgorithmBase
-
runAlgorithm
public void runAlgorithm()
Starts the algorithm.- Specified by:
runAlgorithm
in classAlgorithmBase
-
setCentroids
public void setCentroids(float[] cent)
Accessor to set the centroids.- Parameters:
cent
- Centroids to set.
-
cleanUp
private void cleanUp()
Cleans up the memory usage.
-
cMeans2
private void cMeans2()
DOCUMENT ME!
-
cMeans3
private void cMeans3()
cMeans3.
-
computeCentroids2D
private void computeCentroids2D(float[] buffer, float[] centroids, float[] mems)
Determines the centroids of each cluster given fuzzy membership values.- Parameters:
buffer
- DOCUMENT ME!centroids
- DOCUMENT ME!mems
- DOCUMENT ME!
-
computeCentroids3D
private void computeCentroids3D(float[] buffer)
Determines the centroids of each cluster given fuzzy membership values.- Parameters:
buffer
- DOCUMENT ME!
-
computeMemberships2D
private void computeMemberships2D(float[] buffer, float[] centroids, float[] mems, double exponent)
Determines the membership of each feature vector in each cluster.- Parameters:
buffer
- DOCUMENT ME!centroids
- DOCUMENT ME!mems
- DOCUMENT ME!exponent
- DOCUMENT ME!
-
computeMemberships3D
private void computeMemberships3D(float[] buffer)
Determines the membership of each feature vector in each cluster.- Parameters:
buffer
- DOCUMENT ME!
-
-