SECTION I - DESCRIPTION OF THE PROBLEM OR OBJECTIVE THAT MOTIVATED THE INNOVATION'S DEVELOPMENT

A. - General description of problem/objective:

Segmentation is a partitioning of a data into related sections or regions. For remotely sensed imagery data of the Earth, an example of segmentation would be a labeled map that sections the data into areas covered by distinct Earth surface covers such as water, snow, types of natural vegetation, types of rock formations, types of agricultural crops and types other man created development. In an unsupervised segmentation of data, the initial labeled map may consist of generic labels such as region 1, region 2, etc., which are converted to meaningful labels after post-segmentation analysis.

Segmentation is a key first step in a number of approaches to data analysis and compression. In data analysis, the group of data points contained in each region provides a good statistical sampling of data values for more reliable labeling based on data feature values. In addition, the region shape can be analyzed as an additional clue for the appropriate labeling of the region. In data compression, the regions form a basis for compact representation of the data. The quality of the prerequisite data segmentation is a key factor in determining the level of performance of most of these data analysis and compression approaches.

Determining the best possible data segmentation for a given level of detail is an impossible task with current technology. However, excellent data segmentation results can be obtained with the herein disclosed hybrid of region growing and spectral clustering, even though it can only be shown to be stepwise optimal. However, for even moderately sized data sets, this approach leads to a combinatorial explosion of computations making it impractical. This combinatorial explosion is limited by a herein disclosed recursive formulation of this segmentation approach.

Different applications require different levels of segmentation detail. Further, a particular application may require different levels of segmentation detail depending on the data objects being segmented. Thus, a choice of several levels of segmentation detail may be useful. The segmentation approach disclosed herein produces a hierarchical set of segmenations, based on natural convergence points. An analyst can pick and choose between the segmentations at different levels in the segmentation hierarchy to produce the most appropriate segmentation for the particular application.

B. - Key or unique problem characteristics:

For any segmentation application, the ideal would be to produce the most optimal segmentation for a given number of regions and a given mathematical criterion. However, to actually do this for all but very small data sets would be a huge computational task. Consider what it would entail to evaluate all possible segmentations for an n pixel image data set. One would first have to evaluate all possible 2 region segmentations. Such 2 region segmentations include all possible segmentations with 1 pixel in one region and n-1 pixels in the other for _nC₁ or n! cases, plus all possible segmentations with 2 pixels in one region and n-2 pixels in the other for _nC₂ or cases, and with 3 pixels in one region and n-3 pixels in the other for _nC₃ or cases, down to all possible segmentations with pixels in one region and pixels in the other for _nC_n/2 or cases. (Note that for integer math, does not equal if n is odd.) One does not have to continue past all possible segmentations with pixels in one region and pixels in the other since those segmentations have already been evaluated. However, for the case when n is even, half of the segmentations tabulated by _nC_n/2 are duplicates. Thus:

(1a)

where n is the number of pixels in the image (where n >= 2) and _nN₂ represents the number of possible 2 region segmentation for an n pixel image. If the summation in Equation (1a) is extended to n-1, the additional terms correspond to duplicate segmentations in the first half of the sum. Noting also that _nC₀ =_nC_n = 1 (see [1]), we then have:

nN2 =

(1b)

According to [1],

(2)

Setting x = 1 and substituting in Equation (1b), we get:

nN2 =

(3)

Table 1 shows the result from Equation (3) for several values of mxm=n. Clearly, the number of different segmentations that must evaluated quickly become extremely large as the size of the image grows. And this is even before 3 region, 4 region, etc. segmentations are even considered. Thus, using explicit evaluation to find the optimal segmentation for all but the very smallest data sets is a computationally impossible task.

We have shown that using explicit evaluation to find the optimal data segmentation is computationally unfeasible. However, we need not totally ignore the idea of optimality in devising a segmentation scheme. Beaulieu and Goldberg [2] show that iterative region growing, where most similar pairs of spatially adjacent regions are merged first, is a hierarchical stepwise optimization processes. Beaulieu and Goldberg further show that if each iteration of the region growing process is statistically independent, hierarchical stepwise optimization will produce the optimal data segmentation at any iteration (i.e., for any number of regions). However, since for any realistic data set the iterations of the region growing process will not be statistically independent, region growing segmentation by hierarchical stepwise optimization is necessarily a sub-optimal approach to finding data segmentations. Nevertheless, this approach can produce high quality data segmentation results.

