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

问题描述

我正在考虑一种在更大的 mtrix M 中查找子矩阵 m 的快速方法.我还需要确定部分匹配.

I was thinking of a fast method to look for a submatrix m in a bigger mtrix M. I also need to identify partial matches.

我能想到的几种方法是:

Couple of approaches I could think of are :

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

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

I believe this is quite frequently encountered problem in image processing and would appreciate if someone could pour in their inputs or point me to resources/papers on this topic.

较小的例子:

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

Bigger matrix:
1 2 3 4 5
4 5 6 7 8
9 7 6 5 2

较小的矩阵:
7 8
5 2

Smaller Matrix:
7 8
5 2

结果:(row: 1 col: 3)

Result: (row: 1 col: 3)

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

An example of Smaller matrix which qualifies as a partial match at (1, 3):
7 9
5 2

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

If More than half of pixels match, then it is taken as partial match.

谢谢.

推荐答案

我建议在 Internet 上搜索2d 模式匹配算法".你会得到很多结果.我只会链接谷歌上的第一个点击，一篇论文，为您的问题提供了一种算法.

I recommend doing an internet search on "2d pattern matching algorithms". You'll get plenty of results. I'll just link the first hit on Google, a paper that presents an algorithm for your problem.

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

You can also take a look at the citations at the end of the paper to get an idea of other existing algorithms.

摘要:

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

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.

这篇关于在 M X N 矩阵中查找 m x n 子矩阵的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持html5模板网！