Methods and apparatuses for detecting similar features within an image

• US 7,139,421 B1
• Filed: 06/28/2000
• Issued: 11/21/2006
• Est. Priority Date: 06/29/1999
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Fix, Raymond, Bachelder, Ivan
• Primary Examiner(s): Chawan, Sheela
• Application Number:
  US09/605,247
• Time in Patent Office: 2,337 Days
• Field of Search: 382/141, 382/145, 382/147, 382/149, 382/146, 382/150, 382/151, 382/152, 382/154, 382/206, 382/286, 382/291, 382/190, 382/199, 382/195, 382/203, 382/217, 250/306, 348/87, 348/94, 348/95, 348/126, 356/388, 356/395
• US Class Current: 382/141
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 10/443 by matching or filtering

Abstract

The invention provides methods and apparatuses for finding features that are similar in the image. The invention finds the similar features by searching portions of the image for features that are substantially similar to a feature prototype. First, individual features in the image are located and designated candidate features, and optionally a spatial pattern representing a majority of the candidate features is generated. Next, feature profiles are generated therefrom, and the feature prototype is constructed using at least a subset of feature profiles. An example is described wherein the object is a ball grid array, the similar features are the solder balls on the ball grid array, the feature profiles are local images of balls of a ball grid array, and the feature prototype is an average of a sub-set of the local images of the balls.

Claims

1. A method for finding features that are similar within an image comprising:

finding candidate features within the image;

generating feature profiles of the candidate features;

constructing a feature prototype using at least a subset of the feature profiles; and

searching portions of the image for features that are substantially similar to the feature prototype.

2. The method of claim 1, further comprising:

determining a spatial pattern within the image before searching portions of the image, the spatial pattern being formed by a majority of the candidate features, the spatial pattern providing pattern-position points in the image, and each of the pattern-position points being within the spatial pattern;

wherein searching further includes;

searching the portions of the image that are neighborhoods of the pattern-position points.

3. The method of claim 2, wherein determining the spatial pattern further includes:

grouping at least a portion of the candidate features into first sets of approximately collinear candidate features, each of the first sets representing a first line, the first lines being substantially parallel to one another;

grouping at least a portion of the candidate features into second sets of approximately collinear candidate features, each of the second sets representing a second line, the second lines being substantially parallel to one another and substantially orthogonal to the first lines; and

determining the spatial pattern formed by the first lines and the second lines, the pattern-position points being at intersections of the first lines and second lines.

4. The method of claim 3, wherein the spatial pattern includes an origin and an angle of, and a pitch between, at least one of the first lines and second lines.

5. The method of claim 3, wherein the spatial pattern includes an angle of and a pitch between, at least one of the first lines and second lines.

6. The method of claim 2, wherein searching further includes:

training a search model for the feature prototype; and

searching the neighborhoods of the pattern-position points for features that substantially match the search model.

7. The method of claim 1, wherein searching further includes:

comparing feature-aspects of the features to prototype-aspects of the feature prototype to verify whether at least one the feature-aspects substantially matches one of the prototype-aspects.

8. The method of claim 1, further comprising a run-time phase, where the run-time phase includes:

acquiring a run-time image having run-time features;

generating run-time feature profiles for the run-time features; and

comparing the run-time feature profiles to the feature prototype to verify whether each of the run-time features, represented by the run-time feature profiles, substantially conforms to the feature prototype.

9. The method of claim 1, wherein finding the candidate features further includes:

thresholding the image at multiple thresholds so as to produce a set of candidate features at each of the multiple thresholds; and

using as the candidate features, the candidate features of one of the sets that has more candidate features that are circular.

10. The method of claim 9, wherein the features that are similar are solder balls.

11. The method of claim 1, wherein finding the candidate features further includes:

thresholding the image at multiple thresholds so as to produce a set of candidate features at each of the multiple thresholds; and

using as the candidate features, the candidate features of one of the sets that has more candidate features that share approximately a same shape.

12. The method of claim 1, wherein finding the candidate features further includes:

examining features in the image for a feature aspect; and

designating features having the feature aspect as the candidate features.

13. The method of claim 12, wherein the feature aspect includes a characteristic of a solder ball.

14. The method of claim 12, wherein the feature aspect includes shape.

15. The method of claim 12, wherein the feature aspect includes brightness level.

16. The method of claim 12, wherein the feature aspect includes size.

17. The method of claim 1, wherein finding the candidate features further includes:

extracting the candidate features from the image.

18. The method of claim 1, wherein the features that similar are solder balls.

19. The method of claim 1, wherein generating the feature profiles further includes:

generating sub-images as the feature profiles, each of the sub-images including one of the candidate features and respective neighboring image background;

wherein constructing the feature prototype further includes;

averaging the at least a subset of the sub-images so as to produce the feature prototype.

20. The method of claim 1, wherein generating the feature profiles further includes:

generating statistics representing each of the candidate features to provide the feature profiles.

21. The method of claim 1, wherein constructing the feature prototype further includes:

constructing the feature prototype that represents a majority of the at least a subset of feature profiles.

22. The method of claim 1, further comprising:

determining a spatial pattern within the image formed by a majority of the candidate features, the spatial pattern providing pattern-position points in the image, the pattern-position points being within the spatial pattern;

