3

So with the help of a stack-overflow member, I have the following code:

data = "needle's (which is a png image) base64 code goes here"
decoded = data.decode('base64')
f = cStringIO.StringIO(decoded)
image = Image.open(f)
needle = image.load()

while True:
    screenshot = ImageGrab.grab()
    haystack = screenshot.load()
    if detectImage(haystack, needle):
        break
    else:
        time.sleep(5)

I've written the following code to check if the needle is in the haystack:

def detectImage(haystack, needle):
    counter = 0
    for hayrow in haystack:
        for haypix in hayrow:
            for needlerow in needle:
                for needlepix in needlerow:
                    if haypix == needlepix:
                        counter += 1

    if counter == 980: #the needle has 980 pixels
        return True
    else:
        return False

The issue is that I get this error for line 3: 'PixelAccess' object is not iterable

It was suggested to me that it would be easier to copy both needle and haystack into a numpy/scipy array. And then I can just use a function that checks to see if the 2D array needle is inside the 2D array haystack.

I need help with:

1) converting those arrays to numpy arrays.

2) a function that checks to see if the 2D array needle is inside the 2D array haystack. My function doesn't work.

These are the images:
Needle:
needle
Haystack:
haystack haystack

Improve this question
4
  • Perhaps this line: for x1 in haystack[0]: should say for x1 in y1:. and for x2 in needle[0]: should be for x2 in y2:? Otherwise you're ignoring the y variables (but maybe that's intentional). Commented Mar 29, 2013 at 20:42
  • Oh opps. You're right. Commented Mar 29, 2013 at 20:45
  • Remember that for ___ in 2dobject will give you rows. A better naming convention might be for hayrow in haystack ... for haypix in hayrow Commented Mar 29, 2013 at 20:47
  • What does the pix in haypix stand for? Commented Mar 29, 2013 at 20:47

3 Answers 3

Reset to default
3

To convert the image into a numpy array, you should be able to simply do this:

import numpy as np
from PIL import Image

needle = Image.open('needle.png')
haystack = Image.open('haystack.jpg')

needle = np.asarray(needle)
haystack = np.asarray(haystack)

To get you started with finding the needle, note that this will give you a list of all the places where the corner matches:

haystack = np.array([[1,2,3],[3,2,1],[2,1,3]])
needle = np.array([[2,1],[1,3]])

np.where(haystack == needle[0,0])
#(array([0, 1, 2]),   row-values
# array([1, 1, 0]))   col-values

Then, you can look at all the corner matches, and see if the subhaystack there matches:

h,w = needle.shape
rows, cols = np.where(haystack == needle[0,0])
for row, col in zip(rows, cols):
    if np.all(haystack[row:row+h, col:col+w] == needle):
        print "found it at row = %i, col = %i"%(row,col)
        break
else:
    print "no needle in haystack"

Below is a more robust version that finds the best match, and if it matches better than some percentage, considers the needle found. Returns the corner coordinate if found, None if not.

def find_needle(needle, haystack, tolerance=.80):
    """ input:  PIL.Image objects
        output: coordinat of found needle, else None """

    # convert to grayscale ("L"uminosity) for simplicity.
    needle = np.asarray(needle.convert('L'))   
    haystack = np.asarray(haystack.convert('L'))

    h,w = needle.shape
    H,W = haystack.shape
    L = haystack.max()

    best = (None, None, 1)
    rows, cols = np.where((haystack - needle[0,0])/L < tolerance)
    for row, col in zip(rows, cols):
        if row+h > H or col+w > W: continue # out of range
        diff = np.mean(haystack[row:row+h, col:col+w] - needle)/L
        if diff < best[-1]:
            best = (diff, row, col)

    return best if best[-1] < tolerance else None
Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

