最快的方式找到在m×n矩阵amxn子阵 [英] Fastest way to Find a m x n submatrix in M X N matrix
问题描述
我在想一个快速的方法来寻找一个子矩阵米的更大的mtrix 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 :
- 优化了正常的暴力破解仅处理增加的行和列。
- 在可能被延长拉宾，卡普算法2-D，但不知道如何处理部分匹配它。
我相信这是相当经常遇到的问题，在图像处理和将AP preciate如果有人能浇在他们的投入或指向我的资源/篇关于这个话题。
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
结果：（行：1列：3）
Result: (row: 1 col: 3)
小矩阵的哪资格作为一个部分匹配于（1,3）的一个例子：
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.
感谢。
推荐答案
我建议做的2D模式匹配算法的互联网搜索。你会得到很多结果。我只是链接先打上谷歌，的一文是presents的算法您的问题。
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.
摘要：
这是算法用于搜索在二维nxn的文本的二维MXM图案是presented。它执行上比文本大小的平均水平低的比较：N使用平方公尺额外的空间^ 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×n矩阵amxn子阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
