Methods for finding and characterizing a deformed pattern in an image

• US 20050018904A1
• Filed: 07/22/2003
• Published: 01/27/2005
• 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
• Granted Patent: US 7,190,834 B2
• Time in Patent Office: Days
• 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 finding a deformed pattern in an image, the method comprising:

providing a plurality of features that represent the deformed pattern in the image;

dividing the plurality of features into a plurality of sub-pluralities, each sub-plurality representing a sub-pattern in the image, a plurality of the sub-patterns representing the deformed pattern;

determining a distance between each pair of sub-patterns of the plurality of sub-pluralities;

selecting a first sub-pattern to locate in the image;

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

using the first sub-pattern location to select a second sub-pattern to locate in the image; and

locating the 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 to determine a location of the deformed pattern.

2. The method of claim 1, wherein providing a plurality of features that represent the deformed pattern in the image includes:

detecting features in the image.

3. The method of claim 2, wherein detecting features in the image includes:

detecting features in the image using a Sobel edge detector.

4. The method of claim 1, wherein determining a distance between each pair of sub-patterns of the plurality of sub-patterns includes:

storing each distance for later use.

5. The method of claim 1, wherein determining a distance between each pair of sub-patterns of the plurality of sub-patterns includes:

determining the minimum distance between the pair of sub-patterns.

6. The method of claim 1, wherein determining a distance between each pair of sub-patterns of the plurality of sub-patterns includes:

determining the distance between a first feature of a first sub-pattern and a second feature of a second sub-pattern.

7. The method of claim 1, wherein determining a distance between each pair of sub-patterns of the plurality of sub-patterns includes:

determining the distance between a first center of a first sub-pattern and a second center of a second sub-pattern.

8. The method of claim 1, wherein locating the first sub-pattern in the image so as to provide a first sub-pattern location includes:

using a feature-based search method for locating the first sub-pattern in the image.

9. The method of claim 1, wherein locating the second sub-pattern in the image so as to provide a second sub-pattern location includes:

computing a search area using the location of the first sub-pattern.

10. The method of claim 1, wherein locating the second sub-pattern in the image so as to provide a second sub-pattern location includes:

computing an expected angle and an expected scale of the second sub-pattern.

11. The method of claim 10, wherein the expected scale is the expected X-dimension scale and the expected Y-dimension scale.

12. The method of claim 10, further including computing an expected aspect ratio of the second sub-pattern.

13. The method of claim 10, further including:

using the expected angle and the expected scale of the second sub-pattern so as to provide an angular search range and a scale search range.

14. The method of claim 13, wherein the scale search range is an X-dimension scale search range, and a Y-dimension scale search range.

15. The method of claim 13, further including:

using a distance between the first sub-pattern and the second sub-pattern; and

a deformation rate.

16. The method of claim 1, wherein locating the second sub-pattern in the image so as to provide a second sub-pattern location includes:

computing a search area using the location of the first sub-pattern;

computing an expected angle of the second sub-pattern and an expected scale of the second sub-pattern using the angle and scale of the first sub-pattern;

using the expected angle of the second sub-pattern, the expected scale of the second sub-pattern, a distance between the first sub-pattern and the second sub-pattern, and a deformation rate so as to provide an expanded search area, an angular search range, and a scale search range; and

locating the second sub-pattern within the expanded search area, the angular search range, and the scale search range so as to provide a second sub-pattern location.

17. The method of claim 16, wherein using the expected angle of the second sub-pattern, the expected scale of the second sub-pattern, a distance between the first sub-pattern and the second sub-pattern, and a deformation rate so as to provide an expanded search area, an angular search range, and a scale search range includes:

increasing the size of the expanded search area, the angular search range, and the scale search range upon an increase in the distance between the first sub-pattern and the second sub-pattern.

18. The method of claim 16, wherein using the expected angle of the second sub-pattern, the expected scale of the second sub-pattern, a distance between the first sub-pattern and the second sub-pattern, and a deformation rate so as to provide an expanded search area, an angular search range, and a scale search range includes:

