Method for fast, robust, multi-dimensional pattern recognition

• US 8,295,613 B1
• Filed: 12/31/2004
• Issued: 10/23/2012
• 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, Nichani, Sanjay, Wagman, Adam
• Primary Examiner(s): Koziol, Stephen R
• Application Number:
  US11/028,255
• Time in Patent Office: 2,853 Days
• Field of Search: 382/141, 382/181, 382/190, 382/197, 382/209, 382/215, 382/266, 382/276, 348/92, 348/125, 348/197, 348/209, 348/276
• 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 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 synthetic training of a model of a pattern, the method comprising:

providing a machine vision system that includes a processor that is programmed to perform the steps of;

placing a plurality of positive probes at selected points along a boundary of the pattern;

providing at least one imaginary straight segment parallel to a segment of the boundary of the pattern;

placing a plurality of negative probes at selected points along the imaginary straight segment, each negative probe having a negative weight.

2. The method of claim 1, wherein placing a plurality of positive probes at selected points along a boundary of the pattern includes:

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 target number of probes to be placed along the segment using the total arc length of the segment, and the probe spacing value.

3. The method of claim 2, 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.

4. The method of claim 2, wherein determining a target 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.

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

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

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

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

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

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

9. The method of claim 1, wherein the pattern includes a rounded rectangle and the step of placing a plurality of positive probes at selected points along a boundary of the pattern includes:

identifying a pair of long segments;

identifying a pair of short segments;

associating a long positive weight with each positive probe along each long segment;

associating a short positive weight with each positive probe along each short segment; and

setting the value of each short positive weight as being greater than the value of each long positive weight.

10. The method of claim 1, wherein the pattern includes a rounded rectangle and the step of placing a plurality of positive probes at selected points along a boundary of the pattern includes:

identifying a pair of long segments;

identifying a pair of short segments; and

placing more probes per unit length on the on each short segment than on the long segments.

11. The method of claim 1, wherein placing a plurality of negative probes at selected points along the imaginary straight segment, each negative probe having a negative weight includes:

making the magnitude of each negative weight greater than the magnitude of each positive weights on a straight segment.

12. The method of claim 1, wherein placing a plurality of negative probes at selected points along the imaginary straight segment, each negative probe having a negative weight includes:

placing a number of negative probes along the imaginary straight segment that exceeds the number positive probes on a straight segment.

13. The method of claim 1 wherein the pattern is a rounded rectangle and the step of placing a plurality of positive probes at selected points along a boundary of the pattern includes placing the plurality of positive probes at selected points along the boundary of the rounded rectangle.

14. The method of claim 10 wherein the step of placing more probes per unit length on each short segment than on the long segments includes placing as many probes on each long segment as there are probes placed on each short segment.

15. The method of claim 1 wherein the pattern is a rounded rectangle and the step of placing a plurality of positive probes at selected points along a boundary of the pattern includes placing the plurality of positive probes at selected points along the boundary of the rounded rectangle.

16. In probe-based pattern matching, an apparatus for synthetic training of a model of a pattern, the apparatus comprising:

a machine vision processor that is programmed to perform the steps of;

placing a plurality of positive probes at selected points along a boundary of the pattern;

providing at least one imaginary straight segment parallel to a segment of the boundary of the pattern;

placing a plurality of negative probes at selected points along the imaginary straight segment, each negative probe having a negative weight.

17. The apparatus of claim 16, wherein placing a plurality of positive probes at selected points along a boundary of the pattern comprises:

determining an arc position for each boundary point along a segment of the boundary, starting 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 target number of probes to be placed along the segment using the total arc length of the segment, and the probe spacing value.

18. The apparatus of claim 16, wherein determining a probe spacing value along the segment comprises:

selecting a probe spacing value along the segment such that the probe spacing value is between a minimum and maximum value of pixels.

19. The apparatus of claim 16, wherein placing a plurality of negative probes at selected points along the imaginary straight segment, each negative probe having a negative weight comprises:

placing a number of negative probes along the imaginary straight segment that exceeds the number positive probes on a straight segment.