Schachter, et al [3] and Kettig and Landgrebe [4] and suggest that region growing segmentation be performed in an iterative parallel fashion. Tilton and Cox [5] suggest that iterative parallel region growing could become computationally feasible if implemented on parallel computing platforms. However, Tilton [6] points out the desirability of associating non-spatially adjacent regions together. This reduces the total number of regions needed to represent a data set for a given level of segmentation detail. It also improves the robustness of the evaluation of the statistical characterization of each region for a given level of segmentation detail, as each region will generally consist of a larger number of data points. As a general rule, the robustness of the statistical characterization of a set of data points improves as the number of data points increases.

Tilton [6,7] proposes a hybrid of region growing and spectral clustering, which he calls HSEG, which alternates iterations of stepwise optimal region growing with spectral clustering, in which the region growing step controls the threshold value employed in the spectral clustering step. This approach allows for the merging of non-spatially adjacent regions in a highly controlled manner. However, this controlled spectral clustering adds a heavy computational burden to the segmentation process. Tilton [6,7] reduces this computational burden by approximating the HSEG algorithm with a divide-and-conquer, recursive approach he calls RHSEG. The serial implementation of the HSEG and RHSEG algorithms is fully disclosed within this Disclosure of Invention and New Technology. An implementation of RHSEG on parallel computers is the subject of a patent application being developed under NASA Case No. GSC 14,305-1. This parallel implementation is required for obtaining practical processing times on medium to large data sets.

C. - Prior art, i.e., prior techniques, methods, materials, or devices performing function of the innovation, or previous means for performing function of software:

Most prior techniques and methods for data segmentation, particularly image segmentation, follow the classic definition of image segmentation (following [8]):

Zucker [9] summarized the above definition as follows: The first condition requires that every picture element (pixel) must be in a region. The second condition requires that each region must be connected, i.e. composed of contiguous image pixels. The third condition determines what kind of properties each region must satisfy, i.e. what properties the image pixels must satisfy to be considered similar enough to be in the same region. The fourth condition specifies that, in the final segmentation result, any merging of any adjacent regions would violate the third condition.

Under this classic definition of image segmentation the segmentation obtained is not unique. The number, N, and shape of the partitions, X₁, X₂, ..., X_N, depend on the order in which the image pixels are processed. In addition, there is no concept of optimality contained in this definition of image segmentation. Under this classic definition, all partitions that satisfy the conditions represent equally good or valid segmentations of the image.

Most segmentation approaches based on this classic definition are region growing approaches. One of the earliest (if not the earliest) descriptions of a region growing approach to image segmentation was published in 1968 by Muerle and Allen [10]. In Muerle and Allen's approach, the image is initially partitioned into square cells containing anywhere from 2x2 to 8x8 image pixels. The upper left-hand corner cell is chosen as the initial cell of the first region. All neighboring image cells are compared in turn with this initial region. If the similarity criterion is satisfied for a neighboring image cell, this image cell is combined with the initial region, possibly changing the characteristics of the initial region. When no additional image cells meet the similarity test, the first region is considered complete, and the image is scanned left to right, top to bottom to find an image cell that is not in the first region. A second region is now grown from this image cell from image cells that are not already in the first region. Additional regions are similarly grown until all image cells are in placed in a region. Once an image cell is placed in a region it cannot be considered for inclusion in a different region. Kettig and Landgrebe employed the same region growing approach in their program for sample classification of remotely sensed multispectral data [4,11].

In their survey of image segmentation techniques [12], Haralick and Shapiro classify image segmentation techniques into the following categories:

Measurement space guided spatial clustering. This approach clusters the image data in feature space and then defines a classical image segmentation by performing connected components labeling on the resulting spectral cluster map.

