Method for fast, robust, multi-dimensional pattern recognition

• US 7,016,539 B1
• Filed: 07/13/1998
• Issued: 03/21/2006
• 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., Nichani, Sanjay, Hill, Matthew L., Wagman, Adam, McGarry, E. John, Foster, Nigel, Foster, Willard P.
• Primary Examiner(s): Ahmed, Samir
• Assistant Examiner(s): KIM, CHONG R
• Application Number:
  US09/114,335
• Time in Patent Office: 2,808 Days
• Field of Search: 382/151, 382/291
• US Class Current: 382/216
• 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 determining the presence or absence of at least one instance of a predetermined pattern in a run-time image, and for determining the multidimensional location (pose) of each present instance, the method comprising:

providing a model that represents the pattern to be found, the model including a plurality of probes, each probe representing a relative position at which at least one test is performed in an image at a given pose, each such test contributing evidence that the pattern exists at the pose;

providing the run-time image;

comparing the model with the run-time image at each of a plurality of poses;

computing a match score at each pose to provide a match score surface;

locating local maxima in the match score surface;

comparing the magnitude of each local maxima with an accept threshold; and

returning the location of each local maxima with magnitude that exceeds the accept threshold so as to provide the location any instances of the pattern in the image.

2. The method of claim 1, wherein the model is created from a training image.

3. The method of claim 1, wherein the model is synthesized from a geometric description.

4. The method of claim 1, wherein each probe provides a measurement of gradient direction.

5. The method of claim 1, wherein each probe provides a measurement of both gradient direction and magnitude.

6. The method of claim 1, wherein each probes represent different tests at different steps of the method.

7. The method of claim 1, wherein a probe is characterized by a position, a direction, and a weight.

8. The method of claim 1, wherein probe position is a point in a pattern coordinate system at which, aft transforming to a image coordinate system using a given pose, a measurement and test is to be made.

9. The method of claim 1, wherein probe direction is the expected gradient direction in pattern coordinates at the indicated position, which also must be transformed to image coordinates prior to use.

10. The method of claim 1, wherein probe weight gives the relative importance of the probe in determining the presence and location of the pattern.

11. The method of claim 1, wherein probe weights can be positive or negative, a negative weight indicating that a test showing similar gradient direction and sufficient gradient magnitude counts as evidence against the existence of the pattern at the specified pose.

12. The method of claim 1, wherein the model includes a plurality of probes placed at selected points along boundaries represented by the corresponding pattern.

13. The method of claim 12, wherein the probes are uniformly spaced along segments of the boundaries characterized by a small curvature.

14. The method of claim 12, wherein the spacing between the probes is chosen so that a predetermined number of probes is used.

15. The method of claim 14, wherein fewer probes can be used to prevent the spacing from being set below some predetermined minimum value, and more probes can be used to prevent the spacing from being set above some predetermined maximum value.

16. The method of claim 15, wherein the predetermined number of probes is 64.

17. The method of claim 1, wherein model granularity is selectable over a wide range down to the limit imposed by an sensor that provides the image to be searched.

18. The method of claim 1, wherein providing a model includes automatically choosing a suitable granularity.

19. The method of claim 1, wherein providing a model includes using at least two granularities are used, so that the speed advantages of the coarsest granularity and the accuracy advantages of the finest granularity can be obtained.

20. The method of claim 19, wherein The model includes a separate set of probes for each granularity.

21. The method of claim 1 wherein the horizontal and vertical components of gradient are measured using a Sobel kernel.

22. The method of claim 21, wherein a CORDIC algorithm is used to compute gradient magnitude and direction.

23. The method of claim 1, wherein providing the run-time image includes:

applying Sobel kernels to a filtered, sub-sampled acquired image so as to provide a gradient magnitude image and a gradient direction image that together provide image gradient information at uniformly spaced points.

24. The method of claim 1, wherein computing a match score includes computing gradient direction.

25. The method of claim 24, further including computing gradient magnitude.

26. The method of claim 24, further including computing probe weight.

27. The method of claim 24, wherein computing a match score includes:

assigning a rating of 0 to probe positions having a gradient direction error below a first predetermined value;

assigning a rating of 1 to probe positions having gradient direction error above a second predetermined value; and

assigning a rating between 1 and 0 to probe positions having a gradient direction error that falls between the said first and second predetermined values.

28. The method of claim 1 wherein computing a match score includes:

computing a weighted sum of probe ratings; and

dividing the weighted sum by the total weight of all probes to provide the match score.

30. The method of claim 28, wherein an expected value of the weighted sum of the probe ratings on random gradient directions is subtracted from an actual weighted sum, with the total weight adjusted accordingly, so that a perfect match still gets a score of 1.0 but an expected value of the score on random noise is 0.

31. The method of claim 1, wherein computing a match score includes:

computing a direction rating factor for each probe;

assigning a probe rating to each probe that is the product of the direction rating factor and a gradient magnitude under the probe; and

computing a weighted sum of the probe ratings to provide the match score.

32. The method of claim 1, wherein computing a match score includes:

computing a direction rating factor for each probe;

computing a magnitude rating factor that is 1.0 for gradient magnitudes above a certain first value, 0 for magnitudes below a certain second value, and proportionally between 0 and 1.0 for values between said first and second values;

assigning to each probe a rating that is the product of the direction rating factor and the magnitude rating factor; and

providing a match score that is a weighted sum of the probe ratings divided by the total weight of all the probes.

33. The method of claim 1, wherein returning the location of each local maxima with magnitude that exceeds the accept threshold includes:

refining the found positions of the local maxima by evaluating a small, dense set of poses surrounding each coarse peak.

34. The method of claim 33, further including:

interpolating among the dense set of poses to provide an interpolated position of the local maximum so as to provide a potential instance of the pattern in the run-time image.

35. The method of claim 34, further including:

evaluating a match function to determine whether an instance of the pattern is actually present in the run-time image at said pose by comparing the value of the match function to an accept threshold.

29. The method of clam 28, wherein all probe weights are 1.