Fast algorithm for finding a small picture in big picture?

16
votes

what would be the best (fastest) way to check if a small picture is inside a big picture?

(Zoomed picture:)

enter image description here Want to Find: enter image description here

I have a solution, but it is very slow:

  • i iterate through every single pixel (x,y) in the big picture and compare the pixel (0,0) of the small picture (color value).
  • if the pixel is the same, I iterate through the small picture and compare it with the bigger one.. if it fails, it goes back to the big picture scanning loop..

this method needs like ~7 seconds to find a 50x50 pic on 1600x1200 photo.

maybe you know a better algorithm? i know a software which can do this in under a second.

4
.netalgorithmimage-processingimage
Consider it a string matching. There are several fast string matching algorithms available. See en.wikipedia.org/wiki/String_searching_algorithm. – Captain Giraffe
@Captain The reduction to string matching is nontrivial, however. I’m doing a lot of work with string matching and I don’t see an obvious, efficient reduction (I have some ideas but they are not at all obvious). – Konrad Rudolph
@Konrad I was thinking, one line of pixels per string both for needle and haystack, but you might be quite right about it being nontrivial. – Captain Giraffe
Your algorithm shouldn't be THAT slow. I suspect you're not accessing the two image buffers directly (and calling some GetPixel() function instead). If you're unsure how to do that, post your code + 2 pics, and we can help. – Tom Sirgedas
Do you get a completely new image each time you do this, or are you working with a series of frames that are mostly identical? If the latter, things like quadtrees can make this a lot more efficient. – Nick Johnson

4 Answers

6
votes

The mathematical operation convolution (which can be efficiently implemented with the Fast Fourier Transform) can be used for this.

1
votes

the other answer describes cross-correlation via convolution of images (implemented by multiplying ffts). but sometimes you want to use normalized cross-correlation - see http://scribblethink.org/Work/nvisionInterface/nip.html for a full discussion and details of a fast implementation.

1
votes

If you know the pixel values will be exact, this just becomes a special case of a string matching problem. There are lots of fast string matching algorithms, I'd start with Boyer-Moore or Knuth-Morris-Pratt.

1
votes

You're algo has a worst case of O(hA*wA*hB*wB) where hA,wA,hB,wB are height and width of the big image A and the small image B.

This algo should instead have a worst case of O((wA+wB)*hA*hB)

It's based on string matching and this is how it works:

  • Find each row of the image B in each row of image A using string matching each time.
    • Every time you have a match, store in the array matched_row a triple (rA, cA, rB) where (rA, cA) represents the starting point in the image A of the rB row of the file B.
  • Now you sort matched_row first according to cA, then to rA and then to rB.

  • Now you iterate the array and if you matched an image B of 5 row you will have something like this:

        (12, 5, 0), (13, 5, 1), (14, 5, 2), (15, 5, 3), (15, 5, 4)