18

我正在考虑一种在更大的矩阵 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) 处有资格作为部分匹配的较小矩阵的示例：
7 9
5 2

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

谢谢。

4

4 回答 4

2

我建议对“二维模式匹配算法”进行互联网搜索。你会得到很多结果。我将仅链接 Google 上的第一次点击，这是一篇针对您的问题提出算法的论文。

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

摘要：

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

于 2012-05-10T16:10:03.663 回答
1

如果您愿意对矩阵进行预处理并且您对同一矩阵有很多查询，则有非常快速的算法。

查看多媒体数据库研究小组（波恩大学克劳森教授）关于代数数据库的论文。看看这篇论文，例如：http ://www-mmdb.iai.uni-bonn.de/download/publications/sigir-03.pdf

基本思想是推广倒排列表，因此它们使用任何类型的代数变换，而不是像普通倒排列表那样仅在一个方向上移动。

这意味着只要您需要对输入数据进行的修改可以通过代数方式建模，这种方法就可以工作。这特别是可以检索在任意数量的维度中翻译、旋转、翻转等的查询。

该论文主要针对音乐数据展示这一点，因为这是他们的主要研究兴趣，但您可能会找到其他人，它们也展示了如何将其调整为图像数据（或者您可以尝试自己调整它，如果您理解原理很简单）。

编辑：

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

于 2012-05-10T14:27:08.380 回答
0

如果您只需要将一个小矩阵与一个大矩阵进行匹配，则无法快速完成此操作。但是如果你需要对大矩阵做很多小矩阵，那么就对大矩阵进行预处理。

一个简单的例子，精确匹配，许多 3x3 矩阵与一个巨型矩阵。

制作一个新的“匹配矩阵”，大小与“大矩阵”相同，对于大矩阵中的每个位置，为大矩阵中的每个 x,y 到 x+3,y+3 计算一个 3x3 散列。现在您只需扫描匹配矩阵以查找匹配的哈希值。

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

如果您想进一步加快速度并为其提供内存，请为匹配矩阵创建一个哈希表，并在哈希表中查找哈希值。

3x3 解决方案适用于任何 3x3 或更大的测试矩阵。您不需要完美的哈希方法——您只需要能够拒绝大多数错误匹配的方法，然后对哈希表中的潜在匹配进行完全匹配。

于 2012-06-22T16:41:29.877 回答
0

我认为你不能只用某种方法猜测子矩阵在哪里，但你可以优化你的搜索。

例如，给定一个矩阵 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 个维度。

于 2015-12-06T15:30:43.220 回答