python - 在矩阵中查找匹配的子矩阵

Question

我有一个 100x200 二维数组，表示为一个由黑色 (0) 和白色 (255) 单元组成的 numpy 数组。它是一个位图文件。然后我有 2D 形状（最容易将它们视为字母），它们也是 2D 黑白单元格。

我知道我可以天真地遍历矩阵，但这将是我代码的“热门”部分，所以速度是一个问题。有没有一种快速的方法可以在 numpy/scipy 中执行此操作？

我简要地看了一下 Scipy 的相关函数。我对“模糊匹配”不感兴趣，只对精确匹配感兴趣。我还看了一些学术论文，但它们在我的头上。

Answer 1

您可以使用关联。您需要将黑色值设置为 -1，将白色值设置为 1（反之亦然），以便您知道相关峰值的值，并且它只出现在正确的字母中。

下面的代码做我认为你想要的。

import numpy
from scipy import signal

# Set up the inputs
a = numpy.random.randn(100, 200)
a[a<0] = 0
a[a>0] = 255

b = numpy.random.randn(20, 20)
b[b<0] = 0
b[b>0] = 255

# put b somewhere in a
a[37:37+b.shape[0], 84:84+b.shape[1]] = b

# Now the actual solution...

# Set the black values to -1
a[a==0] = -1
b[b==0] = -1

# and the white values to 1
a[a==255] = 1
b[b==255] = 1

max_peak = numpy.prod(b.shape)

# c will contain max_peak where the overlap is perfect
c = signal.correlate(a, b, 'valid')

overlaps = numpy.where(c == max_peak)

print overlaps

这将输出(array([37]), array([84]))代码中设置的偏移量的位置。

您可能会发现，如果您的字母大小乘以您的大数组大小大约大于 Nlog(N)，其中 N 是您正在搜索的大数组的相应大小（对于每个维度），那么您可能会得到通过使用基于 fft 的算法来加快速度scipy.signal.fftconvolve（请记住，如果您使用的是卷积而不是相关性，则需要翻转其中一个数据集的每个轴 -flipud和fliplr）。唯一的修改是分配 c：

c = signal.fftconvolve(a, numpy.fliplr(numpy.flipud(b)), 'valid')

比较上述尺寸的时间：

In [5]: timeit c = signal.fftconvolve(a, numpy.fliplr(numpy.flipud(b)), 'valid')
100 loops, best of 3: 6.78 ms per loop

In [6]: timeit c = signal.correlate(a, b, 'valid')
10 loops, best of 3: 151 ms per loop

Answer 2

这是一种您可以使用或调整的方法，具体取决于您的需求细节。它使用ndimage.label和ndimage.find_objects：

1. 使用此标记图像ndimage.label查找数组中的所有 blob 并将它们标记为整数。
2. 使用获取这些 blob 的切片ndimage.find_objects
3. 然后使用 set intersection 查看是否found blobs与您的对应wanted blobs

1.和的代码2.：

import scipy
from scipy import ndimage
import matplotlib.pyplot as plt

#flatten to ensure greyscale.
im = scipy.misc.imread('letters.png',flatten=1)
objects, number_of_objects = ndimage.label(im)
letters = ndimage.find_objects(objects)

#to save the images for illustrative purposes only:
plt.imsave('ob.png',objects)
for i,j in enumerate(letters):
    plt.imsave('ob'+str(i)+'.png',objects[j])

示例输入：

标签：

要测试的孤立 blob：