Image pattern matching (if inverse coordinates exist)

Question

I'm currently in C # trying to find a way to search for a specific template in a large image, this is actually a screenshot. A 100% match is required, so the problem is pretty simple.

Test material: http://www.myhideout.eu/temp/pattern.png (NB: transparent pixels are irrelevant and should not be tested). http://www.myhideout.eu/temp/test.png

If the template is found, I will need some kind of coordinate, so I know where, but this is the easy part.

The only approach I came with so far is obvious. Take the first pixel of the pattern and iterate through the test image until a match is found, then check the rest of the pattern until the test is completed or there is no more pattern. If the test fails, go to the next pixel corresponding to the first pixel of the template and try again. If you skip the test image without matching, then obviously there is no such template, and this should be the result of the test.

I suppose this works, but in reality things are a little more complicated. I have not come to you with the proper structuring of the code, and in the test cases I made there were some rather strange errors, which is not a big surprise, given the complexity.

However, my biggest problem is time. This is only a small part of the lengthy process, and the goal is to bring the total execution time to a few seconds. Imagine an image of 1920 * 1200, which is the limit where the pattern is at the end, and before that there are several partial matches.

Of course, I was looking for a network, various forums, etc., but the only material that I came up with is very advanced and will be of little use, even if I could understand it for a variety of purposes.

I also consider the possibility of converting the template and test image into some kind of bitset, and then just AND, SHIFT and / or MASK my way through it, but this is beyond the scope of my current capabilities.

I think I have described my problems in some detail. I apologize for the backlog of code examples, but what I had was of little use to anyone, and also embarrassing.

I would really appreciate any help.

Answer 1

AForge can handle this .

Answer 2

If you can guarantee that your images will be in the same orientation, your simple implementation will probably be the fastest.

However, if you check inverse images converted to grayscale or any other transformations, this will end quickly.

I do not have the code for you, but there are good resources from Generation5 (AI articles), in particular from the McGill University COMP-644 course (pattern recognition) .

I hope you enjoy the math.

Answer 3

In addition to the general pattern matching study

• The description of your search strategy sounds like brute force string search algorithm; can you apply optimized string search methods (e.g. Boyer Mooore) to your problem?
• Looking at your template and your “haystack” - a search (fast?) For a gray frame, before looking for icons, should improve the speed of execution.
• If you can limit the area where you should expect a template and preprocess the templates, using OCR options / code may be an option.

Of course, nothing can defeat a library that does exactly what you want.

Answer 4

Using Aforge framework and Drawing.Imaging, worked for me! public static bool CompareBitmaps(Bitmap imageTemplate, Bitmap imagePattern) { ExhaustiveTemplateMatching tm = new ExhaustiveTemplateMatching(0.9f); // find all matchings with specified above similarity TemplateMatch[] matchings = tm.ProcessImage(imageTemplate, imagePattern); bool retorno = false; try { if (matchings[0].Similarity > 0.95f) { retorno = true; } } catch (Exception) { retorno = false; } return retorno; }