Fast high-accuracy multi-dimensional pattern inspection

• US 7,006,712 B1
• Filed: 11/10/2003
• Issued: 02/28/2006
• Est. Priority Date: 11/26/1997
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Silver, William, Wagman, Adam, Wallack, Aaron
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US10/705,298
• Time in Patent Office: 841 Days
• Field of Search: 382/103, 382/151, 382/197, 382/284, 382/291, 382/293, 382/295, 382/300, 382/305, 348/538, 358/525, 708/290
• US Class Current: 382/300
• 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 for interpolating a vector-valued function, the vector-valued function relating a plurality of at least two-dimensional positions to a plurality of respective displacement vectors, the method comprising:

providing an array of grid elements, each grid element having a coordinate region, and each grid element containing at least a displacement vector magnitude and a displacement vector direction;

providing a real-valued input position vector having real-valued coordinates, the coordinates falling within the coordinate region of a grid element;

rounding the coordinates of the real-valued input position vector so as to provide an integer grid position vector;

subtracting the integer grid position vector from the real-valued input position vector to provide a sub-grid position vector;

using the integer grid position vector to access the contents of a grid element, the contents of the grid element including a displacement vector magnitude, and a displacement vector direction;

using the displacement vector direction to provide a unit vector in the displacement vector direction;

using the unit vector in the displacement vector direction and the sub-grid position vector to provide a component of the sub-grid position vector in the displacement vector direction;

subtracting the displacement vector magnitude from the component of the sub-grid position vector in the displacement vector direction to provide an interpolated displacement vector magnitude; and

combining the interpolated displacement vector magnitude, the unit vector in the displacement direction, and the displacement vector direction so as to provide an interpolated displacement vector corresponding to the real-valued input position vector.

2. The method of claim 1, further comprising:

using the integer grid position vector to provide the contents of a grid element, the contents of the grid element including grid element information.

3. The method of claim 2, wherein the integer grid position vector is used to provide a memory address, the memory address being used to access the contents of the grid element indexed by the memory address.

4. The method of claim 1, wherein using the integer grid position vector to access the contents of a grid element includes:

using the integer grid position vector to provide a memory address; and

using the memory address to access the contents of a grid element indexed by the memory address.

5. The method of claim 1, wherein using the displacement vector direction to provide a unit vector in the displacement direction is performed using a cosine/sine method.

6. The method of claim 1, wherein using the displacement vector direction to provide a unit vector in the displacement direction is performed using a look-up table.

7. The method of claim 1, wherein using the unit vector in the displacement direction and the sub-grid position vector to provide a component of the sub-grid position vector in the displacement direction is performed using a dot product.

8. The method of claim 1, wherein the real-valued input position is provided in grid coordinates.

9. The method of claim 1, further comprising:

using a neighboring grid element.

10. A method for interpolating a vector-valued function, the vector-valued function relating a plurality of at least two-dimensional positions to a plurality of respective displacement vectors, the method comprising:

providing an array of grid elements, each grid element having a coordinate region, and containing at least a displacement vector magnitude and a displacement vector direction;

providing a real-valued input position vector having real-valued coordinates, the coordinates falling within the coordinate region of a grid element;

using a unit vector in the displacement vector direction to provide an interpolated displacement vector magnitude; and

combining the interpolated displacement vector magnitude, the unit vector in the displacement direction, and the displacement vector direction so as to provide an interpolated displacement vector corresponding to the real-valued input position vector.

11. The method of claim 10, wherein using a unit vector in the displacement vector direction to provide an interpolated displacement vector magnitude includes:

using the displacement vector direction to provide a unit vector in the displacement vector direction.

12. The method of claim 10, wherein using a unit vector in the displacement vector direction to provide an interpolated displacement vector magnitude includes:

using the unit vector in the displacement vector direction and the displacement vector magnitude to provide an interpolated displacement vector magnitude.

13. The method of claim 10, wherein the real-valued input position vector is used to access the contents of a grid element, the contents of the grid element including a displacement vector magnitude, and a displacement vector direction.

14. The method of claim 13, wherein the real-valued input position vector is used to access the contents of a grid element by converting the real-valued input position vector into an integer grid position vector.

15. The method of claim 14, wherein the integer grid position vector is used to provide a memory address, the memory address being used to access the contents of the grid element indexed by the memory address.

16. The method of claim 10, wherein using a unit vector in the displacement vector direction includes:

performing a dot product using the unit vector.

17. The method of claim 16, wherein performing a dot product using the unit vector provides a component in the displacement vector direction of the vector derived by subtracting the integer grid position vector from the real-valued input position vector.

