How To Detect If A 2d Array Is Inside Another 2d Array?

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

Solution 1:

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])
forrow, 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.

deffind_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 inzip(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 elseNone

Solution 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:

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

Solution 3:

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: