The GetDPI Photography Forum

Great to see you here. Join our insightful photographic forum today and start tapping into a huge wealth of photographic knowledge. Completing our simple registration process will allow you to gain access to exclusive content, add your own topics and posts, share your work and connect with other members through your own private inbox! And don’t forget to say hi!

fast annd quick pixel matching in big size image

A

ankitnagpal

Guest
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
 

EsbenHR

Member
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.


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.
 
Top