查找矩陣內的匹配子矩陣

Question

我有一個100x200的二維數組，表示爲由黑色（0）和白色（255）單元組成的numpy數組。這是一個位圖文件。然後我有二維形狀（最簡單的把它們想象成字母），它們也是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 and ndimage.find_objects:

1. 標籤使用ndimage.label此找到所有斑點的陣列中，並將其標籤爲整數的圖像。

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

   例如輸入：

2. 使用ndimage.find_objects
3. 然後使用交集，看是否found blobs符合您的wanted blobs

代碼1.和2.獲取這些斑點的片

標記：

孤立的斑點再次進行測試：（甚至計時）