Method and apparatus for inspecting distorted patterns

• US 6,973,207 B1
• Filed: 11/30/1999
• Issued: 12/06/2005
• Est. Priority Date: 11/30/1999
• Status: Expired due to Fees

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Inventors: Akopyan, Mikhail, Jacobson, Lowell, Wang, Lei
• Primary Examiner(s): Bali, Vikkram
• Application Number:
  US09/451,084
• Time in Patent Office: 2,198 Days
• Field of Search: 382/151, 382/155, 382/159, 382/142, 382/143, 382/209, 382/287, 382/289, 382/300
• US Class Current: 382/143
• CPC Class Codes: G06T 7/0004 Industrial image inspection
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

An embodiment of the invention provides a method for training a system to inspect a spatially distorted pattern. A digitized image of an object, including a region of interest, is received. The region of interest is further divided in to a plurality of sub-regions. A size of each of the sub-regions is small enough such that a conventional inspecting method can reliably inspect each of the sub-regions. A search tool and an inspecting tool are trained for a respective model for each of the sub-regions. A search tree is built for determining an order for inspecting the sub-regions. A coarse alignment tool is trained for the region of interest. Another embodiment of the invention provides a method for inspecting a spatially distorted pattern. A coarse alignment tool is run to approximately locate a pattern. Search tree information and an approximate location of a root image, found by the coarse alignment tool, is used to locate sub-regions sequentially in an order according to the search tree information. Each of the sub-regions is inspected, the sub regions being small enough such that a conventional inspecting method can reliably inspect each of the sub-regions.

Claims

1. A method for training a system to inspect a spatially distorted pattern, the method comprising:

receiving a digitized image of an object, the digitized image including a region of interest;

dividing the region of interest in its entirety into a plurality of non-overlapping sub-regions, a size of each of the non-overlapping sub-regions being small enough such that an image-feature-position-based inspecting tool can reliably inspect each of the sub-regions;

training only a fine search tool and an image-feature-position-based inspection tool for a respective single model for each of the plurality of non-overlapping sub-regions;

building a single search tree for determining an order for inspecting each non-overlapping sub-region of the plurality of non-overlapping sub-regions at a run-time; and

training a coarse alignment tool for the region of interest in its entirety so as to enable providing at run time an approximate location for a root sub-region of the single search tree.

2. The method according to claim 1, wherein the size of each of the non-overlapping sub-regions is small enough such that each of the sub-regions is well-approximated by an affine transformation.

3. The method of claim 1, wherein the building of the single search tree comprises:

establishing the order so that location information for located ones of the non-overlapping sub-regions is used to minimize a search range for neighboring ones of the non-overlapping sub-regions.

4. The method of claim 1, wherein the training of only the fine search tool for the respective single model for each of the plurality of non-overlapping sub-regions is performed by using a correlation search.

5. The method of claim 1, wherein the training of the image-feature-position-based inspection tool for the respective single model for each of the plurality of non-overlapping sub-regions is performed by using a golden template comparison method.

6. A method for inspecting a spatially distorted pattern, the method comprising:

running a coarse alignment tool to approximately locate the spatially distorted pattern in its entirety within a region of interest so as to provide an approximate location for a root sub-region of a single search tree;

running only a fine alignment tool in an order according to the single search tree, and using the approximate location of the root sub-region to locate a plurality of non-overlapping sub-regions within the region of interest so as to provide fine location information, the non-overlapping sub-regions covering the region of interest in its entirety, each of the non-overlapping sub-regions being of a size small enough such that an image-feature-position-based inspecting method can reliably inspect each of the non-overlapping sub-regions using respective single models;

inspecting each of the non-overlapping sub-regions using the fine location information and the image-feature-position-based inspecting method so as to produce a difference image for each of the non-overlapping sub-regions.

7. The method of claim 6, further comprising:

comparing the fine location information with model location information so as to provide a distortion vector for each non-overlapping sub-region;

combining all distortion vectors, one for each non-overlapping sub-region, so as to produce a distortion vector field; and

using the distortion vector field to make a pass/fail decision based on user-specified tolerances.

8. The method of claim 7, wherein:

the inspecting using the fine location information and the image-feature-position-based inspecting method produces a difference image for each of the non-overlapping sub-regions and a match image for each of the non-overlapping sub-regions, the method further comprising;

combining the difference images for each of the non-overlapping sub-regions into a single difference image;

combining the match images for each of the non-overlapping sub-regions into a single match image;

comparing the fine location information with model location information so as to provide a distortion vector for each non-overlapping sub-region; and

combining all distortion vectors, one for each non-overlapping sub-region, so as to produce a distortion vector field.

9. The method of claim 6, wherein:

the inspecting using the fine location information and the image-feature-position-based inspecting method produces a match image for each of the non-overlapping sub-regions, the method further comprising;

combining the difference images for each of the non-overlapping sub-regions into a single difference image; and

combining the match images for each of the non-overlapping sub-regions into a single match image.

10. The method according to claim 6, wherein the size of each of the non-overlapping sub-regions is small enough such that each of the non-overlapping sub-regions is well approximated by an affine transformation.

11. The method of claim 6, further comprising:

using the fine location information from located ones of the non-overlapping sub-regions to interpolate location information for a non-overlapping sub-region when the non-overlapping sub-region cannot be located; and

inspecting the non-overlapping sub-region based on the interpolated location information.

12. The method of claim 6, further comprising:

using respective single models for at least some of the non-overlapping sub-regions to determine respective fine location information; and

predicting fine location information in at least one of the non-overlapping sub-regions by using the respective fine location information of neighboring ones of the at least some of the non-overlapping sub-regions when the at least one of the non-overlapping sub-regions cannot be located by running the fine alignment tool.

13. The method of claim 6, wherein the inspecting of each of the non-overlapping sub-regions using an image-feature-position-based inspecting method is performed by a golden-template comparison method.

14. The method of claim 6, further comprising:

dividing one of the non-overlapping sub-regions into a plurality of smaller non-overlapping sub-regions when the one of the non-overlapping sub-regions cannot be located using a fine search tool.

15. An apparatus for inspecting a spatially distorted pattern, the apparatus comprising:

a memory for storing a digitized image of an object;

a region divider for dividing the digitized image of a region of interest in its entirety into a plurality of non-overlapping sub-regions, the non-overlapping sub-regions covering the region of interest completely, a size of each of the non-overlapping sub-regions being small enough such that an image-feature-position-based inspecting method can reliably inspect each of the non-overlapping sub-regions;

a coarse alignment tool for approximately locating the pattern so as to provide an approximate location for a root sub-region of a single search tree;

a fine search tool only for locating each of the non-overlapping sub-regions sequentially in an order based on the single search tree; and

an image-feature-position-based inspector for inspecting each of the non-overlapping sub-regions.

16. The apparatus of claim 15, further comprising:

a vector field producer to combine all location information to produce a distortion vector field for each of the non-overlapping sub-regions; and

a comparing mechanism for using the distortion vector field to make a pass/fail decision based on user specified tolerances.

17. The apparatus of claim 15, wherein:

the image-feature-position-based inspector for inspecting each of the non-overlapping sub-regions produces a difference image for each of the non-overlapping sub-regions and a match image for each of the non-overlapping sub-regions, the apparatus further comprises;

a first combiner for combining the difference images for each of the non-overlapping sub-regions into a single difference image; and

a second combiner for combining the match images for each of the non-overlapping sub-regions into a single match image.

18. The apparatus according to claim 15, wherein the size of each of the non-overlapping sub-regions is small enough such that each of the non-overlapping sub-regions is well-approximated by an affine transformation.

19. The apparatus of claim 15, further comprising:

an interpolator for using location information from located ones of the non-overlapping sub-regions to interpolate location information for a non-overlapping sub-region when the non-overlapping sub-region cannot be located by the fine search tool;

wherein

the image-based inspector inspects the non-overlapping sub-region based on the interpolated location information.

