Apparatus and method for automatic knowlege-based object identification

• US 6,014,461 A
• Filed: 12/24/1997
• Issued: 01/11/2000
• Est. Priority Date: 11/30/1994
• Status: Expired due to Term

• Current Assignee: Rudolph Technologies Incorporated (Onto Innovation Inc.)
• Original Assignee: Texas Instruments, Inc.
• Inventors: Pattikonda, Ramakrishna, Lin, YouLing, Khaja, Veera V. S., Reddy, Rajasekar, Hennessey, Audrey Kathleen, Katragadda, Ramachandra, Lu, Huitian
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/998,315
• Time in Patent Office: 748 Days
• Field of Search: 382/195, 382/197, 382/199, 382/201, 382/217, 382/218, 382/224, 382/227
• US Class Current: 382/195
• CPC Class Codes: G06F 18/24765 Rule-based classification

Abstract

An apparatus and method for automatic knowledge-based object or anomaly classification is provided by capturing a pixel map of an image and from that generating high level descriptors of the object or anomaly such as size, shape, color and sharpness. These descriptors are compared with sets of descriptors in a knowledge-base to classify the object or anomaly.

Claims

1. A method of automated object identification and classification of objects and anomalies comprising the steps of:

capturing a pixel map of an image from a location containing a possible object or anomaly;

decomposing the pixel map into attributed primitives by tracing around edges of the object or anomaly, the primitives comprising numerical representations for a starting place, ending place, length, left and right texture attributes, angle of deviation from previous primitive, and curvature of the edges of the object;

combining adjacent primitives to form segments with width, length, number of vertices in segments and coordinates of vertices and angles between them;

storing separately primitive and segment values;

forming higher level descriptors with an object class from grouped segments representative of the objects and anomalies by determining a plurality of common characteristics including size, shape, average color, edge sharpness, solidity of texture and regularity of texture of the object or anomaly wherein the characteristics are represented numerically;

providing a knowledge base with a class category, each class category comprising a plurality of correctly classified samples of known objects and anomalies stored as sets of high level descriptors, with individual characteristics stored numerically; and

numerically comparing the set of higher level descriptors of the object or anomaly to preclassified high level descriptors in a knowledge base by calculating a similarity function to determine the knowledge base class with the closest similarity to the high level descriptor of the object or anomaly.

2. The method of claim 1 further including the step of detecting repeatable and non-repeatable images.

3. The method of claim 2 wherein said non-repeatable image includes a sudden change in a straight line.

4. The method of claim 2 wherein said non-repeatable image includes an irregular angle.

5. The method of claim 2 wherein said non-repeatable image includes a vague edge.

6. The method of claim 2 wherein said step of detecting repeatable images further includes using area autocorrelation to find repeatable images.

7. The method of claim 2 wherein said step of detecting repeatable images further includes using block subtraction to find repeatable images.

8. The method of claim 1 wherein said object or anomaly is detected by comparison to a reference image and by image subtraction.

9. The method of claim 1 wherein the plurality of correctly classified samples may be deleted or added to a class at any time.

10. The method of claim 9 wherein said knowledge base has supervised learning wherein an expert assigns a class name to a set of example objects or anomalies and unsupervised learning wherein the system groups sets of examples objects or anomalies automatically.

11. The method of claim 1 wherein calculating the similarity function comprises calculating the inner product of a first descriptor and a second descriptor and dividing that result by the algebraic sum of the inner product of the first descriptor with itself, the inner product of the second descriptor with itself and subtracting the inner product of the first descriptor and the second descriptor.

12. The method of claim 11 wherein the maximum calculated similarity determines the classification of an image.

13. A method of detecting defects comprising the steps of:

capturing a pixel map of an image containing a possible defect;

decomposing and storing the pixel map into attributed primitives with starting point, ending point, length, angle of deviation from previous primitives, left and right texture attributes and a curvature;

combining adjacent primitives to form segments with width, length, number of vertices in segments and coordinates of vertices and angles between them;

storing separately primitive and segment values;

forming higher level descriptors with an object class from grouped segments representative of the defect by determining a plurality of common characteristics including size, shape, average color, edge sharpness, solidity of texture and regularity of texture of the defect the characteristics represented numerically; and

numerically classifying defects by grouping defects with similar high level descriptors together.

14. A method of detecting defects comprising the steps of:

precisely locating and outlining a defect;

converting a defect image into high level descriptors by determining a plurality of common characteristics including size, shape, average color, edge sharpness, solidity of texture and regularity of texture of the defect, the characteristics determined numerically; and

classifying without the use of a predetermined rule base said defect by calculating a similarity function which numerically compares the similarity between the higher level descriptors of the defect with higher level descriptors of preclassified defects stored in a knowledge-base with learned identity.

15. A method of automated object identification without using a reference image comprising the steps of:

capturing a pixel map of an image from a location where there is a possible object;

decomposing and storing without the use of a reference image said pixel map into attributed primitives with starting point, ending point, length, angle of deviation from previous primitives, left and right texture attributes and a curvature;

combining primitives to form segments with width, length, number of vertices in segments and coordinates of vertices and angles between them;

storing separately primitive and segment values;

forming higher level descriptors with an object class from grouped segments representative of the object by determining a plurality of common characteristics including size, shape, average color, edge sharpness, solidity of texture and regularity of texture of the object wherein the characteristics are represented numerically; and

storing in a knowledge-base said higher level descriptors with a class category, the correct class category determined by numerically comparing the high level descriptors of the defect with high level descriptors of predefined exemplary defects.

16. A method of processing a digitized image to identify a portion of the digitized image, the method comprising the steps of:

decomposing the digitized image into image primitives by tracing around edges of objects in the image, the primitives comprising numerical representations for a starting place, ending place, length, left and right texture attributes, angle of deviation from previous primitive, and curvature of the edges of the object;

automatically producing from said image primitives a set of high level image descriptors for each object in the image by determining a plurality of common characteristics including size, shape, average color, edge sharpness, solidity of texture and regularity of texture of each object wherein the characteristics are represented numerically;

storing the high level descriptor of each object in a knowledge base;

comparing the high level image descriptors of each image with those of one or more known images represented by known object descriptors containing characteristics represented numerically in a knowledge base by numerically calculating a similarity function that best match the image descriptors; and

identifying the portion of the digitized image areas of the known image having the best set of matching object descriptors.

17. The method of claim 16 further comprising the step of creating the knowledge base of object descriptors by:

(1) entering an explicit definition of image primitives of known objects to form the object descriptors, or

(2) (a) creating a digitized image of a known object, and

(b) decomposing the digitized image of the known object to form object descriptors.

18. A system for automatic object identification and classification comprising a computer and memory having;

a digital image file operable to store a plurality of pixel digital data and primitives,

a knowledge base operable to store a high level description of a set of exemplary defects with individual characteristics stored numerically;

the computer and memory coupled to the knowledge base and the digital file, the computer operable to retrieve an image from the digital image file, to perform automatic object identification on the image, to generate high level descriptors for the object by determining a plurality of common characteristics including size, shape, average color, edge sharpness, solidity of texture and regularity of texture of the object, wherein the characteristics are represented numerically and to numerically compare the high level descriptors of the object with the descriptors stored in the knowledge base by calculating a similarity function.

19. The system of claim 18 wherein the computer and memory are further operable:

to create a pixel map of the image;

to decompose the pixel map into attributed primitives with a starting point, ending point, length, angle of deviation from previous primitives, left and right texture attributes and a curvature;

to combine the primitives to form segments with width, length, number of vertices in segments and coordinates of vertices and angles between them;

to store separately primitive and segment values.