Single linkage region growing. This is the simplest form of region growing. Here neighboring pixels are linked together into regions based on the similarity of their individual pixel values. The characteristics of the population of pixels making up the region the neighboring pixels may already belong to are not considered. While this approach is attractive because of its simplicity, it is susceptible to inappropriate merging of two quite different regions based on the similarity of a single pair of neighboring pixels.

Hybrid linkage region growing. In the simplest version of this approach an edge operator is applied to the image data to determine which pixels are edge pixels. Then a connected component labeling is performed over the non-edge pixels to form regions. The edge pixels can either be left as unlabeled (not in any region), or the edge pixels can be assigned to the most similar spatially adjacent region.

Centroid linkage region growing. In the simplest version of this approach the image data is scanned in some predetermined manner, usually left to right and top to bottom. Each pixel value is compared to the mean value of any neighboring regions. If no neighboring region is similar enough, the pixel is established as the first pixel in a new region. If only one neighboring region mean value is similar enough, the pixel is merged into that region, and the region mean value is updated. If two or more neighboring regions are similar enough, the competing regions are compared and merged (along with the pixel under consideration) if they are similar enough, and the mean of the resulting region is updated. Otherwise, the pixel is merged with the most similar neighboring region and the mean of the region is updated. The previously described region growing approaches by Muerle and Allen [10], and Kettig and Landgrebe [4,11] are forms of centroid linkage region growing.

Using the centroid linkage approach instead of connected components labeling in hybrid linkage region growing results in a combination of the hybrid and centroid linkage approaches. If the threshold value for centroid linkage is set sufficiently high, the result would be the same as for hybrid linkage by itself. However, for lower threshold values, the centroid linkage portion of the combination will introduce additional region boundaries.

Spatial clustering. Spatial clustering is a simultaneous combination of spatial region growing with measurement space clustering. In this approach the pixels corresponding to the highest peak in the measurement space histogram are located and a restricted form of region growing is performed from these pixel locations. A neighboring pixel is included in the region if it is close enough in measurement space and its histogram probability is not higher than the histogram probability of the pixel being grown from.

Split and merge. The split and merge approach was originally developed by Horowitz and Pavlidis [8]. Under this approach, the image is recursively split into quarters until all the resulting segments satisfy a homogeneity criterion. Then region growing is performed on the resulting initial segmentation until there is no merge that can satisfy the similarity criterion.

Haralick and Shapiro's image segmentation categorization assumes the classic definition for image segmentation. As such, the image segmentations produced by these approaches are not guaranteed to be neither unique nor optimal.

Ernst, et al [13] describe an early approach that tends to minimize the non-uniqueness problem. Here, several initial cells, called "germ" cells are chosen throughout the image data, and region growing is performed evenly from each of the germ cells. Several approaches to selecting the germ cells are discussed. The recommended automatic approach is to perform edge detection to obtain a skeleton picture made up of contour lines, and select germ cells that are maximally distance from the image contours. In this form, the approach by Ernst, et al is, in Haralick and Shapiro's categorization, a combination of hybrid and centroid region linking, but with parallel region growing from each germ cell.

As mentioned earlier, Schachter, et al [3] suggest that region growing be implemented as an iterative parallel region growing process. This suggestion was made as a way to eliminate the order dependence problem. Kettig and Landgrebe [4] suggest that the most similar neighboring region be merged first. In Tilton and Cox [5], the most similar pair(s) of spatially adjacent regions are merged at each iteration. This approach was modified by Tilton [14] so that the set of region pairs merged each iteration were selected through merge constraints. These merge constraints were defined with respect to (possibly) overlapping subimages centered on each region.

In Tilton's IPRG program, a subimage with respect to a particular region is defined recursively as follows: A level 0 subimage for any region is the empty set. A level 1 subimage, with respect to a region, is the region itself. A level 2 subimage, with respect to a region, is the level 1 subimage, with respect to that region, plus all regions that are spatially adjacent to the level 1 subimage. Finally, a level n subimage, with respect to a region, is the level n-1 subimage, with respect to that region, plus all regions that are spatially adjacent to the (n-1)^st level subimage.

