How to find an image within another image using python

Question

I'm trying to use python to determine if one (small) image is within another (large) image.

Any suggestions before I take myself completely down the wrong path?

/edit: Ok, some ideas: I'm using PIL, and I'm converting each image to the 'P' mode so I can compare each pixel as an integer. I'm trying to implement something like a Boyer–Moore string search or the Knuth–Morris–Pratt algorithm, but in 2 dimensions.

Maybe this will help: instead of searching for ABC in XXXABCXXX (answer=4) we are searching for

ABC    
DEF    
GHI    

in

XXXXX        
XABCX        
XDEFX       
XGHIX    
XXXXX  

(answer=(2,2))

Answer 1

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

Answer 2

Sikuli does it using OpenCV, see here how match_by_template works and then use the Python OpenCV bindings to do the same. Doing it without OpenCV should be hard, take a look at OpenCV documentation, search for template matching, etc...

Answer 3

pyautogui module does the job using pyautogui.locate(small_image, large_image) method which returns 4-integer tuple: (left, top, width, height).

Answer 4

I know it's a little late, but you can use Boyer-Moore to search for the first line of the small image in each of the lines of the large image. The moment you find a match you have the X and Y position and you just have to check if the remainder of the lines of the smaller image match the remainder of the lines of the larger image starting at position X and Y+1,2,3,... At the first mismatch continue with the search of the first line. I don't think you can get faster than this.