Pattern-matching imaging software overcomes variances
Accuracy, repeatability, and speed are three important system-processing parameters for locating objects within images. To develop imaging systems that optimize these parameters, machine-vision software vendors are complementing long-established techniques such as normalized gray-scale correlation with geometric-based approaches.
Andrew Wilson
Editor at Large
Integrating these two approaches into imaging systems is overcoming the typical rotational variance, poor-lighting, and scaling problems encountered in many manufacturing applications and is enabling machine-vision systems to be used in a wider range of applications. In addition, because object-recognition algorithms are offered with Intel MMX-chip or coprocessor support, systems developers can use them to develop powerful PC-based machine-vision inspection systems.
Algorithm development
"In the 1940s at the Massachusetts Institute of Technology (Cambridge, MA), researchers developed a pattern-matching algorithm to simulate the human brain`s ability to learn and recognize patterns," says Fernando Serra, machine-vision group manager at Imaging Technology (Bedford, MA). "The result was a mathematical algorithm called Normalized Grayscale Correlation (NGC)," he adds. To apply this algorithm, an image is used as a learning model and is mathematically moved by rows and columns over a new image until a correlation peak is found. The higher the intensity of the detected peak, the better the match to the original pattern (see Fig. 1).
In the past, this algorithm, which is computationally intensive and requires recursive calculations, needed a supercomputer to run small models on small images. As a result, it proved inappropriate as an alignment tool for industrial machine-vision applications. Although it is not a fast tool, NGC does provide an accurate way to perform noncontact alignment in machine vision. In the late 1980s, Cognex Corp. (Natick, MA) patented a way of performing the correlation used in NGC, without the then-expensive multiples-adapting NGC as the pattern-matching algorithm, in its Search software product (US pat. #4,972,359).
"Search was superior to binary correlation and displaced it as the technology of choice for pattern-matching," says Bill Silver, chief technology officer at Cognex. "Today, NGC is the most widely used pattern-finding technology in the world," he claims. Indeed, companies such as Imaging Technology, Cognex, Euresys (Angleur, Belgium), and Mutech (Billerica, MA) all offer products based on this technology, which can be accelerated using Intel MMX-based Pentium processors.
MMX-based correlation
For example, the Mutech Locate software combines an optimized search algorithm that provides the capability to search a region of a target image for one or more instances of a taught model. Configured to run on PCs under Windows NT 4.0, Locate uses an enhanced NGC algorithm to perform the comparison between a model and a target on a pixel-by-pixel basis. Because the algorithm uses normalized correlation, the effect of contrast variations typically found in production imaging environments can be minimized.
In operation, Locate produces a score based on the degree to which there is a match between a model and a candidate image. The score varies between zero and one for a given area under consideration--the higher the score, the more similar that area is to the model to which it is being compared.
As in most tools that use NGC, pattern-matching is achieved by defining a threshold. When the score returned from the tool is above the threshold, an instance of a pattern is found. By running on a 300-MHz Pentium II MMX-based processor, the software tool can locate patterns from 32 x 32 models across 640 x 480-pixel images in less than 9 ms with a 1/20-pixel accuracy.
The Matrox Electronic Systems Ltd. (Dorval, Que., Canada) MIL 6.0 pattern-matching software also uses a search-and-locate strategy to find predefined models within target images. According to the company, a search speed for target models rotated by angles up to 360° and a translational accuracy up to 1/40 pixel is possible with a rotational accuracy of up to 1/10 of a degree. Whereas image-capture, transfer, and display functions were available as ActiveX (OCX) controls in the MIL 5.0 software, the MIL 6.0 upgrade makes image-processing and analysis functions available as ActiveX (OCX) controls with the ActiveMIL bundle.
Size and rotation variances
"NGC algorithms such as Cognex`s Search," says Silver, "cannot tolerate variances in size and rotation." For example, although Search performs well with uniform changes in illumination, it cannot handle nonuniform changes that generally occur when imaging three-dimensional metal parts. "Only when parts are well fixtured and illuminated do NGC methods perform well, because any amount of rotation or size change can result in a mismatch," says Silver. If the angle or size change is small, the object can be found, but there is significant error. If the angle or size change is large, these methods can fail altogether (see "Ten points to look for when choosing pattern-matching software," p. 51).
Imaging Technology`s Serra agrees. "NGC has a low tolerance to changes in scale, angle of rotation, and contrast variation," he says. "Its principle is based on a correlation score, which indicates the confidence of the match to the pattern it has been taught. And its accuracy degrades with any changes in contrast, lighting, scale obliteration, rotation, and blur."
Off-the-shelf packages
To overcome these limitations, companies such as Cognex, Hexavision (Sainte-Foy, Que., Canada), and Imaging Technology offer software tools based on the recognition of geometric shapes within images. By representing and analyzing objects as geometric shapes, such software packages can find complex patterns at orientations from 0° to 360° in about 50 ms.
"On metallic parts, where the illumination direction is changing, the background is unpredictable and there are highlights and shadows, then geometric-based techniques will still find the pattern to be recognized," states Silver. "And even when you rotate these patterns by any amount or change their size, the accuracy still remains as high as it was at 0°," he adds.
Cognex was first to offer such software; its PatMax interprets the geometric shapes within objects by reading squares as line segments and patterns such as blobs as a combination of two arcs. Because these descriptions remain constant no matter what angle the object is at or how much its size has changed compared to the trained image, the company`s software can locate and measure objects with a 1/40-pixel accuracy (see Fig. 2).
Recently, Imaging Technology offered a geometric-based search tool called Smart Search (see Vision Systems Design, Jan. 1999, p. 12). Using an assisted pattern-locating process called GeoSearch, Smart Search automatically adapts to variations most often encountered during the manufacturing process, while maintaining up to 1/40-subpixel accuracy and repeatability (see "Comparing geometric with normalized correlation pattern-matching techniques," p. 55).
In operation, Smart Search locates a pattern to within a pixel. Then a calculation is performed using neural-network-based techniques to compute subpixel accuracy. For OEMs, Imaging Technology has included the Smart Search tool in its MVTools, a C/C++ run-time library of vision software tools including NGC, blob, caliper, edge, line, histogram, morphology, and image- processing.
Like Cognex and Imaging Technology, Hexavision`s HexSight also uses the geometry of parts to locate them in a two-dimensional field of view. Algorithms used in the Active X-based software-development system find the contours of a part in the image and identify the part`s position and appearance. These algorithms allow the location and inspection of randomly oriented parts with rotational variances from 0° to 360° to a precision of 1/100 of a degree and 1/40 pixel.
To identify and localize any given part, the HexSight software must first perform parts modeling. In this process, a part is placed on a work surface, an image is acquired, and a vectorized contour scene is developed (see Fig. 3). Using the HexSight Interactive Model Editor, system developers can select the stable features from the vectorized scene that will enable the software to identify the part more easily and then define the features, called points of reference, that can be positioned freely on the model. When a part is identified and located, HexSight determines the locations of the points of reference.
"With the model of a part," says Tremblay, "the software can identify and locate the object, regardless of its position and orientation. To speed the preprocessing and generation of contour scenes, the company has developed an optional PCI-based accelerator board, dubbed the VSX-4100. When used in conjunction with the HexSight software, the board performs these image-processing functions ten times faster than when used with a 450-MHz Intel Pentium II computer.
Algorithms based on geometric analysis of image data complement the NGC methods and ease machine-vision system development. With part orientation, highlights, shadows, and unpredictable background problems solved, geometric methods allow developers to train systems easier with essentially no loss in performance if the magnification, orientation, or illumination varies. Despite this success, such algorithms remain only a portion of the developer`s toolbox. To develop complete systems, developers still need to seek out manufacturers that offer toolkits containing NGC, arithmetic, morphological, and statistical operators.
FIGURE 1. In the Normalized Grayscale Correlation (NGC) algorithm, an image (a) is used as a learning model and is mathematically moved by rows and columns over a new image (b) until a correlation peak is found (c). The higher the intensity of the discovered peak, the better the match to the original pattern (d). (Courtesy Imaging Technology)
FIGURE 2. By representing and analyzing objects as geometric shapes, software packages such as Cognex PatMax can find complex patterns at orientations from 0° to 360° in about 50 ms. Here, a metal automotive part has been accurately located, even though the image
differs from the image that was used to previously train the software. (Courtesy Cognex Corp.)
FIGURE 3. To identify and localize a part, HexSight software first performs parts modeling by acquiring an image and then developing a vectorized contour scene. Developers can then select the stable features from the vectorized scene that enable the software to identify the part more easily. When a part is identified and located, HexSight determines the locations of the points of reference. (Courtesy HexaVision Technologies).
Bulk reprints of all Vision Systems Design articles can be ordered from Cathleen Johnson, reprints manager, Vision Systems Design, at (603) 891-9415; FAX (603) 891-0574; or e-mail: [email protected].
Company Information
For information on additional suppliers of imaging software, see the 1999 Vision Systems Design Buyers Guide (Vision Systems Design, Feb. 1999, p. 56).
Cognex Corp.
Natick, MA 01760
(508) 650-3000
Web: www.cognex.com/
Euresys s.a.
B-4031 Angleur, Belgium
(32) 4 367 72 88
Fax: (32) 4 367 74 66
Web: www.euresys.com/
HexaVision Technologies
Sainte-Foy, Que., G1V 3V9 Canada
(418) 657-5000
Fax: (418) 657-7627
Web: www.hexavision.com/
Imaging Technology Inc.
Bedford, MA 01730
(781) 275-2700
Fax: (781) 275-9590
Web: www.imaging.com/
Matrox Electronic Systems Ltd.
Dorval, Que., H9P 2T4 Canada
(514) 822-6020
Fax: (514) 822-6273
Web: www.matrox.com/imaging
MuTech Corp.
Billerica, MA, 01862
(978) 663-2400
Fax: (978) 663-3444
Web: www.mutech.com/
