Method for fast, robust, multi-dimensional pattern recognition

• US 8,867,847 B2
• Filed: 10/19/2012
• Issued: 10/21/2014
• Est. Priority Date: 07/13/1998
• Status: Expired due to Fees

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Inventors: Silver, William M., McGarry, E. John, Nichani, Sanjay, Wagman, Adam
• Primary Examiner(s): Carter, Aaron W
• Application Number:
  US13/656,167
• Publication Number:
  US 20130142421A1
• Time in Patent Office: 732 Days
• Field of Search: 382/141, 382/159, 382/181, 382/190, 382/197, 382/203, 382/209, 382/215, 382/266, 382/276, 348/92, 348/125
• US Class Current: 382/203
• 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

A method and system for probe-based pattern matching including an apparatus for synthetic training of a model of a pattern. The apparatus comprises a sensor for obtaining an image of the pattern and a processor for receiving the image of the pattern from the sensor and running a program. In the steps performed by the program a boundary of the pattern in the image is identified. A plurality of positive probes are placed at selected points along the boundary of the pattern and at least one straight segment of the boundary of the pattern is identified. The at least one straight segment of the boundary is extended to provide an imaginary straight segment and a plurality of negative probes are placed at selected points along the imaginary straight segment, where each negative probe has a negative weight.

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;

identifying at least one straight segment of the boundary of the pattern;

extending at least one straight segment of the boundary to provide an imaginary straight segment;

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 placing a plurality of positive probes at selected points along a boundary of the pattern includes:

identifying at least one long segments of the boundary of the pattern;

identifying at least one short segments of the boundary of the pattern;

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 placing a plurality of positive probes at selected points along a boundary of the pattern includes:

identifying at least one long segment of the boundary of the pattern;

identifying at least one short segment of the boundary of the pattern; and

placing as many probes on each long segment as there are probes placed on each short segment.

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 positive weights on the at least one straight segment that was extended to provide the imaginary 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:

making the number of negative probes along the imaginary straight segment exceed the number positive probes on the at least one straight segment that was extended to provide the imaginary straight segment.

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

a sensor for obtaining an image of the pattern;

a processor receiving the image of the pattern from the sensor and running a program to perform the steps of;

(i) identifying a boundary of the pattern in the image;

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

(iii) identifying at least one straight segment of the boundary of the pattern;

(iv) extending at least one straight segment of the boundary to provide an imaginary straight segment; and

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

14. The apparatus of claim 13 wherein the processor places a plurality of positive probes at selected points along a boundary of the pattern by performing the steps of:

identifying at least one long segment of the boundary of the pattern;

identifying at least one short segment of the boundary of the pattern;

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.

15. The apparatus of claim 13 wherein the processor places a plurality of positive probes at selected points along a boundary of the pattern by performing the steps of:

identifying at least one long segment of the boundary of the pattern;

identifying at least one short segment of the boundary of the pattern; and

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

16. The apparatus of claim 15 wherein the processor places as many probes on each long segment as there are probes placed on each short segment.