我正在考虑一种在更大的矩阵 M 中查找子矩阵 m 的快速方法。我还需要识别部分匹配项。
我能想到的几种方法是：
我相信这是图像处理中经常遇到的问题，如果有人可以倾注他们的投入或将我指向有关此主题的资源/论文，我将不胜感激。
编辑： 较小的例子：
更大的矩阵：
1 2 3 4 5
4 5 6 7 8
9 7 6 5 2
较小的矩阵：
7 8
5 2
结果：（行：1 列：3）
在 (1, 3) 处有资格作为部分匹配的较小矩阵的示例：
7 9
5 2
如果超过一半的像素匹配，则视为部分匹配。
谢谢。
我建议对“二维模式匹配算法”进行互联网搜索。你会得到很多结果。我将仅链接 Google 上的第一次点击，这是一篇针对您的问题提出算法的论文。
您还可以查看论文末尾的引文，以了解其他现有算法。
摘要：
提出了一种在二维nxn文本中搜索二维mxm模式的算法。它执行的平均比较少于文本大小：n^2/m 使用 m^2 额外空间。基本上，它仅在文本的 n/m 行上使用多个字符串匹配。它最多运行 2n^2 次，并接近许多模式的最佳 n^2 次。它稳步扩展到具有类似最坏情况的与字母无关的算法。实验结果包含在实用版本中。
如果您愿意对矩阵进行预处理并且您对同一矩阵有很多查询，则有非常快速的算法。
查看多媒体数据库研究小组（波恩大学克劳森教授）关于代数数据库的论文。看看这篇论文，例如：http ://www-mmdb.iai.uni-bonn.de/download/publications/sigir-03.pdf
基本思想是推广倒排列表，因此它们使用任何类型的代数变换，而不是像普通倒排列表那样仅在一个方向上移动。
这意味着只要您需要对输入数据进行的修改可以通过代数方式建模，这种方法就可以工作。这特别是可以检索在任意数量的维度中翻译、旋转、翻转等的查询。
该论文主要针对音乐数据展示这一点，因为这是他们的主要研究兴趣，但您可能会找到其他人，它们也展示了如何将其调整为图像数据（或者您可以尝试自己调整它，如果您理解原理很简单）。
编辑：
如果您正确定义它们，这个想法也适用于部分匹配。
如果您只需要将一个小矩阵与一个大矩阵进行匹配，则无法快速完成此操作。但是如果你需要对大矩阵做很多小矩阵，那么就对大矩阵进行预处理。
一个简单的例子，精确匹配，许多 3x3 矩阵与一个巨型矩阵。
制作一个新的“匹配矩阵”，大小与“大矩阵”相同，对于大矩阵中的每个位置，为大矩阵中的每个 x,y 到 x+3,y+3 计算一个 3x3 散列。现在您只需扫描匹配矩阵以查找匹配的哈希值。
您可以使用专门的散列函数实现部分匹配，这些函数为具有相同部分匹配属性的事物提供相同的散列。棘手。
如果您想进一步加快速度并为其提供内存，请为匹配矩阵创建一个哈希表，并在哈希表中查找哈希值。
3x3 解决方案适用于任何 3x3 或更大的测试矩阵。您不需要完美的哈希方法——您只需要能够拒绝大多数错误匹配的方法，然后对哈希表中的潜在匹配进行完全匹配。
我认为你不能只用某种方法猜测子矩阵在哪里，但你可以优化你的搜索。
例如，给定一个矩阵 A MxN 和一个子矩阵 B mxn，你可以这样做：
SearchSubMatrix (Matrix A, Matrix B)
answer = (-1, -1)
Loop1:
for i = 0 ... (M-m-1)
|
| for j = 0 ... (N-n-1)
| |
| | bool found = true
| |
| | if A[i][j] = B[0][0] then
| | |
| | | Loop2:
| | | for r = 0 ... (m-1)
| | | | for s = 0 ... (n-1)
| | | | | if B[r][s] != A[r+i][s+j] then
| | | | | | found = false
| | | | | | break Loop2
| |
| | if found then
| | | answer = (i, j)
| | | break Loop1
|
return answer
这样做，由于子矩阵的大小，您将减少搜索。
Matrix Submatrix Worst Case:
1 2 3 4 2 4 [1][2][3] 4
4 3 2 1 3 2 [4][3][2] 1
1 3 2 4 [1][3]{2 4}
4 1 3 2 4 1 {3 2}
(M-m+1)(N-n+1) = (4-2+1)(4-2+1) = 9
虽然这是O(M*N)，但它永远不会看M*N时间，除非您的子矩阵只有 1 个维度。