Method for fast, robust, multi-dimensional pattern recognition

• US 8,363,972 B1
• Filed: 12/31/2004
• Issued: 01/29/2013
• Est. Priority Date: 07/13/1998
• Status: Expired due to Fees

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Corporation
• Inventors: Silver, William M., McGarry, E. John, Hill, Matthew L., Foster, Nigel J., Nichani, Sanjay, Foster, Willard P., Wagman, Adam
• Primary Examiner(s): Koziol, Stephen R
• Application Number:
  US11/027,963
• Time in Patent Office: 2,951 Days
• Field of Search: 382/118, 382/141, 382/181, 382/190, 382/197, 382/209, 382/261, 382/276, 348/92, 348/125
• US Class Current: 382/261
• 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 pattern matching method for determining the absence or presence of instances of a pattern in an image, and for determining the location of each found instance within a multi-dimensional space, the method comprising:

using a computer to perform the steps of;

receiving a training image;

receiving a list of generalized degrees-of-freedom (DOFs);

receiving a run-time image;

using the training image to provide a model that represents a pattern to be found, the model including a plurality of probes, each probe having a position with respect to the model at which at least one test is to be performed upon the image at a found pose of the model, each such test contributing evidence that the pattern exists at the found pose; and

analyzing the run-time image using the list of generalized degrees-of-freedom (DOFs) and the model to provide a list of results, each result corresponding to an instance of the pattern in the run-time image, using a sequence of increasingly precise match functions to locate each result.

2. The method of claim 1, wherein analyzing the runtime image includes:

initialization;

coarse exhaustive search to provide at least one coarse search candidate; and

fine scanning each coarse search candidate by using a first match function and then a second match function, the second match function being more precise and computationally intensive than the first match function.

3. The method of claim 2, wherein initialization includes:

processing the run-time image to provide a gradient magnitude image and a gradient direction image.

4. The method of claim 2, wherein coarse exhaustive search includes:

a coarse scan of an entire multi-dimensional search space, including nontranslation and translation degrees of freedom, to provide at least one coarse search candidate result.

5. The method of claim 2, wherein coarse exhaustive search includes:

computing a match score for each coarse search candidate result, the match score ignoring gradient magnitude.

6. The method of claim 5, wherein the match score is computed using a match function having a plurality of weights, a plurality of direction rating factors, and a plurality of magnitude rating factors.

7. The method of claim 6, wherein computing a direction rating factor includes:

computing gradient direction error for each probe;

assigning a direction rating factor of 1.0 for a probe that has a gradient direction error below a first value, assigning a direction rating factor of 0 for a probe that has a gradient direction error above a second value, and assigning a direction rating factor that is proportionally between 0 and 1.0 for a probe that has a gradient direction error that falls between the first and second values.

8. The method of claim 2, wherein coarse exhaustive search includes:

discarding weak coarse search candidate results.

9. The method of claim 2, wherein coarse exhaustive search includes:

discarding duplicate coarse search candidate results.

10. The method of claim 2, wherein fine scanning each coarse search candidate includes:

examining each coarse search candidate at a plurality of fine scan positions within a local hyper-neighborhood surrounding the pose of the coarse search candidate.

11. The method of claim 10, wherein the local hyper-neighborhood is a four-dimensional space having degrees-of-freedom including x-translation, y-translation, rotation, and scale.

12. The method of claim 10, wherein examining each fine search candidate includes computing a match score for each fine search candidate result, wherein the match score uses gradient magnitude, and is computed using both positive and negative weights.

13. The method of claim 12, wherein the match score is computed using a match function having a plurality of weights, a plurality of direction rating factors, and a plurality of magnitude rating factors.

14. The method of claim 2, wherein fine scanning each coarse search candidate includes:

discarding weak fine scan search results.

15. The method of claim 2, wherein fine scanning each coarse search candidate includes:

application of a first fine scan that is computed for both positive and negative weights, but is not divided by a sum of both positive and negative weights; and

application of a second fine scan that is that is divided by a sum of both positive and negative weights.

16. A pattern matching method for determining the absence or presence of instances of a pattern in an image, and for determining the location of each found instance within a multi-dimensional space, the method comprising:

using a computer to perform the steps of;

analyzing the image using a model that represents a pattern to be found, so as to provide a list of results, each result corresponding to an instance of the pattern in the image, the model being used at least three times for each result, a different match function being used for each use of the model;

