Understanding undersegmentation and region splitting
Peter Eggleston
A corollary case to the oversegmentation problem (see Vision Systems Design, Dec. 1998, p. 21) is that of undersegmentation. In undersegmentation, segmenting processes are applied to extract objects of interest from an image as adjacent or overlapping objects, rather than discrete components. The best solution to the undersegmentation problem is to avoid it. For example, the techniques of region growing (see Vision Systems Design, Nov. 1998, p. 21) can be used as a segmentation method to deter undersegmentation. However, even these methods might produce undersegmented results with some classes of data.
Morphology-based operations
A technique commonly used to dissect connected regions is a morphological operation called an "opening." An opening is an erosion operation followed by a dilation step. When a binary image is eroded, "0" pixels remain as zeros, whereas "1" pixels are set to 0 if any of the nearest neighbors is a zero. That is, the edges of the regions are eroded away. When an image is dilated, the 1 pixels remain 1s, whereas 0 pixels are set to 1 if any of the nearest neighbors is a one.
Dilation grows the regions outward. It is important to have a symbolic processing library available for implementation of this technique, so as to perform the opening operations on actual data objects, rather than on binary images. Otherwise, the unique identity of the objects is lost once they are dilated, because they will often merge back into one another. A useful but less powerful approach is to label (assign a unique integer identifier to all pixels in a binary blob) each object after erosion but before dilation.
This morphological segmentation may be fragile and even fail if the objects being segmented are of differing sizes, irregular in shape, and have holes or perforations within their bodies. In this case, the regions may need to be preprocessed first. Typical preprocessing steps would be to fill holes interior to the regions and to clip away and smooth the edges. Methods are available to overcome these shortcomings by using more sophisticated methods to dissect objects of interest.
To implement region segmentation (see Fig. 1), an undersegmented image representation is first produced with a binary threshold operation. This results in the segmentation of the objects from the background, but because the objects are overlapping, they are segmented out as one large contiguous region, as opposed to discrete objects.
To spit the regions into distinct objects, a recursive shrink/split/regrow algorithm is used. The shrink and regrow operations being performed by the morphological operators erode and dilate, respectively. Erosions are done in small steps, pealing away one layer at a time. A check for splitting is made after each step. A parameter for the maximum number of contract steps is then used to limit the overall number of erosion steps, which limits the size of the cut that can be made to dissect a region. Cuts are made across the isthmus--the area that connects two regions. The separated regions resulting after the cuts are called seeds, and these are subsequently dilated to regrow the regions. The same number of dilation steps is applied to each region as were taken in the erosion process.
For this morphological splitting, ideal objects have small isthmuses, compared to their relative size. However, if either adjacent component is small, then the isthmus may only be slightly narrower than that component. Very often, if a component has shrunk to a width of one (that is, one more erosion step will eliminate it), then that component is not a good candidate for cutting from its neighbors. The result will be that the object is not split, or the larger object will be cut across its body in an undesired manner (see Fig. 2).
There are two ways in which this excessive splitting can be avoided. First, a parameter of minimum seed size can be used to eliminate components that have small seeds and are adjacent to components with large seeds. That is, components with seed areas less than a minimum seed size are eliminated if they are adjacent to a component with a seed area greater than or equal to the minimum seed size. Components with relatively small seeds can be merged with their neighbors, or simply ignored. This can be adaptive to the data if a parameter is used that is calculated from the ratio of the sizes of two adjacent components.
The splitting technique works only if the objects to be segmented are convex in nature. That is, they must have a shape that can be characterized as ovoid, where the connections to other objects have an acute indentation. In some instances, pre-processing steps can be employed to enhance the definition of the shape of the objects, resulting in a more ideal first segmentation from which the convex segmentation can proceed. One such approach is to apply a morphological top-hat filter (see Fig. 3). Because even this strategy does not work in all cases, other techniques such as feature-based splitting have been devised.
Feature-based splitting
Feature-based region splitting is implemented by recursively splitting large objects into smaller components based on some attribute such as color, texture, intensity, or variance. This is a reiterative process that is continued until the distribution of the selected feature is uniform over each resulting region. Note that this approach is opposite to the region-growing algorithm, where regions are built up from individual pixels (see Vision Systems Design, Nov. 1998, p. 21).
An easy way to implement feature-based region splitting is to intensity-threshold each object. A more sophisticated approach is to perform statistical analysis on each region. For instance, a peak-valley analysis of the associated pixel intensity histograms for each object could be performed (see Vision Systems Design, Oct. 1998, p. 21). For each region in the segmented-image representation, a pixel intensity histogram is created. Only pixels that lie within each region are used to compute the histograms. Again, the implementation of this technique is facilitated through the use of programming tools that support symbolic and arbitrary region-of-interest processing. The thresholds resulting from the histogram analyses are used to threshold the undersegmented regions.
Similar approaches can be devised by considering other attributes of the regions such as color, shape, and size, among others. Some example variants are
Segment when regions exceed some threshold. Preference should be given to some ideal size.
Segment when colors are not the desired types or based on the variance of the color distribution in each region.
Segment when the shape of the regions is not the desired type. Appropriate shape features might be elongation, boundary-to-perimeter, bounding-rectangle-fill, or major axis orientation.
Contrast-based splitting
Inter-region contrast is the second metric that can be used in splitting undersegmented regions. This technique assumes that uniformity exists in the regions and that some change in value or contrast exists at the divisor between objects that are unique. For instance, if two touching light-colored balls are placed on a dark background, an intensity-based approach would segment the balls out from the background but might not be sensitive enough to segment the balls from each other. Because the balls have some curvature where they touch, their surfaces would exhibit a change in shading and, therefore, create contrast within the segmented area (see Fig. 4).
A region-splitting algorithm based on contrast can split objects into smaller segments by applying thresholds that are selected to maximize the global average contrast of edges detected across the image algorithm (see Vision Systems Design, Oct. 1998, p. 22). The contrast is calculated by taking the difference of adjacent pixels that lie on either side of the edges in a boundary. This is an intricate process, but can be summarized as follows:
For each intensity level existing in the segments, threshold the segments and then calculate the average contrast across all of the new edges that are created (across the isthmuses).
Select the threshold value that gives the greatest number of new edges with the greatest contrast.
Reiterate until no new regions are created.
A minimal contrast parameter can be used to limit the granularity of the resulting segmentation. As always, these techniques can be applied to the raw intensity values or to some transformation of the image values (see Vision Systems Design, Sept. 1998, p. 32).
A future Software Vision will present another part of basic segmentation--edge- and line-segmentation operators. And in another article we will discuss the application of grouping and merging techniques to line and edge segments, in contrast to the region segments previously covered.
FIGURE 1. Adjacent or slightly overlapping objects can be dissected from one another using the convex-segmentation technique. Because there is no change in intensity at their boundaries, an initial segmentation of the bronze scanning-electron-microscope image extracts the objects as one connected blob (center). A series of morphological erosion steps reduces the size of the objects until they split at the points of minimum width, as shown in red (right).
FIGURE 2. Ideal candidates for convex segmentation have small isthmuses, compared to their relative sizes. However, if either of the components is small, then the isthmus may only be slightly narrower than that component. The result is that the object will not be split or will be cut across its body in an undesired manner.
FIGURE 3. The convex-segmentation technique works only if the objects to be segmented are convex in nature. That is, they must have a shape that can be characterized as ovoid, where the connections to other objects have an acute indentation. In some instances, pre-processing steps can be employed to enhance the definition of the shape of the objects, resulting in a more ideal first segmentation from which the convex segmentation can proceed. One such approach is to apply a morphological top-hat filter to "round" the particles, which allows an intensity-based segmentation to create larger indents where the particles touch.
FIGURE 4. Splitting-by-contrast is a technique that can be used to break up objects that are overlapping. This technique assumes that uniformity exists in the regions and that some change in value or contrast exists at the divisor between objects. In this image, a threshold-based segmentation technique extracts the spheres from the background, but not from one another. Changes in intensity caused by light interacting with the curvature of the spheres create contrast, which can detect the interobject boundaries.
PETER EGGLESTON is senior director of business development, Imaging Products Division, Amerinex Applied Imaging Inc., Northampton, MA; e-mail: [email protected].
