Method for indexing and retrieving manufacturing-specific digital imagery based on image content

• US 6,751,343 B1
• Filed: 09/20/1999
• Issued: 06/15/2004
• Est. Priority Date: 09/20/1999
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Energy Research Corporation (Martin Marietta Corporation)
• Original Assignee: UT-Battelle LLC
• Inventors: Karnowski, Thomas P., Tobin, Kenneth W. Jr., Ferrell, Regina K.
• Primary Examiner(s): Dastouri, Mehrdad
• Application Number:
  US09/399,394
• Time in Patent Office: 1,730 Days
• Field of Search: 382/112, 382/141, 382/142, 382/143, 382/144, 382/145, 382/146, 382/147, 382/148, 382/149, 382/150, 382/190, 382/195, 382/203, 382/217, 382/218, 382/219, 382/225, 382/226, 382/240, 348/125, 348/126, 700/117, 707/104.1
• US Class Current: 382/145
• CPC Class Codes: G06F 16/5838 using colour

Abstract

A method for indexing and retrieving manufacturing-specific digital images based on image content comprises three steps. First, at least one feature vector can be extracted from a manufacturing-specific digital image stored in an image database. In particular, each extracted feature vector corresponds to a particular characteristic of the manufacturing-specific digital image, for instance, a digital image modality and overall characteristic, a substrate/background characteristic, and an anomaly/defect characteristic. Notably, the extracting step includes generating a defect mask using a detection process. Second, using an unsupervised clustering method, each extracted feature vector can be indexed in a hierarchical search tree. Third, a manufacturing-specific digital image associated with a feature vector stored in the hierarchicial search tree can be retrieved, wherein the manufacturing-specific digital image has image content comparably related to the image content of the query image. More particularly, can include two data reductions, the first performed based upon a query vector extracted from a query image. Subsequently, a user can select relevant images resulting from the first data reduction. From the selection, a prototype vector can be calculated, from which a second-level data reduction can be performed. The second-level data reduction can result in a subset of feature vectors comparable to the prototype vector, and further comparable to the query vector. An additional fourth step can include managing the hierarchical search tree by substituting a vector average for several redundant feature vectors encapsulated by nodes in the hierarchical search tree.

Claims

1. A method for indexing and retrieving stored images based on image content, comprising the steps of:

extracting a plurality of feature vectors from each of a plurality of digital images of in-process or completed semiconductors, said plurality of feature vectors corresponding to distinct descriptive characteristics of said semiconductor images;

recording said plurality of feature vectors from said plurality of semiconductor images;

indexing said plurality of feature vectors from said plurality of semiconductor images using an image clustering method to produce a hierarchical search tree, said clustering method mapping said plurality of images into a set of groups based on similar imaging content, said groups numbering less than a number of said plurality of images, said hierarchical search tree constituting a searchable library of said semiconductor images, wherein searching is based on said groups to achieve efficient retrieval times from said library;

extracting a plurality of said feature vectors from a query image,

retrieving at least one image from said library based on an image similarity criterion to said feature vectors of said query image, and displaying said at least one image.

2. The method according to claim 1, wherein said extracting steps comprise the step of extracting three feature vectors, said three feature vectors corresponding to an image measurement tool, a substrate/background characteristic, and an anomaly/defect characteristic.

3. The method according to claim 2, wherein said extracting steps comprise the steps of:

using a defect mask provided by a detection process selected from the group consisting of thresholding said semiconductor image, comparing said semiconductor image with a golden template, and comparing said semiconductor image with a digital image of a neighboring product; and

,

extracting a feature vector for said substrate/background characteristic or said anomaly/defect characteristic using said defect mask.

4. The method according to claim 2, wherein said extracting steps comprise the steps of:

distinguishing a defect-region from a non-defect region in said semiconductor image;

rendering said defect-region similar to said non-defect region based on an estimate derived from a region surrounding said defect-region, said rendering forming a modified semiconductor image representing an unperturbed substrate/background; and

,

extracting a feature vector corresponding to said substrate/background characteristic from said modified semiconductor image.

5. The method according to claim 1, wherein the retrieving step comprises the steps of:

converting a query image into at least one query vector corresponding to said particular characteristic of said semiconductor image;

performing a first-level data reduction of feature vectors stored in said hierarchical data structure, said first-level data reduction based upon said at least one query vector, said first-level data reduction forming a subset of said feature vectors comparable to said query vector;

accepting relevance feedback comprising a user-chosen selection of semiconductor images corresponding to said subset of feature vectors;

calculating at least one prototype vector from said selection, said prototype vector corresponding to said particular characteristic of said semiconductor image; and

