Class 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 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 

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

      • finalize

        public void finalize()
        Prepares this class for destruction.
        Overrides:
        finalize 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!