The segmentation results discussed in this topic generally lead to binary images, considered to be masks for the segmented features. The information contained in the image values is lost, but the spatial relationship between the mask and the features is retained. Both mask and masked image can be subjected to an analysis of texture (topic 8) or shape (topic 9). Some additional processing of the segmented images is possible to further improve the segmentation results. These steps could be referred to as post segmentation processing and include binary noise reduction and shape modification.
Morphological Image Processing
One important group of operators are called morphological operators. The concept of morphology is a comprehensive subject,23 and for our purposes in this topic, basic morphological operators are introduced more in the spirit of providing the necessary tools in a versatile toolbox than in the sense of introducing the concepts of morphology. The two basic operators are the erosion (thinning) and dilation (thickening) of shapes. A general form of the erosion and dilation operators, defined as vector additions of elements from the image and a pixel mask (called the structuring element) exist.12 However, the most common implementation of the erosion and dilation is to replace the central pixel by the minimum or maximum of its neighborhood, respectively. The neighborhood may either be the 4-neighborhood, which includes the horizontal and vertical neighbors, or the 8-neighborhood, which also includes the four diagonal neighbors. Under this definition, erosion and dilation are rank filters related to the median filter that was discussed in Section 2.2 and are defined for gray-scale images. However, erosion and dilation applied to gray-scale images are not intuitive and are rarely used. In binary images, the definition of erosion and dilation above reduces to two simple rules: If a white (foreground) pixel touches a black (background) neighbor, it turns itself into a background pixel under the erosion operation. Conversely, if a black (background) pixel touches a white (foreground) neighbor, it becomes a foreground pixel under the dilation operation. Each application of the erosion operation therefore removes a single-pixel-wide strip from the boundary of any feature and thins the feature in the process. Furthermore, individual pixels and small pixel groups (e.g., noise) are removed from the image completely. Conversely, each application of the dilation operation adds one single-pixel-wide strip to the boundary of the feature, thickening the feature in the process. Small holes inside the feature and along the boundary get filled in the process. Erosion and dilation are complementary; that is, an erosion acting on white pixels is the same as a dilation acting on the black pixels, and vice versa.
When operating on binary images, the median filter can be seen as a majority filter. If the majority of the neighborhood pixels are white, the central pixel itself becomes white, and if the majority of the neighborhood pixels are black, the central pixel turns black. Therefore, the median filter acts as a noise filter on binary images, where noise removal not only includes the removal of isolated white pixels and the filling of isolated black pixels (holes) in a feature, but also the smoothing of the boundary. Contrary to erosion and dilation, the rank filter leaves the boundary shape widely unchanged.
A possible implementation of the erosion and dilation operators is shown in Algorithm 2.6. Because of their similarity, both are implemented in the same operator, and a flag determines which operation is performed. Algorithm 2.6 contains the general form for gray-value images, but can be used without modification for binary masks. Algorithm 2.6 is designed to consider an 8-neighborhood.
Derived from erosion and dilation are the opening and closing operators. Opening is a single erosion followed by a single dilation, and closing is a single dilation followed by a single erosion. The opening operation removes individual white pixels or small pixel groups, and it separates weakly connected structures, for example, two parts of a feature that are connected by only a single pixel. The closing operation fills small interior holes and strengthens weak connections. Both operations smooth the outlines and thus simplify the shapes, whereby the size of the shape is changed only minimally. An example is given in Figures 2.16 and 2.17. Figure 2.16 shows an epifluorescent image of cell nuclei stained with DAPI, a fluorescent marker that specifically targets DNA. The image was thresholded (Figure 2.17A) and several morphological operators were applied (Figure 2.17B and C). In all cases, two iterations of the operator were applied to make the effect more visible. Whereas the effect of the erosion and dilation is plainly visible, opening and closing have a more subtle effect. The smoothing of the shape boundary can be seen clearly.
Algorithm 2.6 Erosion and dilation operators. The input image is IM with size xmax and ymax. The algorithm stores the result in IM2. Depending on the value of the variable erode, this algorithm can perform either morphological erosion or morphological dilation.
FIGURE 2.16 Cell nuclei made visible with the fluorescent DNA marker DAPI in an epi-fluorescent image.
Outlining is one possible application of this class of operators, in combination with image math. The outline is created by subtracting the original image from its dilated version. A thicker and more symmetric outline with respect to the shape boundary can be obtained by subtracting the eroded version of the image from the dilated version. In this case, the outline is 2 pixels wide. Figure 2.18 shows an example of outlining where the mask (Figure 2.17A) was dilated twice and subtracted from the undilated mask. The outlines were then superimposed over the original gray-scale image. The image outlined shows clearly which cells were included in the hysteresis threshold scheme. Outlining can therefore serve as a visualization tool. Labeling of gray-scale images with text is another example where an operation similar to outlining is helpful. Images with strong local variations of the gray values make superimposed labels difficult to read. To improve readability, the letters (assumed to be white) can be dilated several times. The original letters are then subtracted from the dilated letters, creating a black label over a white background that surrounds the letters. This combination, superimposed over the image, shows high contrast and is easy to read.
In the context of processing binary masks, two more operators are important: skeletonization and watershed segmentation. Skeletonization refers to iterative erosion with two additional constraints: A pixel may not be deleted in the erosion process if it is an endpoint or if its removal would break a feature in two.26 Skeletonization acts best on long, thin objects and extracts their medial axis, which can be thought of as the central ridge. Skeletonization is a fundamental operation for shape classification and is discussed in detail in Section 9.6.
FIGURE 2.17 Examples of morphological operators. Hysteresis thresholding of Figure 2.16 leads to the binary mask (A). The individual operations are thinning by erosion (B, left of the dividing line), thickening by dilation (B, right of the line), opening (C, left of the line), and closing (C, right of the line).
FIGURE 2.18 Outlining by computing the difference between the original mask and the dilated mask. In this example, the outline is superimposed over the unthresholded gray-scale image.
Watershed Segmentation
Watershed segmentation (often incorrectly termed the watershed transform—it is not a transform because no inverse transform to restore the original image exists) is a method to separate in a binary mask two convex shapes that partly overlap. The cells in Figure 2.16 contain typical examples. It can be seen that in the top left region of Figure 2.17A that a group of two cells and another group of three cells have not been separated by thresholding. Postprocessing of the binary mask with the watershed operator can separate those connected features. The watershed operator relies on iterative erosion and iterative dilation, both with certain constraints. If the mask is iteratively eroded, starting with the ring of pixels closest to the background, it is possible to label these rings with an image value identical to the erosion iteration number and to construct an auxiliary image from the eroded points labeled in such a manner. This auxiliary image is a gray-scale image, and the image values get higher with increasing distance of the pixels from the background. In fact, the image value is approximately the Euclidean distance of the pixel to the nearest background pixel and is therefore called the Euclidean distance map. Continuing with the iterative erosions, shapes like the cells mentioned above eventually get separated. The erosion process needs to be constrained such that isolated pixels (i.e., pixels surrounded by eight background neighbors in each and any erosion iteration) may not be eroded. These pixels coincide with local maxima in the Euclidean distance map and are called ultimate eroded points, because further constrained erosions do not change the image of ultimate eroded points. The iterative erosion process ends when only ultimate eroded points are left over. For convenience, the ultimate eroded points can now be numbered consecutively. The ultimate eroded points are now iteratively dilated. Each dilation process, according to its definition, adds a ring of pixels with the same image value as that of the originating ultimate eroded point. Dilations are constrained as well, with two constraints: First, no pixel that was a background pixel in the original mask may be added to the set (i.e., dilation is constrained to the original mask), and second, no pixel may be added to the set if it connects a feature to another feature with a different image value. In this way, merging of two features that grow from different ultimate eroded points is prevented, which is the key purpose of watershed segmentation. The relationship between the Euclidean distance map, ultimate eroded points, and watershed-segmented image is shown in Figure 2.19. Figure 2.19A is a surface rendering of the Euclidean distance map where the elevation of each pixel corresponds to its distance to the background. The peaks of the hills (i.e., points with the greatest distance to the background) coincide with the ultimate eroded points, each of which is the seed point for iterative dilation. The constrained iterative dilation leads eventually to Figure 2.19B, where each ultimate eroded point is now contained in a separate feature that is separated (black lines) from features grown from neighboring ultimate eroded points.
Watershed segmentation can be influenced by the definition of a local maximum in the Euclidean distance map. To improve the segmentation, we need to employ an alternative algorithm to generate the ultimate eroded points, which is not based on iterative erosion. Rather, the Euclidean distance of each feature pixel to the nearest background pixel is determined by an exhaustive search. The Euclidean distance map generated in this fashion can now be subjected to Gaussian smoothing to suppress small local maxima (i.e., noise). Further a priori knowledge may be included by defining the area in which a maximum needs to be unique to be recognized as a local maximum. With these two options, the final size of the segmented features, and therefore the sensitivity of the watershed segmentation, can be influenced.
FIGURE 2.19 Watershed segmentation of the binary mask in Figure 2.17C. The first step is the creation of the Euclidean distance map (A), shown here as a three-dimensional surface rendering. Higher elevations indicate a larger distance to background, and the slopes of the hills are 45°. The peaks of the hills coincide with the ultimate eroded points. A typical example is highlighted (circle). It appears as a single feature in the mask, but the original image (Figure 2.16) clearly shows this to be two different cells. Correspondingly, the Euclidean distance map exhibits two local peaks. Iterative dilation from the ultimate eroded points with the constraint that no two different features may become connected leads to the segmented image (B), where thin black (background) lines separate regions that contain its individual ultimate eroded point.
