c++ - 在 M X N 矩阵中查找 m x n 子矩阵的最快方法

Question

我正在考虑一种在更大的矩阵 M 中寻找子矩阵 m 的快速方法。我还需要识别部分匹配项。

我能想到的几种方法是:

1. 优化普通暴力破解以仅处理增量行和列。
2. 可能会将 Rabin-karp 算法扩展到二维，但不确定如何处理部分匹配。

我相信这是图像处理中经常遇到的问题，如果有人能提供他们的意见或向我指出有关此主题的资源/论文，我将不胜感激。

编辑:小例子:

更大的矩阵:
1 2 3 4 5
4 5 6 7 8
9 7 6 5 2

小矩阵:
7 8
5 2

结果:(行:1 列:3)

在 (1, 3) 处符合部分匹配条件的 Smaller 矩阵示例:
7 9
5 2

如果超过一半的像素匹配，则视为部分匹配。

谢谢。

Answer 1

我建议在互联网上搜索“二维模式匹配算法”。你会得到很多结果。我将链接 Google 上的第一次点击，a paper为您的问题提供算法。

您还可以查看论文末尾的引文，以了解其他现有算法。

摘要:

An algorithm for searching for a two dimensional m x m pattern in a two dimensional n x n text is presented. It performs on the average less comparisons than the size of the text: n^2/m using m^2 extra space. Basically, it uses multiple string matching on only n/m rows of the text. It runs in at most 2n^2 time and is close to the optimal n^2 time for many patterns. It steadily extends to an alphabet-independent algorithm with a similar worst case. Experimental results are included for a practical version.