[Next] [Previous] [Up] [Top]

IV. CONNECTED LABELLING USING LEGION

B. Segmentation Algorithm For Grey Level Images

The LEGION network described in Section II to segment binary images uses external stimulus to define black pixels. To use this network for grey level images, a threshold could be used to binarize each pixel intensity before it is input to the network. This is equivalent to applying a global threshold to the image and then labeling each spatially separate region by the algorithm given in the previous subsection. As mentioned before, however, this gives poor segmentation results in grey level images, because there are usually no clear boundaries between objects. Instead, pixels should be grouped together based upon the similarity between their local intensity values. Thus, to segment grey level image datasets, we utilize a LEGION network in which external stimulus is applied uniformly to all oscillators in the network, and dynamic connection weights are assigned values that reflect the similarity between the corresponding pixels of coupled oscillators.

Our segmentation algorithm for grey level images has the same three steps as the algorithm for binary image data:

G-LEGION For Grey Level Images

1. Initialization

2. Leader Indentification and Recruiting

3. Background Collection

As before, pixels are initially unlabeled and the image is scanned once for unlabeled leader pixels from where regions are grown and labeled. A straightforward assignment for dynamic connection weights between two coupled oscillators is 1/(1 + |p1 - p2|), where we use p1 and p2 to denote the pixels, as well as their intensity values, that correspond to the oscillators. A more sophisticated weight assignment, called adaptive measure to be given later, is used in this paper. Given a "similarity" metric, the grouping between two neighboring pixels, both for leader identification and recruiting, can simply be a threshold (or tolerance) applied to the pixel intensity difference. A leader has at least pixels in its potential neighborhood that are similar to the leader. Three-dimensional segmentation is readily obtained by using 3D neighborhood kernels. For example, in 2D, a 4-neighborhood kernel defines the neighboring pixels to the left of, right of, above, and below the center pixel; an 8-neighborhood kernel contains all pixels with one pixel away, including diagonal directions; and a 24-neighborhood kernel includes all pixels that are two pixels away. In 3D, a neighborhood may be viewed as a cube. A 6-neighborhood kernel contains voxels that are face-adjacent, a 26-neighborhood kernel contains voxels that are face, edge, and vertex adjacent, and 124-neighborhood includes voxels that are two voxels away. As before, the background collection step accumulates all remaining unlabeled pixels into the background.

Once a leader is identified, the recruiting process grows a region by traversing and labeling pixels along all possible paths from the leader. A path is an ordered list of pixels such that each pixel is similar to the preceding pixel along the path. Our algorithm finds all paths from the leader by processing unlabeled pixels on the boundary of the growing region with a data structure called the boundary_set. Initially, only the leader is placed into the boundary_set. At each iteration, a pixel is removed from the set, assigned the region's label, and all unlabeled similar pixels in its coupling neighborhood are placed onto the boundary_set. Our graph formulation implies that the boundary_set is unordered since we essentially identify an LCS. The recruiting process ends when the boundary_set is empty. The implementation of the boundary_set is a tradeoff between memory and computation time, which are key performance issues when dealing with large image datasets. A less memory demanding solution is to eliminate the boundary_set altogether and search the entire image for an unlabeled boundary pixel at each iteration. But this is time consuming, especially for volume data, because most of the visited pixels will not be on the boundary and thus need not be visited. A bounding box may be placed around the growing region to reduce the search. Our implementation uses a stack for the boundary_set (see also [2]). Computation time is reduced because stack operations contain simple push and pop operations and only boundary pixels are processed. The size of the stack is equal to the surface of the region, which may be large for volume datasets.

Our algorithm requires that the user set three parameters: , , and , and the parameters for the similarity metric. Each parameter has an influence on the number and sizes of segmented regions. It is easy to see that leader pixels lie in homogeneous parts of an image. and determine the identification of leaders and the minimum size for a segmented region in an image. Usually, the number of leaders increases as decreases. Since more than one leader may be incorporated into the same region, a smaller potential neighborhood does not necessarily produce more segmented regions. A smaller threshold usually yields many tiny regions in the final segmentation, and a larger value will produce fewer and larger regions. This is because when is small, tiny regions in the image can produce leaders. affects the sizes and number of final segmented regions because it determines the possible paths from a leader in the recruiting process. A smaller coupling neighborhood implies that recruiting is restricted and usually produces smaller regions. In addition, more regions are produced because fewer leaders will be placed into the same region.

Most of the interesting structures in sampled medical image datasets have relatively brighter pixel intensities when compared with other structures. The separation between objects is usually defined by a relatively large change in the intensities of pixels. In addition, an interesting object usually has a cluster of pixels that have relatively homogeneous and gradually varying pixel intensities. For example, see the bony and soft tissue structures in the CT image shown in Fig. 5a, and the cortex and the extracranial tissue in the MRI image shown in Fig. 6a. The simple threshold scheme mentioned previously applies a constant tolerance r to the difference between the intensities of two pixels. This means that a pixel p is considered similar to pixels with intensities in the range . Thus, small values of r will restrict region growing in areas such as the soft tissue in Fig. 5a, and the brain in Fig. 6a. Large values of r, however, may cause undesirable region merging between darker pixels and brighter ones - the flooding problem. This consideration led us to use an adaptive similarity measure as given in the following.

We have three criteria for defining pixel similarity. The first is that leaders should be generated from both homogeneous and brighter parts of the image. Secondly, brighter pixels should be considered similar to a wider range of pixels than darker pixels. The third criterion stipulates that regions should expand to the boundaries of objects where pixel intensities have relatively large variation. We use an adaptive tolerance scheme that satisfies the above three criteria. In this scheme, larger tolerances are used when brighter pixels participate in the similarity measure. A mapping is constructed between the grey level pixel intensities known from the imagery type, and a range of tolerance values given by the user. When two pixels are tested for similarity, their corresponding tolerance values are found and the larger of the two tolerances is applied to the difference between the pixel intensities. The following formula defines our adaptive similarity measure: two pixels p1 and p2 are similar if and only if |p1 - p2| < range(Max(p1, p2)). The function range returns the mapped tolerance value for a given pixel intensity. This mapping determines how much a segmented region depends upon the local pixel intensity variation. For example, a constant range function results in the simple tolerance scheme described earlier. In the segmentation experiments to be reported in Section V, we use three mapping functions that are linear, square, and cubic. Specifically we define these functions as, , for , , and , respectively. Since the range of pixel intensities is finite, the mapping function may be pre-computed and stored in a lookup table. This greatly reduces the segmentation time, especially when the range function is complex, because the function is used heavily within the recruiting procedure.

[Next] [Previous] [Up] [Top]