Pattern matching expands visual inspection

Jason Mulliner

Software-based vision solutions perform a variety of visual inspection tasks, including pattern matching. Pattern matching is a method of identifying features in an image that match a smaller template image. Most pattern-matching algorithms are successful, regardless of surrounding conditions such as poor lighting and template shift. While traditional pattern-matching techniques have certain time constraints and other limitations, newer techniques relying on "image understanding" are faster and have applications in precision alignment, gauging, inspection, vision-guided motion, and icon verification.

Traditional techniques
Normalized cross-correlation, pyramidal matching, and scale-invariant matching are among the more traditional pattern-matching methods used in vision applications. Of these, normalized cross-correlation is one of the most common ways to find a template—the pattern being searched for in an image. Cross-correlation is the process of moving the template or subimage around the image area and computing a value C, which corresponds to how well the template matches the image in that area. The value C is obtained by multiplying each pixel in the template by the image pixel it overlaps and then summing the results over all the pixels of the template. The maximum value of C indicates the position at which the template image best matches. Correlation values are not accurate at the borders of the image. This method can prove time-consuming, and does not meet the speed requirements of many applications.

Several new methods, such as multiprocessor technology, however, allow parallel multiplications to be performed, thus reducing overall computation time. The speed of the matching process also can be increased by reducing the image size and/or by creating a region of interest—a portion of the image where pattern matching will take place. Basic correlation is extremely sensitive to amplitude changes such as intensity in the image and template. This sensitivity can be overcome by computing the normalized correlation coefficient.

Pyramidal matching improves computation time by reducing image size and template. In this method, both image and template are subsampled to spatial resolutions one-fourth their original size. Smaller images result in faster matching. After completion of matching, only areas with a high match are considered as matching areas in the original image.

To take advantage of scale-invariant matching, the process of scaling or resizing the template is repeated and then the correlation is performed. This adds a significant amount of computation to the matching process, in addition to normalizing for rotation. Rotating the template to produce a correlation is exhaustive if the nature of the rotation is unknown. However, correlation can be carried out in the frequency domain using the Fast Fourier Transform (FFT). If the image and template are the same size, this approach is more efficient than performing correlation in the spatial domain. In the frequency domain, a correlation is obtained by multiplying the FFT of the image by the complex conjugate of the template FFT.

New Techniques
New pattern-matching methods rely on "image understanding" techniques to interpret template information. Image understanding refers to processing techniques that generate information about the features of a template. These methods include geometric modeling of images, efficient nonuniform sampling of images, and extraction of template information that is independent of both rotation and scale.

Image-understanding techniques reduce the amount of information needed to fully characterize an image or pattern, which greatly accelerates the search process. In addition, extracting useful information from a template and removing redundant and noisy information provides a more accurate search.

A new pattern-matching technique takes advantage of nonuniform sampling. Most images contain information that is redundant, so using all the information in the image to match patterns is both time-intensive and inaccurate. By sampling an image and extracting a few points that represent its overall content, the accuracy and speed of pattern matching is greatly improved.

Many new techniques for pattern matching use edge information. This method reduces an image's information until it contains only significant edge data; only this data is used to learn about the structure of the image (see Fig. 1). Edge images can be further processed to gain higher-level geometric image information, such as the number of straight lines or circles present in the image.

National Instruments has developed vision software that combines edge information and intelligent image sampling to match patterns. In instances in which an image's pattern can be rotated, a similar technique uses specially chosen template pixels with values (or relative change in values) to reflect the rotation of the pattern. The result is fast and accurate pattern matching that can accurately locate objects that vary in size (±5%) and orientation (between 0° and 360°), as well as determine when the appearance of the image is degraded or occluded.

Another aspect of pattern matching takes advantage of color capabilities. Color pattern matching can be used to quickly locate known fiducials in a color image (see Fig. 2). This technique is also useful in creating a model or template. The search tool first scans an image to match the color distribution, and then scores the match for shape—relating how closely the model matches the pattern found. Color pattern matching locates reference patterns that are fully described by the color and spatial information in the pattern, and can also simplify a monochrome problem by improving contrast or separation of the object from the background.

Binary shape matching
Binary shape matching is not considered a form of pattern matching, but can be used instead of pattern matching to increase system performance. When searching for a feature with a known shape but unknown size and orientation, and if the image can be thresholded, binary shape matching should be considered. This method is performed by extracting parameters from a template object that represents the object's shape and is invariant to the rotation and scale of the shape. Binary shape matching is not concerned with pattern data; only the shapes of the objects are considered for matching. These parameters can then be compared to a similar set of parameters extracted from other objects. This technique finds features, regardless of shape, size, and orientation, and is useful in robotic guidance applications.

Applications
Pattern matching is used by automotive, biomedical, machine control, and telecommunications industries in alignment, gauging, inspection, and color pattern- matching applications.

Alignment determines the position and orientation of a known object by locating alignment marks, or fiducials, which serve as points of reference on the object. An example of a machine-control application is searching an image that contains a printed circuit board for one or more fiducials. The machine-vision application uses the marks to align the board for chip placement from a chip-mounting device.

Gauging applications locate and measure the distance between objects. If the measurement falls within a tolerance range, the part is considered acceptable. If it falls outside the tolerance range, the component is rejected. Searching for and finding a feature is the key processing task that determines the success of gauging applications, such as inspecting the leads on a quad pack or inspecting an antilock-brake sensor. In real-time applications, search speed is critically important.

Inspection applications allow the detection of simple flaws such as missing parts or illegible printing. This type of inspection ensures that fiberoptic core or cladding has a consistent shape and is free of flaws.

Color pattern matching is used in automotive applications to inspect different colored fuses, as well as to code different types of parts to ensure that the correct parts go with the correct colors (see Fig. 3).

Pattern-matching applications span various industries, applications, and tasks. Whether using traditional methods, new methods, or a combination of both, pattern matching can enhance visual inspection application needs.

JASON MULLINER is vision product manager at National Instruments Corp., 11500 North Mopac Expressway, Austin, TX 78759-3504; e-mail: [email protected].