Merge constraint level n signifies that merges are constrained to be the best merge within the union of the level n subimages with respect to each of the potentially merging region pairs. Merge constraint level n-0.5 signifies merges are constrained to the best merge within the level n subimage with respect to only one of the potentially merging region pairs. (By the definition of a level n subimage, the level n-1 subimage of a region is contained within the level n subimage of an adjacent region. Thus, an n-0.5 merge constraint level is equivalent to constraining to the best merge within the union of the level n subimage for one region and the level n-1 subimage for the other region. The notation "n-0.5 merge constraint level" thus refers to the average level of the two subimages controlling the merging process.)

Tilton noted that employing merge constraint level 0.5 is equivalent to performing the best merge for each region in each iteration, without regard to what the best merge is for any neighboring region. This means that any particular region can be involved in multiple merges each iteration: its best merge plus the best merge of any other neighboring region. The merge constraint level 1.0 is equivalent to performing the pairwise mutually best merges for all pairs of spatially adjacent regions (with ties broken arbitrarily). As merge constraint levels are increased higher than 1.0, acceptable merges must be the best merge in larger and larger subsections of the image. The higher the merge constraint level, the closer the merge constraints come to requiring that only a single best merge over the whole image be performed per iteration. However, Tilton found that a merge constraint level of 1.0, implying best pair-wise merges, was often high enough to give reasonable results. (See also Willebeek-LeMair and Reeves [15] for another example of iterative parallel region growing utilizing best pair-wise merges.)

It was noted earlier that Beaulieu and Goldberg [2] published a description and analysis of a region growing approach that provides a theoretical basis iterative parallel region growing (such as proposed by Tilton and Cox [5]). Beaulieu's brief outline of the implementation of his Hierarchical Stepwise Optimization algorithm (HSWO) approach [16] showed how iterative parallel region growing could be efficiently implemented on conventional serial computer using ordered linked lists. However, Beaulieu's implementation still was not efficient enough to process very large remotely sensed imagery data sets, such as a full Landsat Thematic Mapper (TM) scene (typically over 7000x7000 pixels with 6 or 7 spectral bands).

Woodcock and Harward [16] describe a different approach to implementing iterative region growing on a conventional serial computer, which utilizes multiple merges per pass through the data to reduce computational requirements. Their approach is a compromise between an ideal HSWO implementation and centroid linkage region growing based on the classic logical predicate definition of image segmentation. In addition to using a global threshold value, T_glob, to limit the merges performed per pass, they also define a threshold value, T_hist, based on the histogram of the spectral distances between each region and its most similar neighboring region. If N_reg is the current number of regions, then T_hist is the value from the spectral distance histogram below which C_mxN_reg distances lie. C_m is a preset merge coefficient, 0<C_m<=1. In each pass through the data, all merges must be between neighboring regions that have not been involved previously in a merge in the current pass, and which are separated by a spectral distance less than T_pass, which is the minimum of T_glob and T_hist. T_pass normally increases monotonically from one pass to the next until it reaches the value T_glob. Woodcock and Harward then continue with a constrained region growing approach, based on region size constraints, after region growing stops based on T_glob. They demonstrated the usefulness of their segmentation in the delineation of forest stands from Landsat TM and SPOT HRV satellite imagery.

The papers by Tilton and Cox [5], Beaulieu and Goldberg [2], Beaulieu [16] and the papers by Tilton [6,7] are the only papers we have seen in which iterative parallel region growing is performed in a hierarchical stepwise fashion from the original image data. Some practitioners of iterative parallel region growing adopt multiple merge compromises like those adopted by Woodcock and Harward [17] (see also Lobo [18]). The only other instance we have found of hierarchical stepwise optimal region growing is in a recent paper by Haris, et al, [19]. However, Haris, et al initialize the region growing process with a pre-segmentation produced from a morphological segmentation approach using the watershed transform. Haris, et al, also introduce an implementation hierarchical stepwise optimal region growing using a "region adjacency graph," which contrasts with the linked list approaches of Beaulieu [16] and our HSEG algorithm. Of most interest, however, is the following statement by Haris, et al:

...The solution adopted here is based on ... stepwise optimization... In other words, the sought sequence of merges is constructed step-by-step, where at each step the region pair merge that produces the partition with the minimum value of [the dissimilarity function] is selected. Such a sequence of merges does not guarantee the construction of the optimal [partition]. The latter suggests that the sequence of region merges may contain false ones, that is, merges of dissimilar regions. The probability of a false merge depends both on the sizes of the regions to be merged and on the noise variance. Therefore, the larger the initial partition, the higher the expected number of false merges during merging. In this respect, the worst possible initial partition would be the one where each image pixel is a separate region. In our approach sever oversegmentation [of our initial partition] is avoided...

Our experience with remotely sensed imagery data from such instruments as Landsat MSS and TM, AVHRR, SPOT, GOES, etc. is just the opposite of the opinion expressed by Haris, et al above. We have consistently obtained excellent results with these data sets starting from an initial partition consisting of each image pixel as a separate region. We have always thought that the reason other researchers did not start with such an initial partition was due to computational constraints, not due to poor segmentation results.

D. - Disadvantages or limitation of prior art:

It was noted earlier that data segmentation approaches that follow the classic definition of image segmentation give results that depend on the order in which the data elements (e.g., image pixels) are processed. This is because all partitions that satisfy the conditions are considered to be equally good or valid segmentations of the image. However, it was also noted earlier that it is computationally unfeasible to find by direct evaluation the optimal data segmentation for all but the smallest data sets.

Most forms of data segmentation following the classic definition of image segmentation are region growing techniques. Region growing techniques are preferred over approaches such as "measurement space guided spatial clustering," since region growing techniques exploit spatial information and the other approaches do not.

Of all the region growing techniques, only the step-wise optimal approaches use the concept of optimality to find a unique segmentation. However, this step-wise optimality does not guarantee finding the actual optimal segmentation result after all region growing steps are completed. Nevertheless, excellent segmentation results can be achieved.

An advantage of the stepwise optimal approach is that hierarchically related segmentations at several levels of detail are a natural product of this approach. Other segmentation approaches produce a single segmentation for a given threshold. While re-running the segmentation for several threshold values can produce segmentations at several different levels of detail, the segmentations so produced will not necessarily have a hierarchical (or any other) relationship with each other.

Beaulieu [16] gives a brief outline of the serial implementation of his Hierarchical Stepwise Optimization (HSWO) approach. However, this implementation is not efficient enough to provide segmentations of very large data sets, such as a full Landsat Thematic Mapper (TM) scene (typically over 7000x7000 pixels with 6 or 7 spectral bands).

A problem with all region growing approaches, including Beaulieu's, is that non-adjacent data regions are never associated together. This leads to redundant data region labeling and a fragmentation of the statistical analysis of the region types contained in the data.

Tilton [7] introduces a hybrid of hierarchical stepwise optimal region growing with spectral clustering, in which alternates iterations of region growing and spectral clustering. In this approach, the threshold for the spectral clustering iterations is set by the previous iteration of region growing. This hybrid approach, which Tilton calls HSEG, allows for the association of similar non-adjacent data regions, but in a manner guided by the spatial information sensitive region growing process. However, the addition of the spectral clustering iterations significantly increases the computational demands of the HSEG approach. Tilton [6,7] reduces this computational burden by approximating the HSEG algorithm with a divide-and-conquer, recursive approach he calls RHSEG. Table 2 contrasts the processing times of the HSEG and RHSEG approaches when implemented on a conventional serial processing workstation. As the table shows, just two levels of recursion on a small 108x84 pixel image cuts processing time by a factor of nearly 42.

Introducing the recursive approximation does change the final segmentation results by a small amount (see Table 3). Sometimes the result improves slightly and sometimes it degrades slightly with the recursion. However, the results remain very similar with or without recursion.

