Method for fast, robust, multi-dimensional pattern recognition

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.

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.

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.

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.

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.

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.