increasing, in proportion to the deformation rate, the size of the expanded search area, the angular search range, and the scale search range.

19. The method of claim 16, wherein using the expected angle of the second sub-pattern, the expected scale of the second sub-pattern, a distance between the first sub-pattern and the second sub-pattern, and a deformation rate so as to provide an expanded search area, an angular search range, and a scale search range includes:

increasing, in proportion to the deformation rate, the size of the expanded search area, the angular search range, and the scale search range upon an increase in the distance between the first sub-pattern and the second sub-pattern.

20. The method of claim 16, wherein computing an expected angle of the second sub-pattern and an expected scale of the second sub-pattern using the angle and scale of the first sub-pattern includes:

computing an expected X-dimension scale and an expected Y-dimension scale using the X-dimension scale of the first sub-pattern and the Y-dimension scale of the first sub-pattern, respectively.

21. The method of claim 16, wherein computing an expected angle of the second sub-pattern and an expected scale of the second sub-pattern using the angle and scale of the first sub-pattern includes:

computing an angular uncertainty and a scale uncertainty of the second sub-pattern using an angular uncertainty and a scale uncertainty of the first sub-pattern, respectively.

22. The method of claim 21, wherein computing an angular uncertainty and a scale uncertainty of the second sub-pattern using an angular uncertainty and a scale uncertainty of the first sub-pattern, respectively includes:

computing an X-dimension scale uncertainty and a Y-dimension scale uncertainty of the second sub-pattern using an X-dimension scale uncertainty of the first sub-pattern, and a Y-dimension scale uncertainty of the first sub-pattern, respectively.

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

providing a plurality of features that represent the deformed pattern in the image;

dividing the plurality of features into a plurality of sub-pluralities, each sub-plurality representing a sub-pattern in the image, a plurality of the sub-patterns representing the deformed pattern;

determining a distance between each pair of sub-patterns of the plurality of sub-pluralities;

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 for determining a deformation mapping that characterizes the deformed pattern in the image.

24. 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;

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 the first sub-pattern pose and the second sub-pattern pose for determining a deformation mapping that characterizes the deformed pattern in the image.

25. The method of claim 24, wherein using the first sub-pattern pose and the second sub-pattern pose for determining a deformation mapping that characterizes the deformed pattern in the image includes:

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

generating 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 plurality of destination points so as to create the global deformation map.

26. The method of claim 25, wherein the transform is a perspective transform.

27. The method of claim 25, wherein the transform is an affine transform.

28. The method of claim 25, wherein the transform is a spline transform.

29. The method of claim 25, wherein the transform is a thin-plate spline transform.

30. The method of claim 25, wherein the transform is a cylinder transform.

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

32. The method of claim 25, wherein the transform is fit using a Total Variation method.

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

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

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

36. The method of claim 24, wherein the first sub-pattern and the second sub-pattern each include a plurality of feature points.

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

38. The method of claim 37, wherein each region is converted into feature points.

39. The method of claim 38, wherein each region is converted into feature points by:

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

selecting a plurality of boundary points along the boundary.

40. The method of claim 39, wherein the boundary points include corners.

41. The method of claim 39, where the boundary points include a point midway between two vertices of the boundary.

42. The method of claim 25, 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 at least one interior point.

43. The method of claim 25, 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.

44. The method of claim 43, wherein the boundary points include corners.

45. The method of claim 43, where the boundary points include a point midway between two vertices of the boundary.

46. The method of claim 25, wherein dividing the deformed pattern into at least a first sub-pattern and a second sub-pattern includes:

dividing the deformed pattern in the image into a plurality of contiguous rectilinear regions so as to form a grid that extends over at least most of the deformed pattern, thereby providing at least a first sub-pattern and a second sub-pattern; and

deriving a plurality of source points from at least the first sub-pattern and the second sub-pattern.

47. The method of claim 25, 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.