How to Find One Image Inside of Another

How to find one image inside of another?

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.

How do I find an image contained within an image?

For anyone who stumbles across this in the future.

This can be done with template matching. To summarize (my understanding), template matching looks for an exact match of one image within another image.

Here's an example of how to do it within Python:

import cv2

method = cv2.TM_SQDIFF_NORMED

# Read the images from the file
small_image = cv2.imread('small_image.png')
large_image = cv2.imread('large_image.jpeg')

result = cv2.matchTemplate(small_image, large_image, method)

# We want the minimum squared difference
mn,_,mnLoc,_ = cv2.minMaxLoc(result)

# Draw the rectangle:
# Extract the coordinates of our best match
MPx,MPy = mnLoc

# Step 2: Get the size of the template. This is the same size as the match.
trows,tcols = small_image.shape[:2]

# Step 3: Draw the rectangle on large_image
cv2.rectangle(large_image, (MPx,MPy),(MPx+tcols,MPy+trows),(0,0,255),2)

# Display the original image with the rectangle around the match.
cv2.imshow('output',large_image)

# The image is only displayed if we call this
cv2.waitKey(0)

Finding an Image Inside Another Image

I'm answering my question since I've found the solution:

this worked out for me:

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.5%)

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

The only problem was it was finding all (58) boxes for said game. But changing the value 0.921f to 0.98 made it perfect, i.e. it finds only the specified number's image (template)

Edit: I actually have to enter different similarity thresholds for different pictures. I found the optimized values by trying, in the end I have a function like

float getSimilarityThreshold(int number)

How to find an image within another image using python

EDIT: Ok, here is the naive way to do this:

import Image, numpy

def subimg(img1,img2):
    img1=numpy.asarray(img1)
    img2=numpy.asarray(img2)

    #img1=numpy.array([[1,2,3],[4,5,6],[7,8,9]])
    #img2=numpy.array([[0,0,0,0,0],[0,1,2,3,0],[0,4,5,6,0],[0,7,8,9,0],[0,0,0,0,0]])

    img1y=img1.shape[0]
    img1x=img1.shape[1]

    img2y=img2.shape[0]
    img2x=img2.shape[1]

    stopy=img2y-img1y+1
    stopx=img2x-img1x+1

    for x1 in range(0,stopx):
        for y1 in range(0,stopy):
            x2=x1+img1x
            y2=y1+img1y

            pic=img2[y1:y2,x1:x2]
            test=pic==img1

            if test.all():
                return x1, y1

    return False

small=Image.open('small.tif')
big=Image.open('big.tif')

print subimg(small, big)

It works just fine, but I want to SPEED IT UP. I think the key is in the array 'test' which we might be able to use to skip some positions in the image.

Edit 2: Make sure you use images in a loss-less format to test this.

On Mac, install Pillow and from PIL import Image

How to find one image inside of another? Node.js

This is called optical-recognition. It may seem complicated (it is) but can be very simple in implementation, so don't shy away from it!

Let Image A be the image we're looking for, and Image B be the larger image with Image A in it.

Method 1

If Image A's scale in Image B hasn't been altered, and the colors are all preserved, you can place Image B on an HTML 5 canvas and iterate over the pixel data. You would load the first line of pixels from Image A and then iterate over every pixel in Image B. If a pixel was the same, you would store that pixels column in a variable and check if the next matched too. If the first row was a full match, then hop to the next row and compare those. You'd repeat that until you either got a match or hit an (or enough) pixels that didn't match. In that case, you would reset all variables and start all over again looking for a match to row 1.

Method 2

If Image A isn't perfectly identical in Image B, new complications arise and things become a lot more complicated. If only the scale changes, we can make a few tweaks to Method 1 to get something that works. Instead of grabbing any pixel and seeing if 80% or so matches, we additionally need to track the images sheer/compression.

In each row, go over pixel incrementally. For example, we'll check every tenth pixel. If we find a match for pixel 1, we then check 10 pixels away and see if that pixel exists anywhere in our row. If we find it, the distance from 0 to that pixel divided by 10 (our increment) is how many times larger the original image is.

If we found a pixel 20 slots from 0 in Image A, and it was only 10 pixels apart in Image B (remember, 10 is our increment), then our original image was 2 times larger. In other words, the new image is half the size of the original.

1) compression = target_width / original_width
2) compression = 20 / 10
3) compression = 2

This is a much more complex but robust way to detect a match. Enough matching rows mean you've got a matching image, but what about vertical stretching?

Similar logic. If you find a row that matches, start at 0 and go down by 10, then find that pixel's match in Image A.

Edit

The methods I provided are generic methods to work with looking for any image inside any other image. As you can imagine this is performance intensive. I don't know what image you're trying to detect but if there are common shapes, sometimes you can do alternative algorithms. If you have a circle, for example, you can just check that there are pixels that match outside a radius and pixels that are the same within.

The methods I presented also don't compensate for warping. Method 2 should be fine if the image is stretched but keeps a rectangular ratio. If the image has for example been warped into a circle shape, things get infinitely more complicated. For that case, the only hint I could give would be to check pixels within a radius of the original for matches.

Find image inside another in SimpleCV

Use matchTemplate in OpenCV:

diff = cv2.matchTemplate(img1, img2, cv2.TM_CCORR_NORMED)
x, y = np.unravel_index(np.argmax(diff), diff.shape)

---

Related Topics