Filters (Wavelet): Thresholding

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.

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 C-Means 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 K-Means 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) $J=\sum _{j\varepsilon \Omega }\sum _{k=1}^{C}j_{jk}^{q}\left\|{y_{j}-v_{k}}\right\|^{2}$

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 C-means > Single channel in the MIPAV window):

(EQ 2) $u_{jk}={\frac {\left\|{y_{j}-g_{j}v_{k}}\right\|^{-{\frac {2}{(q-1)}}}}{\sum _{k=1}^{C}\left\|{y_{j}-g_{j}v_{k}}\right\|^{-{\frac {2}{(q-1)}}}}}$

The minimization process also computes the centroids using current estimates of the membership functions.

In the single channel case:

(EQ 3) $v_{k}={\frac {\sum j\epsilon \Omega u_{jk}^{q}g_{j}y_{i}}{\sum j\epsilon \Omega u_{jk}^{q}g_{j}^{2}}}$

In the multispectral case:

(EQ 4) $v_{k}=\sum _{s}\sum _{k=1}^{C}{\frac {\sum j\epsilon \Omega u_{jk}^{q}g_{j}y_{i}}{\sum j\epsilon \Omega u_{jk}^{q}g_{j}^{2}}}$

where summation is over all classes k and all images s

The iteration continues until the user-specified 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 C-Means 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 unsigned-byte 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:

1. Click Load. The Open dialog box appears.
2. 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 C-means > 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 black-and-white 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 C-means 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 C-means algorithm.

Dzung L. Pham, Chenyang Xu, and Jerry L. Prince, "A Survey of Current Methods in Medical Image Segmentation," Technical Report JHU/ECE 99-01 (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. 737-752.

Figure 1. Fuzzy C-means algorithm processing

Applying the Fuzzy C-means 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:

1. Start MIPAV if not already started. The MIPAV and the Output windows open.
2. Open an image. After a few moments, the image appears.
3. Select Algorithms > Fuzzy C-means > Multispectral. The Fuzzy C-means dialog box (Figure 2) opens.
4. Complete the fields.
5. 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.

Figure 2. Fuzzy C-Means dialog box for a single image

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 C-means 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 segmentation-hard and soft-on the image.
OK	Performs the Fuzzy C-Means 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:

1. Start MIPAV if not already started. The MIPAV and the Output windows open.
2. Open an image. After a few moments, the image appears.
3. Select Algorithms > Fuzzy C-means > Multispectral. The Fuzzy C-means dialog box (Figure 3) opens.
4. 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.

1. 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.

Figure 3. Fuzzy C-Means dialog box for multispectral images Â

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 C-means > 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 c-means 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 segmentation-hard and soft-on the image.
Load	Loads the images that you select.
Remove	Removes the images that you select.
OK	Performs the FuzzyC-Means 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.