如何检测一个二维数组是否在另一个二维数组中？

Question

在一位Stack Overflow的会员的帮助下，我有了以下代码：

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)

我已经编写了以下代码来检查针是否在堆栈中：

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

问题在于我得到了第3行的错误：'PixelAccess'对象不可迭代。

有人建议我将needle和haystack都复制到numpy/scipy数组中。然后，我可以使用一个函数来检查2D数组needle是否在2D数组haystack中。

我需要帮助完成以下事项：

1）将这些数组转换为numpy数组。

2）编写一个函数来检查2D数组needle是否在2D数组haystack中。我的函数无法工作。

这些是图片：
Needle:

Haystack:

- user1251385

---

也许这一行代码：for x1 in haystack[0]: 应该改为 for x1 in y1:，而 for x2 in needle[0]: 则应该改为 for x2 in y2:？否则你会忽略 y 变量（但也许这是有意的）。 - askewchan

哦，糟糕。你是对的。 - user1251385

请记住for ___ in 2dobject会给你行。 更好的命名约定可能是for hayrow in haystack ... for haypix in hayrow。 - askewchan

haypix中的pix代表什么？ - user1251385

Answer 1

要将图像转换为numpy数组，您只需要执行以下操作：

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)

为了帮助你开始查找关键信息，以下列出所有角落匹配的位置：

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

然后，您可以查看所有角落匹配项，并查看那里的子串是否匹配：

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"

下面是一个更强大的版本，它可以找到最佳匹配项，并且如果匹配程度高于某个百分比，则认为针已经找到。 如果找到了，则返回拐角坐标，否则返回 None。

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

- askewchan

---

针：http://s24.postimg.org/f8fmxkqg1/needle.png 干草堆：http://s1.postimg.org/th80b1a26/haystack.jpg 是的，这根针完全在干草堆里。 - user1251385

这仍然无法在你的草堆图像中找到针头图像，但我认为这是因为其中一个是jpg格式，可能jpg格式的失真略微扭曲了它。 - askewchan

哇，我正要放弃呢。谢谢！我会测试并提供结果的。 - user1251385

@askewchan 尝试了卷积的方法，但不起作用：干草堆图像的白色区域（即 [255, 255, 255]）给出了卷积的最大值。 - Jaime

@Jaime：一般来说，卷积方法效果很好，至少在我的经验中是这样的，但你需要进行归一化处理。顺便提一下，卷积是OpenCV的matchTemplate工作的一种方式..所有这些都只是一些简单的方程，在numpy中只需几行代码即可实现：http://docs.opencv.org/modules/imgproc/doc/object_detection.html - tom10

Answer 2

我终于成功地做出了一个仅使用numpy实现的互相关搜索... 互相关是使用互相关定理和FFT计算的。

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

所以最高得分的点是真正的针头：

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

- Jaime

---

+1：感谢您发布这篇文章！在SO上发布numpy版本的子图像匹配非常棒。我很想听听它现在为什么能够工作，特别是关于白色像素与匹配像素之间的区别等方面的内容。 - tom10

@tom10 很大一部分是让我的互相关定理正确应用，并在计算 np.sum(needle**2) 的目标值时处理 int 溢出。但要使其实际工作，最大的诀窍是不要交叉相关图像，而是图像减去 128。仍然有很多图像会给出相同的互相关结果，但显然不是很多。如果没有这个技巧，真正的针就是第100个最佳匹配...坦白地说，我认为上面描述的算法并不是非常健壮。 - Jaime

@tom10 如果你在2 * image - 1中搜索，它对于二进制图像可以完美工作。 - Jaime

Answer 3

您可以使用OpenCV中的matchTemplate来检测位置：

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

这里是输出：

- HYRY

---

TM_CCOEFF_NORMED值的完美匹配将为1。您可以使用一些阈值，例如0.9。 - HYRY

出现了这个错误：NameError: name 'Rectangle' is not defined :( - user1251385

change it to pl.Rectangle. - HYRY

cv2.TM_CCORR_NORMED 是一个标志，告诉 matchTemplate 计算图像和模板之间的 CCORR_NORMED 值。np.max(diff) 将给出最大值。将此值与阈值进行比较。 - HYRY

谢谢！=] 我把这两个名字搞混了。 - user1251385