Finding the position of an object in an image

Question

My goal is to find the location of specific images on other images, using python. Take this example:

I want to find the location of the walnut in the image. The image of the walnut is known, so I think there is no need for any kind of advanced pattern matching or machine learning to tell if something is a walnut or not.

How would I go about finding the walnut in the image? Would a strategy along these lines work:

• read images with with PIL
• transform them into Numpy arrays
• use Scipy's image filters (what filters?)

Thanks!

Answer 1

I would go with pure PIL.

1. Read in image and walnut.
2. Take any pixel of the walnut.
3. Find all pixels of the image with the same color.
4. Check to see if the surrounding pixels coincide with the surrounding pixels of the walnut (and break as soon as you find one mismatch to minimize time).

Now, if the picture uses lossy compression (like JFIF), the walnut of the image won't be exactly the same as the walnut pattern. In this case, you could define some threshold for comparison.

---

EDIT: I used the following code (by converting white to alpha, the colors of the original walnut slightly changed):

#! /usr/bin/python2.7

from PIL import Image, ImageDraw

im = Image.open ('zGjE6.png')
isize = im.size
walnut = Image.open ('walnut.png')
wsize = walnut.size
x0, y0 = wsize [0] // 2, wsize [1] // 2
pixel = walnut.getpixel ( (x0, y0) ) [:-1]

def diff (a, b):
    return sum ( (a - b) ** 2 for a, b in zip (a, b) )

best = (100000, 0, 0)
for x in range (isize [0] ):
    for y in range (isize [1] ):
        ipixel = im.getpixel ( (x, y) )
        d = diff (ipixel, pixel)
        if d < best [0]: best = (d, x, y)

draw = ImageDraw.Draw (im)
x, y = best [1:]
draw.rectangle ( (x - x0, y - y0, x + x0, y + y0), outline = 'red')
im.save ('out.png')

Basically, one random pixel of the walnut and looking for the best match. This is a first step with not too bad an output:

What you still want to do is:

• Increase the sample space (not only using one pixel, but maybe 10 or 20).

• Not only check the best match, but the best 10 matches for instance.

---

EDIT 2: Some improvements

#! /usr/bin/python2.7
import random
import sys
from PIL import Image, ImageDraw

im, pattern, samples = sys.argv [1:]
samples = int (samples)

im = Image.open (im)
walnut = Image.open (pattern)
pixels = []
while len (pixels) < samples:
    x = random.randint (0, walnut.size [0] - 1)
    y = random.randint (0, walnut.size [1] - 1)
    pixel = walnut.getpixel ( (x, y) )
    if pixel [-1] > 200:
        pixels.append ( ( (x, y), pixel [:-1] ) )

def diff (a, b):
    return sum ( (a - b) ** 2 for a, b in zip (a, b) )

best = []

for x in range (im.size [0] ):
    for y in range (im.size [1] ):
        d = 0
        for coor, pixel in pixels:
            try:
                ipixel = im.getpixel ( (x + coor [0], y + coor [1] ) )
                d += diff (ipixel, pixel)
            except IndexError:
                d += 256 ** 2 * 3
        best.append ( (d, x, y) )
        best.sort (key = lambda x: x [0] )
        best = best [:3]

draw = ImageDraw.Draw (im)
for best in best:
    x, y = best [1:]
    draw.rectangle ( (x, y, x + walnut.size [0], y + walnut.size [1] ), outline = 'red')
im.save ('out.png')

Running this with scriptname.py image.png walnut.png 5 yields for instance: