I want to find a know image (a sub image) in a larger image.
i have written a fairly simple code that searches for all the occurrences.
But the thing is, it's really slow.
Anybody know a faster (and i mean a lot faster) way to do this?
What i know on how to improve this is:
instead of comparing the entire arrays is just to look for the beginning of the array (the image i'm looking for) and see where i find it in the 'canvas'-array (the image i'm looking in).
from these location look for the entire image (the one i'm looking for).
But perhaps you guys (or girls) know a lot faster way.
Joris Cools wrote:Anybody know a faster (and i mean a lot faster) way to do this?
Well, I suspect there may well be an ImageComparer class out there in Googleland. However, there are also optimized 'substring' searches such as this one, or its rather simpler cousin; and I suspect you could modify either one to work with pixels rather than characters. That said, I still wouldn't expect it to be blazingly fast.
Isn't it funny how there's always time and money enough to do it WRONG?
I wouldn't create PixelGrabber objects for each pixel, because there's no need to compare all pixels of the subimage for each possible location. The common case is that the subimage is *not* found at position (x,y), so that's the case you should make fast. Start by comparing the top-left pixel; if that's not identical the search can move on. If that's identical, proceed around the perimeter and stop as soon as a pixel is found that does not match.
Tim Moores wrote:Start by comparing the top-left pixel; if that's not identical the search can move on. If that's identical, proceed around the perimeter and stop as soon as a pixel is found that does not match.
Interesting idea, and probably very well-suited to images. Boyer-Moore similarly works backwards from the far end and so is likely to find mismatches quickly (and also know how much to skip when it does); but it was designed for string searching, not for images.