Method for fast, robust, multi-dimensional pattern recognition

• US 8,270,748 B1
• Filed: 12/24/2004
• Issued: 09/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., Nichani, Sanjay, Wagman, Adam
• Primary Examiner(s): Strege, John
• Application Number:
  US11/022,895
• Time in Patent Office: 2,825 Days
• Field of Search: 382/254, 382/276
• US Class Current: 382/254
• 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 automatically determining a best non-integer granularity in a machine vision system, the method comprising:

using a processor running a program to generate a plurality of integer values of granularity;

using the processor to compute a quality rating for each integer value of granularity;

using the processor to determine a best integer value of granularity by determining the integer value of granularity having the greatest quality rating; and

using the processor to interpolate a best non-integer value of granularity using the best integer value of granularity, and nearest neighbor integer values of granularity.

2. The method of claim 1, wherein the processor is programmed to generate a plurality of integer values of granularity by:

determining an estimate of a suitable granularity; and

generating a plurality of integer values of granularity using the estimate of a suitable granularity.

3. The method of claim 2, wherein the processor determines an estimate of a suitable granularity by using a size of a training window.

4. The method of claim 2, wherein the processor determines an estimate of a suitable granularity by using an area of a pattern in pixels.

5. The method of claim 4, wherein the processor determines an estimate of a suitable granularity by using (a^1/2/8)^1/2, where a is the area of a pattern in pixels.

6. The method of claim 2, wherein the processor generates a plurality of integer values of granularity using the estimate of a suitable granularity by:

generating integer values from 1 to a maximum value based on the estimate of a suitable granularity.

7. The method of claim 6, wherein the maximum value based on the estimate of a suitable granularity is equal to a floor function of a function of the estimate of a suitable granularity.

8. The method of claim 1, wherein the step of computing a quality rating for each integer value of granularity results in higher quality ratings to the extent that:

granularities are closer to an estimate of a suitable granularity;

boundary points are more spread out, covering more area;

chains are longer;

curvature is lesser along the chains;

gradient magnitudes are greater; and

boundary points are not near other parallel boundaries.

9. The method of claim 1, wherein the quality rating is normalized so ratings at different granularities can be effectively compared.

10. The method of claim 1, wherein the processor computes a quality rating for each integer value of granularity by computing a product of:

boundary point moment of inertia that takes into account spread of the boundary points and their weights, which in turn takes into account chain length, curvature, gradient magnitude, and parallel boundaries;

an attenuation factor that attenuates the boundary point moment of inertia based on a ratio of a value of granularity to an estimate of a suitable granularity; and

a scale factor gⁿ that compensates for the fact that all distances scale by an exponentiated value of granularity.

11. The method of claim 10, where n depends on scaling properties of number of boundary points, moment of inertia, and arc length.

12. The method of claim 1, wherein the processor interpolates a best non-integer value of granularity using the best integer value of granularity, and nearest neighbor integer values of granularity by:

performing three-point parabolic interpolation.

13. The method of claim 1, wherein the best granularity is non-integer, and is used as input to an edge detector.

14. A method for automatically determining a best granularity from among both integer and non-integer values of granularity in a machine vision system, the method comprising:

using a processor that is programmed to generate a plurality of values of granularity;

using the processor to process a training image at each of the plurality of granularities and compute a quality rating for each value of granularity;

using the processor to determine a best value of granularity by determining the value of granularity having the greatest quality rating.

15. The method of claim 14, wherein the processor generates a plurality of values of granularity by:

generating a plurality of values of granularity that include non-integer values.

16. The method of claim 14, wherein the processor generates a plurality of values of granularity by:

generating a plurality of values of granularity that include integer values.

17. The method of claim 14 wherein the processor processes the training image by extracting boundary points at each of the plurality of granularities from the training image and computes by processing the boundary points to generate a quality rating for each granularity value.

18. An apparatus for determining a non-integer granularity comprising:

a storage device; and

a data processing device programmed to generate a plurality of integer values of granularity;

compute quality ratings for the plurality of integer values of granularity;

determine the integer value of granularity having a maxima quality rating; and

interpolate a non-integer value of granularity using the maxima quality rating, the non-integer value of granularity being stored in the storage device.

19. The apparatus claim 18, wherein the data processing device is programmed to generate the plurality of integer values of granularity by:

determining an estimate of a suitable granularity using the size of one of a training window or an area of a pattern in pixels; and

generating the plurality of integer values of granularity using the estimate of a suitable granularity.

20. The apparatus of claim 18, wherein the data processing device computes quality ratings for the plurality of integer values results in higher quality ratings to the extent that:

granularities are closer to an estimate of a suitable granularity;

boundary points are more spread out, covering more area;

chains are longer;

curvature is lesser along the chains;

gradient magnitudes are greater; and

boundary points are not near other parallel boundaries.

21. The method of claim 18, wherein the data processing device interpolates a non-integer value of granularity by:

performing three-point parabolic interpolation.

22. A non-transitory computer readable medium having computer-executable instructions for performing a method comprising:

generating a plurality of values of granularity;

training an image at each of the plurality of granularities and computing a quality rating for each value of granularity; and

determining a value of granularity by determining the value of granularity having a maxima quality rating.