Fuzzy CMeans: Multispectral and Single Channel Algorithms
Segmentation involves dividing an image into distinct classes or types. For example, researchers may segment the brain into three classes: gray matter, white matter, and cerebrospinal fluid. There are two types of segmentation: hard and soft, or fuzzy.
Contents
Hard segmentation
A pixel is assigned to only one class. In medical images, absolute classification of a pixel is often not possible because of partial volume effects where multiple tissues contribute to a pixel or because a voxel causes intensity blurring across boundaries.
Soft, or fuzzy, segmentation
This type 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 has the value of zero if the pixel does not belong to the class. At each pixel location a class membership function has a value of 1 if the pixel belongs, with absolute certainty, to the class. 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 be 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.
Background
The Fuzzy CMeans algorithm is an unsupervised method. That is, it works without the use of a specialized set of data for determining parameters of an algorithm. This algorithm, which allows for fuzzy segmentation based on fuzzy set theory, generalizes the KMeans algorithm. The technique clusters data by iteratively computing a fuzzy membership function and mean value estimate for each tissue class. The algorithm minimizes the sum over all pixels j and all classes k of:
(EQ 1) 
where u'jk is the membership value at pixel location j for class k such that the sum over k from k = 1 to k =C (nClass) for ujk = 1.
 q is a weighing exponent on each membership value and determines the amount of "fuzziness" of the resulting segmentation. q must be greater than 1, is typically set to 2.
 y'j is the observed single channel or multispectral image intensity at location j.
 v'k is the centroid of class k
 C is a number of classes (nClass)
Users provide initial centroid values or simply use 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 iterative process that performs two computations. First, the minimization process computes the membership functions using a current estimate of the centroids.
In the single channel case (select Algorithms > Segmentation > Fuzzy Cmeans > Single channel in the MIPAV window):
(EQ 2) <math> u_{jk} = \frac {\left \ {y_j g_jv_k} \right \^{ \frac {2} {(q1)}}} {\sum_{k=1}^C \left \{y_jg_jv_k} \right\^{\frac{2} {(q1)}}} </math> 
The minimization process also computes the centroids using current estimates of the membership functions.
In the single channel case:
(EQ 3) <math> v_k = \frac {\sum j \epsilon \Omega u^q_{jk}g_jy_i} {\sum j \epsilon \Omega u^q_{jk}g^2_j} </math> 
In the multispectral case:
(EQ 4) 
where summation is over all classes k and all images s
The iteration continues until the userspecified maximum number of iterations occurs or until convergence is detected. Convergence occurs when all membership functions over all pixel locations j change by less than the tolerance value between two iterations. The default maximum iteration number is 100 for the single channel case and 200 for the multispectral case. The default tolerance is 0.01.
After entering the parameters for the algorithm in the Fuzzy CMeans dialog box (Figure 2), researchers select one of three choices for the output images:
 HARD ONLY
 FUZZY ONLY
 HARD & FUZZY BOTH
Hard segmentation produces only one unsignedbyte output image. Pixels that do not meet threshold requirements are assigned the value of 0. The first class is assigned a value of 255/(nClass); the second class is assigned a pixel value of 2 x 255/(nClass), and so on. The last class has a value of 255.
Fuzzy segmentation produces one image, of the same type as the first source image, for every segmentation class. The membership function is scaled so that the minimum membership value scales to the first source image minimum value and the maximum membership value scales to the first source image maximum value. If boundary cropping is applied, all pixels outside the bounding box are assigned the minimum value of the first source image.
If researchers apply the multispectral version of the algorithm, they can add images to a list.
Adding images to the list
To add an image to the list:
 Click Load. The Open dialog box appears.
 Select an image.
 If the following are true, MIPAV adds the image to the list

 The image has the same dimensionality as the original image.
 The length of each dimension is the same as that of the original image.
 Otherwise, an error message appears.
Removing images from the list
To remove an image from the list, click Remove.
Note: You cannot remove the original image (the first image in the list) that was present at the time you selected Algorithms > Fuzzy Cmeans > Multispectral. The Remove Image button is only enabled (active) when at least two images are in the list. 
The multispectral case allows color images to be loaded. If the original image is color, then the initial dialog box includes, by default, three selected check boxes for red, green, and blue components. If the original image is not color, then the later loaded images cannot be color.
With the single channel case, the signal threshold value is entered on the initial dialog box and the image centroids are entered on a later dialog box. The multispectral case does not have signal threshold on the initial dialog box. With the multispectral case, a later dialog box appears for every blackandwhite image or for every selected component of every color image and the signal thresholds and initial centroids are entered on these later dialog boxes.
Image types
The Fuzzy Cmeans algorithm runs on 2D and 3D datasets and can also be applied to RGB datasets. This algorithms cannot run to complex datasets.
Special notes
None.
References
Refer to the following references for more information about the Fuzzy Cmeans algorithm.
Dzung L. Pham, Chenyang Xu, and Jerry L. Prince, "A Survey of Current Methods in Medical Image Segmentation," Technical Report JHU/ECE 9901 (Baltimore: Department of Electrical and Computer Engineering, The Johns Hopkins University, 2001).
Alberto F. Goldszal and Dzung L. Pham, "Volumetric Segmentation," Chapter 12 in Handbook of Medical Image Processing, (San Diego: Academic Press, 2000).
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. 737752.
Applying the Fuzzy Cmeans algorithm
You can apply this algorithm on single images separately, or you can apply it on multispectral images.
On single images
To run this algorithm, complete the following steps:
 Start MIPAV if not already started. The MIPAV and the Output windows open.
 Open an image. After a few moments, the image appears.
 Select Algorithms > Fuzzy Cmeans > Multispectral. The Fuzzy Cmeans dialog box (Figure 2) opens.
 Complete the fields.
 Click OK.
 The Threshold & Initial Centroids dialog box appears.
 By default, MIPAV determines the value of the initial centroids by result of the total number of intensities divided by the number of classes. To change the values, click OK.
Number of desired classes

Indicates the number of groups into which the algorithm divides the dataset structures. By default, the number of desired classes is 3.


Desired exponent value

Determines the amount of "fuzziness" in the resulting segmentation. By default, the exponent value is 2.
 
End tolerance

Indicates when convergence is reached. Generally, membership functions over all pixel locations change between iterations of the application of the fuzzy Cmeans algorithm. Convergence occurs if the change is equal to or less than the end tolerance level and when all membership functions over all pixel locations change by less than the tolerance value between two iterations. By default, the tolerance is 0.01.
 
Maximum number of iterations

Indicates the maximum number of times the algorithm is applied. If convergence occurs, the system may apply the algorithm less times than the maximum number of iterations. By default, the maximum iteration value for single channel cases is 200.
 
Signal treshold

Determines the treshold. By default, the exponent value is 0.0.
 
Background cropping

Finds the smallest bounding box in the image or delineated VOI outside of which all image pixel values are below the image threshold.
 
Whole image

Applies the algorithm to the whole image.
 
VOI region(s)

Applies the algorithm only to the delineated VOIs.
 
HARD ONLY

Performs only hard segmentation on the image
 
FUZZY ONLY

Performs only fuzzy segmentation on the image.
 
HARD & FUZZY BOTH

Performs both types of segmentationhard and softon the image.
 
OK

Performs the Fuzzy CMeans algorithm on the image based on your choices in this dialog box.
 
Cancel

Disregards any changes that you made in this dialog box and closes the dialog box.
 
Help

Displays online help for this algorithm.

On multispectral images
To run this algorithm, complete the following steps:
 Start MIPAV if not already started. The MIPAV and the Output windows open.
 Open an image. After a few moments, the image appears.
 Select Algorithms > Fuzzy Cmeans > Multispectral. The Fuzzy Cmeans dialog box (Figure 3) opens.
 Complete the fields.
 To add an image to the list, click Load and then select the image in the Open dialog box. The system then adds the image to the list and then, if it has the same dimensions as the original image, opens it in a new window.
 To remove an image from the list, click Remove.
 Click OK.
 The Threshold & Initial Centroids dialog box appears.
 By default, MIPAV determines the value of the initial centroids by result of the total number of intensities divided by the number of classes. To change the values, click OK.
Note: If you are applying this algorithm to several datasets, when you click OK another Threshold & Initial Centroids window appears sequentially for each dataset. Click OK when complete. MIPAV applies the algorithm to the datasets. The resultant images appear in new image windows. 
Number of desired classes

Indicates the number of groups into which the algorithm divides the dataset structures.


Desired exponent value

Determines the amount of "fuzziness" in the resulting segmentation.
 
Boundary noise cropping

Finds the smallest bounding box outside of which all first image pixel values are below the first image threshold. To save space, MIPAV copies values inside the bounding box to a smaller array and then uses the reduced array to performs calculations.
 
Signal threshold

Appears only when you select Algorithm > Fuzzy Cmeans > Single Channel. By default, MIPAV assigns the image minimum value and uses only pixels whose values equal or exceed the theshold used in the centroid calculation. If you select the HARD ONLY option, MIPAV sets the pixels whose values are less than the threshold to a segmentation value of 0. This means that the pixels are outside of the specified classes.
 
End tolerance

Indicates when convergence is reached. Generally, membership functions over all pixel locations change between iterations of the application of the fuzzy cmeans algorithm. Convergence occurs if the change is equal to or less than the end tolerance level and when all membership functions over all pixel locations change by less than the tolerance value between two iterations. By default, the tolerance is 0.01.
 
Maximum number of iterations

Indicates the maximum number of times the algorithm is applied. If convergence occurs, the system may apply the algorithm less times than the maximum number of iterations. By default, the maximum iteration value for single channel cases is 100. The maximum number in multispectral cases is 200.
 
Background noise cropping

Finds the smallest bounding box in the image or delineated VOI outside of which all image pixel values are below the image threshold.
 
Whole image

Applies the algorithm to the whole image.
 
VOI region(s)

Applies the algorithm only to the delineated VOIs.
 
HARD ONLY

Performs only hard segmentation on the image
 
FUZZY ONLY

Performs only fuzzy segmentation on the image.
 
HARD & FUZZY BOTH

Performs both types of segmentationhard and softon the image.
 
Load

Loads the images that you select.
 
Remove

Removes the images that you select.
 
OK

Performs the FuzzyCMeans algorithm on the selected images based on your choices in this dialog box.
 
Cancel

Disregards any changes that you made in this dialog box and closes the dialog box.
 
Help

Displays online help for this algorithm.
