How to find one image inside of another?

Question

I have 2 bmp images. ImageA is a screenshot (example) ImageB is a subset of that. Say for example, an icon.

I want to find the X,Y coordinates of ImageB within ImageA (if it exists).

Any idea how I would do that?

Shadshadberry

Can you post the two BMP images here? – Boycie

Answer 1

1. So is there any warping of ImageB in ImageA?
2. How "exact" are the images, as in, pixel-for-pixel they will be the same?
3. How much computational power do you have for this?

If the answers to the first two questions are No and Yes, then you have a simple problem. It also helps to know the answer to Q3.

Update:

The basic idea's this: instead of matching a window around every pixel in imageB with every pixel in imageA and checking the correlation, let's identify points of interest (or features) in both images which will be trackable. So it looks like corners are really trackable since the area around it is kinda similar (not going into details) - hence, let's find some really strong corners in both images and search for corners which look most similar.

This reduces the problem of searching every pixel in B with A to searching for, say, 500 corners in B with a 1000 corners in A (or something like that) - much faster.

And the awesome thing is you have several such corner detectors at your disposal in OpenCV. If you don't feel using emguCV (C# varriant), then use the FAST detector to find matching corners and thus locate multiple features between your images. Once you have that, you can find the location of the top-left corner of the image.

Esteresterase

1. if by warping you mean they are of different sizes, then no. 2. yes, they will be pixel by pixel the same. i would like to account for a tiny bit of a margin of error or a specified margin of error (1%, 15%, 50%) etc.. but it is not a must. 3. assume minimum requirement is dual proc x64 2.2GHz with 2GB RAM – Shadshadberry

I know all this might seem excessive but if you could post links to the BMP files, I can show you how effective/fast it is. – Esteresterase

Easy enough .. the type of stuff I want this for is existing windows applications. So just take a screenshot of chrome dl.dropbox.com/u/2809/Chrome.bmp and the idea is to find the X/Y of the home button dl.dropbox.com/u/2809/HomeButton.bmp within that. – Shadshadberry

Are all your imageBs going to be that small? – Esteresterase

No, they can vary in size, probably from 16x16 to 800x600 – Shadshadberry

@Esteresterase - I don't mean to put any pressure on, but it's been just over 60,452 hours. What exactly did you mean by a few? :P – Stefanysteffane

um, bud. 69,284 hours. – Pulmotor

timeanddate.com/date/… – Pulmotor

Answer 2

Here's a quick sample but it is slow take around 4-6 seconds, but it does exactly what you looking for and i know this post is old but if anyone else visiting this post recently you can look this thing you need .NET AForge namespace or framework google it and install it include AForge name space in your project and that's it it finds the pictiure with another and gives out the coordinates.

System.Drawing.Bitmap sourceImage = (Bitmap)Bitmap.FromFile(@"C:\SavedBMPs\1.jpg");
            System.Drawing.Bitmap template = (Bitmap)Bitmap.FromFile(@"C:\SavedBMPs\2.jpg");
            // create template matching algorithm's instance
            // (set similarity threshold to 92.1%)

           ExhaustiveTemplateMatching tm = new ExhaustiveTemplateMatching(0.921f);
                // find all matchings with specified above similarity

                TemplateMatch[] matchings = tm.ProcessImage(sourceImage, template);
                // highlight found matchings

           BitmapData data = sourceImage.LockBits(
                new Rectangle(0, 0, sourceImage.Width, sourceImage.Height),
                ImageLockMode.ReadWrite, sourceImage.PixelFormat);
            foreach (TemplateMatch m in matchings)
            {

                    Drawing.Rectangle(data, m.Rectangle, Color.White);

                MessageBox.Show(m.Rectangle.Location.ToString());
                // do something else with matching
            }
            sourceImage.UnlockBits(data);

Ciel

Thanks this is exactly what i was looking for. Is there a way to reduce the time 6sec? it is bit too high for what i am doing – Symbology

This worked for me too. I reduced time by first shrinking both the sourceImage and template to 40% of original size. (Pick a size that works for you.) bitmap = new ResizeBicubic((int)(bitmap.Width * 0.4), (int)(bitmap.Height * 0.4)).Apply(bitmap); – Oneal

Now in year 2020 you just need to install the nuget package AForge.Imaging, solve namespaces (using AForge.Imaging; / using System.Drawing;) and the code works quickly. (-: – Herbivore

@Herbivore Hi! We're in 2023, I have a core -i7 desktop from 2020 that I don't think it is slow ;-) However, the program method takes minutes to find a 5 ko jpg mouth extracted from a 375 ko jpg (picture of one person). How does it seem to you? – Kosey

Answer 3

If image B is an exact subset of image A (meaning, the pixel values are exactly the same), this is not an image processing problem, it's just string matching in 2D. In 99% of the cases, taking a line form the middle of B and matching it against each line of A will do what you want, and super fast &mdhas; I guess C# has a function for that. After you get your matches (normally, a few of them), just check the whole of B against the appropriate part of A.

The only problem I can see with this is that in some cases you can get too many matches. E.g. if A is your desktop, B is an icon, and you are unlucky enough to pick a line in B consisting of background only. This problem is easy to solve (you have to choose lines from B a bit more carefully), but this depends on the specifics of your problem.

Gresham

how would you do the full 2d string search, instead of just one line? – Vannessavanni

I'd find all valid pixel colours from B, and the largest continuous / non-transparent rectangular area, then I could use that to skip around the large image & limit the areas I tested. – Aliform

Answer 4

Finding sub images in an image
Find an image in an Image
Check if an image exists within another image

Quixote

The first 2 are not the same question as mine and produce very different results. The last one does not work (another user reported so), and even if it did '720p took a couple of minutes'. I would be scanning 1920x1200 images and multiple minutes would not be acceptable. Even an algorithm where you took Pixel1 from ImageB, found all instances of it in ImageA, then took Pixel2 and removed all instances where it isn't 'next to (horiz/vert respective)', and repeated until the list is empty or all pixels have been scanned would be faster than a couple of minutes. – Shadshadberry

I am just looking for something better than that idea .. there has to be a decent algorithm for something like this. – Shadshadberry