Fast high-accuracy multi-dimensional pattern inspection

• US 6,993,192 B1
• Filed: 11/10/2003
• Issued: 01/31/2006
• Est. Priority Date: 11/26/1997
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Wallack, Aaron, Silver, William, Wagman, Adam
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US10/705,288
• Time in Patent Office: 813 Days
• Field of Search: 382/103, 382/151, 382/181, 382/199, 382/203, 382/209, 382/216, 382218-219, 382/291, 348/135
• US Class Current: 382/209
• CPC Class Codes: G06T 7/75 involving models
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method and apparatus are provided for identifying differences between a stored pattern and a matching image subset, where variations in pattern position, orientation, and size do not give rise to false differences. The invention is also a system for analyzing an object image with respect to a model pattern so as to detect flaws in the object image. The system includes extracting pattern features from the model pattern; generating a vector-valued function using the pattern features to provide a pattern field; extracting image features from the object image; evaluating each image feature, using the pattern field and an n-dimensional transformation that associates image features with pattern features, so as to determine at least one associated feature characteristic; and using at least one feature characteristic to identify at least one flaw in the object image. The invention can find at least two distinct kinds of flaws: missing features, and extra features. The invention provides pattern inspection that is faster and more accurate than any known prior art method by using a stored pattern that represents an ideal example of the object to be found and inspected, and that can be translated, rotated, and scaled to arbitrary precision much faster than digital image re-sampling, and without pixel grid quantization errors. Furthermore, since the invention does not use digital image re-sampling, there are no pixel quantization errors to cause false differences between the pattern and image that can limit inspection performance.

Claims

1. A geometric pattern matching apparatus for refining a starting pose of an object in a run-time image, the object having an expected shape and a true pose in the run-time image, the starting pose representing an initial estimate of the true pose of the object in the run-time image, the apparatus comprising:

a stored model pattern, the stored model pattern including a geometric description of the expected shape of the object, the geometric description including a plurality of pattern boundary points, and information about the pattern boundary points; and

a run-time module configured to;

receive the stored model pattern, the starting pose, and the run-time image;

detect in the run-time image a plurality of image boundary points; and

use the stored model pattern, the starting pose, and the plurality of image boundary points in a sequence of pose refinements to provide;

a refined pose, the refined pose representing a refined estimate of the true pose of the object in the run-time image;

an error value;

an aggregate clutter value; and

an aggregate coverage value.

2. The apparatus of claim 1, wherein the run-time module is also configured to provide:

provide an evaluated image boundary point list that provides, for each of a plurality of said image boundary points, a numerical evaluation of the likelihood that the image boundary point was present in the stored model pattern.

3. The apparatus of claim 1, wherein the run-time module is also configured to provide:

an evaluated pattern boundary point list that provides, for each of a plurality of said pattern boundary points, a numerical evaluation of the likelihood that the pattern boundary point was present in the run-time image.

4. The apparatus of claim 1, wherein the run-time module is also configured to:

receive and use a coordinate transformation that maps points in an orthonormal coordinate system to points in the run-time image.

5. The apparatus of claim 1, wherein the run-time module is also configured to:

determine, using the starting pose and the model pattern, an evaluation of reliability of at least some of the plurality of image boundary points, and a corresponding position along a boundary of the model pattern corresponding to at least some of the plurality of image boundary points.

6. The apparatus of claim 1, wherein parameters are used to help detect in the run-time image a plurality of image boundary points.

7. The apparatus of claim 1, wherein parameters are used to facilitate the sequence of pose refinements.

8. The apparatus of claim 1, wherein the error value is an rms error value.

9. The apparatus of claim 1, wherein the information about the pattern boundary points is a vector-valued function of position within a region that includes the pattern boundary points.

10. The apparatus of claim 9, wherein the vector-valued function relates a plurality of at least two-dimensional positions to a plurality of respective displacement vectors.

11. The apparatus of claim 10, wherein each displacement vector indicates a distance and direction from a two-dimensional position to a nearest point along a pattern boundary that includes pattern boundary points.

12. The apparatus of claim 9, wherein the vector-valued function relates a plurality of two-dimensional positions and associated directions to a plurality of respective displacement vectors.

13. A geometric pattern matching apparatus for refining a starting pose of an object in a run-time image, the object having an expected shape and a true pose in the run-time image, the starting pose representing an initial estimate of the true pose of the object in the run-time image, the apparatus comprising:

a stored model pattern, the stored model pattern including a geometric description of the expected shape of the object, the geometric description including a plurality of pattern boundary points, and information about the pattern boundary points;

a feature detector configured to detect in the run-time image a plurality of image boundary points; and

