A Region-Analysis Subsystem For Interactive Scene Analysis

I. Introduction

Most computer analyses of real-world scenes first attempt to partition the iaage into coherent regions corresponding to known objects (1, 2, 3, 4). Regions provide a convenient basis for seaantic analysis by reducing both the amount of detail and the ambiguities of interpretation found at the picture-element level.

An Interactive Scene Interpretation System (ISIS) is being developed by Stanford Research Institute's Artificial Intelligence Center as a tool for constructing and experimenting with man­ machine and automatic scene-analysis methods tailored for particular image domains (5, 6). A subsystem was developed to explore systematically region-analysis techniques applied to several image domains. We summarize our most informative find­ ings in this paper. A more complete presentation of our results can be found in (6).

11. Basic Model

Following Brice and Fennema (7), we divide region analysis into two stages: first partition and region growing. The purpose of the first par­ tition stage is to obtain a conservative initial segmentation of the image where each region con­ sists of picture elements belonging to only one object. In the region growing stage, adjacent regions with similar characteristics are merged into a single region to simplify further the organi­ zation. The desired result is a set of ·regions corresponding to distinct objects in the scene.

Region analysis is computationally expensive, making it desirable to obtain a first partition that is as coarse as possible without extending the starting regions beyond object boundaries. The common practice is to sample the picture to reduce Following Yakimovsky (3), our region-growing algorithm proceeds by serially selecting the pair of adjacent regions in the current organization that are globally "110st alike," and merging these into a single region. The order in which regions are merged ts determined by a function that com­ pares the si·ilarity of a given pair of adjacent regions with the similarities of other pairs of regions that remain to be merged. A variety of criteria for region similarity have been used, including brightness contrast (7, 8) and average color contrast (3). We present experimental re­ sults with various similarity functions in Sec­ tion IV.

The experiments described in this report are illustrated by the landscape and indoor scenes in Figure 1. The basic region analysis process is shown in Figures 2 through 5. The first partition in Figure 2 is based on the brightness values associated with the landscape scene shown in Fig­ ure la, sampled to a 40 X 40 resolution. This partition includes 806 initial regions, half as many regions as individual picture elements. Region growing proceeds sequentially by merging adjacent regions across the weakest remaining boundary in the present partition. The boundary strength is based on average absolute brightness and color difference. The results of merging are illustrated, respectively, with 600, 450, and 250 regions remaining (see Figures 3 through 5).

III. First-Partition Experiments

The objective of the first partition stage is to group adjacent picture samples having similar attributes to obtain the fewest initial regions without a false merge occurring. In the example above, the picture was sampled to a 40 x 40 resolu­ tion; then adjacent samples with identical bright­ ness were combined to form homogeneous atomic regions (Figure 2). We consider here some attempts to improve the quality of the first partition by using different sampling methods and different criteria for judging the similarity of adjacent samples.

*The research reported herein was supported by the

National Aeronautics and Space Administration under contract NASW-2086.

Sampling Experiments

We experimented with modal, mean, and straight sampling to determine which method is the most ad­ visable for first partition. All experiments were performed on gray scale images using a 40 X 40 rec­ tangular sampling grid. Note that in scenes with periodic texture a random sampling strategy would have been necessary to avoid aliasing effects.

In modal sampling (Figure 6), the gray level of each grid point is taken to be the most fre­ quently occurring value of gray level for nearby points. The number of initial regions obtained in this manner is significantly reduced (by about one­ third) because many small "noise" points (which occurred in the treetop and the ground) disappeared. Some fine detail and contrast boundaries were lost, however, in the modal smoothing . Mean sampling of the gray level in a small neighborhood around each grid point is a poor technique because it tends to smooth discontinuities (see Figure 7).

From experiments with the images presented here and several others, we concluded that first partitions based on a straight sampling of the gray-scale image taken through a neutral density filter contained most of the information necessary to arrive at a conservative partition of real land­ scape and indoor scenes.

Color Quantization

The sampling experiments of the last section were based entirely on brightness information. The other extreme is to base the first partition exclu­ sively on color information, with brightness norma­ lized out. One way to accomplish this is to trans­ form the original image into a two-dimensional color space based on the relative content of red, green, and blue at each point [using the model des­ cribed in (5)]. This color space can be quantized into uniform intervals, with image points falling into the same color quantum grouped together into regions. We found that the partitions obtained in this manner were consistently worse than partitions based on sampled brightness. Major leaks occurred between semantically distinct regions in both land­ scape and indoor scenes. Moreover, because of tex­ tural irregularities, the total number of regions in landscape scenes was greater than the number pro­ duced by partitions based on sampled brightness.

We tried to improve first partitions based on color quantization by selecting quantization inter­ vals corresponding to characteristic colors of prominent objects. Our attempts were unsuccessful in both landscape scenes, because of the overlapping hue distributions of the principal objects, and in indoor scenes, because interior surfaces are gener­ ally color coordinated and hues tend to cluster in a narrow range.

Extraction of Distinguished Objects

Objects can often be extracted from the image prior to general partitioning by selecting conti­ guous collections of image points with distinguish­ ing properties. For example, the sky was the only region in our landscape scenes that is brighter than 30 (on a scale of 31). Extraction is especially ef­ fective when multisensory data are available, in­ creasing the probability that particular objects will be distinguished along some dimension. By ex­ tracting distinguished objects sequentially (or, in general, hierarchically) we can take advantage of context reductions achieved by earlier predicates. For example, although the picture on the wall in Figure la is a complex pattern, we were able to ex­ tract it by simple conditions on height, hue, and saturation once the wall samples were accounted for.

