矩阵比较算法

Question

如果您有两个维度为N*M的矩阵，那么获取差异矩形的最佳方法是什么？

示例：

2 3 2 3 2 3 2 3                      2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3                      2 3 2 3 2 3 2 3
2 3 4 5 4 3 2 3      <--->           2 3 2 3 2 3 2 3
2 3 4 5 2 3 2 3                      2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3                      2 3 2 3 2 3 2 3

                      |
                      |
                     \ /
             Rect([2,2] , [3,4])
                    4 5 4
                    4 5 2-> A (2 x 3 Matrix)

我能想到的最好方法是从左上角开始扫描，直到找到有差异的点。然后从右下角开始扫描，找到有差异的点。

但是在最坏情况下，这需要O(N*M)的时间复杂度。有更高效的算法吗？或者我是否可以通过改变矩阵的表示方式来应用更高效的算法？请注意，这个矩阵可能非常大。

- SysAdmin

---

这是一个非常有趣的问题。你能告诉我你将用它做什么应用，还是这更多是一项研究？ - Xavier Ho

@Xavier Ho - 不需要学习。我可以将相同的算法应用于原始图像。 - SysAdmin

你可以比较每行和每列的傅里叶变换并比较结果。DFT非常快，因此可能更有效率。尝试查看OpenCV，它是一个处理图像的很棒的库，而且还是免费的。使用一张图像在另一张图像上的卷积也可能有效 - 你需要验证一下（从数学角度来说）。 - gramm

Answer 1

没有更高效的算法。对于相同的矩阵，您必须扫描所有元素，因此算法必然是 O(n*m)。

- jemfinch

Answer 2

“但在最坏的情况下，这是O(NM)。是否有更有效率的算法？”由于数据的维度为O(NM)，可能没有更好的算法。许多类似的矩阵操作都是M*N的顺序，因为在最坏的情况下，有M*N个元素需要检查，以确保矩阵相等。

从平均情况来看，如果差异框必须是整个矩阵中的单个矩形，则我认为您可以通过平均扫描少于所有元素来完成。

以下是我的想法： 跟踪当前元素，称之为XY

1. 从左上角开始，现在XY是顶部的角。 2. 检查两者中的XY元素是否相等，如果不相等，请转到3，否则请转到4。 3. 如果元素不是，则您有一个差异矩阵的元素。记录此元素，然后搜索该行和列以查找其他元素（可能使用二进制搜索之类的东西最快）。一旦搜索了行/列，您就有了边缘的坐标。如果元素不相等，请移动到4。 4. 下一步将XY对角线向下移动一个元素并向右移动一个元素，然后再次转到2。 5. 一旦覆盖了对角线，那么您将需要沿着下一个对角线进行测试（我认为选择与当前对角线最远的新对角线将是最佳选择，尽管我没有证明这是最佳选择），直到覆盖所有元素。在最坏的情况下，这仍然是O(NM)，但在平均情况下可能会更快。

实质上，您正在尝试尽快找到一个不同的元素，因此目标是选择第一个元素，以最小化找到第一个不同元素的搜索次数的期望值。

- shuttle87

---

虽然这很好...但在我的情况下...我有重叠的矩形，非重叠的矩形等。 - SysAdmin

我一直希望有一种"Zig-zag magic" ：它可以最小化撞上最坏情况的概率。 - SysAdmin

Answer 3

正如其他人指出的那样，O(N*M)是最优的。

我想补充一点，在扫描矩阵时，应该记住它的内存布局。如果矩阵按行排列，则最好水平扫描。如果按列排列，则最好垂直扫描。这将导致几乎最优的缓存行为。

当然，这假设要求的差异确实是矩形形状。如果它是其他形状，并且您需要边界矩形，则无论如何都必须扫描行和列。

- Thomas

Answer 4

我认为这个算法是最优秀的。不过，我建议你尝试一下非常高效的BLAS库，并进行性能比较。此外，Boost uBlas库提供了C++接口和矩阵表达式方法。

- Canopus