Выравнивание двух двоичных матриц для максимального перекрытия - PullRequest
Новая
       9

Выравнивание двух двоичных матриц для максимального перекрытия

2 голосов
/ 08 января 2020

Я хотел бы найти количество максимальных перекрытий 1 двух двоичных матриц, допускающих только перемещение (вращение и отражение не допускаются). Мой вопрос очень похож на этот , но я хочу на самом деле эффективно кодировать «наивное» решение, предложенное OP в этом вопросе.

Итак, чтобы Напомним, у меня есть две матрицы ( не обязательно одинакового размера ) с записями, равными 0 или 1, например: 

   [0 0]      [0 0 1]
A: [1 1]   B: [0 0 1]
   [1 0]      [1 0 0]

Максимальное перекрытие может быть найдено с помощью выравнивание одного из углов одной матрицы с каждой возможной позицией другой матрицы и подсчет всех перекрывающихся 1. Затем мы находим, что максимальное перекрытие равно два и дается, когда мы выравниваем нижний левый угол (2,0) от A до (1,2) of B.

Я хотел бы закодировать в python простую (и, возможно, быструю) реализацию этого метода, но я не знаю, с чего начать ...

1 Ответ

1 голос
/ 08 января 2020

Чтобы найти максимальное перекрытие, вы можете использовать функцию correlate2d от scipy: 

import scipy

scipy.signal.correlate2d(a, b).max()

Или вы можете реализовать ее с нуля, используя numpy (что немного сложно): 

import numpy as np
from numpy.lib.stride_tricks import as_strided


def max_overlap(a, b):
    b_p = np.pad(b, ((a.shape[0]-1, a.shape[0]-1), (a.shape[1]-1, a.shape[1]-1)), 'constant', constant_values=0)
    output_shape = (b_p.shape[0] - a.shape[0] + 1, b_p.shape[1] - a.shape[1] + 1)
    b_w = as_strided(b_p, shape=output_shape + a.shape,
                          strides=b_p.strides*2)
    c = (b_w * a).sum(axis=(2,3))
    return c.max()
...