Image analysis – Applications – Manufacturing or product inspection
Reexamination Certificate
2000-06-28
2003-09-02
Chang, Jon (Department: 2623)
Image analysis
Applications
Manufacturing or product inspection
C382S195000, C382S203000, C382S217000, C382S145000
Reexamination Certificate
active
06614926
ABSTRACT:
FIELD
This invention relates to machine vision, and particularly to methods and apparatuses for feature detection.
BACKGROUND
Many machine vision applications use geometrical descriptions as canonical models for inspecting or aligning an object within an image. A geometrical description is a collection of data that specifies the basic geometry of the object, that is the location of object features and dimensions of the object features relative to each other, where the object features might include the object body, number of balls in a ball grid array, and the presence or absence of balls in a ball grid array, for example. A ball grid array is a surface-mount device consisting of a more-or-less rectangular package and a grid of balls. A geometrical-based model for a ball grid array typically consists of a grid spacing in two dimensions (x and y); a nominal, a minimum, and a maximum dimension of the balls in the grid; the presence or absence of balls at each of the grid points; and an origin location.
The machine-vision system can use a geometrical model to locate an instance of an object in an image and align the object in the proper orientation (i.e., register the object). Often, one or more balls are purposely missing to indicate the correct orientation of the ball grid array. For example, a vision-based automatic surface mounter (SMD) machine typically employs a geometrical-based model of a ball grid array to place the ball grid array on a printed circuit board by aligning, in the proper orientation, the balls with pads on the printed circuit board.
The process of creating accurate geometrical models of objects, either by manually measuring the dimensions of the object, or by extracting the dimensions from manufacturing specifications, can be very tedious, especially when the objects are complicated.
In many ball grid array applications, further problems exist because it is difficult to identify the balls in images because of lighting effects. The balls often image poorly because the metal balls specularly reflect the light of the imaging system, and, thus, image less accurately. Also, the three-dimensional shape of the balls causes shadowing, which obscures the balls in the images. The three-dimensional shape also causes stronger reflections from some portions of the balls more than from other portions. Additionally, cheaper light and optic systems or light and optic systems that are focused to image an aspect of the production other than identifying balls decrease the quality of the ball images. Each of these lighting effects contributes to poor quality ball images and often frustrates identification of the balls in images.
Several known machine-vision techniques are used to identify balls. One technique uses search tools, such as normalized correlation with a synthetic circular model, where normalized correlation searching is known in the art and described at B. K. D. Horn, “Robot Vision”, MIT Press, London England, 1985, Section 6.1.2, pp. 129-132. This technique often misses balls because of lighting effects. For example,
FIG. 1
illustrates an instance of the reflectivity of a ball
100
against a background
108
. The reflected light from the ball
100
forms two distinct regions, a brighter region, region
102
, and a darker region, region
104
. The search tool is searching the image for a match to the synthetic circular model. No single region
102
,
104
, or
108
is circular because of the lighting effects. Therefore, no single region matches the model well. Typically, the correlation search tool fails to realize that region
102
and
104
are part of the same object. Thus, the search tool often misses the ball
100
or, at the very least, generates a low correlation score for the ball
100
(i.e., indicates a low probability that the feature in the image is circular).
Another known technique to find balls is blob analysis, where blob analysis is also commonly called region analysis. Blob analysis segments foreground objects from background objects by the grey values of the foreground and the background pixels in the image. As is known in the art, it is often difficult to choose a threshold grey value between the foreground and the background. Even when features image well, a good threshold grey value can segment extraneous features. Choosing the correct threshold grey value is even more difficult for poor quality ball images. Consequently, blob analysis of poor quality ball images also often fails to segment enough balls to be useful in many applications.
Many applications can use the above techniques only if the application incorporates an expensive lighting system. The expensive lighting system can make the imaged balls appear roughly circular and/or annular, and, therefore, match well enough against the expected model, thereby making blob analysis useful. However, in some applications an expensive lighting system may not be desirable.
SUMMARY
The invention provides methods and apparatuses for generating from an image a model of an object, where the object has similar features. The invention finds the similar features in the image by searching portions of the image for features that are substantially similar to a feature prototype.
The feature prototype is generated using candidate features within the image. Specifically, the candidate features are found in the image, feature profiles are generated therefrom, and the feature prototype is constructed using at least a subset of feature profiles. In one embodiment, 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.
One of the reasons the invention is robust is because the invention uses a feature prototype that is generated from the image to find the other features. Because the feature prototype is generated from the image, the feature prototype exhibits at least some of the same lighting effects as the features. Therefore, the lighting effects are less likely to frustrate the identification of the similar features. Thus, less expensive lighting systems can be employed.
In one embodiment, the subset of feature profiles creating the feature prototype are only the “best” feature profiles. The “best” feature profiles are ones representing the candidate features positioned near pattern-position points, where pattern-position points are given by a pattern that is generated as described below.
In one embodiment, a spatial pattern within the image is used to focus the search for similar features. More particularly, the search is conducted in neighborhoods of the image as directed by the pattern-position points of the spatial pattern. The spatial pattern is a pattern formed by a majority of the candidate features, and the pattern contains the pattern-position points. For instance, the pattern of an image of a ball grid array is the grid and specifics about the grid, while the pattern-positions are the intersections of the gridlines. The pattern is determined by: grouping at least a portion of the candidate balls into first sets of approximately collinear candidate balls, 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 balls into second sets of approximately collinear candidate balls, 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 pattern formed by the first lines and the second lines. In one embodiment, the pattern includes the located gridlines and a patterned or uniform pitch or pitches between the located gridlines. The pattern can also include other information such as the origin and a grid angle of the located gridlines, where the grid angle is information that is implicit from the gridline.
One of the advantages of the invention is that it is less sensitive to poor lighting. Thus, an application of the invention remains robust while using less expensive lighting systems
Bachelder Ivan
Fix Raymond
Calabresi Tracy
Chang Jon
Cognex Corporation
LandOfFree
Methods and apparatuses for generating from an image a model... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatuses for generating from an image a model..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatuses for generating from an image a model... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3107824