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

Are you looking for the small image exactly or could the image be rotated/skewed/scaled/etc.? — Justin Peel, Jun 15 '10 at 22:40
Zach, have you ever solved this? I'm in the same boat right now — mikew, Feb 16 '13 at 07:52
@mikew I never solved this beyond the naive algorithm I posted below. I suspect you can solve this problem with OpenCV, but I never found any example code. I'd also still be interested to see a good solution in pure python. — Zach, Feb 16 '13 at 14:37
Since this is the top search result at the moment on google, future viewers may be interested in a [(much) faster approach using OpenCV](http://stackoverflow.com/questions/7853628/how-do-i-find-an-image-contained-within-an-image). — jedwards, May 16 '14 at 21:45

score 10 · Accepted Answer · edited Jul 20 '16 at 05:38

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

score 8 · Answer 2 · edited Apr 19 '13 at 00:16

8

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...

edited Apr 19 '13 at 00:16

stormdrain

7,915
4
37
76

answered Jun 15 '10 at 22:42

Tarantula

19,031
12
54
71

score 4 · Answer 3 · edited Jan 25 '19 at 18:05

4

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

edited Jan 25 '19 at 18:05

Eric Aya

69,473
35
181
253

answered Jan 25 '19 at 14:01

rockikz

586
1
6
17

score 3 · Answer 4 · answered Sep 26 '11 at 14:39

3

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.

answered Sep 26 '11 at 14:39

rslite

81,705
4
44
47

1

i too would really appreciate an example of how to use Boyer-Moore(-Horspool) in 2d space – mikew Feb 16 '13 at 07:49
3

actually this answer only does optimising in one dimension, on the X plane. you are speeding up the search of the horizontal search using B-M by shifting across. but then you are doing naive search in the veritcal plane, since you are never shifting down. still, its very intuitive and definitely an improvement – mikew Feb 18 '13 at 01:40

score 0 · Answer 5 · edited May 23 '17 at 12:25

0

Have a look at my answer to a similar question for a code example using OpenCV. The conversion from PIL to numpy is straight forward, e.g. just use np.array(pilimage).

edited May 23 '17 at 12:25

Community

1
1

answered Feb 13 '12 at 00:03

PiQuer

2,383
25
29

How to find an image within another image using python

5 Answers5

Linked