Algorithm Choices Give Pattern Matching an Edge

Pattern-matching operations still challenge vision systems, but matching edges rather than patterns can ease the task.

Gary Wagner, Imaging Technology, Bedford, MA -- Test & Measurement World, 9/1/2000

Developers of machine-vision systems face a significant challenge: Their systems must accurately locate reference patterns that may appear different from one product to the next. For many years, developers chose mathematical-correlation algorithms for most pattern-matching applications—a technique that still works well, as long as you can adapt your inspection system to its limitations. A better choice, though, may be geometric pattern matching, which overcomes many of the limitations of correlation.

You can think of a correlation as taking a properly scaled transparency of a signal and passing it over a graph of an unknown signal to look for a match. (See “How Does Correlation Work?”) In images, however, a computer correlates matrices of pixel values rather than continuous functions or waveforms. One matrix holds gray-scale values that represent a target pattern (the information on the transparency). The other matrix contains the gray-scale values acquired from a test image (the unknown signal). Each gray-scale value corresponds to a pixel in an acquired image, and the values represent light intensities from white to black.

Unfortunately, because gray-scale correlation algorithms use pixel intensities, they have difficulty coping with changes in the appearance of features in images. Traditional correlation software will adequately locate patterns under ideal conditions, but it cannot tolerate variations of scale, angle, focus, and contrast in acquired images. Day-to-day variations in materials and processing can produce precisely those variations.

A simple example illustrates how such changes cause problems for correlations. Imagine you want to find a gray rectangle in a series of test images. You use a known-good image of the gray rectangle—the target—as a standard for the correlations. The shape of the rectangles remain constant from one test image to the next, but the gray shading changes in unpredictable ways. To overcome changes in lighting from image to image, correlation techniques normalize images before they process them. The normalizing steps tend to minimize lighting differences and make the images more “normal.” Normalizing the images, increases the probability of a good match of two patterns. People who use pattern-matching algorithms usually refer to “normalized gray-scale correlations,” which indicates normalization is part of the correlation processing steps.

But even normalized gray-scale correlations can cause problems. When the gray-scale values in the target and test pattern aren’t equal—or within a preset tolerance—the correlation indicates a low match of the target and test patterns.

Engineers using normalized gray-scale correlation try to overcome gray-scale problems before a camera acquires an image. If images included bright reflections of the source light into the camera, for example, those reflections could saturate an area of the camera’s sensor, thus forming white spots in acquired images. These bright spots have nothing to do with the image, but they will cause problems for correlation software. An engineer could change the arrangement of light sources, add light filters, or reposition the camera in relation to the associated production equipment. Often, though, engineers have no feasible way to work around a lighting or image-acquisition problem.

Figure 1. Geometric pattern-matching tools let users set up a target for use in a machine-vision system. The software trains itself to handle any pattern, and it can create test suites that help it optimize search parameters.

Figure 2. This screen shows an image that contains the target image. The lettering above the image notes an 86% match with the target, a rotation of 269.67°, as well as information about the scale and location of the matched feature.

Detect Edges Instead
You can use geometric pattern matching—available in many software packages—to overcome most of the limits of gray-scale correlation. Rather than acquiring a gray-scale pattern to use as a target, geometric pattern matching acquires information about the edges of the pattern or feature you want to locate in an image, as shown in Figure 1. An algorithm fits the edges of the pattern to a geometric model that the software uses to detect features in the acquired image that match the target pattern.

Geometric edge detection is not new: Researchers at MIT developed the algorithm in the 1940s. But the technique saw little commercial use because it required more computer power than was available for machine-vision systems at the time. It remained unused until the limitations of correlation became increasingly apparent in semiconductor and electronic applications.

By matching only the positions of the edges of a pattern or feature in an image, the geometric pattern-matching technique overcomes problems such as changing gray-scale values. Using the geometric pattern-matching algorithm with the gray rectangle pattern described earlier yields information about the rectangle’s edges, not about the gray-scale levels in the rectangle. The rectangle could exist in test images as only an outline around a white area, or as a completely black rectangle, and the geometric pattern-matching algorithm would identify it.

