Geometric modeling challenges normalized correlation to pattern matching
In 1997, the Automated Imaging Association estimated the machine-vision market at $1.3 billion. "Of this," says Gary Wagner, president of Imaging Technology Inc. (ITI; Bedford, MA), more than half comes from the semiconductor inspection industry." Robotic wafer handlers, reticle inspection systems, wire bonding, and IC assembly systems all incorporate vision to automate the inspection and test and place semiconductors as they are manufactured or placed on PCBs.
"In these applications," says Wagner, "more than 50% use search algorithms to locate known objects within images before edge detection and connectivity algorithms measure their parameters." To perform these searches, OEM vision-system vendors have, in the past, relied on normalized correlation, a method that provides positional information to subpixel accuracy. It is independent of linear brightness changes in the image and achieves an absolute indication of pattern similarity under different lighting conditions. For these reasons, it has been used in a number of semiconductor-inspection systems and other applications such as dollar-bill inspection (see Vision Systems Design, Nov. 1998, p. 25).
"In applications in which images may be rotated, scaled, blurred, or occluded," says Marc Landman, president of Vision Machines (North Reading, MA), a systems integrator of both ITI and Cognex (Natick, MA) products, "any pixel grid-matching method--such as normalized correlation--will break down." For this reason, both Cognex and ITI are incorporating more novel pattern-matching algorithms into their software packages.
In December 1997, Cognex introduced its PatMax machine-vision software, a proprietary and patent-pending technology developed by Cognex`s cofounder William Silver. "Current object-location technology based on standard approaches such as normalized correlation just can`t keep pace with the demands of today`s manufacturing processes," says Ed DeCosta, Cognex senior marketing manager. "With PatMax, developers can locate and align parts under widely varying conditions," he says.
A key PatMax feature is its ability to locate parts at any angle or scale. This capability eliminates the need for systems integrators to install costly material-handling equipment to mechanically fixture parts. And, with PatMax, the vision system is not confused by nonuniform changes in lighting or background. Although the technology behind PatMax is proprietary, it uses geometric image analysis to represent the image as a vector model.
In the design of its latest search algorithm, SmART Search for the Sherlock image-processing package, ITI uses the same approach. "While correlation methods were developed because they were less computationally intensive than geometric-based approaches, they are less robust," says Fernando Serra, ITI vision group manager. With the advent of fast host CPUs, geometric-based approaches are gaining favor because of their increased robustness.
In the development of the SmART search tools, Serra uses the geometric relationship of, and within, images to describe them. Performing an edge-detection operation on the image, for example, means that the length and angle between edges (now image vectors) can be computed. Once determined, the image is then represented as a series of angles and vectors that are naturally invariant to rotation, scaling, and occlusion of the image. To train the SmART search tools, an area within an image is digitized, translated, and rotated, resulting in a set of test suites of templates and images that are then used to locate similar objects in other images.
Geometric modeling challenges normalized correlation to pattern matching
