Pattern Matching With Normalised Greyscale Correlation

Welcome back to ClearView Blog. Having outlined the basics of Pattern Matching in the last post, this time we’ll be diving deeper into normalised greyscale correlation (NGC) pattern matching for machine vision. This form of pattern recognition is very different to geometric-based methods, and understanding how it works will help you when choosing an algorithm for your vision application.

Correlation Pattern Matching Explained

An NGC algorithm, in simple terms, is looking to compare pixel intensities between a full resolution image and a small resolution sample area. This sample is known as a model.

Monochrome/greyscale images must be used in NGC as greyscale values are easy to compare. Colour images would need a different correlation algorithm, and this would be unnecessarily complicated compared to greyscale.

Let’s say we want to inspect the integrated circuits (ICs) on images of circuit boards. We want to use a pattern matching algorithm here to check for the presence of ICs on each circuit board.

Pattern matching can find a pattern in a target image, even when the objects in the target image are rotated, or when the image is uniformly darker or brighter than expected.

To get started with pattern matching, we will need to select a good picture that we can use as a source image. In our example, this will be an image of a circuit board.

From this, we can define our model. This is typically the object or pattern that we want to find, in this case, the IC (highlighted in blue below).

Using the model that we have defined, we can now examine further target images to find the pattern we are looking for.

How Does Pattern Matching Work?

Pattern matching is based on the principle of template matching, which is the process of comparing the intensities of the model and the intensities of the area of the target image around a given pixel.

Intensity is the greyscale value of a pixel; this is a value between true black (0) and true white (255). Some examples can be seen in the below chart.

Examples of Greyscale Values

So, how does template matching work?

For each pixel in the target image, the algorithm will compare the intensities in an area of the target image with the intensities of the model. Pixel by pixel, it scans the entire image and finds the area with the highest similarity to the model. The algorithm then returns the location of the pixel that had the highest similarity measure.

A simplified animation of how a pattern matching algorithm scans an image to find an area that matches the model’s intensities.

Areas on the target image that have similar pixel intensities to the model

If the greyscale values around are similar to those in our target image, then we can expect a good score for our matched pattern.

What Makes Pattern Matching so Fast?

So, we know that the algorithm compares the intensities of the model with the intensities of an area around each pixel.

Unfortunately, it would be too time consuming to perform this comparison for every pixel in the target image – the higher the target image’s resolution, the more time spent searching.

In line with this logic, the pattern matching tool applies a shortcut: hierarchical search.

What is Hierarchical Search?

The process of hierarchical search is based around scanning lower-resolution versions of the target image and model. The tool then searches every pixel of the smaller target image, and finds a promising area that may contain the model.

The tool then searches a larger version of the smaller image, this time only searching the area previously returned from the previous image.

The tool repeats the process with a larger image again. Eventually, it settles on the correct match, and the position is returned, with the entire process executed more efficiently than painstakingly combing through each pixel area of the full-resolution target image.

Hierarchical search strategy

How Does a Pattern Matching Algorithm Calculate Similarity?

Pattern Matching in Matrox Imaging Library (MIL) X uses a process called match score, which is based on the normalised correlation coefficient.

Normalised (Pearson’s) Correlation Coefficient

P is the covariance of an area of the target image (I) and the Model (M), divided by the product of the individual Model and Target variations.

In this example, the normalised correlation coefficient of these two images is 0.44.

Because the covariance is normalised, the value can be from -1 to 1.

1 would be a perfect correspondence between the model and the target, and 0 would be a complete absence of correspondence.

Match score’s equation to turn P into a final score

To end up with the final Match Score, the tool takes the normalised correlation coefficient P and clips all negative values to 0. Then, P is squared and multiplied by 100, so that the match score is a value between 0-100. Below is a guide on interpreting scores, as well as examples.

Score grading

This target has a poor match score of 19.3.

This target has a great match score of 90.2.

What does ‘Normalised’ Mean in Normalised Greyscale Correlation?

Essentially, in the process of normalisation, the intensities in the target image are taken into account and aligned with the range of intensities in the model. So, although illumination should be kept as consistent as possible, normalisation will account for changes here, with the aim to mitigate the potential negative effects of lightning inconsistencies.

Normalisation involves calculating the pixel intensities and average brightness of the whole image and adjusting it according to desired range in the model.

For instance, let’s say the intensity range of our target image is 50 to 180, and the range within the model is 0 to 255. The process of normalisation would entail subtracting 50 from each of the pixel values, making the range 0 to 130. Then, each pixel intensity is multiplied by 255/130, making the range 0 to 255.

The advantage here is that you have a relative output rather than an absolute output, which is of course more likely to result in accurate matching.

Which Imaging Software is Best for Pattern Matching?

There are a few different software packages you can use to run a correlation algorithm, and the intentions of your project will dictate which is best to use.

Pattern Matching in Matrox Design Assistant (DA) X

If you are looking to create a vision system that will do pattern matching, and prefer a flowchart-based approach to developing your application, then DA X is the best programme to use.

Pattern Matching in Matrox Design Assistant X

DA X is simple to use, and contains powerful image processing tools like Pattern Matching that will perform brilliantly in a wide variety of vision applications.

Pattern Matching in Matrox Imaging Library (MIL) X

MIL X is an advanced and rugged image processing software development kit, built with flexibility and capability in mind. If you are looking to build and develop a full vision application for pattern matching and more using C++, C#, CPython, or Visual Basic, then MIL X is the best software to do this. Not only does it come with all the features of DA X, but you also gain the ability to design and implement your own GUI.

If you want to go a step further, we recommend getting the most out of MIL X with CoPilot.

Pattern Matching in MIL CoPilot

MIL CoPilot provides a unified interactive environment to experiment with MIL, allowing programmers to test one or more approaches to solving an application before writing any code. In the context of pattern matching, this means you could create a model, and test it with both Pattern Matching (NGC) and Geometric Model Finder to see which gives the best results for your application – all without writing a single line of code. This flexible, programming-free environment offers those new to MIL an easier way to try it out.

MIL CoPilot Overview

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!