Object analysis of multi-valued images

• US 4,847,786 A
• Filed: 08/20/1986
• Issued: 07/11/1989
• Est. Priority Date: 08/20/1986
• Status: Expired due to Term

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Wang, Jing, Beni, Gerardo
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Herndon, H. R.
• Application Number:
  US06/898,076
• Time in Patent Office: 1,056 Days
• Field of Search: 364/518-522, 382/51, 382/48, 382/18, 358/163, 358/166, 358/280-284
• US Class Current: 382/171
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

Method and apparatus for analyzing a 2-dimensional sensory-input field containing three or more distinct classes of objects. The field is represented by a 2-dimensional array of elements in which each separate class of objects in the field has a separate classification value. The field is scanned with a 2×2 window containing the element being scanned and three adjacent and connected window elements, where each of the adjacent window elements has been previously assigned an object label which identifies one object containing that element. If the element being scanned has the same classification value as any of the adjacent window element, it is assigned the object label of that same-classification window element. Otherwise, the element being scanned is assigned a new label. If the element being scanned has the same classification value as two adjacent and orthogonal elements, and these orthogonal elements have been previously given different object labels, the two different object labels are merged. The result is to identify each separate object in the image. Geometric properties of the objects can be calculated during the scanning procedure.

Claims

1. A computerized method of analyzing a sensory-input field containing three or more distinct classes of objects, said method comprising:

representing the field as a 2-dimensional array of elements in which (a) each element represents a portion of a single object in the field, (b) all of the elements representing the same class of objects are assigned a single classification value, and (c) each of the three or more classes of objects in the field is assigned a different classification value,

scanning each individual element in the array systematically with a 2×

2 window containing the element being scanned and three adjacent and connected window elements, where each of the adjacent window elements has been previously assigned an object label which uniquely identifies an object containing such adjacent element,

determining the classification value of each individual element being scanned,

matching the classification values in the 2×

2 scanning window with one of fifteen same/not-same case patterns which indicates which of the elements in the window have the same classification values, and which have unique values, irrespective of actual classification values,

from the same/not-same case pattern associated with the 2×

2 window, assigning the element being scanned an existing object label or a new object label,

storing the object labels determined for each of the scanned elements, and

by said scanning and assigning, identifying each separate object in the field by a separate object label.

2. The method of claim 1, wherein object merging is performed whenever such an identified pattern has three orthogonal elements, including the element being scanned, which have the same classification value, and a fourth diagonal element which has a different classification value, and the two elements orthogonal to the element being scanned have been previously assigned different object labels.

3. The method of claim 1, for use in generating geometrical information about each object in the field, wherein such information is calculated on an updated basis during said scanning, based on the object label assignment made with respect to each scanned element.

4. The method of claim 1, for use in analyzing a black and white digitized image, wherein said representing includes the steps of forming an image-brightness histogram which contains at least three distinct brightness classes separated from each other by local minima,

giving a unique classification value to each brightness class, and

mapping each element in the array into one of the brightness classes and assigning to that element the classification value given to that brightness class.

5. The method of claim 1, for use in analyzing a multi-colored field in which different colors represent different classes of objects, wherein said representing includes the steps of selecting a finite set of at least three different colors which is sufficient to allow representation of each different class in the field with a distinct color,

giving a unique classification value to each of the different colors, and

mapping each element in the array into one of the different colors and assigning to that element the classification value given to that color.

6. Apparatus for analyzing a sensory-input field containing three or more distinct classes of objects, said apparatus comprising:

a classification device for representing the field as a 2-dimensional arary of elements in which (a) each element represents a portion of a single object, (b) all of the elements representing the same class of objects are assigned a single classification value, and (c) each of the three or more classes of objects in the field is assigned a different classification value,

means for scanning each individual element in the array systematically with a 2×

2 window containing the element being scanned and three adjacent and connected window elements, where each of the adjacent window elements has been previously assigned on object label which uniquely identifies an object containing such adjacent element,

program means for (i) determining the classification value of each individual element being scanned, (ii) matching the classification values in the 2×

2 scanning window with one of fifteen possible same/not-same case patterns which indicate which of the elements in the window have the same classification values, and which have unique values, irrespective of actual classification values, and (iii) from the same/not-same case pattern associated with the 2×

2 window, assigning the element being scanned an existing object label or a new object label, and

a storage buffer for storing the object labels assigned to each of the scanned elements.

7. The apparatus of claim 6, which further includes means for merging all orthogonally connected objects having the same classification value but different object labels.

8. The apparatus of claim 6, for use in identifying objects in a black and white 2-dimensional image field, based on the different brightness of different objects in the field, wherein the classification device includes

means for photoimaging the field to produce a 2-dimensional array of element in which each element has a certain brightness value,

means for constructing an image-brightness histogram which contains, for each class of objects in the field, at least three brightness classes which are separated from each other by local minima, and

means for assigning to each element in the array, a classification value corresponding to the brightness class whose brightness range includes the brightness value of that element.

9. The apparatus of claim 6, for use in analyzing a multi-colored 2-dimensional field in which different colors represent different classes of objects, wherein said classification device includes

means for photoimaging the field to produce a 2-dimensional array of elements in which the color associated with each element is indicated by a vector in a defined color space,

means for associating each element vector with one of a at least three color regions in the color space, where the total number of color regions is sufficient to allow representation of each different class in the field with a distinct color region, and

means for mapping each element in the array into one of the different colors and assigning to that element the classification value associated with the color.