, performing a second-level data reduction of feature vectors stored in said hierarchical data structure, said second-level data reduction based upon said at least one prototype vector, said second-level data reduction forming a subset of said feature vectors comparable to said at least one prototype vector, and further comparable to said at least one query vector.

6. The method of claim 1, wherein said at least one image retrieved in said retrieving step comprises a plurality of retrieved images.

7. The method of claim 6, wherein respective ones of said plurality of retrieved images are ranked in similarity relative to said query image.

8. The method according to claim 1, further comprising the step of managing said hierarchical search tree.

9. The method according to claim 8, wherein the managing step comprises the steps of:

identifying a level node referencing redundant nodes having redundant feature vectors;

equating the vector average encapsulated by said level node with all feature vectors and vector averages encapsulated by nodes referenced by said level node; and

,

pruning said hierarchical search tree of said redundant nodes referenced by said level node.

10. A method for indexing and retrieving manufacturing-specific digital images based on image content comprising the steps of:

extracting at least one feature vector from a manufacturing-specific digital image stored in an image database, said at least one feature vector corresponding to a particular characteristic of said manufacturing-specific image;

using an unsupervised clustering method to index said at least one feature vector in a hierarchical search tree; and

,

retrieving a manufacturing-specific image corresponding to a feature vector stored in said hierarchical search tree, said manufacturing-specific image having image content comparably related to image content of a query image, wherein the retrieving step comprises the steps of;

converting a query image into at least one query vector corresponding to said particular characteristic of said manufacturing-specific digital image;

performing a first-level data reduction of feature vectors stored in said hierarchical data structure, said first-level data reduction based upon said at least one query vector, said first-level data reduction forming a subset of said feature vectors comparable to said query vector;

accepting relevance feedback comprising a user-chosen selection of manufacturing-specific digital images corresponding to said subset of feature vectors, wherein the accepting step comprises the steps of;

for each manufacturing-specific digital image in said selection, extracting three independent feature vectors of manufacturing-based digital imagery, said three independent feature vectors corresponding to a digital image modality and overall characteristic, a substrate/background characteristic, and an anomaly/defect characteristic;

logically combining each said independent feature vector for each manufacturing-specific digital image in said selection, said logical combination forming a prototype vector for each said independent feature vector;

calculating at least one prototype vector from said selection, said prototype vector corresponding to said particular characteristic of said manufacturing-specific digital image; and

,

performing a second-level data reduction of feature vectors stored in said hierarchical data structure, said second-level data reduction based upon said at least one prototype vector, said second-level data reduction forming a subset of said feature vectors comparable to said at least one prototype vector, and further comparable to said at least one query vector.

11. The method according to claim 10, wherein the retrieving step further comprises the step of fetching from said image database a manufacturing-specific digital image defined by an intersection of said three independent feature vectors corresponding to said at least one prototype vector.

12. A computer apparatus programmed with a routine set of instructions stored in a fixed medium, said computer apparatus comprising:

means for extracting a plurality of feature vectors from each of a plurality of digital images of in-process or completed semiconductors, said plurality of feature vectors corresponding to distinct descriptive characteristics of said semiconductor images;

means for recording said plurality of feature vectors from said plurality of semiconductor images;

means for indexing said plurality of feature vectors from said plurality of semiconductor images using an image clustering method to produce a hierarchical search tree, said clustering method mapping said plurality of images into a set of groups based on similar image content, said groups numbering less than a number of said plurality of images, said hierarchical search tree being a searchable library of said semiconductor images, wherein searching is based on said groups to achieve efficient retrieval times from said library;

means for extracting at least one of said feature vectors from said query image,

means for retrieving at least one image from said library based on an image similarity criterion to said feature vector of said query image, and means for displaying said at least one image.

13. The computer apparatus according to claim 12, wherein said extracting means comprise the means for extracting three independent feature vectors, said three independent feature vectors corresponding to an image measurement tool, a substrate/background characteristic, and an anomaly/defect characteristic, respectively.

14. The computer apparatus according to claim 13, wherein said extracting means comprise:

means for using a defect mask provided by a detection process selected from the group consisting of thresholding said semiconductor image, comparing said semiconductor image with a golden template, and comparing said semiconductor image with a digital image of a neighboring product; and

,

means for extracting a feature vector for said substrate/background characteristic or said anomaly/defect characteristic using said defect mask.

15. The computer apparatus according to claim 13, wherein said extracting means comprise:

means for distinguishing a defect-region from a non-defect region in said semiconductor image;

means for rendering said defect-region similar to said non-defect region based on an estimate derived from a region surrounding said defect-region, said rendering means forming a modified semiconductor image representing an unperturbed substrate/background; and

,

