Gary Wagner
In the semiconductor and electronics industries, machine vision tools are used to precisely guide a variety of robotic handling, assembly, and inspection processes. The most significant challenge for machine vision in these automated applications is to maintain the ability to locate reference patterns despite changes in material appearance. Normal process variations can produce a number of unpredictable conditions, including contrast reversal and intensity gradients, angular uncertainties, blur caused by changes in depth of field, scale changes, and partial obliteration or missing features.
Gray-scale correlation
The traditional approach to machine vision has been normalized gray-scale correlationa pattern matching technique that compares the shading between an image of the subject being inspected and an image that the vision system is trained on. For many years, correlation was the algorithm of choice for most machine vision system applications. It was reliable, easy to implement, and relatively undemanding for earlier generations of computing technology.
Unfortunately, most gray-scale correlation tools have difficulty coping with changes in appearance after being trained on a particular pattern. While correlation tools are adequate for locating patterns under ideal conditions, they exhibit low tolerance to image changes in scale, angle, blur, obliteration, and contrast variation.
The traditional approach would be to work around or simply avoid manufacturing processes that create optical problems for the vision system. For example, if the inspection process produced specular reflectionbright patches where light reflects back toward the viewerusers probably would have worked around the problem by changing the lighting, adding special filters, or repositioning the machine in relation to the camera. In today's environment, these steps would put constraints on the manufacturing process that would very likely be unacceptable.
Geometric pattern matching
Today, there is another way to approach these challengesgeometric pattern matching. Rather than evaluating gray-scale patterns within an image, this technique trains on the edges. It then fits the edges to a geometric model, which it uses to detect corresponding featuresand the target objectin an incoming image (see figure).
Vision challenges, such as contrast reversal and intensity gradient, that would be daunting to a correlation-based system are no longer an issue because geometric pattern matching is not keyed to gray-scale values, only to the position of edges. The system would not train on a gray bar, for example, but on the fact that an object is a bar in the first place, then it would search for the presence of the bar in new images. Even if the bar is a different shade, the geometry remains the same. It may no longer be gray (which would result in poor correlation), but the structure (the pattern and edges) is still there.
Geometric edge detection was developed at the Massachusetts Institute of Technology (Cambridge, MA) in the 1940s. It saw little commercial use, however, because the amount of computing power required was too expensive and complex to install on a manufacturing floor. Today, with the greater power of off-the-shelf processors, geometric pattern matching has become both technically and economically feasible.
What's in a score?
Both gray-scale correlation and geometric pattern matching produce a score that ranks the closeness of the match. However, correlation is only able to provide a "best guess" that does not necessarily indicate a valid match.
Suppose, for example, that the correlation system is trained on a black square and examines a blank white wall with a black square in the middle. Correlation will be poor in the white wall and good in the middle, where the system returns a peak value of where the black square was best correlated with the new scene. But what if the object was a black circle? It would still be far better correlated with the black square than the white wall. The score won't be perfect, but will be relatively high. But what does it mean? Unfortunately, we simply don't know. Perhaps the score wasn't perfect because of some optical anomalyor maybe it wasn't the object being sought.
Geometric pattern matching would approach the problem by measuring how well the edges of the square that the system was trained on match up to the edges of the circle. It can also return a number of sub-scores that provide details about the image and its contents, such as XY location, rotation from the trained reference image, contrast variance, geographic score (how well the edges matched up), and percentage of conformance (how many edges were found). By analyzing the structure, the vision system can provide much more concrete information about whether an object is present than the "best guess" attempts provided by gray-scale correlation.
Real-world examples
Geometric edge matching is well-suited for a wide variety of applications in the semiconductor industry where there is a need to precisely align wafers or die so that activities such as lithography, cutting, placing, and/or bonding can be performed to extremely tight tolerances. One example is Pick and Place, where a robot picks up parts from a tray or waffle pack. The robot moves to where the parts are supposed to be, snaps a picture, then calculates the location with great precision in order to pick up the component and position it on a printed circuit assembly. In a more challenging scenario, components could be scattered about a shaker table, with their orientation and location not known. Edge detection tools would be able to locate the parts, then rotate them as needed. In contrast, correlation would be stymied by the rotated patterns.
Another real world example can be seen in CMP (chemical/mechanical polishing), a chip fabrication process that involves polishing a wafer to remove surface debris. As the top of the wafer is smoothed away, features become smaller and closer together, like a canyon closing in toward the bottom. Scale differences as a result of this process would create problems for correlation attempting to match gray-scale values. A vision system using edge detection, however, can still identify the structure and edges based on the geometric model on which it was trained.
Adapting to the process
The emergence of edge detection vision tools does not mean the imminent demise of normalized gray-scale correlation. There will be situations in which correlation will still remain feasibleeven optimal, such as when examining closely similar images that are not susceptible to major variations. However, with its greater accuracy under adverse conditions, geometric edge detection is becoming the pattern matching technique of choice for complex and challenging applications.
Gary Wagner is president of Imaging Technology Inc., 55 Middlesex Turnpike, Bedford, MA 01730-1421; e-mail: [email protected].