Method for fast, robust, multi-dimensional pattern recognition

• US 8,335,380 B1
• Filed: 12/31/2004
• Issued: 12/18/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,996
• Time in Patent Office: 2,909 Days
• Field of Search: 382/181, 382/209
• 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. In probe-based pattern matching, a method for placing a plurality of probes at selected points along a boundary in an image including a plurality of pixels, the method comprising:

providing a computer programmed to perform the steps of;

determining an arc position for each boundary point along a segment of the boundary, starting with zero at a first boundary point at a first end of the segment, and increasing while moving away from the first end by an amount equal to the distance between the boundary points along the segment;

determining the total arc length of the segment as being the arc position of a boundary point most distal from the first boundary point of the segment;

determining a probe spacing value along the segment; and

determining a number of probes to be placed along the segment using the total arc length of the segment, and the probe spacing value.

2. The method of claim 1, wherein determining an arc position for each boundary point along a segment of the boundary results in a distance between boundary points that is smaller than one pixel.

3. The method of claim 1, wherein determining an arc position for each boundary point along a segment of the boundary results in a distance between boundary points that is larger than one pixel.

4. The method of claim 3, wherein the segment of the boundary is a diagonal.

5. In probe-based pattern matching, a method for placing a plurality of probes at selected points along a boundary in an image including a plurality of pixels, the method comprising:

providing a computer programmed to perform the steps of;

determining an arc position for each boundary point along a segment of the boundary, starting with zero at a first boundary point at a first end of the segment, and increasing while moving away from the first end by an amount equal to the distance between the boundary points alone the segment;

determining the total arc length of the segment as being the arc position of a boundary point most distal from the first boundary point of the segment;

determining a probe spacing value along the segment; and

determining a number of probes to be placed alone the segment using the total arc length of the segment, and the probe spacing value;

wherein determining a probe spacing value along the segment includes selecting a probe spacing value along the segment such that the probe spacing value is no less than 0.5 pixels, and such that the probe spacing value is no more than 4.0 pixels.

6. The method of claim 1, wherein determining a number of probes to be placed along the segment includes:

computing a ratio of the arc length of the segment to the probe spacing value along the segment;

computing a floor function of the ratio; and

adding 1.

7. The method of claim 1, after determining a number of probes to be placed along the segment, further comprising:

using fewer than the number of probes to ensure that the spacing does not fall below a predetermined lower limit.

8. The method of claim 1, after determining a number of probes to be placed along the segment, further comprising:

using more than the number of probes to ensure that the spacing does not exceed a predetermined upper limit.

9. The method of claim 1, after determining a number of probes to be placed along the segment, further comprising:

using exactly the number of probes.

10. The method of claim 1, after determining a number of probes to be placed along the segment, further comprising:

placing a plurality of probes along the segment by centering a number of probes along the segment between the first boundary point and the boundary point most distal from the first boundary point, the separation between each pair of neighboring probes of the plurality of probes being the probe spacing value.

11. The method of claim 10, wherein a position of each probe is interpolated from positions of surrounding boundary points.

12. The method of claim 10, wherein a direction of each probe is interpolated from directions of surrounding boundary points.

13. In probe-based pattern matching, a method for placing a plurality of probes at selected points along a boundary in an image including a plurality of pixels, the method comprising:

providing a computer programmed to perform the steps of;

determining an arc position for each boundary point along a segment of the boundary, starting with zero at a first boundary point at a first end of the segment, and increasing while moving away from the first end by an amount equal to the distance between the boundary points along the segment;

determining the total arc length of the segment as being the arc position of a boundary point most distal from the first boundary point of the segment;

selecting a probe spacing value along the segment such that the probe spacing value is no less than 0.5 pixels, and such that the probe spacing value is no more than 4.0 pixels;

determining a target number of probes to be placed along the segment by computing a ratio of the arc length of the segment to the probe spacing value along the segment, computing a floor function of the ratio, and then adding 1; and

placing a plurality of probes along the segment by centering a number of probes along the segment between the first boundary point and the boundary point most distal from the first boundary point, the separation between each pair of neighboring probes of the plurality of probes being the probe spacing value.

14. The method of claim 13, wherein determining an arc position for each boundary point along a segment of the boundary results in a distance between boundary points that is smaller than one pixel.

15. The method of claim 13, wherein determining an arc position for each boundary point along a segment of the boundary results in a distance between boundary points that is larger than one pixel.

16. The method of claim 15, wherein the segment of the boundary is a diagonal.

17. The method of claim 13, after determining a number of probes to be placed along the segment, further comprising:

using fewer than the number of probes to ensure that the spacing does not fall below a predetermined lower limit.

18. The method of claim 13, after determining a number of probes to be placed along the segment, further comprising:

using more than the number of probes to ensure that the spacing does not exceed a predetermined upper limit.

19. The method of claim 13, after determining a number of probes to be placed along the segment, further comprising:

using exactly the number of probes.

20. The method of claim 13, wherein a position of each probe is interpolated from positions of surrounding boundary points.

21. The method of claim 13, wherein a direction of each probe is interpolated from directions of surrounding boundary points.

22. An computerized apparatus for placing probes at selected points along a two-dimensional boundary in an image, the apparatus comprising:

an arc position module for calculating an arc position of each boundary point on a segment of the boundary by computing the arc position of each boundary point as the distance along the boundary from an initial boundary point position of the segment, the initial boundary point position having an initial boundary point position value, where any of the boundary point positions along the boundary may differ from a pixel center;

an arc length module for computing the total arc length of the segment as being the arc position of a boundary point most distal from the initial boundary point position of the segment minus the initial boundary point position value; and

a probe module for computing a probe spacing value along the segment and a number of probes to be placed along the segment using the total arc length of the segment and the probe spacing value.

23. The apparatus of claim 22, wherein calculating an arc position of boundary points in a segment of the boundary results in at least one distance between boundary points that is smaller than one pixel.

24. The apparatus of claim 22, after computing a number of probes to be placed along the segment, further comprising:

selecting a different number of probes than the number of probes to ensure that the spacing does not fall outside predetermined limits.

25. The apparatus of claim 22, wherein a position of each probe is interpolated from positions of surrounding boundary points.