在MXN矩阵中查找amxn子矩阵的最快方法

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

我能想到的几种方法是:

  1. 优化正常的暴力,只处理增量的行和列。
  2. 可能会将Rabin-karp算法扩展到2-d但不确定如何处理它的部分匹配。

我相信这是图像处理中经常遇到的问题,如果有人可以投入他们的意见或指向我关于这个主题的资源/论文,我将不胜感激。

编辑:较小的例子:

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

较小的矩阵:
7 8
5 2 2

结果:(行:1列:3)

较小矩阵的一个例子,它在(1,3)处有资格作为部分匹配:
7 9
5 2 2

如果超过一半像素匹配,则将其视为部分匹配。

谢谢。

我建议在“2d模式匹配算法”上进行互联网搜索。 你会得到很多结果。 我将链接Google上的第一个热门话题, 这篇论文提供了针对您的问题的算法。

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

摘要:

提出了一种在二维n×n文本中搜索二维mxm模式的算法。 它平均执行的比较小于文本的大小:n ^ 2 / m使用m ^ 2额外空间。 基本上,它仅对文本的n / m行使用多个字符串匹配。 它最多运行2n ^ 2次,并且接近许多模式的最佳n ^ 2时间。 它稳步扩展到与字母无关的算法,具有类似的最坏情况。 实验结果包括实际版本。

如果您愿意预处理矩阵并且对同一矩阵有很多查询,则可以使用非常快速的算法。

查看多媒体数据库研究小组关于代数数据库的论文(波恩大学Clausen教授)。 以本文为例: http : //www-mmdb.iai.uni-bonn.de/download/publications/sigir-03.pdf

基本思想是推广反转列表,因此它们使用任何类型的代数变换,而不是像普通的反向列表那样只在一个方向上移位。

这意味着只要您需要对输入数据进行的修改可以用代数方式建模,这种方法就可以工作。 具体而言,可以检索以任意数量的维度,旋转,翻转等进行翻译的查询。

本文主要是针对音乐数据展示这一点,因为这是他们的主要研究兴趣,但您可能能够找到其他人,这些人也展示了如何使其适应图像数据(或者您可以尝试自己调整,如果你理解它的原理非常简单)。

编辑

如果您正确定义它们,这个想法也适用于部分匹配。

如果你只需要将一个小矩阵与一个大矩阵匹配,就没有办法快速完成。 但是如果你需要针对大矩阵做很多小矩阵,那么就预处理大矩阵。

一个简单的例子,精确匹配,对一个巨型矩阵的许多3×3矩阵。

创建一个新的“匹配矩阵”,大小与“大矩阵”相同,对于大矩阵中的每个位置,计算每个x的3×3散列,y到大矩阵中的x + 3,y + 3。 现在,您只需扫描匹配矩阵以获得匹配的哈希值。

您可以使用专门的哈希函数实现部分匹配,这些哈希函数为具有相同部分匹配属性的事物提供相同的哈希。 棘手。

如果要进一步加速并为其创建内存,请为匹配矩阵创建哈希表,并在哈希表中查找哈希值。

3×3解决方案适用于任何3×3或更大的测试矩阵。 您不需要拥有完美的哈希方法 – 您只需要拒绝大多数不匹配的东西,然后对哈希表中的潜在匹配进行完全匹配。

我想你不能只想到子矩阵的某些方法,但你可以优化你的搜索。

例如,给定矩阵A MxN和子矩阵B mxn,您可以这样做:

SearchSubMatrix (Matrix A, Matrix B) answer = (-1, -1) Loop1: for i = 0 ... (Mm-1) | | for j = 0 ... (Nn-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维。