c++ - Fastest way to Find a m x n submatrix in M X N matrix

Question

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. Optimize the normal bruteforce to process only incremental rows and columns.
2. May be extend Rabin-karp algorithm to 2-d but not sure how to handle partial matches with it.

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.

EDIT: Smaller example:

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

Smaller Matrix:
7 8
5 2

Result: (row: 1 col: 3)

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.

Thanks.

Answer 1

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.

The abstract:

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.