Info

3 Region Growing

By normalizing each coefficient with the sum of all (1115) a filter that preserves the scale of the image is obtained.

Goshtasby and Turner [38] reported that smoothing with a Gaussian filter reduced noise and helped in thresholding of the endocardial surfaces on cardiac MR images.

Preprocessing with extremum sharpening combined with median filtering has proven to be useful in segmenting microscopic images of blood cells [14,65]. In this method, a minimum and maximum are calculated within an N by N window around each pixel (x, y). The value of the extremum operator is simply whichever of the two extrema is the closest to the value at pixel (x, y). When the pixel (x, y) has a value exactly midway between minimum and maximum, the operator takes the value of the pixel. The appropriate window size for the extremum sharpening has to be commensurate with the width of the image edges.

The extremum sharpening is usually followed by median filtering, which smoothes out the slightly ragged contours left by the sharpening operation. The standard procedure suggested in [65] for segmenting cells was: 9x9 median filter (noise removal), 3x3 extremum sharpening, and finally 5x5 median filter, followed by thresholding based on threshold determined from the histogram.

The median and Gaussian smoothing, as well as extremum sharpening, "improve" image histograms by producing images with strongly bimodal histograms. Additional techniques for making histogram valleys deeper are discussed in Weszka et al. [127].

A more elaborate approach used for specific types of images is provided by adaptive filtering techniques where the parameters of the algorithm are modified locally based on the pixel's neighborhood [51,68]. If, for example, the neighborhood has relatively constant intensity, we can assume that we are within an object with constant features and we can apply an isotropic smoothing operation to this pixel to reduce the noise level. If an edge has been detected in the neighborhood, we could still apply some smoothing, but only along the edge. Adaptive filtering combines an efficient noise reduction and an ability to preserve and even enhance the edges of image structures. Westin used adaptive filtering successfully for the thresholding of bones on CT images [126]. Adaptive filtering is discussed in Chapter 2.

Whereas thresholding focuses on the difference of pixel intensities, the region growing method looks for groups of pixels with similar intensities. Region growing, also called region merging, starts with a pixel or a group of pixels (called seeds) that belong to the structure of interest. Seeds can be chosen by an operator, or provided by an automatic seed finding procedure. In the next step neighboring pixels are examined one at a time and added to the growing region, if they are sufficiently similar based on a uniformity test, (also called a homogeneity criterion). The procedure continues until no more pixels can be added. The object is then represented by all pixels that have been accepted during the growing procedure [1,6,36,77,85,96,102,104,107,113,116].

One example of the uniformity test is comparing the difference between the pixel intensity value and the mean intensity value over a region. If the difference is less than a predefined value, for example, two standard deviations of the intensity across the region, the pixel is included in the region; otherwise, it is defined as an edge pixel. The results of region growing depend strongly on the selection of the homogeneity criterion. If it is not properly chosen, the regions leak out into adjoining areas or merge with regions that do not belong to the object of interest. Another problem of region growing is that different starting points may not grow into identical regions.

The advantage of region growing is that it is capable of correctly segmenting regions that have the same properties and are spatially separated. Another advantage is that it generates connected regions.

Instead of region merging, it is possible to start with some initial segmentation and subdivide the regions that do not satisfy a given uniformity test. This technique is called splitting [41,96,107]. A combination of splitting and merging adds together the advantages of both approaches [6, 84, 133].

Various approaches to region growing segmentation have been described by Zucker [133]. Excellent reviews of region growing techniques were done by Fu and Mui [30], Haralick and Shapiro [41], and Rosenfeld and Kak [96].

An interesting modification of region growing technique called hill climbing was proposed by Bankman et al. for detecting microcalcifications in mammograms [8]. The technique is based on the fact that in a given image f (x, y), the edge of a microcalcification to be segmented is a closed contour around a known pixel (x0, y0), the local intensity maximum. For each pixel, a slope value s(x, y) is defined as s(x, y)

where d(x0, y0, x, y) is the Euclidean distance between the local maximum pixel and pixel (x, y).

In the first step, the object's edge points are identified by radial line search emanating from the local maximum. The line search is applied in 16 equally spaced directions originating from the pixel (x0, y0), and for each direction, a pixel is considered to be on the edge if it provides the maximal slope value. Next, the edge points are used as seeds for region growing with a spatial constraint (growing the region inward, toward local maximum), and an intensity constraint (including pixels with intensity values increasing monotonically toward the local maximum). Figure 5 shows the steps of segmentation using the hill-climbing algorithm. The technique was successfully applied to segment low-contrast microcalcification clusters on mammography images. The advantages of this algorithm are that it does not need selection of a threshold and that, because it grows the region from the edges toward the center, it circumvents excessive growth of a region.

Region growing has found many other medical applications, such as segementation of ventricles on cardiac images [104], extraction of blood vessels on angiography data [48], or extraction of brain surface [21].

