The idea of thresholding can be extended to encompass multiple criteria. For example, color images contain different information in the various color channels. Gray-scale images contain additional information in the local neighborhood of each pixel: for example, the local standard deviation or the local contrast. For each pixel, multiple criteria can be defined to determine whether they belong to a feature or to the background. Figure 2.12 demonstrates a difficult segmentation situation where multidimensional thresholding may help. A histology section of a rat aorta taken under phase-contrast microscopy is shown in Figure 2.12A and one taken under fluorescent microscopy is shown in Figure 2.12B. Before histology, the lumen of the ex vivo aorta was filled with a green fluorescent dye that stains cell membranes10; therefore, the inner part of the aorta wall is more strongly fluorescent than the outer part (Figure 2.12B). Based on pure intensity thresholds, the aorta wall cannot be segmented from the lumen in Figure 2.12A because the intensities are very similar (mean image value in lumen, 85; mean value of wall, 89).
Nonetheless, the aorta wall and the lumen can be separated, because the standard deviations are very different (CTlumen = 19 and ctwall = 38). A suitable filter would be the local variance or the range operator, followed by strong Gaussian blurring. The local variance operator replaces each pixel by the variance of the pixel values inside an n x n neighborhood. The range operator replaces a pixel by the difference between maximum and minimum value in an n x n neighborhood. By using the result of this filter for red colors and the fluorescent image for green, and by using Figure 2.12A for the luminance information, a composite image can be created (Figure 2.13A) where strong green or blue colors indicate the inner wall, red and orange hues indicate the outer wall, and darker areas indicate the lumen. A thresholding strategy can be seen in Figure 2.13B, which shows a two-dimensional histogram: the pixel counts of the filtered version of Figure 2.12A in one dimension combined with Figure 2.12B in the other dimension.
FIGURE 2.12 Example of difficult intensity-based segmentation. A phase-contrast microscopy image of a histology section of the rat aorta is shown (A). Image values between the blood vessel wall and the aorta are very similar, but the standard deviation (irregularity) of the wall, where individual cells become visible, is higher. Furthermore, the inner side of the vessel wall was stained fluorescently and can be identified easily in a fluorescent microscopy image (B).
The two-dimensional histogram reveals a very prominent peak where the local variance operator has low values (the homogeneous area of the lumen) and where at the same time there is no fluorescence. Low fluorescence, in combination with high local variance (the cell layer of the outer aorta wall), creates the peaks labeled "ow" in Figure 2.13B. Finally, a comparatively small number of pixels have high fluorescence in Figure 2.12B in combination with some irregularity in Figure 2.12A. This combination creates a third peak ("iw"), which indicates the inner wall, in Figure 2.13B.
Higher-dimensional feature vectors can be devised. In topic 8 we describe how local pixel behavior (texture) can be quantified. Often, it is sufficient to separate the pixel classes with simple rectangular or elliptical thresholds (e.g., a square from 0,0 to 60,60 in Figure 2.13B can separate the lumen pixels). However, unsupervised methods exist to assign the points in a multidimensional histogram to classes: k-means clustering and fuzzy c-means clustering. For both clustering methods, it is necessary to know the number of clusters K in advance. In the context of segmentation, K is identical to the number of classes into which the image is to be subdivided. The examples of Figures 2.12 and 2.13 have three classes (bk, iw, and ow); therefore, K = 3 in this example. The goal of k-means clustering is to assign each relevant point Pi = (xi,yi) (e.g., each nonzero point in the histogram) to one cluster in such a manner that the sum of the squared distances of each point to its assigned cluster centroid Cc = (xc,yc) is minimized. In the general case, the points and centroids are n-dimensional, and the distance metric Dic between point Pi and centroid Cc is usually the Euclidean distance. K-means clustering requires the following steps:
Step 1. Initialize all centroids Cc for
Often, local maxima or random initial locations are used. Alternatively, centroids may be placed manually.
FIGURE 2.13 Multichannel thresholding. The upper image shows a composite created from Figure 2.12A (luminance), Figure 2.12B (green-blue hues), and the local range operator applied to Figure 2.12A (red-orange hues). A two-dimensional histogram of the last two images (B) shows peaks for the lumen (bk), the outer wall (ow) with high local irregularity but low fluorescence, and the inner wall (iw) with intermediate irregularity and high fluorescence.
Step 2. Populate a N x K assignment matrix U, where N is the number of points to be assigned and U(i,c) contains the value 1 when point Pi is assigned to cluster Cc, and the value 0 otherwise. The cluster assignment is determined for each point Pi by computing its distance to all cluster centroids Cc and choosing the centroid with the smallest distance. Each point can only be assigned to one cluster.
Step 3. Recompute the centroid locations by using the equation
Step 4. Repeat steps 2 and 3 until the clustering process has converged. Convergence is achieved when either the matrix U does not change between two iterations, or the centroids move less than a predetermined distance e.
For a multidimensional histogram, the cluster assignment of all locations in the histogram needs to be translated back into the original image. Each location of Pi corresponds to a vector of values in the various channels of the original image (irregularity and fluorescence in the examples of Figures 2.12 and 2.13). In the simplest form, each pixel of the original image channels would be examined: Its associated feature vector is used to look up the assigned cluster in the matrix U, and the cluster number is the new image value of the segmented image.
Fuzzy c-means clustering follows a similar principle, but the membership of a point Pi in cluster Cc is continuous; that is, the values in the membership matrix U may assume any value between 0 and 1, and each point Pi is to some degree a member of all clusters. The membership function can be very flexible, but a suitable membership function is D^1, the reciprocal of the Euclidean distance between point Pi and centroid Cc under the assumption that neighboring pixels have the distance 1. Fuzzy c-means clustering follows the same algorithm as k-means clustering. The distinction is that the matrix U in step 2 is computed through the membership function rather than by determining the shortest distance. The final cluster assignment for Pi takes place after the algorithm has converged by choosing the cluster c for which U(i,c) has the highest value.
Finally, region splitting and merging deserve to be mentioned as unsupervised segmentation methods. From the pixel feature vector, a similarity measure can be defined. For example, when two feature vectors have a Euclidean distance below e, they are considered similar and the associated pixels are considered to belong to the same class (i.e., feature). Connected pixels of the same class form a region. The following conditions hold true for all regions: (1) regions are composed of connected pixels; (2) pixels may belong to one region only, that is, regions are nonoverlapping; and (3) all regions, joined together, fill the original image. Region splitting is a top-down segmentation approach where the image is originally considered to be one region. If pixels within the region fail the similarity criterion, the region is split into four equal-sized rectangular subregions. Each subregion is recursively analyzed and split in the same manner until all pixels within individual regions meet the similarity criterion and splitting is no longer possible. The disadvantage of region splitting is its tendency to produce distinctly rectangular regions, which can be perceived as an unnatural segmentation of the image.
Region merging is the complementary bottom-up approach. Adjacent pixels are joined to form regions if they meet the similarity criterion. Iteratively, the regions formed in such a manner are joined if they meet the similarity criterion until no more regions can be joined. Frequently, region splitting and merging are combined into the split-merge approach, where one iteration of splitting is followed by one iteration of merging until no more splitting or merging is possible. The segmentation results of the split-merge segmentation tend to follow much more the natural object outlines in the image than the region-split segmentation alone.
