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.

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

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.