对齐两个二进制矩阵以获得最大重叠

Question

我想找出两个二进制矩阵的最大重叠数 1，只允许平移（不允许旋转和反射）。我的问题与非常相似，但我想做的是以有效的方式实际编码 OP 在该问题中提出的 "naive" 解决方案。

因此，回顾一下，我有两个矩阵（大小不一定相同），条目为 0 或 1，例如：

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

最大重叠可以通过将一个矩阵的一个角与另一个矩阵的每个可能位置对齐并计算所有重叠 1 来找到。然后，我们发现最大重叠是 two 并且当我们将 A 的左下角 (2,0) 对齐到 (1,2) 的 B.

我想在 python 中编写此方法的简单（并且可能很快）实现，但我真的不知道从哪里开始...

Answer 1

要找到最大重叠，您可以使用 scipy 中的 correlate2d 函数：

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

对齐两个二进制矩阵以获得最大重叠

Aligning two binary matrices for maximum overlap

python

binary

numpy

matrix

counting