我在考虑一种快速查找包含子矩阵 m 的大矩阵 M 的方法。同时，我还需要识别部分匹配。
我能想到的几种方法是：
我相信这是图像处理中经常遇到的问题，如果有人能提供他们的建议或指向关于这个主题的资源/论文，我将不胜感激。
编辑: 较小的示例：
大矩阵：
1 2 3 4 5
4 5 6 7 8
9 7 6 5 2
小矩阵：
7 8
5 2
结果：(row: 1 col: 3)
一个在 (1, 3) 符合部分匹配条件的小矩阵示例：
7 9
5 2
如果超过一半的像素匹配，则被视为部分匹配。
谢谢。
如果您愿意预处理矩阵并且有许多相同矩阵的查询，那么这方面有非常快速的算法。
请查看博恩大学（Clausen教授的多媒体数据库研究小组）关于代数数据库的论文。例如，请参考此论文：http://www-mmdb.iai.uni-bonn.de/download/publications/sigir-03.pdf
基本思想是推广倒排列表，因此它们使用任何类型的代数变换，而不仅仅是普通倒排列表中的单向移位。这意味着只要您需要对输入数据进行的修改可以用代数方式建模，就可以使用此方法。具体来说，可以检索在任意数量的维度、旋转、翻转等方面进行翻译的查询。
该论文主要展示了音乐数据的情况，因为这是他们的主要研究兴趣，但您可能还能找到其他论文，展示如何将其适应于图像数据（或者如果您理解原则，可以尝试自己适应它，因为它很简单）。
编辑：
如果您正确定义了部分匹配，那么这个想法也适用于部分匹配。
我认为你不能仅凭一些方法猜测子矩阵的位置，但你可以优化你的搜索。
例如，给定一个矩阵 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个维度。
如果您只需要将一个小矩阵与一个大矩阵进行匹配，那么很难快速完成。但是，如果您需要对许多小矩阵与大矩阵进行匹配，则可以预处理大矩阵。
以精确匹配为例，假设有许多3x3的矩阵需要与一个巨大的矩阵进行匹配。
创建一个新的“匹配矩阵”，大小与“大矩阵”相同。对于大矩阵中的每个位置，计算从x，y到x+3，y+3的每个x，y的3x3哈希值。现在，您只需扫描匹配矩阵以查找匹配的哈希值即可。
您可以使用专门的哈希函数实现部分匹配，这些哈希函数会为具有相同部分匹配属性的内容提供相同的哈希值。这有点棘手。
如果您想进一步加快速度并且有足够的内存，请为匹配矩阵创建哈希表，并在哈希表中查找哈希值。
3x3解决方案适用于任何测试矩阵3x3或更大的矩阵。您不需要拥有完美的哈希方法-您只需要拥有能够拒绝大多数错误匹配的东西，然后在哈希表中进行潜在匹配的完全匹配即可。