Needle: s24.postimg.org/f8fmxkqg1/needle.png Haystack: s1.postimg.org/th80b1a26/haystack.jpg Yes, the needle is entirely in the haystack.
This still doesn't find the needle image in your haystack image, but I believe that's because one is a jpg and perhaps the lossiness of the jpg distorts it a bit.
Oh wow. I was just about to give up. Thanks! Will test and provide results.
@askewchan Tried the convolution way, doesn't work: white areas of the haystack image (so [255, 255, 255]) give the largest values of the convolution.
@Jaime: In general the convolution method works well, at least in my experience, but you need to normalize. Convolution, btw, is one of the ways that OpenCV's matchTemplate works.. all of which are just simple equations that are a few lines in numpy: docs.opencv.org/modules/imgproc/doc/object_detection.html
|
2

I finally managed to make a numpy-only implementation of a cross correlation search work... The cross-correlation is calculated using the cross-correlation theorem and FFTs.

from __future__ import division
import numpy as np
from PIL import Image
import matplotlib.pyplot as plt

def cross_corr(a, b):
    a_rows, a_cols = a.shape[:2]
    b_rows, b_cols = b.shape[:2]
    rows, cols = max(a_rows, b_rows), max(a_cols, b_cols)
    a_f = np.fft.fft2(a, s=(rows, cols), axes=(0, 1))
    b_f = np.fft.fft2(b, s=(rows, cols), axes=(0, 1))
    corr_ab = np.fft.fft2(a_f.conj()*b_f, axes=(0,1))
    return np.rint(corr_ab / rows / cols)

def find_needle(haystack, needle, n=10):
    # convert to float and subtract 128 for better matching
    haystack = haystack.astype(np.float) - 128
    needle = needle.astype(np.float) - 128
    target = np.sum(np.sum(needle*needle, axis=0), axis=0)
    corr_hn = cross_corr(haystack, needle)
    delta = np.sum(np.abs(corr_hn - target), axis=-1)
    return np.unravel_index(np.argsort(delta, axis=None)[:n],
                            dims=haystack.shape[:2])

haystack = np.array(Image.open('haystack.jpg'))
needle = np.array(Image.open('needle.png'))[..., :3]
plt.imshow(haystack, interpolation='nearest')
dy, dx = needle.shape[:2]
candidates = find_needle(haystack, needle, 1)
for y, x in zip(*candidates):
    plt.plot([x, x+dx, x+dx, x, x], [y, y, y+dy,y+dy, y], 'g-', lw=2)
plt.show()

So the highest scoring point is the real needle:

enter image description here

>>> print candidates
(array([553], dtype=int64), array([821], dtype=int64))
Improve this answer

3 Comments

+1: Thanks for posting this! It's great to have numpy version of subimage matching posted on SO. I'd be interested to hear about why it now works, especially regarding white pixels vs matched pixels, etc.
@tom10 A lot of it was getting my cross-correlation theorem applied properly, and dealing with int overflows when computing the target value with the np.sum(needle**2). But for it to actually work, the big trick was to not cross correlate the images, but the images - 128. There are still a large number of images that will give the same result for the cross correlation, but apparently not so many. Without that trick, the real needle is something like the 100th best match... Frankly, I don't think the algorithm, as described above, is very robust.
@tom10 It does work perfectly with binary images, if you search in 2*image - 1.
1

You can use matchTemplate in opencv to detect the position:

import cv2
import numpy as np
import pylab as pl

needle = cv2.imread("needle.png")
haystack = cv2.imread("haystack.jpg")

diff = cv2.matchTemplate(haystack, needle, cv2.TM_CCORR_NORMED)
x, y = np.unravel_index(np.argmax(diff), diff.shape)

pl.figure(figsize=(12, 8))
im = pl.imshow(haystack[:,:, ::-1])
ax = pl.gca()
ax.add_artist(pl.Rectangle((y, x), needle.shape[1], needle.shape[0],  transform=ax.transData, alpha=0.6))

here is the output:

enter image description here

Improve this answer

7 Comments

Currently downloading OpenCV. In the meantime, how would I know if it has found a match or not? By looking at the diff value, right? There is probably some threshold, correct?
the TM_CCOEFF_NORMED value of perfect match will be 1. You can use some threshold such as 0.9.
Getting this error: NameError: name 'Rectangle' is not defined :(
change it to pl.Rectangle.
cv2.TM_CCORR_NORMED is always 3 for some reason. Even if I change images.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.