Methods for finding and characterizing a deformed pattern in an image

• US 8,345,979 B2
• Filed: 02/01/2007
• Issued: 01/01/2013
• Est. Priority Date: 07/22/2003
• Status: Active Grant

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Inventors: Davis, Jason
• Primary Examiner(s): Patel, Kanji
• Application Number:
  US11/670,199
• Publication Number:
  US 20070183668A1
• Time in Patent Office: 2,161 Days
• Field of Search: 382/151, 382/173, 382/177, 382/181, 382/190, 382/191, 382/194, 382/195, 382/197, 382/199, 382/217, 382/218, 382/291, 382294-296, 382/321, 345/467, 381/408, 235/494
• US Class Current: 382/181
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

A method is disclosed for finding a deformed pattern in an image using a plurality of sub-patterns. By advantageously restricting sub-pattern search ranges, search speed is improved, and the incidence of spurious matches is reduced. The method also quickly decides which sub-pattern result, of several potential candidates, is most likely to be the correct match for a deformed sub-pattern. Also, a method is provided for characterizing a deformed pattern in an image by using results from feature-based search tools to create a mapping that models the deformation of the pattern. A transform, selectable by a user, is fit to the results from the search tools to create a global deformation mapping. This transformation is fit only to feature points derived from matches resulting from successful sub-pattern search, without including data from areas of the pattern that were blank, not matched, or otherwise didn'"'"'t contain information about the pattern'"'"'s distorted location.

Claims

1. A method for characterizing a deformed pattern in a single image, the method comprising:

providing a plurality of 2D features that represent the deformed pattern in the image, the 2D features include edge information;

dividing the plurality of 2D features into a plurality of sub-pluralities, wherein the sub-pluralities represent respective sub-patterns in the image, the sub-pattern having more than one 2D feature, a plurality of the sub-patterns are spatially coherent representing the deformed pattern;

locating a first sub-pattern in the image so as to provide a first sub-pattern location;

locating a second sub-pattern in the image so as to provide a second sub-pattern location; and

using the first sub-pattern location and the second sub-pattern location and a processor for determining a deformation mapping that characterizes a deformation of the deformed pattern in the image.

2. The method of claim 1, wherein the locating the sub-patterns in over at least one of translation, rotation, x-scale, and y-scale.

6. The method of claim 1, wherein the transform is a perspective transform.

7. The method of claim 1, wherein the transform is an affine transform.

8. The method of claim 1, wherein the transform is a spline transform.

9. The method of claim 1, wherein the transform is a thin-plate spline transform.

10. The method of claim 1, wherein the transform is a cylinder transform.

11. The method of claim 1, wherein the transform is fit using a least-squares-fit method.

12. The method of claim 1, wherein the transform is fit using a Total Variation method.

13. The method of claim 1, wherein the transform is fit using a Robust M-estimators method.

14. The method of claim 1, wherein the transform is fit using a Minimum L_p-Norm Estimation.

15. The method of claim 1, wherein the transform is fit using a Least Median Squares method.

3. A method for characterizing a deformed pattern in an image, the method comprising:

dividing the deformed pattern into at least a first sub-pattern and a second sub-pattern, the sub-patterns are spatially coherent and having more than one 2D feature, where the 2D features include edge information;

locating the first sub-pattern in the image so as to provide a first sub-pattern pose;

locating the second sub-pattern in the image so as to provide a second sub-pattern pose; and

using a transform to fit the first sub-pattern pose and the second sub-pattern pose using a processor for determining a deformation mapping that characterizes a deformation of the deformed pattern in the image.

4. The method of claim 3, wherein the first sub-pattern and second sub-pattern each include a region.

5. A method for characterizing a deformed pattern in an image, the method comprising:

dividing the deformed pattern into at least a first sub-pattern and a second sub-pattern, the sub-patterns are spatially coherent and having more than one 2D feature, where the 2D features include edge information;

locating the first sub-pattern in an image so as to provide a first sub-pattern pose;

locating the second sub-pattern in the image so as to provide a second sub-pattern pose;

deriving a plurality of source points from the first sub-pattern and a plurality of source points from the second sub-pattern;

generating, using a processor, a plurality of destination points from the source points and the sub-pattern poses; and

using a transform to fit the plurality of source points and the plurality of destination points using the processor so as to create a global deformation map that characterizes a deformation of the deformed pattern in the image.

16. The method of claim 5, wherein deriving aplurality of source points from the first sub-pattern and a plurality of source points from the second sub-pattern includes:

representing each sub-pattern as a region having a boundary and an interior area;

selecting at least one interior point.

17. The method of claim 5, wherein deriving a plurality of source points from the first sub-pattern and a plurality of source points from the second sub-pattern includes:

representing each sub-pattern as a region having a boundary and an interior area;

selecting a plurality of boundary points along the boundary.

18. The method of claim 17, wherein the boundary points include corners.

19. The method of claim 17, wherein the boundary points include a point midway between two vertices of the boundary.

20. The method of claim 5, wherein deriving a plurality of source points from the first sub-pattern and a plurality of source points from the second sub-pattern includes:

representing each sub-pattern as a plurality of feature points; and

sub-sampling the plurality of feature points so as to reduce the number of feature points in each sub-pattern.

21. The method of claim 5, wherein deriving a plurality of source points from the first sub-pattern and a plurality of source points from the second sub-pattern includes:

representing sub-patterns as regions, the region having a boundary and an interior area;

selecting a plurality of boundary points along the boundary.