在矩阵内查找匹配的子矩阵

Question

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

我知道我可以天真地遍历矩阵,但这将成为我的代码的"热门"部分,因此速度是一个问题.在numpy/scipy中有没有快速的方法来执行此操作？

我简要地看了看Scipy的相关功能.我对'模糊匹配'不感兴趣,只对完全匹配感兴趣.我也看了一些学术论文,但它们都在我的头上.

Answer 1

你可以使用correlate.您需要将黑色值设置为-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测试: