Fast high-accuracy multi-dimensional pattern inspection

• US 6,850,646 B1
• Filed: 11/10/2003
• Issued: 02/01/2005
• Est. Priority Date: 12/31/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,295
• Time in Patent Office: 449 Days
• Field of Search: 382/103, 382/151, 382/154, 382/181, 382/197, 382/199, 382/203, 382/209, 382/216, 382/242, 382/256, 382/276, 382/285, 382/289, 382/291, 382/295, 348/169
• US Class Current: 382/199
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

A method and apparatus are provided for identifying diffe rences 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 method for mapping a current pose P of an image boundary in a digital image into a more accurate pose P′

of the image boundary, the image boundary having N image boundary points, the method comprising;

solving a plurality of simultaneous equations, the plurality including an equation for each of a respective plurality of image boundary points of the image boundary, so as to provide a coordinate transform; and

applying the coordinate transform to each of the image boundary points that maps the current pose P of the image boundary into a more accurate pose P′

of the image boundary, the coordinate transform being of the form P′

=CP+t, where C is a matrix, and t is a translation vector.

2. The method of claim 1, wherein the coordinate transform is a six degree-of-freedom coordinate transform.

3. The method of claim 1, wherein each image boundary point includes a position.

4. The method of claim 1, wherein each image boundary point includes a position and a direction.

5. The method of claim 1, wherein the plurality of simultaneous equations is solved repeatedly, using the more accurate pose P′

as a starting pose P with each repetition.

6. The method of claim 1, wherein more than twelve equations are solved simultaneously.

7. The method of claim 1, wherein solving a plurality of simultaneous equations includes:

using an error minimization method to minimize a sum of a plurality of error terms, each error term corresponding to an image boundary point.

8. The method of claim 7, wherein an error term is equal to a magnitude of a component of a vector in the direction of a displacement vector representing a minimum distance between an image boundary point and a pattern boundary, minus a magnitude of the displacement vector.

9. The method of claim 1, wherein solving a plurality of simultaneous equations includes:

using a least-squares method.

10. The method of claim 9, wherein the least squares method includes an error term for each image boundary point, and a weight value is determined for each image boundary point.

11. The method of claim 10, wherein a total error is computed by summing, over a plurality of image boundary points, the product of the square of an associated error term and an associated weight value.

12. The method of claim 11, wherein each error term includes a contribution from each degree of freedom.

13. The method of claim 9, wherein using the least squares method involves no more than four degrees of freedom.

14. The method of claim 12, wherein the four degrees of freedom are selected from:

x-translation, y-translation, orientation, and size.

15. The method of claim 14, wherein the degrees of freedom selected are determined by at least one parameter.

16. The method of claim 14, wherein the orientation degree of freedom is defined by an orthonormal real-world coordinate system.

17. A method for mapping a current pose P of an image boundary in a digital image into a more accurate pose P′

of the image boundary, the image boundary having N image boundary points, the method comprising;

solving a plurality of simultaneous equations so as to provide a coordinate transform, the plurality including an equation for each of a respective plurality of image boundary points of the image boundary, the plurality being simultaneously solved using a least-squares method to minimize a linear sum of a plurality of squared error terms, each error term corresponding to an image boundary point; and

applying the coordinate transform to each of the image boundary points that maps the current pose P of the image boundary into a more accurate pose P′

of the image boundary, the coordinate transform being of the form P′

=CP+t, where C is a matrix, and t is a translation vector.

18. The method of claim 17, wherein the coordinate transform is a six degree-of-freedom coordinate transform.

19. The method of claim 17, wherein each image boundary point includes a position.

20. The method of claim 17, wherein each image boundary point includes a position and a direction.

21. The method of claim 17, wherein the plurality of simultaneous equations is solved repeatedly, using the more accurate pose P′

as a starting pose P with each repetition.

22. The method of claim 17, wherein more than twelve equations are solved simultaneously.

23. The method of claim 17, wherein each error term is equal to a magnitude of a component of a vector in the direction of a displacement vector representing a minimum distance between an image boundary point and a pattern boundary, minus a magnitude of the displacement vector.

24. The method of claim 17, wherein the linear sum includes a weight coefficient for each squared error term.

25. The method of claim 24, wherein a total error is computed by summing, over a plurality of image boundary points, the product of the square of an associated error term and an associated weight value.

26. The method of claim 25, wherein each error term includes a contribution from each degree of freedom.

27. The method of claim 17, wherein using the least squares method involves no more than four degrees of freedom.

28. The method of claim 27, wherein the four degrees of freedom are selected from:

x-translation, y-translation, orientation, and size.

29. The method of claim 28, wherein the degrees of freedom selected are determined by at least one parameter.