Get Other Shape Data
In addition to measuring how well the edges of a target match the edges of a test feature, the geometric pattern-matching algorithm can be equipped to provide other information about the test image: rotation with respect to the target image, contrast variance, geographic score (how well the edges matched), and conformance score (how many of the edges it found). The image in Figure 2 shows some of this information superimposed on the display. This added information goes beyond the capability of the “best guess” scores provided by a correlation algorithm.

In a vision system set up to detect the presence and location of an X, for example, the system finds a mark that looks like an X but which lacks a segment. The algorithm returns a score of 75 to indicate that it detected most of the X. The geographic score indicates three edges fit the target perfectly and shows the test image lacks only one edge. These measurements further establish the “goodness” of the match between the target X and the partial X.

Geometric edge matching works particularly well in machine-vision systems used by semiconductor manufacturers. Automated equipment must precisely align wafers or die for lithography, cutting, placing, or bonding operations that demand tight tolerances. Usually, the vision system searches for fiducial marks so it can properly align components. On a wire-bonding line, for example, the system aligns a die with a frame and then extrapolates the location of the bonding pads for electrical connections.

You’ll also find edge-matching algorithms used in pick-and-place machines that must precisely locate the PCB pads on which to place components. The machines include vision systems that acquire images of the locations and then guide robotic positioners to place components properly oriented in the proper places. Again, the vision system searches for fiducial marks on a PCB so it can properly locate component-mounting positions.

In a more challenging application, a machine-vision system must examine components scattered on a shaker table. (A shaker table lightly vibrates parts to move them apart and position them for use in an automated production machine.) The production equipment has no way to know beforehand the orientation and location of individual components. But a geometric edge-detection algorithm could locate individual parts and command a robotic system to pick them up and orient them properly for placement on a PCB or assembly.

The re-emergence of geometric edge-detection algorithms doesn’t mean the imminent demise of normalized gray-scale correlation. You can still use correlation when you plan to examine similar shapes or features that won’t exhibit major variations. T&MW

FOR FURTHER READING
1. Galbiati, Louis J., Jr., Machine Vision and Digital Image Processing Fundamentals, Prentice-Hall, Englewood Cliffs, NJ,1990.

2. Geraghty, Steve, Geometric Search Techniques Break Through Traditional Gray-scale Correlation Barriers, Imaging Technology, Bedford, MA., 2000. www.imaging.com/techinfo/tutorials/00000020/tutorial.html.

3. Hanks, John, “Basic Functions Ease Entry into Machine Vision” Test & Measurement World, March 2000. pp. 69–76.

Gary Wagner is the president of Imaging Technology, a developer of machine-vision tools for the electronics and semiconductor industries. E-mail: gwagner@imaging.com.

How Does Correlation Work? Figure A. A correlation “scans” a 2-D target across an image one pixel position at a time. The maximum correlation occurs when the target square and the test pattern coincide, as shown in the position plot for the 10th “scan.” Figure B. A target may correlate well with a similar but not exact pattern. In this example, the correlation reaches a maximum—but not 100%—when the target completely overlays the black circle. To illustrate how correlation works, assume someone has trained a vision system that uses a correlation algorithm to recognize a black square—the target pattern. The system received a test pattern of a white area with a black square in the middle. The correlation algorithm “scans” the target pattern across the test pattern one pixel at a time ( Fig. A). (No actual scanning takes place. The operations use matrix math and operate on gray-scale values.) When the target scans across the white area, the algorithm produces a low “score.” The score increases as the target starts to cross the black square in the test image, and the score reaches a maximum when the squares overlap precisely. The maximum score indicates the position at which the patterns exhibit the best match. By convention, engineers settle on a specific passing score such as 70%, or 70 out of 100, as indicating a good match. But even with passing scores, you still can’t tell whether the correlation algorithm found a match, or something that resembles the learned pattern. You must use correlation scores with some caution.  Suppose a test image contains a black circle rather than a black square. The target still would correlate poorly with the white area, but it would correlate fairly well, although not perfectly, with the black circle (Fig. B). The graph of the scores shows about an 80% correlation at its maximum. But does the maximum correlation score locate a black square in the image? You can’t tell by simply examining the score. Perhaps the algorithm matched the template with a black square, or perhaps it matched it with a black circle, or with some other black shape. Gary Wagner