Fast high-accuracy multi-dimensional pattern inspection

• US 7,164,796 B1
• Filed: 11/11/2003
• Issued: 01/16/2007
• Est. Priority Date: 11/26/1997
• Status: Expired due to Fees

• 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,287
• Time in Patent Office: 1,162 Days
• Field of Search: 382/151, 382/197, 382/199, 382/203, 382/209, 382/216, 382/218, 382/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 method of training a model pattern for use in geometric pattern matching, the method comprising:

obtaining a digital image of an object;

detecting boundary points in the digital image so as to form a pattern boundary; and

producing a plurality of displacement vectors, each displacement vector indicating at least a distance and a direction to a nearest point on the pattern boundary, the model pattern including at least the pattern boundary and the plurality of displacement vectors, the model pattern being for use in geometric pattern matching.

2. The method of claim 1, wherein each displacement vector is stored at a grid element of an array of grid elements.

3. The method of claim 2, wherein producing a plurality of displacement vectors includes:

producing a displacement vector at a grid element using a displacement vector from a neighboring grid element.

4. The method of claim 3, wherein producing a displacement vector at a grid element using a displacement vector from a neighboring grid element includes:

constructing a first vector from the center of the grid element, to the center of the neighboring grid element;

constructing a projection of the first vector, onto the displacement vector from the neighboring grid element; and

constructing the displacement vector at the grid element by adding the displacement vector from the neighboring grid element, to the projection of the first vector onto the displacement vector from the neighboring grid element.

5. The method of claim 4, further including,

computing an offset value having:

a length equal to the length of the difference between the displacement vector at a grid element, and the projection of the first vector onto the displacement vector from the neighboring grid element; and

a sign that is determined by the direction in which the first vector must be rotated to coincide with the projection of the first vector.

6. The method of claim 5, wherein counter-clockwise rotation is deemed to result in a positive sign.

7. The method of claim 3, wherein the neighboring grid element is a diagonal neighbor.

8. The method of claim 3, wherein the neighboring grid element is a neighbor that shares a side of the neighboring grid element.

9. The method of claim 3, wherein producing a displacement vector at a grid element using a displacement vector from a neighboring grid element includes:

producing a displacement vector at the grid element that is parallel to the displacement vector from the neighboring grid element.

10. The method of claim 3, wherein producing a displacement vector at a grid element using a displacement vector from a neighboring grid element includes:

producing a displacement vector at the grid element that is parallel to the displacement vector from the neighboring grid element, and that extends from the center of the grid element to the nearest point along the pattern boundary.

11. The method of claim 2, wherein producing a plurality of displacement vectors occurs over a sequence of propagation events, each propagation event providing additional displacement vectors at respective additional grid elements.

12. The method of claim 11, wherein grid elements are initialized to a pre-defined value before the sequence of propagation events.

13. The method of claim 12, wherein the pre-defined value is one of:

a value independent of any boundary point, and a value dependent on at least one boundary point.

14. The method of claim 12, wherein the pre-defined value is “

expect blank”

.

15. The method of claim 11, wherein each propagation event includes:

for each grid element considered for propagation of a displacement vector to the grid element, all neighbors of the grid element are examined such that, if at least two adjacent neighbors have valid displacement vectors, a displacement vector will be propagated to the grid element during that propagation event, else, a displacement vector will not be propagated to the grid element during that propagation event.

16. The method of claim 15, wherein for each adjacent neighbor of the grid element having a valid displacement vector, a new displacement vector originating at the grid element, and an associated offset, is computed such that the new displacement vector is parallel to the valid displacement vector, resulting in a plurality of new displacement vectors originating at the grid element, and a plurality of associated offsets.

17. The method of claim 16, wherein a propagated displacement vector is computed by interpolating between two of the plurality of new displacement vectors.

18. The method of claim 16, wherein the two of the plurality of new displacement vectors are selected using the plurality of associated offsets.

