Найти место, где меньший массив больше всего подходит большему - PullRequest
Новая
       69

Найти место, где меньший массив больше всего подходит большему

1 голос
/ 24 октября 2019

Мне нужно найти, где меньший 2d массив, array1 соответствует ближайшему внутри другого 2d массива, array2.

  • array1 с размером grid_size от 46x46 до 96x96.

  • массив2 будет больше (184x184).

У меня есть доступ только к numpy.

В настоящее время я пытаюсьиспользуйте формулу Тверского , но я к ней не привязан.

Эффективность - самая важная часть, так как она будет выполняться много раз. Мое текущее решение, показанное ниже, очень медленное. 

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

Редактировать: Цель состоит в том, чтобы найти место, где уменьшенное изображение соответствует другому изображению.

1 Ответ

1 голос
/ 24 октября 2019

Вот подход, основанный на БПФ / свертке, который минимизирует евклидово расстояние: 

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