Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1998-12-18
2002-04-30
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
Feature extraction
C382S201000
Reexamination Certificate
active
06381366
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention pertains to machine vision and, more particularly, to methods and apparatus for comparing patterns and images. The invention has application, for example, in quality control and in the automated inspection of parts under assembly.
Machine vision refers to the automated analysis of images to determine characteristics of objects shown in them. It is often employed in automated manufacturing lines, where images of components are analyzed to determine placement and alignment prior to assembly. Machine vision is also used for quality assurance. For example, in the semiconductor device industry, images of chips are analyzed to insure that leads, solder paste and other components do not overrun designated boundaries.
Central to many machine vision applications is the comparison of patterns and images. To “read” a product label, for example, a machine vision system must compare each symbol in an image of the label against patterns representing all possible letters and numbers. Likewise, to determine whether a particular part is present on a conveyor belt, a machine vision system must compare each object from an image of that belt against a pattern representing the sought-after part.
A common machine vision technique for comparing a pattern and an image is golden template comparison, or GTC. This involves aligning the pattern—here, referred to as a “template”—with the image and subtracting the two. The result can be used to determine if an object represented by the template is present in the image at the alignment location. For example, in semiconductor die inspection, GTC can be used to subtract a template representing a model die from a runtime image of a die under assembly. If the latter is properly formed, the resultant image or pixel array is blank (e.g., all black or white). On the other hand, if there are defects in the die under assembly, e.g., adhesive blotches, these will appear as patterns in the resultant image or array.
As parts under inspection become smaller, manufacturing tolerances more exacting, and manufacturing lines faster, GTC and other comparison techniques are continually pressed to provide results to sub-pixel levels of accuracy. This is problematic at the boundaries of the objects being inspected, since the image data along edges is often unreliable. Though GTC remains a mainstay of machine vision, there is a need for still better image comparison tools. An object of this invention is to provide such tools.
A more particular object of this invention is to provide improved methods and systems for comparing a pattern to an image. A still more particular object of the invention is to provide such methods and systems that are accurate along boundaries of objects contained in the pattern or image.
Another object of the invention is to provide such methods and systems as facilitate quantitative and qualitative analysis of the similarities and differences between a compared pattern and image.
Still yet another object of the invention is to provide such methods and systems as are amenable to use withing existing machine vision apparatus and which operate without undue consumption of resources.
SUMMARY OF THE INVENTION
The foregoing are among the objects attained by the invention which provides boundary-based machine vision methods and systems for comparing a pattern to an image. Such a method, according to one aspect of the invention, includes the steps of finding boundary points in the image and comparing those points with boundary points in the pattern. This point-by-point comparison identifies “matches,” i.e., boundary points in the image that match boundary points in the pattern, “extras,” i.e., boundary points in the image which do not match boundary points in the pattern, and “missing,” i.e., boundary points in the pattern that do not match boundary points in the image.
Further aspects of the invention provide methods as described above in which features defined by boundary points from the image are identified, e.g., by connectivity analysis or other such image analysis techniques that identify sequences of adjacent boundary points. During such analysis, boundary points that are nearby to one another, but not quite adjacent, can be treated as adjacent and, thus, as defining a common feature. Moreover, following such analysis, the pattern and image can be aligned with another and transformed to a common orientation or canonical pose.
In related aspects, the invention provides methods as described above in which boundary points in the image and pattern are deemed to “correspond” to one another if they reside at substantially the same locations, e.g., if the distance between their respective coordinate locations is within a selected range. Such points are deemed to “match” if, in addition, they lie at substantially the same angles with respect to their respective neighbors (e.g., the difference between their respective angles is within a selected range) and if they are of substantially the same contrasts (e.g., the difference between their respective contrasts is within a selected range).
In another aspect, the invention provides methods as described above including generating quantitative and/or qualitative information about matching, extra or missing points. This includes the determining the distance between each boundary point in the image and the corresponding boundary point in the pattern. It can also include determining the differences between the directions of those points and/or the differences in their contrasts.
Still further aspects of the invention provide for feature-by-feature comparison of the pattern and image. After point-by-point matching has been performed, for example, an image boundary features identified during connectivity analysis can be marked or identified as “matching” if, for example, the majority of points making up the feature match boundary points in the pattern. Alternatively, or in addition, a boundary feature in the image can be marked as matching if an average, or other statistical measure, of location, angle and/or contrast differences between the points making up that feature and the corresponding points in the pattern fall within selected ranges.
According to related aspects of the invention, an image boundary feature can be marked or identified as “extra” if the majority of its boundary points do not match points in the pattern and/or if an average (or other statistical measure) of location, angle and/or contrast differences between the points making up that feature and corresponding points in the pattern fall outside a selected range. A feature can be likewise be identified as “missing” if the majority of points that define it in the pattern do not match points in the image boundary and/or if an average (or other statistical measure) of differences between the points making up that feature in the pattern and corresponding points in the image fall outside a selected range
In another aspect, the invention provides a method as described above including generating quantitative and/or qualitative information about the matching, extra or missing features. This can also include counting the number of matching points that make up each feature and/or, by way of further example, determining the minimum and maximum distances between the points that make up that feature and the corresponding points that make up the corresponding feature in the pattern. Quantitative information can also include, in the case of features identified as extra, their lengths, and/or their degree of linearity. In addition to, or in lieu of, such quantitative information, the information can include a qualitative characterization of the similarity of each matching point or feature (e.g., “good,” “bad,” etc.)
Still further aspects of the invention provide machine vision systems operating in accord with the methods described above.
REFERENCES:
patent: 3816722 (1974-06-01), Sakoe et al.
patent: 3936800 (1976-02-01), Ejiri et al.
patent: 3967100 (1976-06-01), Shimomura
patent: 3968475 (1976-07-01), McMahon
patent: 3978326
Garakani Arman
Taycher Leonid
Cognex Corporation
O'Dea Arthur J.
Powsner David J.
LandOfFree
Machine vision methods and system for boundary point-based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Machine vision methods and system for boundary point-based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Machine vision methods and system for boundary point-based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2849214