0
$\begingroup$

I have this pattern in the first image which I want to find in the second image. However the two images are totally different so I just need to find the closest set of indices where these two images match. So how to go about it? Are there existing algorithms doing the same?

$\endgroup$
1
$\begingroup$

The simplest algorithm that is mathematically tractable is the matched filter. It is designed to find both the presence of (yes/no) and the location on a "target" in a "scene". However, the matched filter does not work incredibly well if there are rotations or scaling of the "target" in the scene relative to the target's image.

Assuming the "target" is in the "scene", the matched filter gives incredibly good results if the only thing corrupting the "scene" is noise. To deal with rotations, one can try "matching" rotated and scaled versions of the target image in the scene. There are many variations of the matched filter for many different signal processing applications, but in image processing, it is sometimes called "cross-correlation".

The modern approach to this "pattern recognition" problem is machine learning, using Neural Networks or Support Vector Machines. These concepts are much more difficult to learn.

MATLAB has a lot of useful tools for accomplishing these tasks, and their online documentation has a lot of examples.

A variation of the matched filter that is more robust to different types of noise existing in the same image is the Normalized Cross-Correlation (also a function in MATLAB, normxcorr2 as opposed to xcorr2, which is a classic matched filter). Theoretically, it is described here by Lewis...

http://s3.amazonaws.com/academia.edu.documents/3607630/10.1.1.21.6062.pdf?AWSAccessKeyId=AKIAIWOWYYGZ2Y53UL3A&Expires=1488301575&Signature=HpDWFoqWiZAQH7VPkr19hCbUrYQ%3D&response-content-disposition=inline%3B%20filename%3DFast_normalized_cross-correlation.pdf

But, although norm x-corr can deal with different types of noise, it is still useless under scaling and rotation, unless one repeats the function over and over for different combinations of rotations and scales. Even then, it can be difficult to find the target, unless you get very granular with the rotations and scales.

Hope this helps. I can describe more of these methods in detail if needed.

Note that although the theory of the matched filter might seem extreme, the implementation is very easy, especially if you just use xcorr2 or normxcorr2 in MATLAB.

$\endgroup$
  • $\begingroup$ Thank you for the answer. I will try match filter approach today. I was wondering if we can use the same approach that is used to detect circles/shapes in an image? $\endgroup$ – PallavBakshi Mar 1 '17 at 7:39
  • $\begingroup$ What approach are you referring to? Check out the MATLAB example for normxcorr2. Even if you are not using MATLAB, this page completely explains what normxcorr2 does and how one would use it if you defined it in another language. mathworks.com/help/images/ref/normxcorr2.html $\endgroup$ – Radu S. Visina Mar 1 '17 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.