Pattern matching improves object location and reduces image-processing overhead

In many machine vision systems, it is necessary to locate objects or features of objects as rapidly as possible so that further image-processing algorithms can extract additional features. For example, finding the correct orientation of a part within 2-D or 3-D space can speed up robotic-based pick-and-place applications. In food and beverage applications, pattern matching techniques allow for the reading and examination of specific characters or patterns, reducing the processing power needed to extract further data from an image.

There are two main approaches to pattern matching: those based on correlation, and geometric pattern matching. While they are technically dissimilar, both approaches rely on first locating a region or regions of a template image to provide reference data. Once extracted, this data is compared with a newly captured unknown image to find matching characteristics. Establishing a correspondence between the reference template image and the newly captured image allows for the location of objects in the captured image.

Cross-correlation

Historically, cross-correlation (CC) was one of the first statistical approaches used for pattern matching. In this rather brute-force approach, a simple sum of pairwise multiplications of corresponding pixel values of the template image and regions of the same size in the captured image is computed, yielding a similarity value between the images. However, because this value is subject to changes in reflectivity or illumination in the captured image, the approach has been replaced by normalized gray-scale correlation (NGC), in which the correlation value is invariant to global brightness changes.

While traditional CC and NGC are not invariant to large degrees of rotation, translation, and scale, such methods can be improved by rotating, translating, and scaling the template image and then using the template image to perform pattern matching.

"If geometrical transformations such as rotation, size changes, tilting, and changes in illumination have been taught during the teaching phase, the correlation value between the template and the captured image increases," said Dr. Jonathan Vickers, common vision blox product manager, Stemmer Imaging. However, such methods are more computationally intensive since numerous templates need to be correlated with the captured image.

To reduce this computational overhead, a pyramid-based approach can be used. In this method, both the template and the captured image are subsampled a number of times, in effect building two pyramids, with increasingly lower resolutions as levels increase. Correlation is performed at the top level of the pyramid and used as an initial estimate for a possible correlation match at the next level.

This process is repeated at different levels and areas of successively increasing resolution of the pyramid until a suitable correlation coefficient is determined. The method is more fully explained by W. James MacLean and John K. Tsotsos in their paper "Fast Pattern Recognition Using Normalized Grey-Scale Correlation in a Pyramid Image Representation." This method can be used with both correlation-based and geometric-based pattern matching methods.

Geometric pattern matching

While standard correlation methods have limitations in terms of rotational, translational, and scale invariance, they are also limited if the part being inspected is somewhat occluded. To overcome this problem, geometric pattern matching techniques can be used to extract geometric features, such as shapes, dimensions, angles, and arcs, within a template image. Then their spatial relationships are used to find correspondences within a captured image.

This is the approach pioneered in 1999 by Bill Silver, co-founder of Cognex. The company’s geometric pattern matching technology is marketed under the brand name PatMax. Its principles have been adopted by numerous other companies including National Instruments (NI).

"There are two modes within PatFind," said Kyle Voosen, section manager of product marketing at NI, "an area model that uses standard cross-correlation to find matches in an image and an edge model that uses edges, outlines, and shapes to find matches. This is very similar to the pattern matching and geometric matching methods used by NI.

"For most applications, pattern matching is often preferred because it is more straightforward to configure. However, geometric matching is useful for applications where there is inconsistent lighting, objects that change size, occlusion, or overlapping parts and perspective distortion," he continued.

Trees and randomly-generated templated

As well as geometric pattern matching, Stemmer Imaging provides a number of other innovative pattern matching software products. While NGC and geometric pattern matching usually need one template image, the generation of a classifier based on decision trees requires several images per class. An example of this approach is the company’s software that uses a learning algorithm to extract single features or the absence of features from gray-scale images and stores them in a tree structure.

According to Vickers, grouping the single features in a tree structure enables a search that does not increase with the size of the learning set and can be used to differentiate two similar patterns. "It is fast. A small number of distinguishing features are being searched for rather than enough features to characterize a shape [geometric pattern matching] or comparing all pixels in the image [as with correlation methods]," he said. Stemmer’s pattern matching tool uses a series of training images to characterize the variation in a target and then generates thousands of randomly generated views internally to synthetically create a much larger training set.

Ron Pulicari, senior marketing manager for Cognex, said, "While many companies have adopted both NGC and geometric pattern matching methods, each one uses different algorithms to find salient features within an image, so performance characteristics can vary widely. Thus it may be difficult to determine which product is best suited for any particular application. Thus, when evaluating such software, systems integrators should carefully examine the accuracy, speed, and pattern training required with each method."

Winn Hardin is contributing editor for AIA. This article originally appeared in Vision Online. AIA is a part of the Association for Advancing Automation (A3), a CFE Media content partner. Edited by Chris Vavra, production editor, CFE Media, cvavra@cfemedia.com.

Original content can be found at www.visiononline.org.

Do you have experience and expertise with the topics mentioned in this content? You should consider contributing to our CFE Media editorial team and getting the recognition you and your company deserve. Click here to start this process.