Method for fast, robust, multi-dimensional pattern recognition

• US 8,244,041 B1
• Filed: 12/31/2004
• Issued: 08/14/2012
• Est. Priority Date: 07/13/1998
• Status: Expired due to Term

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Corporation
• Inventors: Silver, William M., McGarry, E. John, Nichani, Sanjay, Foster, Nigel J.
• Primary Examiner(s): Koziol, Stephen R
• Application Number:
  US11/029,104
• Time in Patent Office: 2,783 Days
• Field of Search: 382/118, 382/209, 382/261
• US Class Current: 382/209
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding
• CPC Class Codes: G06V 10/752 Contour matching

Abstract

Disclosed is a method for determining the absence or presence of one or more instances of a predetermined pattern in an image, and for determining the location of each found instance within a multidimensional space. A model represents the pattern to be found, the model including a plurality of probes. Each probe represents a relative position at which a test is performed in an image at a given pose, each such test contributing evidence that the pattern exists at the pose. The method further includes a comparison of the model with a run-time image at each of a plurality of poses. A match score is computed at each pose to provide a match score surface. Then, the match score is compared with an accept threshold, and used to provide the location any instances of the pattern in the image.

Claims

1. A method for running a probe-based system at high speed on a digital computer, the method comprising:

providing a computer programmed to perform the steps of;

converting probe information of a probe, including probe position represented as a real 2-vector into compiled probe information of the probe including a mapped image pixel address offset represented as a single integer.

2. The method of claim 1, wherein the probe information is represented by a probe data set including:

probe position;

probe direction; and

probe weight.

3. The method of claim 2, wherein probe position is in pattern coordinates.

4. The method of claim 2, wherein probe direction is in pattern coordinates.

5. The method of claim 2, wherein probe direction is expected gradient direction.

6. The method of claim 2, wherein probe direction is a binary angle.

7. The method of claim 2, wherein probes of zero weight are not used.

8. The method of claim 1, wherein the compiled probe information is represented by a compiled probe data set including:

offset;

direction; and

weight.

9. The method of claim 8, wherein the offset is a pixel address offset of the probe in a gradient magnitude image and a gradient direction image.

10. The method of claim 8, wherein direction is a binary angle.

11. The method of claim 8, wherein the direction is an expected gradient (boundary) direction, mapped to image coordinates.

12. The method of claim 8, wherein the weight is the probe weight copied from the probe data set.

13. The method of claim 8, wherein the weight is a scaled integer converted from a real number.

14. The method of claim 1, wherein converting probe information of a probe into compiled probe information of the probe includes:

using as inputs;

a coordinate transformation, and a rectangle to be set to a minimum enclosing rectangle of the pixel offsets of the compiled probes.

15. The method of claim 14, further including:

initializing by setting the rectangle to a null rectangle; and

setting a list of compiled probe objects to null.

16. The method of claim 14, wherein the coordinate transformation represents a specific setting of generalized degree-of-freedom (DOF) parameters.

17. The method claim 1, wherein converting probe information of a probe into compiled probe information of the probe includes:

for each probe in a list of probes, mapping each probe using a 2-dimensional coordinate transformation, the 2-dimensional coordinate transformation including a non-translation portion and a translation portion.

18. The method of claim 17, wherein mapping each probe using a 2-dimensional coordinate transformation includes:

mapping probe position of each probe to image coordinates using the input coordinate transform to provide a mapped image pixel offset in X, and a mapped image pixel offset in Y;

rounding the mapped image pixel offset in X, and rounding the mapped image pixel offset in Y, to provide a rounded mapped image pixel offset in X, and a rounded mapped image pixel offset in Y; and

adding the product of the rounded mapped image pixel offset in X and a pixel address difference between columns, to the product of the rounded mapped image pixel offset in Y and a pixel address difference between the rows, to provide a compiled probe offset value.

19. The method of claim 18, wherein mapping each probe using a 2-dimensional coordinate transformation includes:

constructing a unit vector in a gradient direction, with respect to pattern coordinates, by computing the cosine and sine of the angle of the gradient direction;

rotating the unit vector 90 degrees to get a direction along a boundary that contains the probe, thereby providing a rotated unit vector;

mapping the rotated unit vector, using the non-translation portion of the 2-dimensional coordinate transformation, to image coordinates to get a boundary direction in image coordinates, thereby providing a mapped rotated unit vector;

rotate the mapped rotated unit vector minus 90 degrees to get a direction normal to the boundary in image coordinates, thereby providing a resulting vector;

if the determinant of the non-translation portion is negative, rotate the direction normal to the boundary by 180 degrees, thereby providing a resulting vector; and

computing an angle of the resulting vector using an arctan function, to provide a compiled probe direction.

20. The method of claim 19, wherein converting probe information of a probe into compiled probe information of the probe includes:

for each probe in a list of probes, setting a compiled weight of the probe to the original weight of the probe.

21. A method for running a probe-based system at high speed on a digital computer, the method comprising:

providing a computer programmed to perform the steps of;

converting probe information of a probe, comprising probe position represented as a floating point 2-vector, into compiled probe information of the probe comprising a mapped image pixel address offset represented as a single integer.

22. The method of claim 21, wherein converting further comprises the step of rounding.

23. The method of claim 21, wherein the probe information is represented by a probe data set including:

the probe position;

probe direction; and

probe weight.

24. A non-transitory and processor readable medium having stored thereon a data structure for probe-based system, the data structure comprising:

a probe object, having at least a 2-vector representation of position, and

a compiled probe object having one integer as a pixel address offset derived by altering information of the position of the probe object, such that a portion of the information of the position of the probe object is lost.

25. A computerized program apparatus, the apparatus comprising:

a memory,

a probe object, stored on the memory, having a 2-vector probe coordinates

a compiled probe object, stored on the memory, having a single integer image pixel offset address,

the computer program apparatus comprising instructions being operable in a probe-based system to cause data processing apparatus to derive the single integer image pixel offset address by converting the 2-vector probe coordinates.

26. The apparatus of claim 25, wherein deriving the single integer image pixel offset address includes:

for each probe in a list of probes, mapping each probe using a 2-dimensional coordinate transformation, the 2-dimensional coordinate transformation comprising a non-translation portion and a translation portion.

27. The apparatus of claim 25, wherein deriving the single integer image pixel offset address includes:

using as inputs;

a coordinate transformation, and a rectangle to be set to a minimum enclosing rectangle of the pixel offsets of the compiled probes.

28. The apparatus of claim 25, wherein the 2-vector probe coordinates are 2 vector coordinates and deriving the single integer image pixel offset address includes:

altering information of the position of the probe object, such that a portion of the information of the position of the probe object is lost.

29. The apparatus of claim 25, wherein probe information is represented by a probe data set including:

the probe position;

probe direction; and

probe weight.