在 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 :
- 优化普通暴力破解，仅处理增量行和列.
- 可能会将 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.
相关文章