Fast algorithm for finding a small picture in big picture?

Question

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

(Zoomed picture:)

Want to Find:

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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)