algorithm - 对齐 2 矩阵以获得最大重叠

Question

所以下面是一道面试题。

Given two N² matrices with entries being 0 or 1. How can we find out the number of maximum overlapping 1's possible?

注意:只能上下左右移动矩阵，不能旋转

目前我被困在最天真的 O(N^4) 方法中，即将一个矩阵的左上角与另一个矩阵的每个可能位置对齐并计算所有重叠 1s。

示例:

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

那么最大重叠 1 的数量是 2，我们将 B 的 (0,2) 下到 (1,0)的 A，则 (0,2) 和 (1,0) 都是 1，并且 (1,2) 和 (2,0) 都是 1。

能否从O(N⁴)开始优化？

Answer 1

如果浮点算术计算是可能的，这个问题可能会用 2D cross-correlation 来解决。 (本质上使用快速傅里叶变换)在 O(n^2 logn) 时间内。该方法用于二维模式搜索。

不太明显的提示:要实现相关性并获得正确的结果，应该移动值以使“信号”具有双极性(将零转换为 -1 或从所有矩阵元素中减去矩阵平均值)

计算相关矩阵，找到最大值的索引(dx,dy) - 它应该对应对齐向量。