18. The method of claim 17, wherein subtracting the displacement vector magnitude, from the component in the displacement vector direction, of the vector derived by subtracting the integer grid position vector from the real-valued input position vector, provides the interpolated displacement vector corresponding to the real-valued input position vector.

19. The method of claim 10, wherein using a unit vector in the displacement vector direction includes:

performing a dot product using the unit vector and a vector derived from the real-valued input position vector.

20. The method of claim 19, wherein the vector derived from the real-valued input position vector is obtained by subtracting the integer grid position vector from the real-valued input position vector.

21. An apparatus for interpolating a vector-valued function, the vector-valued function relating a plurality of at least two-dimensional positions to a plurality of respective displacement vectors, the apparatus comprising:

a grid element source configured to provide an array of grid elements, each grid element having a coordinate region, and each grid element containing at least a displacement vector magnitude and a displacement vector direction;

a position source configured to provide a real-valued input position vector having real-valued coordinates, the coordinates falling within the coordinate region of a grid element;

an integer rounding module, cooperative with the position source, and configured to round the coordinates of the real-valued input position vector so as to provide an integer grid position vector;

a first subtraction module, cooperative with the integer rounding module, and configured to subtract the integer grid position vector from the real-valued input position vector to provide a sub-grid position vector;

an address generation module, cooperative with the integer rounding module and the grid element source, and configured to use the integer grid position vector to access the contents of a grid element, the contents of the grid element including a displacement vector magnitude, and a displacement vector direction;

a unit vector module, cooperative with the grid element source, and configured to use the displacement vector direction to provide a unit vector in the displacement vector direction;

a component extractor, cooperative with the unit vector module, and configured to use the unit vector in the displacement vector direction and the sub-grid position vector to provide a component of the sub-grid position vector in the displacement vector direction;

a second subtraction module, cooperative with the component extractor, and configured to subtract the displacement vector magnitude from the component of the sub-grid position vector in the displacement vector direction to provide an interpolated displacement vector magnitude; and

an output module, cooperative with the second subtraction module, and configured to combine the interpolated displacement vector magnitude, the unit vector in the displacement direction, and the displacement vector direction so as to provide an interpolated displacement vector corresponding to the real-valued input position vector.

22. The apparatus of claim 21, further comprising:

an address generation module, cooperative with the integer rounding module and the grid element source, and adapted to use the integer grid position vector to provide a memory address to the grid element source, the memory address being used to access the contents of the grid element indexed by the memory address.

23. The apparatus of claim 21, wherein the unit vector module includes a look-up table.

24. The apparatus of claim 21, wherein the grid element source includes a memory array.

25. An apparatus method for interpolating a vector-valued function, the vector-valued function relating a plurality of at least two-dimensional positions to a plurality of respective displacement vectors, the apparatus comprising:

a grid element source configured to provide an array of grid elements, each grid element having a coordinate region, and containing at least a displacement vector magnitude and a displacement vector direction;

a position source, cooperative with the grid element source, and configured to provide a real-valued input position vector having real-valued coordinates, the coordinates falling within the coordinate region of a grid element;

a unit vector module, cooperative with the grid element source, and configured to use the displacement vector direction to provide a unit vector in the displacement vector direction for use in computing an interpolated displacement vector magnitude; and

an output module, cooperative with the unit vector module, and configured to combine the interpolated displacement vector magnitude, the unit vector in the displacement direction, and the displacement vector direction so as to provide an interpolated displacement vector corresponding to the real-valued input position vector.

26. The apparatus of claim 25, further comprising:

a sub-grid position module, cooperative with the position source, and configured to use the real-valued input position vector to provide a sub-grid position vector.

27. The apparatus of claim 26, further comprising:

a component extractor, cooperative with the unit vector module, and configured to use the unit vector in the displacement vector direction and the sub-grid position vector to provide a component of the sub-grid position vector in the displacement vector direction.

28. The apparatus of claim 27, further comprising:

a force magnitude modifier, cooperative with the component extractor and the grid element source, and configured to modify the force magnitude in accordance with the component of the sub-grid position vector in the displacement vector direction to provide the interpolated displacement vector magnitude.

29. The apparatus of claim 25, further comprising:

a memory addresser, cooperative with the position source and the grid element source, for converting the real-valued input position vector into a memory address, the memory address being for accessing the contents of a grid element.

30. The apparatus of claim 25, wherein the unit vector module includes a look-up table.

31. The apparatus of claim 25, wherein the unit vector module includes cosine/sine module.