Image Pattern Matching (if exist return coordinates)

Question

I'm currently, in C#, trying to figure out a way of finding a specific pattern in a large image, a screenshot actually. A 100% match is needed, so the problem is pretty straight forward.

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 a pattern is found, I'll need some sort of coordinate so I know where, but that's the easy part.

The only approach I've come up with so far is the obvious one. Take the first pixel of the pattern and iterate through the test image until a match is found, then test the rest of the pattern until the test fails or there is no more pattern. If the test fails, continue to the next pixel that match the first pixel of the pattern and try again. If you run through the test image without a match, then obviously there is no such pattern and that should be the result of the test.

I theory this works, but in reality things are a bit more complicated. I've yet to come u with a proper way of structuring the code and the test cases I've made have had some rather weird bugs, which is not a big surprise considering the complexity.

However, my biggest concern is time. This is just a small part of a long process and the goal is to bring the total execution time down to a couple of seconds. Imagine a 1920*1200 image, which is about the limit, where the pattern is at the end and several partial matches occur before that.

I have of course searched the net, various fora, etc., but the only material I come up with is very advanced and would be of little use even if I managed to understand it's meant for very different purposes.

I've also been considering if it would be possible to convert the pattern and test image to some sort of bitset and then just AND, SHIFT and/or MASK my way through it, but that's beyond my current capabilities.

I think I've pretty much described my problem(s) here. I'm sorry for the lag of code examples, but what I've got would be of little use to anyone and also kind of embarrassing.

I'll very much appreciate any help.

Solution 1

AForge can handle that.

Solution 2

If you can guarantee your images are going to be in the same orientation, then your simple implementation is probably going to be the quickest.

However, if you're checking against images that have been rotated, converted to grayscale, or any other kind of transformation, it'll quickly fail.

I don't have any code for you, but there are some good resources from Generation5 (AI articles), specifically from McGill University's COMP-644 (Pattern Recognition) course.

Hope you like math.