Table 1 presents a set of sequentially applied criteria developed interactively using ISIS for Stanford Research Institute office scenes. Points not classified by the criteria given in Table 1 were partitioned on the basis of their sampled brightness. Figure 8 provides a comparison of the partition obtained using these criteria with the partition obtained by sampled brightness alone . The simplification of the partition is clear from the comparison.

In landscape scenes objects are usually dis­ tinguished by texture and shape rather than by features at the image point level. Consequently, object extraction techniques are more difficult to apply and we have not, as yet, been able to use them successfully.

IV. Merge Priority Experiments

The sequence of merges performed during region growing is ordered by nonsemantic measures of region similarity. The purpose of these experiments was to determine conservative similarity .measures, which will defer questionable merges in the hope that the decision will be clarified or even rendered unneces­ sary in the context resulting from the execution of more reliable merges.

We compared the quality of several different measures of region similarity by performing a first partition based on sampled brightness, and then by applying a global, best-first merge order based on each measure of similarity until only 250 regions remained in the scene. The results of the merge sequences were compared on the basis of how well they honored the correct organization on the scene.

Figures 5 and 9 through 13 present the results of merging, down to 250 regions with six different measures of region similarity. Each figure legend gives the formula used for computing the similarity of adjacent regions in each case. In these formulas, br 1 is the brightness seen through a neutral density fifter, of the ith image point on the boundary of region a, and brbi is the brightness of adjacent image points in region b; rai· gai· and bat are the brightnesses of the 1th boundary element from region a seen through the red, green, and blue filters re­ spectively, and rbi· gbi· and bbi are the correspond­ ing brightnesses from region b; ~a· ga, and oa are the average brightnesses over region a seen through the r ed, green, and blue filters, and rb, gb, and ob are the corresponding averages over region b.

In Figure 11, the similarity of adjacent re­ gions was determined by averaging over sample points along the common boundary the maximum color contrast between any two picture elements drawn from the original, full-resolution, sampling neighborhoods on opposite sides of the boundary. This method was ex­ pected to overcome errors resulting from inadequate sampling; however, textured regions, such as the ground and the treetop, failed to coalesce before before distinct smooth regions grew together . Our best results were obtained using the measure of similarity applied in Figure 13. In this case the similarity of two regions was computed conservative­ ly using the maximum of both the boundary color con­ trast and the region color contrast as defined in the l egends of Figures 5 and 12.

V. Semantic Region Growth

We saw in the merge priority function experi­ ments of the previous section that, regardless of the nonsemantic similarity criterion used, an er­ roneous merge is proposed well before a final par­ tition is obtained. Semantics must be used either to refine the boundary strength criterion so that it proposes fewer erroneous merges (3) or to block proposed merges that are incorrect. Stepping through merges proposed by our best nonsemantic similarity criterion, we observed that serious false merges seldom occurred until the regions involved had grown sufficiently large to permit semantic interpretations based on region proper­ ties. This suggested that merging errors could be avoided on semantic grounds simply by refusing to merge regions with different interpretations: We tested this idea interactively by modifying the region growing algorithm to check semantic compata­ bility before performing a proposed merge. Merging is allowed only if both regions carry the same in­ terpretation or if at least one of the regions is not yet interpreted. Newly merged regions inherit the interpretation of their parents (or parent, if only one region is interpreted). When two uninter­ preted regions are merged, if the size of the re­ sultant regions exceeds a threshold, the program requests the experimenter to supply manually a cor­ rect interpretation.

This interactive region-growing algorithm par­ titioned both a landscape and an indoor scene with only minor errors (caused primarily, by inadequate spatial sampling). In both experiments, the size threshold for manual interpretation was set empiri­ cally at seven samples. The final partition depict­ ed in Figure 14 was based on the first partition in Figure 8b. Initially, manual interpretations were provided for the 20 (out of 253) first partition regions that exceeded threshold size. About 20 ad­ ditional interpretations were provided during the subsequent analysis when uninterpreted regions at­ tained threshold size by merging. Approximately the same number of interpretations had to be sup­ plied initially and during region growing in the landscape scene. When our semantic region-growing algorithm was applied to the first partition of Figure 2, we obtained the results shown in Figure 15. In both cases there were seven distinct inter­ pretations.

VI. Conclusion and Future Plans

Several experiments in automatic and inter­ active scene analysis using ISIS were performed. Our positive results with the interactive, semantic region grower suggest two directions for future work.

First, this method can be used as the basis for a practical approach to cooperative (man-machine) segmentation of scenes that are too complex to process completely automatically, or too detailed to segment rapidly by hand. With relatively little effort a user could crudely outline and label major regions. These outlines would provide most of the required region interpretations and also serve as a good initial partition from which detailed boundar­ ies can be grown rapidly .

Second, the semantic region growing algorithm provides a promising basis for a future automatic system in which region interpretations are deduced from local attributes and contextual constraints imposed by previously interpreted regions. The automatic system will have to deal with regions that are ambiguous at a given stage of partitioning. Merges involving such regions will be deferred until the ambiguity has been resolved as a result of other, more reliable merges. The use of semantics for blocking merges, rather than for altering the order in which merges are proposed [ cf. (3)], should sim­ plify training, since region labeling criteria and contextual constraints can be introduced or refined in direct response to specific merging errors as these errors are observed.