Матричный матч в питоне

Question

Как найти наилучшее «соответствие» для маленькой матрицы в большой матрице? Например:

 small=[[1,2,3],
        [4,5,6],
        [7,8,9]]



    big=[[2,4,2,3,5],
         [6,0,1,9,0],
         [2,8,2,1,0],
         [7,7,4,2,1]]

Совпадение определяется как разность чисел в матрице, поэтому совпадение в позиции (1,1) такое, как если бы число 5 от малого было бы на числе 0 от большой матрицы (поэтому центральное число от маленькой матрицы в координатах (1) , 1) большой матрицы.

Значение совпадения в позиции (1,1): м (1,1) = | 2-1 | + | 4-2 | + | 2-3 | + | 6-4 | + | 0-5 | + | 1-6 | + | 2-7 | + | 8-8 | + | 2-9 | = 28

Цель состоит в том, чтобы найти самую низкую разницу в этих матрицах.

Маленькая матрица всегда имеет нечетное количество строк и столбцов, поэтому ее легко найти в центре.

Answer 1

Я бы использовал numpy, чтобы помочь с этим.

Для начала я бы преобразовал массивы в numpy массивы

import numpy as np

small = np.array([[1,2,3], [4,5,6], [7,8,9]])
big = np.array([[2,4,2,3,5], [6,0,1,9,0], [2,8,2,1,0], [7,7,4,2,1]])

, затем я бы инициализировал массив для хранения результатов теста.(необязательно: также словарь)

result_shape = np.array(big.shape) - np.array(small.shape) + 1
results = np.zeros((result_shape[0], result_shape[1]))
result_dict = {}

Затем выполните итерации по позициям, в которых небольшая матрица может быть расположена над большой матрицей, и рассчитайте разницу:

insert = np.zeros(big.shape)
for i in range(results.shape[0]):
    for j in range(results.shape):
        insert[i:small.shape[0] + i, j:small.shape[1] + j] = small
        results[i, j] = np.sum(np.abs(big - insert)[i:3+i, j:3+j])
        # Optional dictionary 
        result_dict['{}{}'.format(i, j)] = np.sum(np.abs(big - insert)[i:3+i, j:3+j])

Затем выможно print(results) и получить:

[[ 28.  29.  38.]
 [ 24.  31.  39.]]

и / или поскольку позиция маленькой матрицы над большой матрицей хранится в ключах словаря, вы можете получить положение маленькой матрицы надбольшая матрица, где наименьшая разница при манипуляциях с ключами:

pos_min = [int(i) for i in list(min(result_dict, key=result_dict.get))]

, а если вы print(pos_min), вы получите:

[1, 0]

, тогда если вам нужен индекс для всего, что вы можете повторитьнад ним, если требуется.Надеюсь, это поможет!

Answer 2

Другое возможное решение будет таким: возврат минимальной разности и координат в матрице big:

small=[[1,2,3],
       [4,5,6],
       [7,8,9]]

big=[[2,4,2,3,5],
     [6,0,1,9,0],
     [2,8,2,1,0],
     [7,7,4,2,1]]

def difference(small, matrix):
    l = len(small)
    return sum([abs(small[i][j] - matrix[i][j]) for i in range(l) for j in range(l)])

def getSubmatrices(big, smallLength):
    submatrices = []
    bigLength = len(big)
    step = (bigLength // smallLength) + 1
    for i in range(smallLength):
        for j in range(step):
            tempMatrix = [big[j+k][i:i+smallLength] for k in range(smallLength)]
            submatrices.append([i+1,j+1,tempMatrix])
    return submatrices

def minDiff(small, big):
    submatrices = getSubmatrices(big, len(small))
    diffs = [(x,y, difference(small, submatrix)) for x, y, submatrix in submatrices]
    minDiff = min(diffs, key=lambda elem: elem[2])
    return minDiff

y, x, diff = minDiff(small, big)

print("Minimum difference: ", diff)
print("X = ", x)
print("Y = ", y)

Вывод:

Minimum difference:  24
X =  1
Y =  2

Answer 3

Можно выполнить итерацию по жизнеспособным строкам и столбцам и сжать фрагменты big с помощью small, чтобы вычислить сумму различий, и использовать min, чтобы найти минимум среди различий:

from itertools import islice
min(
    (
        sum(
            sum(abs(x - y) for x, y in zip(a, b))
            for a, b in zip(
                (
                    islice(r, col, col + len(small[0]))
                    for r in islice(big, row, row + len(small))
                ),
                small
            )
        ),
        (row, col)
    )
    for row in range(len(big) - len(small) + 1)
    for col in range(len(big[0]) - len(small[0]) + 1)
)

или в одну строку:

min((sum(sum(abs(x - y) for x, y in zip(a, b)) for a, b in zip((islice(r, col, col + len(small[0])) for r in islice(big, row, row + len(small))), small)), (row, col)) for row in range(len(big) - len(small) + 1) for col in range(len(big[0]) - len(small[0]) + 1))

Возвращает: (24, (1, 0))

Answer 4

Сделано вручную:

small=[[1,2,3],
       [4,5,6],
       [7,8,9]]


big=[[2,4,2,3,5],
     [6,0,1,9,0],
     [2,8,2,1,0],
     [7,7,4,2,1]]

# collect all the sums    
summs= [] 

# k and j are the offset into big

for k in range(len(big)-len(small)+1):
    # add inner list for one row
    summs.append([])
    for j in range(len(big[0])-len(small[0])+1):
        s = 0
        for row in range(len(small)):
            for col in range(len(small[0])):
                s += abs(big[k+row][j+col]-small[row][col])
        # add to the inner list
        summs[-1].append(s)

print(summs)

Вывод:

[[28, 29, 38], [24, 31, 39]]

Если вас просто интересуют координаты в большем, храните кортежи (rowoffset,coloffset,sum) и списки не выводить ящикив списки.Вы можете использовать min() с ключом таким образом:

summs = []
for k in range(len(big)-len(small)+1):
    for j in range(len(big[0])-len(small[0])+1):
        s = 0
        for row in range(len(small)):
            for col in range(len(small[0])):
                s += abs(big[k+row][j+col]-small[row][col])
        summs .append( (k,j,s) )  # row,col, sum

print ("Min value for bigger matrix at ", min(summs , key=lambda x:x[2]) )

Вывод:

Min value for bigger matrix at  (1, 0, 24)

Если бы у вас было "рисование", это вернуло бы только одно с минимальным смещением строки и столбца.