Method for fast, robust, multi-dimensional pattern recognition

• US 8,320,675 B1
• Filed: 12/31/2004
• Issued: 11/27/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, Wagman, Adam
• Primary Examiner(s): Koziol, Stephen R
• Application Number:
  US11/026,004
• Time in Patent Office: 2,888 Days
• Field of Search: 382/118, 382/141, 382/181, 382/190, 382/197, 382/209, 382/279, 382/266, 348/92, 348/125
• US Class Current: 382/181
• 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 of training a model pattern for use in probe-based pattern matching, the method comprising:

providing a processor that performs the steps of;

obtaining a description of an object as at least one boundary;

selecting a subset of boundary segments along the at least one boundary for probe placement based on curvature along the subject of boundary segments; and

placing probes along the selected boundary segments.

2. The method of claim 1, wherein each probe indicates boundary direction at a point along the at least one boundary.

3. The method of claim 1, wherein obtaining a description of an object as at least one boundary includes:

forming a chain of boundary points.

4. The method of claim 1, wherein a corner of a boundary is a boundary zone having positions that are not selected for probe placement.

5. The method of claim 1, wherein placing probes along the reliable selected boundary segments includes:

placing a number of probes with predetermined spacing along the reliable selected boundary segment.

6. The method of claim 1, wherein placing probes along the selected boundary segments includes:

placing a predetermined number of probes with equal spacing along the selected boundary segments.

7. The method of claim 6, wherein the predetermined number of probes is 64.

8. The method of claim 6, wherein a minimum spacing between probes is enforced.

9. The method of claim 6, wherein a maximum spacing between probes is enforced.

10. The method of claim 6, wherein both a minimum spacing and a maximum spacing is enforced.

11. The method of claim 1, wherein obtaining a description of an object as at least one boundary includes:

choosing an appropriate granularity.

12. The method of claim 1, wherein obtaining a description of an object as at least one boundary includes:

processing a training image to obtain boundary points.

13. The method of claim 1, wherein obtaining a description of an object as at least one boundary includes:

processing a CAD description to obtain boundary points.

14. The method of claim 3, wherein forming a chain of boundary points includes:

connecting neighboring boundary points that have consistent directions; and

organizing connected boundary points into chains of boundary points.

15. The method of claim 14, further including:

removing short chains of boundary points.

16. The method of claim 14, further including:

removing weak chains of boundary points.

17. The method of claim 1, wherein selecting reliable boundary segments along the at least one boundary includes:

dividing chains of boundary points into segments of low curvature separated by corners of high curvature.

18. The method of claim 12, wherein processing a training image to obtain boundary points includes:

detecting boundary points in the training image.

19. The method of claim 14, wherein organizing connected boundary points into chains of boundary points includes:

for each chain, storing starting and ending points, length, total gradient magnitude, and whether the chain is open or closed.

20. The method of claim 16, wherein removing weak chains of boundary points includes:

removing chains of boundary points having a total gradient magnitude that is below a parameter.

21. The method of claim 16, wherein removing weak chains of boundary points includes:

removing chains of boundary points having an average gradient magnitude that is below a parameter.

22. The method of claim 1, wherein using curvature along a boundary includes:

determining whether a direction of a boundary point differs from that of either neighbor by more than 22.5 degrees.

23. The method of claim 1, wherein placing probes along the selected boundary segments includes:

placing a target number of probes with equal spacing along the selected boundary segments, such that probe spacing is not allowed to fall beyond predetermined limits.

24. The method of claim 23, wherein the target number of probes is 64.

25. The method of claim 23, wherein the predetermined limits include:

probe spacing cannot fall below 0.5 pixels; and

probe spacing cannot be greater than 4.0 pixels.

35. The method of claim 1 wherein the step of selecting boundary segments includes selecting less than all boundary segments.

36. The method of claim 1 wherein the step of selecting boundary segments includes selecting boundary segments of low curvature and rejecting boundary segments of high curvature.

26. A method of training a model pattern for use in probe-based pattern matching, the method comprising:

providing a processor that performs the steps of;

detecting boundary points in a training image of an object;

forming a chain of boundary points so as to provide at least one boundary;

selecting only boundary segments of low curvature along the at least one boundary for probe placement; and

placing a target number of probes along the selected boundary segments.

27. The method of claim 26, wherein each probe indicates boundary direction at a point along the at least one boundary.

28. The method of claim 26, wherein the target number of probes is 64.

29. The method of claim 26, wherein both a minimum and a maximum spacing between probes is enforced.

30. The method of claim 26, wherein detecting boundary points includes:

choosing an appropriate granularity.

31. The method of claim 26, wherein detecting boundary points in a training image of an object is replaced by:

processing a CAD description of an object to obtain boundary points.

32. The method of claim 26, wherein forming a chain of boundary points includes:

connecting neighboring boundary points that have consistent directions; and

organizing connected boundary points into chains of boundary points.

33. The method of claim 32, further including:

removing weak chains of boundary points.

34. The method of claim 33, wherein removing weak chains of boundary points includes:

removing chains of boundary points having an average gradient magnitude that is below a parameter.

37. A method of training a model pattern for use in probe-based pattern matching, the method comprising:

providing a processor that performs the steps of;

obtaining a description of an object as at least one boundary wherein the boundary includes a plurality of boundary portions;

selecting a subset of the plurality of boundary portions as selected boundary segments where the subset includes less than all of the plurality of boundary portions; and

placing probes along the selected boundary segments.

38. A computer program product, tangibly embodied in a non-transitory computer readable medium, the computer program product comprising instructions being operable to cause a data processing apparatus to:

obtain a description of an object as at least one boundary;

select a subset of boundary segments along the at least one boundary for probe placement based on curvature along the subject of boundary segments; and

place probes along the selected boundary segments.

39. The product of claim 38, wherein a corner of a boundary is a boundary zone having positions that are not selected for probe placement.

40. The product of claim 38, further comprising:

removing short chains of boundary points.

41. The product of claim 38, further comprising:

removing weak chains of boundary points.

42. The product of claim 38, wherein selecting reliable boundary segments along the at least one boundary includes:

dividing chains of boundary points into segments of low curvature separated by corners of high curvature.