Find image inside of another (corners detection?)

asked 2012-09-13 00:36:11 -0600

Alex11223
31 ●1 ●4

Hello.

I want to write a function that checks if one large image (screenshot of the whole screen, for example 1920x1200) contains specified small image (from 32x32 to 300x300). And I want that it works fast, not more than 1 second (system requirements is something like Athlon II X3 3GHz + GTS250).

I've read that one of the ways to do this is to use corners detection.

How should I start? Can't find any tutorial about that.

I am using C# and EmguCv but I think C++ example also would be great.

edit retag flag offensive close merge delete

Comments

What do you mean by 'contains small image'? If it should be completely identical to some small image, this is one type of problems (a very simple one). If there some uncertainty about scale or rotation of small image, it will be harder. If the content of small image is somewhat different (for example same object but from different point of view) the problem will be even harder. And so on.

Michael Burdinov ( 2012-09-13 00:56:50 -0600 )edit

Yes, it should be completely identical.

Alex11223 ( 2012-09-13 01:24:06 -0600 )edit

add a comment

2 answers

Sort by » oldest newest most voted

answered 2012-09-13 03:18:14 -0600

Michael Burdinov
4638 ●6 ●33 ●86

Corner detection and matching is for cases that much more complicate than yours. Your problem is much easier than that. Here number of possible solutions:

Task: Assume that you want to find 100x100 image inside 1000x1000 image. You have 900x900 possible locations of small image. You need to find one location among them where both images will be identical.

Solution 1: Lets start with the most simple and naive way. For each possible location of small image inside big image start comparing pixels. If you find pair of pixels that are different, this location is unacceptable. Stop comparing and move to next possible location. This may sound as bad option because you has 900x900 candidate locations and for each one you need to make up to 100x100 comparisons. But if you are working with natural images you will make only couple of comparisons before discovering that candidate location is wrong. This is because in natural images most pixels are different from each other, so vast majority of candidates will be rejected very fast.

Solution 2: If you are working with artifical images solution 1 is not too good. For example if you are working with binary images you will match lot of pixels before discovering that candidate location should be rejected. In this case you should try to reduce amount of candidate locations. It can be done in many different ways. For example you can check if sum of pixels in candidate region is equal to sum of pixels in small image. Use integral image which implemented in OpenCV to make this comparison in constant time per candidate region.

There many other ways to solve your problem. For example you may calculate Fourier transform of both images, and find location of best correlation between them in frequency space. Not a best option, but option non the less. But don't try compicate solutions before you tried simpler ones.