wherein constructing the feature prototype further includes;

constructing the feature prototype using as the subset of feature profiles ones of the feature profiles representing candidate features positioned near the pattern-position points given by the spatial pattern.

23. The method of claim 1, wherein searching further includes:

training a search model for the feature prototype; and

searching portions of the image for features that substantially match the search model.

24. The method of claim 1, wherein searching further includes:

searching the portions of the image that are neighborhoods of the candidate features.

25. The method of claim 1, wherein searching further includes:

searching portions of the image for features that are substantially similar to the feature prototype to a predetermined extent.

26. A method for finding features of a specified-feature type within an image:

finding candidate features within the image;

generating feature profiles from the candidate features;

constructing a feature prototype of the specified-feature type using at least a subset of the feature profiles; and

comparing portions of the image to the feature prototype to verify whether any of the portions of the image contain one of the features of the specified-feature type.

27. The method of claim 26, wherein the specified-feature type is a ball of a certain size.

28. The method of claim 26, wherein the specified-feature type includes a characteristic of a solder ball.

29. The method of claim 26, wherein the specified-feature type includes a shape.

30. The method of claim 26, wherein the specified-feature type includes a characteristic of a solder ball and wherein finding the candidate features further includes:

thresholding the image at multiple thresholds so as to produce a set of candidate features at each of the multiple thresholds; and

using as the candidate features, the candidate features of one of the sets that has more candidate features that are circular.

31. The method of claim 26, further comprising:

determining a spatial pattern within the image before comparing, the spatial pattern being formed by a majority of the candidate features, the spatial pattern providing pattern-position points in the image, and each of the pattern-position points being within the spatial pattern;

wherein comparing further includes;

comparing the portions of the image that are neighborhoods of the pattern-position points.

32. The method of claim 31, wherein determining the spatial pattern further includes:

grouping at least a portion of the candidate features into first sets of approximately collinear candidate features, each of the first sets representing a first line, the first lines being substantially parallel to one another;

grouping at least a portion of the candidate features into second sets of approximately collinear candidate features, each of the second sets representing a second line, the second lines being substantially parallel to one another and substantially orthogonal to the first lines; and

determining the spatial pattern formed by the first lines and the second lines, the pattern-position points being at intersections of the first lines and second lines.

33. The method of claim 32, wherein the spatial pattern includes an origin and an angle of and a pitch between, at least one of the first lines and second lines.

34. An apparatus for finding similar features within an image:

finding means adapted to find candidate features within the image;

profile means, in cooperation with the finding means, adapted to generate feature profiles from the candidate features;

prototype means, in cooperation with the profile means, adapted to construct a feature prototype using at least a subset of the feature profiles; and

search means, in cooperation with the prototype means, adapted to search portions of the image for features that are substantially similar to the feature prototype.

35. The apparatus of claim 34, wherein the finding means further includes:

thresholding means adapted to threshold the image at multiple thresholds so as to produce a set of candidate features at each of the multiple thresholds; and

choosing means, in cooperation with the thresholding means, adapted to use as the candidate features, the candidate features of one of the sets that has more candidate features that are circular.

36. The apparatus of claim 34, wherein the finding means further includes:

thresholding means adapted to threshold the image at multiple thresholds so as to produce a set of candidate features at each of the multiple thresholds; and

choosing means, in cooperation with the thresholding means, adapted to use as the candidate features, the candidate features of one of the sets that has more candidate features that share approximately a same shape.

37. The apparatus of claim 34, wherein finding means further includes:

examining means adapted to examine features in the image for a feature aspect; and

designating means, in cooperation with the examining means, adapted to designate features having the feature aspect as the candidate features.

38. The apparatus of claim 34, further comprising:

pattern means, in cooperation with finding means and the search means, adapted to determine a spatial pattern within the image, the spatial pattern being formed by a majority of the candidate features, the spatial pattern providing pattern-position points in the image, and each of the pattern-position points being within the spatial pattern;

wherein the search means is further adapted to search the portions of the image that are neighborhoods of the pattern-position points.

39. The apparatus of claim 38, wherein the pattern means further includes:

first grouping means, in cooperation with the finding means, adapted to group at least a portion of the candidate features into first sets of approximately collinear candidate features, each of the first sets representing a first line, the first lines being substantially parallel to one another;

second grouping means, in cooperation with the finding means, adapted to group at least a portion of the candidate features into second sets of approximately collinear candidate features, each of the second sets representing a second line, the second lines being substantially parallel to one another and substantially orthogonal to the first lines;

wherein the pattern means is adapted to determine the spatial pattern formed by the first lines and the second lines, the pattern-position points being at intersections of the first lines and second lines.

40. The apparatus of claim 39, wherein the spatial pattern includes an angle of, and a pitch between, at least one of the first lines and second lines.

41. The apparatus of claim 34, wherein the prototype means is further adapted to construct the feature prototype of a specified-feature type.

42. The apparatus of claim 41, wherein the specified feature type includes a characteristic of a solder ball.

43. The apparatus of claim 41, wherein the specified-feature type includes a shape.

44. The apparatus of claim 34, wherein the search means is further adapted to search portions of the image for features that are substantially similar to the feature prototype to a predetermined extent.