Package gov.nih.mipav.model.algorithms

Class AlgorithmFuzzyCMeans

java.lang.Object
java.lang.Thread
gov.nih.mipav.model.algorithms.AlgorithmBase
gov.nih.mipav.model.algorithms.AlgorithmFuzzyCMeans
All Implemented Interfaces:
ActionListener, WindowListener, Runnable, EventListener
public class AlgorithmFuzzyCMeans extends AlgorithmBase
Fuzzy C-Means Segmentation algorithm

Segmentation 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 invalid input: '<' 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 invalid input: '&' 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:

  • Field Details

    • BOTH_FUZZY_HARD

      public static final int BOTH_FUZZY_HARD
      possible values for segmentation.
      See Also:

    • FUZZY_ONLY

      public static final int FUZZY_ONLY
      DOCUMENT ME!
      See Also:

    • HARD_ONLY

      public static final int HARD_ONLY
      DOCUMENT ME!
      See Also:

    • MAX_FLOAT

      public static final float MAX_FLOAT
      DOCUMENT ME!
      See Also:

    • ALPHA

      public static final float ALPHA
      DOCUMENT ME!
      See Also:

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

    • 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 stored
      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.

  • Method Details

    • finalize

      public void finalize()
      Prepares this class for destruction.
      Overrides:
      finalize in class AlgorithmBase

    • runAlgorithm

      public void runAlgorithm()
      Starts the algorithm.
      Specified by:
      runAlgorithm in class AlgorithmBase

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