Methods and apparatuses for generating from an image a model of an object

• US 6,614,926 B1
• Filed: 06/28/2000
• Issued: 09/02/2003
• Est. Priority Date: 06/29/1999
• Status: Active Grant

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Fix, Raymond, Bachelder, Ivan
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US09/605,441
• Time in Patent Office: 1,161 Days
• Field of Search: 382/145, 382/146, 382/149, 382/150, 382/151, 382/190, 382/195, 382/203, 382/209, 382/217, 382/218, 348/87, 348/126
• US Class Current: 382/150
• CPC Class Codes: G06T 7/0004 Industrial image inspection

Abstract

The invention provides methods and apparatuses for generating from an image of an object a model of the object, when the object contains similar features. First, the invention finds the similar features. The similar features are found by searching portions of the image for features that are substantially similar to a feature prototype. More particularly, 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. Thereafter, the model is generated using the similar features and, optionally, the spatial pattern. An example is described wherein the model is of 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 generating a model of an object from an image of the object, the method 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;

searching portions of the image for features that are substantially similar to the feature prototype, the features that are substantially similar being designated verified features; and

generating the model of the object using the verified features.

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 2, wherein generating the model of the object further includes:

generating the model of the object using the spatial pattern and the verified features.

8. 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.

9. 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.

10. 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.

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

12. 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 the same shape.

13. 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.

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

15. The method of claim 13, wherein the feature aspect includes shape.

16. The method of claim 13, wherein the feature aspect includes brightness level.

17. The method of claim 13, wherein the feature aspect includes size.

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

extracting the candidate features from the image.

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

20. 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.

21. 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.

22. 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.

23. 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.

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

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

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

26. The method of claim 1, wherein the model is a geometric model of a ball grid array device.

27. 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.

28. The method of claim 27, wherein the predetermined extent is application specific.

29. A method for generating a model of an object from an image of the object, the method comprising:

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;

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, the features that are of the specified-feature type being designated verified features; and

generating the model of the object using the verified features.

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

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

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

33. The method of claim 29, 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.

34. The method of claim 29, 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.

35. The method of claim 34, 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.

36. The method of claim 35, 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.

37. The method of claim 35, wherein generating the model further comprises:

generating the model of the object using the spatial pattern and the verified features.

38. An apparatus for generating a model of an object from an image of the object, the apparatus comprising:

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;

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, the features that are substantially similar being designated verified features; and

model means, in cooperation with the search means, adapted to generate the model of the object using the verified features.

39. The apparatus of claim 38, 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.

40. The apparatus of claim 38, 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.

41. The apparatus of claim 38, 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.

42. The apparatus of claim 38, 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.

43. The apparatus of claim 42, 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; and

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.

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

45. The apparatus of claim 43, wherein the model means is further adapted to generate the model of the object using the spatial pattern and the verified features.

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

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

48. The apparatus of claim 47, wherein the specified-feature type includes a shape.

49. The apparatus of claim 38, 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.