Class AlgorithmMSpectralFuzzyCMeans

  • All Implemented Interfaces:
    java.awt.event.ActionListener, java.awt.event.WindowListener, java.lang.Runnable, java.util.EventListener

    public class AlgorithmMSpectralFuzzyCMeans
    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 < 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.

    /** 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 < 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.

    A dialog for each image will ask the user for a threshold value for that image. The default value is the image minimum value. In the centroid calculation only those pixels whose values equal or exceed threshold in all of the images are used in the centroid calculation. In the hard segmentation pixels whose values are less than threshold in any of the images or not in the selected first image VOI if the whole image is not used are set to a 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 first image pixel values are below the first 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 outisde the box all have a value of 0. If the cropping checkbox is selected, the user is constrained to select the whole image rather than VOI regions.

    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 range from 0.0 to 1.0. If boundary cropping is used, pixels outside the bounding box are all assigned the value 0.0.

    The first dialog provides buttons for loading and removing images. The multispectral dialog has a list of loaded images. The button labeled Load another image causes an Open File dialog to appear. An opened file will only cause an image to be added to the loaded images list if it has the same dimensionality as the original image and if the length of each dimension is the same as that of the original image. Also, if the original image is not color, then the later loaded images cannot be color.

    The button labeled Remove selected image can be used to remove one image from the list. However, the original image that was present when the multispectral file menu command was invoked(the first image in the list) cannot be removed. This button will only be enabled when at least 2 images are in the list.

    If the first loaded image is color, checkboxes appear allowing the user to select red, green, and blue components. The default is all components selected.

    A later dialog appears for every black and white image and for every selected component of every color image and the signal thresholds and initial centroids are entered on these later dialogs.

    Image Types:
    This algorithm can be applied to 2D and 3D data sets that are not COMPLEX.

    References: This code is not original - it is simply a ported subset of 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:
    JDialogMSFuzzyCMeans, AlgorithmMSpectralFuzzyCMeans, JDialogCentroidThreshold
    • Field Detail

      • BOTH_FUZZY_HARD

        public static final int BOTH_FUZZY_HARD
        possible values for segmentation.
        See Also:
        Constant Field Values
      • buffer2

        private float[] buffer2
        DOCUMENT ME!
      • centroids

        private float[] centroids
        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!
      • doBlue

        private boolean doBlue
        DOCUMENT ME!
      • doGreen

        private boolean doGreen
        DOCUMENT ME!
      • doRed

        private boolean doRed
        DOCUMENT ME!
      • exponent

        private float exponent
        DOCUMENT ME!
      • imageNumber

        private int imageNumber
        DOCUMENT ME!
      • iterations

        private int iterations
        DOCUMENT ME!
      • jacobiIters1

        private int jacobiIters1
        jacobiIters1 and jacobiIter2 are only used with gain field 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!
      • newVolSize

        private int newVolSize
        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!
      • 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.
      • qVal

        private float qVal
        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
      • spectraNumber

        private int spectraNumber
        DOCUMENT ME!
      • srcImage

        private ModelImage[] srcImage
        DOCUMENT ME!
      • threshold

        private float[] threshold
        DOCUMENT ME!
      • tolerance

        private float tolerance
        DOCUMENT ME!
      • volSize

        private int volSize
        DOCUMENT ME!
      • wholeImage

        private boolean wholeImage
        wholeImage is constrained to be true.
      • xDim

        private int xDim
        DOCUMENT ME!
      • yDim

        private int yDim
        DOCUMENT ME!
      • zDim

        private int zDim
        DOCUMENT ME!
    • Constructor Detail

      • AlgorithmMSpectralFuzzyCMeans

        public AlgorithmMSpectralFuzzyCMeans​(ModelImage[] destImg,
                                             ModelImage[] srcImg,
                                             int _nClass,
                                             int _pyramidLevels,
                                             int _jacobiIters1,
                                             int _jacobiIters2,
                                             float _q,
                                             float _smooth1,
                                             float _smooth2,
                                             boolean _outputGainField,
                                             int _segmentation,
                                             boolean _cropBackground,
                                             int _maxIter,
                                             float _tolerance,
                                             boolean _doRed,
                                             boolean _doGreen,
                                             boolean _doBlue,
                                             boolean _wholeImage)
        AlgorithmMSpectralFuzzyCMeans - Constructor.
        Parameters:
        destImg - list of image models where result image is to stored
        srcImg - list of source image models
        _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.
        _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.
        _doRed - If true, do red component of color image
        _doGreen - If true, do green component of color image
        _doBlue - If true, do blue component of color image
        _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 class AlgorithmBase
      • setCentroids

        public void setCentroids​(float[] centroids)
        DOCUMENT ME!
        Parameters:
        centroids - DOCUMENT ME!
      • setThreshold

        public void setThreshold​(float[] threshold)
        DOCUMENT ME!
        Parameters:
        threshold - DOCUMENT ME!
      • cleanUp

        private void cleanUp()
        Cleans up the memory usage.
      • cMeans2

        private void cMeans2()
        DOCUMENT ME!
      • cMeans3

        private void cMeans3()
        DOCUMENT ME!
      • ComputeCentroids2D

        private void ComputeCentroids2D​(float[] buffer,
                                        float[] centroids,
                                        float[] mems,
                                        float qVal)
        ComputeCentroids2D - Determine the centroids of each cluster given fuzzy membership values.
        Parameters:
        buffer - DOCUMENT ME!
        centroids - DOCUMENT ME!
        mems - DOCUMENT ME!
        qVal - DOCUMENT ME!
      • ComputeCentroids3D

        private void ComputeCentroids3D​(float[] buffer,
                                        float[] centroids,
                                        float[] mems,
                                        float qVal)
        ComputeCentroids3D - Determine the centroids of each cluster given fuzzy membership values.
        Parameters:
        buffer - DOCUMENT ME!
        centroids - DOCUMENT ME!
        mems - DOCUMENT ME!
        qVal - DOCUMENT ME!
      • ComputeMemberships2D

        private void ComputeMemberships2D​(float[] buffer,
                                          float[] centroids,
                                          float[] mems,
                                          float exponent)
        ComputerMemberships2D - Determine 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,
                                          float[] centroids,
                                          float[] mems,
                                          float exponent)
        ComputerMemberships3D - Determine membership of each feature vector in each cluster.
        Parameters:
        buffer - DOCUMENT ME!
        centroids - DOCUMENT ME!
        mems - DOCUMENT ME!
        exponent - DOCUMENT ME!
      • distancems2

        private float distancems2​(float[] buffer,
                                  int index,
                                  float[] centroids,
                                  int c)
        This function performs a truncated FMV cycle. It stops performing V-cycles at the pyramid level given by 'truncLevel'.
        Parameters:
        buffer - DOCUMENT ME!
        index - DOCUMENT ME!
        centroids - DOCUMENT ME!
        c - DOCUMENT ME!
        Returns:
        DOCUMENT ME!
      • distancems3

        private float distancems3​(float[] buffer,
                                  int index,
                                  float[] centroids,
                                  int c)
        DOCUMENT ME!
        Parameters:
        buffer - DOCUMENT ME!
        index - DOCUMENT ME!
        centroids - DOCUMENT ME!
        c - DOCUMENT ME!
        Returns:
        DOCUMENT ME!