a sequential pose refinement module configured to use the stored model pattern, the starting pose, and the plurality of image boundary points in a sequence of pose refinements to provide;

a refined pose, the refined pose representing a refined estimate of the true pose of the object in the run-time image;

an error value;

an aggregate clutter value; and

an aggregate coverage value.

14. The apparatus of claim 13, wherein the sequential pose refinement module receives and uses a coordinate transformation that maps points in an orthonormal coordinate system to points in the run-time image.

15. The apparatus of claim 13, wherein the sequential pose refinement module also being adapted to provide an evaluation of reliability of at least some of the plurality of image boundary points, and a corresponding position along a boundary of the model pattern corresponding to at least some of the plurality of image boundary points.

16. The apparatus of claim 13, wherein the sequential pose refinement module also being adapted to provide an evaluated image boundary point list that provides, for each of a plurality of said image boundary points, a numerical evaluation of the likelihood that the image boundary point was present in the stored model pattern.

17. The apparatus of claim 13, wherein the sequential pose refinement module also being adapted to provide an evaluated pattern boundary point list that provides, for each of a plurality of said pattern boundary points, a numerical evaluation of the likelihood that the pattern boundary point was present in the run-time image.

18. The apparatus of claim 13, wherein the feature detector uses parameters to help detect in the run-time image the plurality of image boundary points.

19. The apparatus of claim 13, wherein the sequential pose refinement module uses parameters to facilitate the sequence of pose refinements.

20. The apparatus of claim 13, wherein the error value is an rms error value.

21. The apparatus of claim 13, wherein the information about the pattern boundary points is a vector-valued function of position within a region that includes the pattern boundary points.

22. The apparatus of claim 21, wherein the vector-valued function relates a plurality of at least two-dimensional positions to a plurality of respective displacement vectors.

23. The apparatus of claim 22, wherein each displacement vector indicates a distance and direction from a two-dimensional position to a nearest point along a pattern boundary that includes pattern boundary points.

24. The apparatus of claim 21, wherein the vector-valued function relates a plurality of two-dimensional positions and associated directions to a plurality of respective displacement vectors.

25. A geometric pattern matching method for refining a starting pose of an object in a run-time image, the object having an expected object boundary and a true pose in the run-time image, the starting pose representing an initial estimate of the true pose of the object in the run-time image, the method comprising:

providing model pattern boundary information of a model pattern of the object;

providing an image boundary description of an object boundary in the run-time image; and

using the model pattern boundary information, the starting pose, and the image boundary description in a sequence of pose refinements to provide at least a refined pose, the refined pose representing a refined estimate of the true pose of the object in the run-time image and an aggregate coverage value.

26. The method of claim 25, wherein providing an image boundary description of a boundary in the run-time image includes:

detecting in the run-time image a plurality of image boundary points.

27. The method of claim 26, wherein each image boundary point obtained by detecting in the run-time image a plurality of image boundary points includes:

position information and direction information.

28. The method of claim 25, wherein providing an image boundary description of a boundary in the run-time image includes:

synthetically generating a plurality of image boundary points.

29. The method of claim 25, wherein using the model pattern boundary information, the starting pose, and the image boundary description in a sequence of pose refinements further provides an error value.

30. The method of claim 25, wherein using the model pattern boundary information, the starting pose, and the image boundary description in a sequence of pose refinements further provides an aggregate clutter value.

31. The method of claim 25, wherein providing model pattern boundary information of a model pattern of the object includes:

providing a stored model pattern, the stored model pattern including a geometric description of the expected shape of the object, the geometric description including a plurality of pattern boundary points, and information about the pattern boundary points.

32. The method of claim 31, wherein the information about the pattern boundary points is a vector-valued function of position within a region that includes the pattern boundary points.

33. The method of claim 32, wherein the vector-valued function relates a plurality of at least two-dimensional positions to a plurality of respective displacement vectors.

34. The method of claim 33, wherein each displacement vector indicates a distance and direction from a two-dimensional position to a nearest point along a pattern boundary that includes pattern boundary points.

35. The method of claim 31, wherein each pattern boundary point of the plurality of pattern boundary points includes:

position information and direction information.

36. The method of claim 32, wherein the vector-valued function relates a plurality of two-dimensional positions and associated directions to a plurality of respective displacement vectors.

37. The method of claim 25, wherein providing model pattern boundary information of a model pattern of the object includes:

providing a geometric description of the expected shape of the object.

38. The method of claim 37, wherein the geometric description includes a plurality of pattern boundary points.

39. The method of claim 25, wherein providing model pattern boundary information of a model pattern of the object includes:

providing a plurality of pattern boundary points, and information about the pattern boundary points.