19. The method of claim 18, wherein adjacent neighbors are sequentially scanned to detect a single positive-to-negative transition between adjacent neighbors, the single positive-to-negative transition being used to select the two of the plurality of new displacement vectors.

20. The method of claim 19, wherein adjacent neighbors are scanned counter-clockwise in sequence.

21. The method of claim 17, wherein interpolating between two of the plurality of new displacement vectors includes:

computing a weighted average of the two of the plurality of new displacement vectors.

22. The method of claim 21, wherein computing a weighted average of the two of the plurality of new displacement vectors includes:

weighting of each of the two new displacement vectors using the magnitude of the offset of the other of the two new displacement vectors.

23. The method of claim 21, wherein computing a weighted average of the two of the plurality of new displacement vectors includes:

scaling each new displacement vector by its corresponding weight, adding the results, and then scaling by the inverse of the sum of the weights.

24. The method of claim 21, wherein computing a weighted average of the two of the plurality of new displacement vectors includes:

performing an independent weighted average of the x and y components of the two of the plurality of new displacement vectors.

25. The method of claim 21, wherein computing a weighted average of the two of the plurality of new displacement vectors includes:

performing an independent weighted average of the magnitude and direction of the two of the plurality of new displacement vectors.

26. The method of claim 17, wherein if the two of the plurality of new displacement vectors are pointing to distant points along a pattern boundary, or are pointing to different boundaries, the grid element is not assigned a propagated displacement vector, instead being assigned a “

don'"'"'t care”

code.

27. The method of claim 26, wherein the two of the plurality of new displacement vectors are pointing to distant points along a pattern boundary if their magnitudes differ by more than 3 grid units.

28. The method of claim 26, wherein the two of the plurality of new displacement vectors are pointing to distant points along a pattern boundary if their directions differ by more than 135 degrees.

29. The method of claim 26, wherein the two of the plurality of new displacement vectors are pointing to different boundaries if their magnitudes differ by more than 3 grid units.

30. The method of claim 26, wherein the two of the plurality of new displacement vectors are pointing to different boundaries if their directions differ by more than 135 degrees.

31. The method of claim 1, wherein producing a plurality of displacement vectors results in a vector-valued function of position within a region of the image that includes the pattern boundary.

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

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

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

35. The method of claim 11, wherein each propagation event includes:

for each adjacent neighbor of the grid element having a valid displacement vector, computing a new displacement vector originating at the grid element, and computing an associated offset; and

for each grid element considered for propagation of a displacement vector to the grid element, if a neighboring grid element with a valid displacement vector is associated with a small positive offset, and if no counter-clockwise adjacent neighbor has a valid displacement vector, propagating a displacement vector to the grid element during that propagation event using the new displacement vector without interpolation.

36. The method of claim 35, wherein a small negative offset is an offset of magnitude less than 1/10 of a grid element.

37. The method of claim 11, wherein each propagation event includes:

for each adjacent neighbor of the grid element having a valid displacement vector, computing a new displacement vector originating at the grid element, and computing an associated offset; and

for each grid element considered for propagation of a displacement vector to the grid element, if a neighboring grid element with a valid displacement vector is associated with a small negative offset, and if no clockwise adjacent neighbor has a valid displacement vector, propagating a displacement vector to the grid element during that propagation event using the new displacement vector without interpolation.

38. The method of claim 37, wherein a small positive offset is an offset of magnitude less than 1/10 of a grid element.

39. The method of claim 11, wherein there are four propagation events.

40. The method of claim 11, wherein the number of propagation events is determined by a user-settable parameter.

41. The method of claim 11, wherein each propagation event provides a plurality of displacement vectors, each displacement vector indicating a distance and direction toward the pattern boundary.

42. The method of claim 11, wherein each propagation event provides a plurality of displacement vectors that are disposed at a greater distance from the pattern boundary than the plurality of displacement vectors provided by a previous propagation event.