Introduction to Pattern Matching

Introduction to Pattern Matching

 Welcome back to ClearView Blog. In this article we’ll be defining pattern matching for machine vision, and exploring the types, uses, and challenges commonly associated with one of the most widely used image processing functions around.

What is Pattern Matching?

Pattern matching is a way to automate the process of finding a pattern or part in an image using machine vision techniques.

Pattern Matching locates a part or an object in a field of view and verifies its presence or absence. It can help guide robots, it can prove useful for finding patterns in medicine and can be an important tool in scientific applications– and it’s all thanks to trusted machine vision algorithms.

Types of Pattern Matching

There are two traditional types of pattern matching: Geometric & Correlation (also known as Normalised Greyscale Correlation).

Geometric Pattern Matching

Geometric is an advanced type of pattern matching as it is an edge-based algorithm. This means it will be looking for the edges of each object that has been defined. Geometric pattern matching is advantageous because we can locate these parts even when they are scaled, rotated or displaced.

With geometric algorithms, a 50% increase or decrease in size will still result in pattern detection, and rotated parts would not be an issue for the algorithm either.

Furthermore, as this is looking for edges, it can handle changes in lighting, and the parts can still be detected even in the presence of occlusions and overlaps.

The mechanical T and L shapes in the images above could even be picked and placed by a robot using an edge-based algorithm.

In the below video, we demonstrate how this can be done with Matrox’s Iris smart camera and the Geometric Model Finder algorithm within Matrox Design Assistant X.

Correlation Pattern Matching

Correlation is looking more simplistically at pixel values. In this case we will be looking at normalised greyscale correlation (NGC).

In the above example, greyscale correlation is being used within Matrox's MIL Pattern Matching functionality to detect the presence of plus symbols [+] on these semi-conductors. MIL is used here as it utilises a hierarchical search strategy to locate a pattern, including multiple occurrences, which are translated and slightly rotated, with sub-pixel accuracy.

Greyscale correlation is an extremely fast and efficient algorithm, but it can be temperamental. Rather than finding edges, it is trying to find the pattern by matching up the greyscale values of individual pixels in an image.

It’s really important with correlation to maintain good, consistent illumination where you are performing imaging tasks. Changes in illumination will alter these greyscale values, which usually results in the part not being detected.

Examples of Greyscale Values

Rotations and translated matches will work, but it cannot deal with scaling, displacement, and overlapping. What it does excel at, however, is speed, and therefore will contribute greatly to the overall efficiency of a machine vision system.

This means that generally speaking, if you can get away with greyscale correlation for your pattern matching task, then by all means use it. It would save you time as well as money spent on potentially expensive machine vision software licenses and/or computational power.

However, if your application has those restrictions, or if you have limited control over the lighting in your imaging environment, then moving up to geometric would be necessary.

This would mean trading speed for reliability, however if you find you’re spending lots of time and mental energy on trying to get a correlation algorithm working, then in the long run, the expenses will be worth it. In the world of machine vision, time wasted is money wasted, so being sure of the results is never a bad thing.

Pattern Matching Applications

There’s really no end to the list of use-cases when it comes to these algorithms. As we’ve shown, pick-and-place applications can work really well using pattern matching. This would also apply to sorting, which could be done on a factory line as suggested below.

Pattern matching is commonly used in automotive and electronical manufacturing because it can quickly verify the presence of key parts in varying stages of construction.

However, there are certainly applications in medical fields as well, such as using it to quickly verify whether a patient in a hospital has an abnormal growth that may need removing. All in all, these algorithms are powerful tools in the world of today - and in the next blog, we'll be diving deeper into how they work.

Need Machine Vision Help? Give us a shout!

Thanks for reading this machine vision blog – but your time with us doesn’t have to end here!

Want to find out more about machine vision algorithms? Could you use a hand with your vision system or with automating industrial processes? Look no further – get in touch with us.

Also, be sure to check out our great range of machine vision cameras and machine vision software over in our products section!

Here at ClearView, we have a broad range of knowledge and machine vision expertise to help you decide on the right solution for your project.

We offer friendly expertise and a huge range of industry-standard quality machine vision components for printing and packaging, robotics, industrial automation, medicine, life sciences, and the automotive industry, just to name a few.

Our experts are happy to help no matter what your question or problem may be. Feel free to get in touch with us and one of our machine vision experts will be ready to help you get going with your project!