Automated image analysis aimed at identifying types, number and properties of objects in a multi-object field has several important applications. For example, as a quality control device in industry, automated image analysis would allow for rapid inspection of electronic or other complex components for quality control purposes, to check, for example, that a complex microchip contains the requisite numbers of each type of circuit elements. Another application is in satellite picture analysis. Here it is desirable to identify a number of different objects, such as water, clouds, land, buildings, roads, and the like, and to characterize the identified objects either as to number and/or physical characteristics, such as position, size, shape, and orientation. Robotics vision, for use in acting on one or more objects in a multi-image field, is another application.
Connectivity analysis is widely used for lower-level image analysis where objects are to be classified as to type, number, and/or geometric properties. In this method, each pixel element is labelled with a specified object value which is related either to the brightness of the object in a black/white image, or to the color in a multi-color image, or to some other physical characteristic which can be distinguished and classified on the basis of information available from the image. Each pixel is then scanned, in a row-by-row manner, with a scanning window that includes the pixel being scanned and adjacent row and column pixels. In two-dimensional analysis, the adjacent pixels in the window may include either two orthogonally adjacent pixels (4-connectivity) or two orthogonally and one diagonally adjacent pixels (6-connectivity or 8-connectivity). The reader is referred to above-cited articles by Rosenfeld, Lumia, Samet, Duta, Ward, Cunningham, Pratt and Ballard for a discussion of various aspects of connectivity analysis.
Connectivty analysis has been applied primarily to binary images heretofore. In the usual application, a black and white image is broken down by a brightness histogram into two or more distinct regions of brightness which are separated by local minima. One of these minima is selected as a brightness threshhold, with all pixels on the lower side of the threshhold being assigned a background "zero" value, and all pixels above the threshhold being assigned an object "one" value. The image is then analysed for "one" value connectivity, to determine the number and geometric properties of such one-value objects.
The connectivity analysis of binary images generally involves examining the pattern of zero and one value connectivity in a 2.times.2 scanning window, and on the basis of the pattern, assigning the scanned pixel to either (a) background (b) an already established object (c) a new object or (d) a merger of two previously distinct objects. In the case of 6-connectivity, the number of distinct cases which may be considered in the analysis is 2.sub.4, which can be reduced to eight symmetrically equal (zero and one values interchanged) cases. The connectivity algorithm, which must consider only eight cases at each scanning position, can be executed rapidly by computer.
In the case of multivalued images, such as images in which different classes of objects are represented by different shades of grey, or by different colors, the number of cases which must be considered, for absolute configuration matching, increases rapidly, with increasing number of pixel values. Thus, in a 2.times.2 window, the number of cases which must be considered for a m-valued image is m.sup.4, which even for a three-valued image means considering about 81 cases (less symmetrical cases). It can be appreciated that large-valued images could not be practically handled in this way.
One solution to multi-valued connectivity analysis which has been employed heretofore involves analysis of a series of binary images which are generated at different threshhold values of a black and white image, or by different filter values for a multi-color image. For example, in the case of a black and white image whose brightness histogram contains three or more brightness regions separated by local minima, each minimum can be selected as threshold to generate a separate binary image, with the two or more images being combined after separate connectivity analysis. This approach requires additional processing time and/or additional parallel computational capacity with each added class of objects, and thus becomes impractical for many-valued images. However, it is these many-valued images which are expected to be of greatest interest for future applications, as suggested above.