wherein the at least three match functions are used in order of increasing reliability and decreasing speed.

18. The method of claim 16, wherein a first time a model is used,

the model is used with a first faster less reliable match function, and

the multidimensional space is searched in its entirety to provide a plurality of candidate locations, the match function being applied at locations spanning the entire multi-dimensional space.

21. The method of claim 16, wherein a first match function ignores gradient magnitude, and is computed for only positive weights.

22. The method of claim 16, wherein a second match function uses gradient magnitude, and is computed for both positive and negative weights, but is not divided by a sum of both positive and negative weights.

23. The method of claim 16, wherein a third match function uses gradient magnitude, and is divided by a sum of both positive and negative weights.

24. The method of claim 16, wherein the first match function ignores gradient magnitude, and includes a noise term.

25. The method of claim 24, wherein the noise term when polarity is considered is half the noise term when polarity is ignored.

26. The method of claim 16, wherein the model includes a plurality of probes, each probe having a position with respect to the model at which at least one test is to be performed upon the image at a found pose of the model, each such test contributing evidence that the pattern exists at the found pose.

17. A pattern matching method for determining the absence or presence of instances of a pattern in an image, and for determining the location of each found instance within a multi-dimensional space, the method comprising:

using a computer to perform the steps of;

analyzing the image using a model that represents a pattern to be found, so as to provide a list of results, each result corresponding to an instance of the pattern in the image, the model being used at least three times for each result, a different match function being used for each use of the model;

wherein at least three match functions are used to find each result using the model, the three match functions differing in speed and reliability,

wherein a less reliable match function yields more false positives than a more reliable match function and is relatively faster, and

wherein a more reliable match function yields less false positives than a less reliable match function and is relatively slower.

19. A pattern matching method for determining the absence or presence of instances of a pattern in an image, and for determining the location of each found instance within a multi-dimensional space, the method comprising:

using a computer to perform the steps of;

analyzing the image using a model that represents a pattern to be found, so as to provide a list of results, each result corresponding to an instance of the pattern in the image, the model being used at least three times for each result, a different match function being used for each use of the model;

wherein a second time a model is used,

the model is used with a second slower more reliable match function, and

the multi-dimensional space is searched only within a neighborhood surrounding each candidate location, the match function being applied at only a plurality of locations within each neighborhood, thereby refining the results found by the first match function.

20. The method of claim 19, wherein a third time a model is used,

the model is used with a third even slower and even more reliable match function, and

the multi-dimensional space is searched only within a neighborhood surrounding each candidate location, the match function being applied at only a plurality of locations within each neighborhood, thereby refining the results found using the second match function.

27. A computer program product to compute the presence or absence of instances of a two-dimensional pattern in an image, the product tangibly embodied in a non-transitory computer readable medium, the computer program product comprising including instructions being operable to cause a data processing apparatus to:

analyze the image based on model that represents a two-dimensional pattern to be found, so as to provide a list of results, each result corresponding to an instance of the pattern in the image, the model being used at least three times for each result, a different match function being used for each use of the model;

wherein the at least three match functions are used in order of increasing reliability and decreasing speed.

28. The apparatus of claim 27, wherein a less reliable match function yields more false positives than a more reliable match function and is relatively faster, and

wherein a more reliable match function yields less false positives than a less reliable match function and is relatively slower.

29. The apparatus of claim 27, wherein a first time a model is used,

the model is used with a first faster less reliable match function, and

the multidimensional space is searched in its entirety to provide a plurality of candidate locations, the match function being applied at locations spanning the entire multi-dimensional space.

30. The apparatus of claim 27, wherein a second time a model is used,

the model is used with a second slower more reliable match function, and

the multi-dimensional space is searched only within a neighborhood surrounding each candidate location, the match function being applied at only a plurality of locations within each neighborhood, thereby refining the results found by the first match function.

31. The apparatus of claim 30, wherein a first match function ignores gradient magnitude, and is computed for only positive weights.

32. The apparatus of claim 30, wherein a second match function uses gradient magnitude, and is computed for both positive and negative weights, but is not divided by a sum of both positive and negative weights.

33. The apparatus of claim 30, wherein a third match function uses gradient magnitude, and is divided by a sum of both positive and negative weights.

34. The apparatus of claim 30, wherein the first match function ignores gradient magnitude, and includes a noise term.

35. The apparatus of claim 30, wherein the noise term when polarity is considered is half the noise term when polarity is ignored.