4 Watershed Algorithm

Watershed segmentation is a region-based technique that utilizes image morphology [16,107]. It requires selection of at least one marker ("seed" point) interior to each object of the image, including the background as a separate object. The markers are chosen by an operator or are provided by an automatic procedure that takes into account the application-specific knowledge of the objects. Once the objects are marked, they can be grown using a morphological watershed transformation [10]. Avery intuitive description of watersheds can be found in Ref. [16]. To understand the watershed, one can think of an image as a surface where the bright pixels represent mountaintops and the dark pixels valleys. The surface is punctured in some of the valleys, and then slowly submerged into a water bath. The water will pour in each puncture and start to fill the valleys. However, the water from different punctures is not allowed to mix, and therefore the dams need to be built at the points of first contact. These dams are the boundaries of the water basins, and also the boundaries of image objects.

An application of watershed segmentation to extract lymph nodes on CT images is shown in Fig. 6 [95]. In this implementation a 3x3 Sobel edge operator [36,96] is used

FIGURE 6 Image segmentation using Sobel/watershed algorithm. (A) Original image of a lymph node; (B) operator's marks: a point inside the node, and a circle enclosing the area well outside the node; (C) binary image generated from B; (D) result of a 3 x 3 Sobel edge detection operation performed on the original image A; (E) result of the watershed algorithm performed on image D using markers from image C; (F) edges of the lymph node (interior region from image E) superimposed on the original image. Reprinted with permission from J. Rogowska, K. Batchelder, G. S. Gazelle, et al. Quantitative CT lymphography: evaluation of selected two-dimensional techniques for computed tomography quantitation of lymph nodes. Investigative Radiology, vol. 31, no. 3, pp. 138-145, 1999. See also Plate 3.

FIGURE 5 Steps of segmentation with the hill climbing algorithm; (A) a 0.5x0.5 mm image showing a subtle microcalcification, (B) 16 edge points determined by the algorithm, (C) result of region growing, (D) edges of region enclosing the segmented microcalcification. Reprinted with permission from I. N. Bankman, T. Nizialek, I. Simon, et al., "Segmentation algorithms for detecting microcalcifications in mammograms", IEEE Trans. Inform. Techn. Biomed, vol. 1, no. 2, pp. 141-149, 1997. ©1997 IEEE.

FIGURE 6 Image segmentation using Sobel/watershed algorithm. (A) Original image of a lymph node; (B) operator's marks: a point inside the node, and a circle enclosing the area well outside the node; (C) binary image generated from B; (D) result of a 3 x 3 Sobel edge detection operation performed on the original image A; (E) result of the watershed algorithm performed on image D using markers from image C; (F) edges of the lymph node (interior region from image E) superimposed on the original image. Reprinted with permission from J. Rogowska, K. Batchelder, G. S. Gazelle, et al. Quantitative CT lymphography: evaluation of selected two-dimensional techniques for computed tomography quantitation of lymph nodes. Investigative Radiology, vol. 31, no. 3, pp. 138-145, 1999. See also Plate 3.

in place of the morphological gradient to extract edge strength. The original lymph node image is shown in Fig. 6A. In the first step, the operator positions a cursor inside the node (Fig. 6B). All pixels within a radius of two pixels of the mark are used as seed points for the lymph node. To mark the exterior of lymph node, the operator drags the cursor outside of the node to define a circular region, which completely encloses the node (Fig. 6C). All pixels outside this circle mark the background.

In the next step, an edge image is created using the Sobel edge operator (Fig. 6D). The edge image has high values for the pixels with strong edges. With the seed point marking the node interior, the circle marking the background (Fig. 6C), and the edge image generated by the Sobel operator (Fig. 6D), the segmentation proceeds directly with the watershed operation (Fig. 6E). The watershed operation operates on an edge image to separate the lymph node from the surrounding tissue. By using a technique called simulated immersion [119], the watershed considers whether a drop of water at each point in the edge image would flow to the interior seed point or the exterior marker. Points that drain into the interior belong to the lymph node, whereas points that drain to the exterior belong to the surrounding tissue. More formal discussions of morphological segmentation can be found in Refs. [75,119,120].

Watershed analysis has proven to be a powerful tool for many 2D image-segmentation applications [75]). An example of segmentation of microscopic image of human retina is included in Ref. [107]. Higgins and Ojard [43] applied a 3D extension of the watershed algorithm to cardiac volumetric images.

that are proportional to the magnitude of the local intensity changes, while the direction image will have gray levels representing the direction of maximum local gradient in the original image.

Most gradient operators in digital images involve calculation of convolutions, e.g., weighted summations of the pixel intensities in local neighborhoods. The weights can be listed as a numerical array in a form corresponding to the local image neighborhood (also known as a mask, window or kernel). For example, in case of a 3 x 3 Sobel edge operator, there are two 3x3 masks:

0 0

Post a comment