Ask Your Question
3

Find image inside of another (corners detection?)

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

Alex11223 gravatar image

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

1

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 gravatar imageMichael Burdinov ( 2012-09-13 00:56:50 -0500 )edit

Yes, it should be completely identical.

Alex11223 gravatar imageAlex11223 ( 2012-09-13 01:24:06 -0500 )edit

2 answers

Sort by ยป oldest newest most voted
5

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

Michael Burdinov gravatar image

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.

edit flag offensive delete link more
2

answered 2012-09-13 04:03:16 -0500

Ben gravatar image

Have a look at template matching.

edit flag offensive delete link more
Login/Signup to Answer

Question Tools

1 follower

Stats

Asked: 2012-09-13 00:36:11 -0500

Seen: 3,459 times

Last updated: Sep 13 '12