20. The apparatus of claim 15, further comprising:

an interpolator for using the respective models for at least some of the non-overlapping sub-regions to determine respective location information, and for predicting location information in at least one of the non-overlapping sub-regions by using the respective location information of neighboring ones of the at least some of the non-overlapping sub-regions when the at least one of the non-overlapping sub-regions cannot be located.

21. The apparatus of claim 15, wherein the image-feature-position-based inspector inspects each of the non-overlapping sub-regions by using a golden-template comparison method.

22. An apparatus for inspecting a spatially distorted pattern, the apparatus comprising:

a storage for storing a digitized image of an object, the digitized image including a region of interest;

a region divider for dividing the region of interest in its entirety into a plurality of non-overlapping sub-regions, a size of each of the non-overlapping sub-regions being small enough such that an image-feature-position-based inspecting method can reliably inspect each of the non-overlapping sub-regions;

a trainer for training a respective single model for a fine search tool only and for an image-feature-position-based inspector for each of the plurality of non-overlapping sub-regions;

a search tree builder for building a single search tree for determining an order for image-feature-position-based inspecting of each sub-region of the plurality of non-overlapping sub-regions at a run time;

a coarse alignment trainer;

a coarse alignment tool for approximately locating the pattern so as to provide an approximate location for a root sub-region of a single search tree, the coarse alignment tool being configured to be trained by the coarse alignment trainer;

a fine search tool only for locating each of the non-overlapping sub-regions sequentially in an order based on the single search tree, the root sub-region of the single search tree being provided by the coarse alignment tool; and

an image-based inspector for inspecting each of the non-overlapping sub-regions.

23. The apparatus according to claim 22, further comprising:

a vector field producer to combine all location information to produce a distortion vector field for each of the non-overlapping sub-regions; and

a comparing mechanism for using the distortion vector fields to make a pass/fail decision based on user specified tolerances.

24. The apparatus of claim 22, wherein:

the image-feature-position-based inspector produces a difference image for each of the non-overlapping sub-regions and a match image for each of the non-overlapping sub-regions, the apparatus further comprises;

a first combiner for combining the differences images for each of the non-overlapping sub-regions into a single difference image; and

a second combiner for combining the match images for each of the non-overlapping sub-regions into a single match image.

25. The apparatus according to claim 22, wherein the size of each of the non-overlapping sub-regions is small enough such that each of the non-overlapping sub-regions is well approximated by an affine transformation.

26. The apparatus of claim 22, wherein the building of the single search tree comprises:

establishing the order so that location information for located ones of the non-overlapping sub-regions is used to minimize a search range for neighboring ones of the non-overlapping sub-regions.

27. The apparatus of claim 22, further comprising:

an interpolator for using location information from located ones of the non-overlapping sub-regions to interpolate location information for a non-overlapping sub-region when the sub-region cannot be located, wherein

the image-feature-position-based inspector inspects the previously unlocated non-overlapping sub-region based on the interpolated location information.

28. A medium having a stored therein machine-readable information, such that when the machine-readable information is read into a memory of a computer and executed, the machine-readable information causes the computer:

to receive a digitized image of an object, the digitized image including a region of interest;

to divide the region of interest in its entirety into a plurality of non-overlapping subregions, a size of each of the non-overlapping sub-regions being small enough such that an image-feature-position-based inspecting method can reliably inspect each of the non-overlapping sub-regions;

to train a respective single model for a fine search tool only and for an image-feature-position-based inspection tool for each of the plurality of non-overlapping sub-regions;

to build a single search tree for determining an order for inspecting the plurality of non-overlapping sub-regions at a run-time; and

to train a respective model for a coarse alignment tool so as to enable providing at run time an approximate location for a root sub-region of the single search tree.

29. The medium of claim 28, wherein when building the single search tree, the machine-readable information causes the computer:

to establish the order so that location information for located ones of the non-overlapping sub-regions is used to minimize a search range for neighboring ones of the non-overlapping sub-regions.

30. The medium of claim 28, wherein the machine-readable information further causes the computer:

to run a coarse alignment tool to approximately locate a pattern so as to provide an approximate location for a root sub-region of a single search tree;

to run only a fine alignment tool in an order according to the single search tree and using the approximate location of the root sub-region approximately located by the coarse alignment tool to locate a plurality of non-overlapping sub-regions so as to provide fine location information, each of the non-overlapping sub-regions being of a size small enough such that an image-feature-position-based inspecting method can reliably inspect each of the non-overlapping sub-regions; and

to perform image-based inspection of each of the non-overlapping sub-regions to produce a difference image for each of the non-overlapping sub-regions and a match image for each of the non-overlapping sub-regions.

31. The medium of claim 30, wherein the machine-readable information further causes the computer:

to combine the difference images for each of the non-overlapping sub-regions into a single difference image; and

to combine the match images for each of the non-overlapping sub-regions into a single match image.

32. The medium of claim 30, wherein the machine-readable information further causes the computer:

to compare the fine location information with model location information so as to provide a distortion vector for each non-overlapping sub-region;

to combine all distortion vectors, one for each non-overlapping sub-region, so as to produce a distortion vector field; and

to use the distortion vector field to make a pass/fail decision based on user-specified tolerances.

33. The medium of claim 28, wherein the machine-readable information further causes the computer:

to use fine location information from located ones of the non-overlapping sub-regions to interpolate fine location information for a non-overlapping sub-region when the non-overlapping sub-region cannot be located; and

to run an image-feature-position-based inspection tool on the non-overlapping sub-region based on the interpolated fine location information.

34. A method for inspecting a spatially distorted pattern, the method comprising:

running a coarse alignment tool to approximately locate the pattern so as to provide an approximate location for a root sub-region of a single search tree;

running only a fine alignment tool in an order according to the single search tree, and using the approximate location of the root sub-region, to locate a plurality of non-overlapping sub-regions so as to provide fine location information, each of the non-overlapping sub-regions being of a size small enough such that an image-feature-position-based inspecting method can reliably inspect each of the non-overlapping sub-regions;

comparing the fine location information with model location information so as to provide a distortion vector for each non-overlapping sub-region;

combining all distortion vectors, one for each non-overlapping sub-region, so as to produce a distortion vector field; and

using the distortion vector field to make a pass/fail decision based on user-specified tolerances.

35. An apparatus for inspecting a spatially distorted pattern, the apparatus comprising:

a memory for storing a digitized image of an object;

a region divider for dividing the digitized image of a region of interest in its entirety into a plurality of non-overlapping sub-regions, a size of each of the non-overlapping sub-regions being small enough such that an image-feature-position-based inspecting method can reliably inspect each of the non-overlapping sub-regions;

a coarse alignment tool for approximately locating the pattern so as to provide an approximate location for a root sub-region of a single search tree;

a fine search tool only for locating each of the non-overlapping sub-regions sequentially in an order based on the single search tree so as to provide fine location information;

a vector field producer for comparing the fine location information with model location information so as to provide a distortion vector for each non-overlapping sub-region, and for combining the distortion vectors to produce a distortion vector field; and

a comparing mechanism for using the distortion vector field to make a pass/fail decision based on user specified tolerances.

36. A medium having stored therein machine-readable information, such that when the machine-readable information is read into a memory of a computer and executed, the machine-readable information causes the computer:

to run a coarse alignment tool to approximately locate a pattern so as to provide an approximate location for a root sub-region of a single search tree;

to run only a fine alignment tool in an order according to the single search tree using the root sub-region approximately located by the coarse alignment to locate a plurality of non-overlapping sub-regions so as to provide fine location information, each of the non-overlapping sub-regions being of a size small enough such that an image-feature-position-based inspecting method can reliably inspect each of the non-overlapping sub-regions;

to compare the fine location information with model location information so as to provide a distortion vector for each non-overlapping subregion;

to combine all distortion vectors, one for each non-overlapping sub-region, so as to produce a distortion vector field; and

to use the distortion vector field to make a pass/fail decision based on user-specified tolerances.