How to detect if a 2D array is inside another 2D a

问题:

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:

Haystack:

回答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:

回答2:

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

回答3:

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:

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