1. M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Table, National Bureau of Standards, United States Department of Commerce, Ninth printing, November 1970, pp. 822-823.
2. J.-M. Beaulieu and M. Goldberg, "Hierarchy in picture segmentation: A stepwise optimization approach," IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 11, No. 2, pp. 150-163, Feb. 1989.
3. B. J. Schachter, L. S. Davis and A. Rosenfeld, "Some experiments in image segmentation by clustering of local feature vectors," Pattern Recognition, Vol. 11, No. 1, pp. 19-28, 1979.
4. R. L. Kettig and D. A. Landgrebe, "Computer classification of remotely sensed multispectral iamge data by extraction and classification of homogeneous objects," LARS Information Note 050975, Laboratory for Applications of Remote Sensing, Purdue University, West Lafayette, IN, 1975.
5. J. C. Tilton and S. C. Cox, "Segmentation of remotely sensed data using parallel region growing," Digest of the 1983 International Geoscience and Remote Sensing Sympoisum, San Francisco, CA, pp. 9.1-9.6, August 31 - September 2, 1983.
6. J. C. Tilton, "A recursive PVM implementation of an image segmentation algorithm with performance comparisons in-between the HIVE and the Cray T3E," Proceedings of the Seventh Symposium on the Frontiers of Massively Parallel Computation (Frontiers &lsquo;99), Annapolis, MD, pp. 146-153, Feb. 21-25, 1999.
7. J. C. Tilton, "Image segmentation by region growing and spectral clustering with a natural convergence criterion," Proc. of the 1998 International Geoscience and Remote Sensing Symposium, Seattle, WA, July 6-10, 1998.
8. S. L. Horowitz and T. Pavlidis, "Picture segmentation by a directed split-and-merge procedure," Proc. Second Int. Joint Conf. Pattern Recognition, pp. 424-433, 1974.
9. S. W. Zucker, "Region growing: childhood and adolescence," Computer Graphics and Image Processing, Vol. 5, pp. 382-399, 1976.
10. J. L. Muerle and D. C. Allen, "Experimental evaluation of techniques for automatic segmentation of objects in a complex scene," in Pictorial Pattern Recognition, G. C. Cheng, R. S. Ledley, D. K. Pollack and A. Rosenfeld, editors, pp. 3-13, Thompson: Washington, DC, 1968.
11. R. L. Kettig and D. A. Landgrebe, "Automatic boundary and sample classification of remotely sensed multispectral data," LARS Information Note 041773, The Laboratory for Applications of Remote Sensing, Purdue Univ., W. Lafayette, IN, 1973.
12. R. M. Haralick and L. G. Shapiro, "Image segmentation techniques," Computer Vision, Graphics, and Image Processing, Vol. 29, pp. 100-132, 1985.
13. D. Ernst, B. Bargel and F. Holdermann, "Processing of remote sensing data by a region growing algorithm," IEEE International Joint Conference on Pattern Recognition, Coronado, CA, pp. 679-683, 1976.
14. J. C. Tilton, "Image segmentation by iterative parallel region growing and splitting," Proc. of the 1989 International Geoscience and Remote Sensing Symposium (IGARSS'89), Vancouver, BC, Canada, pp. 2420-2423, July 10-14, 1989.
15. M. Willebeek-LeMair and A. P. Reeves, "Region growing on a highly parallel mesh-connected SIMD computer," Proceedings of the 2^nd Symposium on the Frontiers of Massively Parallel Computation, Fairfax, Va, pp. 93-100, October 10-12, 1988.
16. J.-M. Beaulieu, "Versatile and efficient hierarchical clustering for picture segmentation," Proc. of the 10^th Annual International Geoscience and Remote Sensing Symposium (IGARSS'90), College Park, MD, p. 1663, May 20-24, 1990.
17. C. Woodcock and V. J. Harward, "Nested-hierarchical scene models and image segmentation," International Journal of Remote Sensing, Vol. 13, No. 16, pp. 3167-3187, 1992.
18. A. Lobo, "Image segmentation and discriminant analysis for the identification of land cover units in ecology," IEEE Transactions on Geoscience and Remote Sensing, Vol. 35, No. 5, pp. 1136-1145, September 1997.
19. K. Haris, S. N. Efstratiadis, N. Maglaveras and A. K. Katsaggelos, "Hybrid image segmentation using watersheds and fast region merging," IEEE Transactions on Image Processing, Vol. 7, No. 12, pp. 1684-1699, December 1998.