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.

Solution 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.

Solution 2

There are very fast algorithms for this if you are willing to preprocess the matrix and if you have many queries for the same matrix.

Have a look at the papers on Algebraic Databases by the Research group on Multimedia Databases (Prof. Clausen, University of Bonn). Have a look at this paper for example: http://www-mmdb.iai.uni-bonn.de/download/publications/sigir-03.pdf

The basic idea is to generalize inverted list, so they use any kind of algebraic transformation, instead of just shifts in one direction as with ordinary inverted lists.

This means that this approach works whenever the modifications you need to do to the input data can be modelled algebraically. This specifically that queries which are translated in any number of dimensions, rotated, flipped etc can all be retrieved.

The paper is mainly showing this for musical data, since this is their main research interest, but you might be able to find others, which show how to adapt this to image data as well (or you can try to adapt it yourself, if you understand the principle it's quite simple).

Edit:

This idea also works with partial matches, if you define them correctly.

Comments

[amit]

What are the restrictions the smaller matrix needs to obey? If none exist - just take the first m x n submatrix,...

[harold]

That's not a restriction. Just take the upper left square then.

[Michael Foukarakis]

The link is now dead, unfortunately. Is there any chance to update it, or include its title for future reference?