对齐2个矩阵以实现最大重叠 [英] align 2 matrice for maximum overlap

问题描述

因此，以下是面试问题.

So following is an interview problem.

给出两个 N ² 个矩阵，其条目为0或1.我们如何找出最大可能重叠的1的数量?

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

注意:您只能向上，向下，向左和向右移动矩阵，因此不允许旋转

Note: You can only move the matrix upward, downward, leftward and rightward, so rotation is not allowed

当前，我被最幼稚的O(N^4)方法所困，该方法是将一个矩阵的左上角与另一个矩阵的每个可能位置对齐，并计算所有重叠1s.

Currently I'm stuck at the most naive O(N^4) method, which being align the top left corner of one matrix to every possible position of the other matrix and count the all the overlap 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.

Then the number of maximum overlapping 1s are 2, that we alight (0,2) of B to (1,0) of A, then (0,2) and (1,0) are both 1, and (1,2) and (2,0) are both 1.

可以从 O(N ⁴ )中进行优化吗?

Can it be optimise from O(N⁴)?

推荐答案

如果可以进行浮点算术计算，则可以使用2D 互相关(本质上使用快速傅立叶变换).此方法用于2D模式搜索.

If floating-point arithmetics calculations are possible, this problem might be solved with 2D cross-correlation (using fast Fourier transform intrinsically) in O(n^2 logn) time. This method is used in 2D pattern searching.

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

Not so obvious tip: to implement correlation and get proper results, one should shift values to make "signals" bi-polar (transform zeros to -1 or subtract matrix average from all matrix elements)

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

Calculate correlation matrix, find index (dx,dy) of maximum value - it should correspond to align vector.

这篇关于对齐2个矩阵以实现最大重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！