# Thread: fast annd quick pixel matching in big size image

1. ## fast annd quick pixel matching in big size image

Hi,

I am stuck in a pixel matching algorithm for finding sybmols in an image. I have 2 images of symbols that I intend to find in an image that has big resolution.

Instead of a pixel by pixel matching algorithm, is there a fast algorithm that gives the same result as that of pixel matching algorithm. the result should be similar to: (percentage of pixel matched) divide by (total pixels). My problem is that I wish to find certain symbols in a 1 bit image. the symbol appear with exact similarity in the target image and 95% of total pixel match with the target block in the image. but it takes hours to do iterations. the image is 10k X 10k and the symbol size is 20 X 20, so it will 10 power of 10 calculations which is too much to handle. Is there any filter/NN combination or any other algorithm that can give same results as that of pixel matching in a few minutes? The point here is that pixels are almost same in the but problem is that size is very large. I do not want complex features for noise handling or edges, fuzzy etc. just a simple algorithm to do pixel matching quickly and the result should be similar to: (percentage of pixel matched) divide by (total pixels)

Any help is appreciated.

--
Thanks,
Ankit

2. ## Re: fast annd quick pixel matching in big size image

Originally Posted by ankitnagpal
Hi,
I am stuck in a pixel matching algorithm for finding sybmols in an image. I have 2 images of symbols that I intend to find in an image that has big resolution.
Strange question for a photographic site. I think you are pretty off topic.

Originally Posted by ankitnagpal
I do not want complex features for noise handling or edges, fuzzy etc. just a simple algorithm to do pixel matching quickly and the result should be similar to: (percentage of pixel matched) divide by (total pixels)
Still an interesting question. You can use tricks similar to those used in string matching. Check out Knuth-Morris-Pratt.

1) If it takes hours, you are probably using a slow interpreted language. Use a compiled language and a recent computer. Also, this task is trivial to parallelize, so you want to do that.

2) For bonus points, do it in a GPU. I bet you could get several frames a second if you do it right.

3) If you have found a lot of matches, you do no need to test these again when you move you search window right. If you have a column where everything matches, then you know immediately know how many matches you have when you move the search window right. Simply precompute these values in a table and you got something like a factor of 10.

4) You can also use fast convolution techniques (keyword: FFT). I think your search patterns are just slightly too small to makes this method faster.