查找较小数组与较大数组最匹配的位置

Question

我需要找到较小的2d数组array1匹配另一个2d数组array2中最接近的数组的位置。

• array1的大小为grid_size 46x46至96x96。

• array2将更大（184x184）。

我只能访问numpy。

我目前正在尝试使用Tversky formula，但并不局限于此。

效率是最重要的部分，因为它将多次运行。我下面显示的当前解决方案非常慢。

for i in range(array2.shape[0] - grid_size):
    for j in range(array2.shape[1] - grid_size):
        r[i, j] = np.sum(array2[i:i+grid_size, j:j+grid_size] == array1 ) / (np.sum(array2[i:i+grid_size, j:j+grid_size] != array1 ) + np.sum(Si[i:i+grid_size, j:j+grid_size] == array1 ))

编辑：目的是找到较小图像与另一图像匹配的位置。

Answer 1

[这是基于FFT /卷积的方法，可将欧几里德距离减至最小：

import numpy as np
from numpy import fft

N = 184
n = 46
pad = 192

def best_offs(A,a):
    A,a = A.astype(float),a.astype(float)
    Ap,ap = (np.zeros((pad,pad)) for _ in "Aa")
    Ap[:N,:N] = A
    ap[:n,:n] = a
    sim = fft.irfft2(fft.rfft2(ap).conj()*fft.rfft2(Ap))[:N-n+1,:N-n+1]
    Ap[:N,:N] = A*A
    ap[:n,:n] = 1
    ref = fft.irfft2(fft.rfft2(ap).conj()*fft.rfft2(Ap))[:N-n+1,:N-n+1]
    return np.unravel_index((ref-2*sim).argmin(),sim.shape)

# example
# random picture
A = np.random.randint(0,256,(N,N),dtype=np.uint8)
# random offset
offy,offx = np.random.randint(0,N-n+1,2)
# sub pic at random offset
# randomly flip half of the least significant 75% of all bits
a = A[offy:offy+n,offx:offx+n] ^ np.random.randint(0,64,(n,n))

# reconstruct offset
oyrec,oxrec = best_offs(A,a)
assert offy==oyrec and offx==oxrec

# speed?
from timeit import timeit
print(timeit(lambda:best_offs(A,a),number=100)*10,"ms")

# example with zero a
a[...] = 0
# make A smaller in a matching subsquare
A[offy:offy+n,offx:offx+n]>>=1

# reconstruct offset
oyrec,oxrec = best_offs(A,a)
assert offy==oyrec and offx==oxrec

样品运行：

3.458537160186097 ms