2D pattern search algorithms

Question

I need to learn about 2D pattern searching algorithms. Tips and links greatly appreciated.

More to the point:

Given a matrix of M[m,n] with values in K
example

000000000000
000001000000
010100010010 = M, K = {0, 1}
010100010001
101111010111

and a matrix L[i, j] with values in K + {X} representing a "shape"
example, the shape of letter "L"

1X
1X = L
11

What algoritms can answer to the following questions:

1. Can L be found in M ?
2. How many times L can be found in M (disjunctive L's, no common pieces (1's or 0's))
3. How many times L can be found in M (can have common pieces (1's or 0's))
4. How many times L, and K (K is defined similarly like L, K != L) can be found in M (disjoint) etc.

The language of implementation is to be JavaScript, but any other will do.

EDIT Also found this PDF.

Answer 1

Take a look at this presentation it should give you a basic knowledge.

The X symbol can be treated like wildcard so it will always give a match.

Don't know what exactly you mean by

How many times L, and K (K is defined like L) can be found in M (disjoint) etc.

K stands for alphabet or shape (like L)?

Problem of determining maximum number of disjoint matches will be harder. The approach would be following:

• find all possible matches
• create graph where node represents matches and edge represents that two matches have common field.
• now you have to find maximum independent set in this graph (wiki) - set of vertices in a graph, no two of which are adjacent so problem constraints are not violated.

EDIT: If your shape is L the match can be computed efficently. Create tables for columns and rows and for each cell check if there is a match upwards and to the right.