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.

.netalgorithmimage-processingimage

MilMike

Reputation: 12851

Fast algorithm for finding a small picture in big picture?

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:

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.

Upvotes: 17

Answers (4)

Simone

Reputation: 2311

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)
```

Upvotes: 1

Mark Ransom

Reputation: 308530

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.

Upvotes: 1

andrew cooke

Reputation: 46892

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.

Upvotes: 1

Aasmund Eldhuset

Reputation: 38010

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

Upvotes: 6

Fast algorithm for finding a small picture in big picture?

Answers (4)

Related Questions