30. The method of claim 28, wherein the orientation degree of freedom is defined by an orthonormal real-world coordinate system.

31. In 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 geometric pattern matching apparatus having (1) 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 of a pattern boundary, and a vector-valued function of position within a region that includes the pattern boundary points, and (2) a feature detector configured to detect in the run-time image a plurality of image boundary points, a method for mapping a current pose P of an image boundary in the run-time image into a more accurate pose P′

of the image boundary, the image boundary having a plurality of image boundary points, the method comprising;

solving a plurality of simultaneous equations, the plurality including an equation for each of a respective plurality of image boundary points of the image boundary, so as to provide a coordinate transform; and

applying the coordinate transform to each of the image boundary points that maps the current pose P of the image boundary into a more accurate pose P′

of the image boundary.

32. The apparatus of claim 31, wherein the coordinate transform is a six degree-of-freedom coordinate transform.

33. The apparatus of claim 31, wherein the coordinate transform is of the form

P′

=CP+t, where C is a matrix, and t is a translation vector.

34. The apparatus of claim 31, wherein each image boundary point includes a position and a direction.

35. The apparatus of claim 31, wherein the plurality of simultaneous equations is solved repeatedly, using the more accurate pose P′

as a starting pose P with each repetition.

36. The apparatus of claim 31, wherein more than twelve equations are solved simultaneously.

37. The apparatus of claim 31, wherein solving a plurality of simultaneous equations includes:

using an error minimization method to minimize a sum of a plurality of error terms, each error term corresponding to an image boundary point.

38. The apparatus of claim 37, wherein an error term is equal to a magnitude of a component of a vector in the direction of a displacement vector representing a minimum distance between an image boundary point and a pattern boundary, minus a magnitude of the displacement vector.

39. The apparatus of claim 31, wherein solving a plurality of simultaneous equations includes:

using a least-squares method.

40. The apparatus of claim 39, wherein the least squares method includes an error term for each image boundary point, and a weight value is determined for each image boundary point.

41. The apparatus of claim 40, wherein a total error is computed by summing, over a plurality of image boundary points, the product of the square of an associated error term and an associated weight value.

42. The apparatus of claim 41, wherein each error term includes a contribution from each degree of freedom.

43. The apparatus of claim 39, wherein using the least squares method involves no more than four degrees of freedom.

44. The apparatus of claim 43, wherein the four degrees of freedom are selected from:

x-translation, y-translation, orientation, and size.

45. The apparatus of claim 44, wherein the degrees of freedom selected are determined by at least one parameter.

46. The apparatus of claim 44, wherein the orientation degree of freedom is defined by an orthonormal real-world coordinate system.

47. A method for mapping a current pose P of an image boundary in a digital image into a more accurate pose P′

of the image boundary, the image boundary having N image boundary points, the method comprising;

solving a plurality of simultaneous equations so as to provide a coordinate transform, the plurality including an equation for each of a respective plurality of image boundary points of the image boundary, the plurality being solved by using an error minimization method to minimize a sum of a plurality of error terms, each error term corresponding to an image boundary point;

each error term including a magnitude of a component of a vector in the direction of a displacement vector representing a minimum distance between an image boundary point and a pattern boundary, minus a magnitude of the displacement vector; and

applying the coordinate transform to each of the image boundary points that maps the current pose P of the image boundary into a more accurate pose P′

of the image boundary.

48. The method of claim 47, wherein the coordinate transform is of the form

P′

=CP+t, where C is a matrix, and t is a translation vector.

49. The method of claim 47, wherein the coordinate transform is a six degree-of-freedom coordinate transform.

50. The method of claim 47, wherein each image boundary point includes a position and a direction.

51. The method of claim 47, wherein the plurality of simultaneous equations is solved repeatedly, using the more accurate pose P′

as a starting pose P with each repetition.

52. The method of claim 47, wherein more than twelve equations are solved simultaneously.

53. The method of claim 47, wherein solving a plurality of simultaneous equations includes:

using a least-squares method.

54. The method of claim 47, wherein a weight value is determined for each image boundary point.

55. The method of claim 54, wherein a total error is computed by summing, over a plurality of image boundary points, the product of an error term and an associated weight value.

56. The method of claim 55, wherein each error term includes a contribution from each degree of freedom.

57. The method of claim 47, wherein using the error minimization method involves no more than four degrees of freedom.

58. The method of claim 57, wherein the four degrees of freedom are selected from:

x-translation, y-translation, orientation, and size.

59. The method of claim 58, wherein the degrees of freedom selected are determined by at least one parameter.

60. The method of claim 58, wherein the orientation degree of freedom is defined by an orthonormal real-world coordinate system.