means for extracting a feature vector corresponding to said substrate/background characteristic from said modified semiconductor image.

16. The computer apparatus according to claim 12, wherein the retrieving means comprises:

means for converting a query image into at least one query vector corresponding to said particular characteristic of said semiconductor image;

means for performing a first-level data reduction of feature vectors stored in said hierarchical data structure, said first-level data reduction based upon said at least one query vector, said first-level data reduction forming a subset of said feature vectors comparable to said query vector;

means for accepting relevance feedback comprising a user-chosen selection of semiconductor images corresponding to said subset of feature vectors;

means for calculating at least one prototype vector from said selection, said prototype vector corresponding to said particular characteristic of said semiconductor image; and

,

means for performing a second-level data reduction of feature vectors stored in said hierarchical data structure, said second-level data reduction based upon said at least one prototype vector, said second-level data reduction forming a subset of said feature vectors comparable to said at least one prototype vector, and further comparable to said at least one query vector.

17. The computer apparatus according to claim 12, further comprising means for managing said hierarchical search tree.

18. The computer apparatus according to claim 17, wherein the managing means comprises:

means for identifying a level node referencing redundant nodes having redundant feature vectors;

means for equating the vector average encapsulated by said level node with all feature vectors and vector averages encapsulated by nodes referenced by said level node; and

,

means for pruning said hierarchical search tree of said redundant nodes referenced by said level node.

19. A computer apparatus programmed with a routine set of instructions stored in a fixed medium, said computer apparatus comprising:

means for extracting at least one feature vector from a manufacturing-specific digital image stored in an image database, said at least one feature vector corresponding to a particular characteristic of said manufacturing-specific image;

means for using an unsupervised clustering method to index said at least one feature vector in a hierarchical search tree;

means for retrieving a manufacturing-specific image corresponding to a feature vector stored in said hierarchical search tree, said manufacturing-specific image having image content comparably related to image content of a query image, wherein the retrieving means comprises;

means for converting a query image into at least one query vector corresponding to said particular characteristic of said manufacturing-specific digital image;

means for performing a first-level data reduction of feature vectors stored in said hierarchical data structure, said first-level data reduction based upon said at least one query vector, said first-level data reduction forming a subset of said feature vectors comparable to said query vector;

means for accepting relevance feedback comprising a user-chosen selection of manufacturing-specific digital images corresponding to said subset of feature vectors, wherein the accepting means comprises;

for each manufacturing-specific digital image in said selection, means for extracting three independent feature vectors of manufacturing-based digital imagery, said three independent feature vectors corresponding to a digital image modality and overall characteristic, a substrate/background characteristic, and an anomaly/defect characteristic;

means for logically combining each said independent feature vector for each manufacturing-specific digital image in said selection, said logical combination forming a prototype vector for each said independent feature vector;

means for calculating at least one prototype vector from said selection, said prototype vector corresponding to said particular characteristic of said manufacturing-specific digital image; and

,

means for performing a second-level data reduction of feature vectors stored in said hierarchical data structure, said second-level data reduction based upon said at least one prototype vector, said second-level data reduction forming a subset of said feature vectors comparable to said at least one prototype vector, and further comparable to said at least one query vector.

20. The computer apparatus according to claim 19, wherein the retrieving means further comprises means for fetching from said image database a manufacturing-specific digital image defined by an intersection of said three independent feature vectors corresponding to said at least one prototype vector.

21. A method of content-based image retrieval (CBIR) for manufacturing, comprising the steps of:

extracting a plurality of descriptive features from each of a plurality of digital images which represent in-process or completed semiconductors, said images obtained from a plurality of different measurement tools at a plurality of different manufacturing steps;

recording said plurality of descriptive features to form a historical image collection;

indexing said historical image collection using an image clustering method to produce a hierarchical search tree, said clustering method mapping said plurality of imaging into a set of groups based on similar image content, said groups numbering less than a number of said plurality of images, said hierarchical search tree constituting a searchable library of said semiconductor images, wherein searching is based on said groups to achieve efficient retrieval times from said library;

extracting said query image from an in-process or completed manufactured article to be characterized, said query image comprising a plurality of said descriptive features,

retrieving at least one candidate image from said library based on an image similarity criterion to said descriptive features of said query image, and displaying said at least one image.

22. The method of claim 21, wherein said plurality of descriptive features comprise color, texture and shape.

23. The method of claim 21, wherein said plurality of different measurement tools include at least one optical microscope and at least one scanning electron microscope (SEM).

24. The method of claim 21, wherein said at least one candidate image retrieved in said retrieving step comprises a plurality of retrieved images.

25. The method of claim 24, wherein respective ones of said plurality of retrieved candidate images are ranked in similarity relative to said query image.