Method for fast, robust, multi-dimensional pattern recognition

• US 8,249,362 B1
• Filed: 12/31/2004
• Issued: 08/21/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
• Primary Examiner(s): Koziol, Stephen R
• Application Number:
  US11/028,076
• Time in Patent Office: 2,790 Days
• Field of Search: 382/215, 382/218, 382/141, 382/181, 382/190, 348/92, 348/125
• US Class Current: 382/215
• 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 plurali 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. In a pattern matching method for determining the absence or presence of instances of a pattern in an image where the pattern includes a representation of an object, and for determining the location of each found instance within a multi-dimensional space, a method for evaluating an extent of translation overlap of a pair of search results, the method comprising:

using a processor programmed to perform the steps of;

computing an x-overlap term;

computing a y-overlap term; and

computing a product of the x-overlap term and the y-overlap term to provide an extent of translation overlap.

2. The method of claim 1, further comprising:

using the extent of translation overlap to determine whether the pair of search results are one of neighbors and duplicates.

3. The method of claim 1, wherein the extent of translation overlap is a value between 0 and 1, inclusive.

4. The method of claim 1, wherein computing an x-overlap term includes:

dividing a difference in x-position between the two search results by half the sum of their respective widths to provide a ratio;

subtracting the ratio from 1 to provide a first argument; and

selecting the larger of the first argument and 0 as the x-overlap term.

5. The method of claim 1, wherein computing a y-overlap term includes:

dividing a difference in y-position between the two search results by half the sum of their respective heights to provide a ratio;

subtracting the ratio from 1 to provide a second argument; and

selecting the larger of the second argument and 0 as the y-overlap term.

6. The method of claim 1, wherein the pair of search results is a pair of rectangles, each having a respective height and width.

7. The method of claim 1, wherein the pair of search results is a pair of minimum enclosing rectangles.

8. The method of claim 1 further including the step of, prior to computing the x-overlap term and the y-overlap term, identifying a pair of overlapping search results that correspond to instances of a single pattern in an image.

9. The method of claim 2 further including the step of, where the pair of search results are duplicates, disregarding one of the duplicates.

10. The method of claim 1 further comprising the step of using the extent of translation overlap to determine whether the pair of search results are duplicates corresponding to the same instance of the pattern in the image.

21. The method of claim 1 wherein the representation of the object includes an appearance of the specific object.

22. The method of claim 1 wherein the representation of the object includes an ideal appearance of the specific object.

23. The method of claim 1 wherein the representation of the object includes an ideal appearance of the specific object modified by at least one non-translational degree of freedom.

28. The method of claim 1 wherein the pattern includes a representation of a specific object.

11. An apparatus for determining the absence or presence of instances of a pattern in an image where the pattern includes a representation of an object, and for determining the location of each found instance within a multi-dimensional space, the apparatus for evaluating an extent of translation overlap of a pair of search results, the apparatus comprising:

a processor programmed to perform the steps of;

computing an x-overlap term;

computing a y-overlap term; and

computing a product of the x-overlap term and the y-overlap term to provide an extent of translation overlap.

12. The apparatus of claim 11 wherein the processor is further programmed to perform the step of using the extent of translation overlap to determine whether the pair of search results are one of neighbors and duplicates.

13. The apparatus of claim 11, wherein the extent of translation overlap is a value between 0 and 1, inclusive.

14. The apparatus of claim 11, wherein the processor computes an x-overlap term by:

dividing a difference in x-position between the two search results by half the sum of their respective widths to provide a ratio;

subtracting the ratio from 1 to provide a first argument; and

selecting the larger of the first argument and 0 as the x-overlap term.

15. The apparatus of claim 11, wherein the processor computes a y-overlap term by:

dividing a difference in y-position between the two search results by half the sum of their respective heights to provide a ratio;

subtracting the ratio from 1 to provide a second argument; and

selecting the larger of the second argument and 0 as the y-overlap term.

16. The apparatus of claim 11, wherein the pair of search results is a pair of rectangles, each having a respective height and width.

17. The apparatus of claim 11, wherein the pair of search results is a pair of minimum enclosing rectangles.

18. The apparatus of claim 11 wherein the processor is further programmed to perform the step of, prior to computing the x-overlap term and the y-overlap term, identifying a pair of overlapping search results that correspond to instances of a single pattern in an image.

19. The apparatus of claim 12 wherein the processor is further programmed to perform the step of, where the pair of search results are duplicates, disregarding one of the duplicates.

20. The apparatus of claim 11 wherein the processor is further programmed to perform the step of using the extent of translation overlap to determine whether the pair of search results are duplicates corresponding to the same instance of the pattern in the image.

24. The apparatus of claim 11 wherein the representation of the object includes an appearance of the specific object.

25. The apparatus of claim 11 wherein the representation of the object includes an ideal appearance of the specific object.

26. The apparatus of claim 11 wherein the representation of the object includes an ideal appearance of the specific object modified by at least one non-translational degree of freedom.

27. The apparatus of claim 11 wherein the pattern includes a representation of a specific object.

29. In a two-dimensional pattern matching data processing product for evaluating an extent of translation overlap of a pair of possible found instances of the the pattern within a multi-dimensional space, the product tangibly embodied in a non-transitory and processor readable medium, the product comprising instructions being operable to cause a data processing apparatus to:

compute an x-overlap term;

compute a y-overlap term; and

compute a product of the x-overlap term and the y-overlap term to provide the extent of translation overlap.

30. The product of claim 29, wherein computing an x-overlap term further comprises:

dividing a difference in x-position between the two search results by half the sum of their respective widths to provide a ratio;

subtracting the ratio from 1 to provide a first argument; and

selecting the larger of the first argument and 0 as the x-overlap term.

31. The product of claim 29, wherein the pair of search results is a pair of rectangles, each having a respective height and width.

32. The product of claim 29, wherein the product further comprising instructions being operable to cause a data processing apparatus to:

compute whether the pair of search results are one of neighbors or duplicates based on the extent of translation overlap.

33. The product of claim 29, wherein the product further comprising instructions being operable to cause a data processing apparatus to:

compute whether the pair of search results are duplicates corresponding to the same instance of the pattern in the image.