"Grammar inference" for 2-D images
I'm researching related ideas using context-free grammars at the moment, so I might be able to give you some things to think about by describing the approach I've taken (which is just one approach).

Firstly, I use rules that describe the production of multisets and not sequences (or trees in fact). So whereas a conventional production rule:

$s \rightarrow abc$

would produce the (ordered) string 'abc', the rule below would produce an unordered set of the same symbols

$s \rightarrow \{a, b, c\}$

In such a grammar non-terminal symbols can operate as variables in the same way as sequential grammars, e.g.:

$ 
s \rightarrow \{X, c\}\\
X \rightarrow \{b, a\}
$

Now, going back to 2D images. Perhaps surprisingly, it turns out you can encode an image as an (unordered) collection of non-terminal symbols, each producing a (unordered) multi set that describes each pixel. In your question you describe a set of terminal symbols that describes that possible values of each pixel, let's say $\Sigma=\{0,1\}$. I'm going to add to that 2 terminal symbols $x$ and $y$, each of which representing an offset of 1 pixel from the origin on each axis, so  $\Sigma=\{0,1, x, y\}$.

Now consider the pixel $A[2,2] = 1$. This can be encoded in the grammar scheme I describe using a multi set production:

$p \rightarrow \{x, x, y, y, 1\}$

So, you could encode a whole image this way. It's easy to imagine the amount of bloat you'd get in such a grammar. However, it is possible to compress the whole grammar by using a hierarchy of production rules that can be inferred. For example, take the derivation of the point $A[18, 9]=1$

Instead of:

$p \rightarrow \{x, \text{(repeat 17 more times)}, y, \text{(repeat 8 more times)}, 1\}$

you can have:

$p \rightarrow \{D, A, G, y, 1\}\\
A \rightarrow \{x, x\}\\
B \rightarrow \{A, A\}\\
C \rightarrow \{B, B\}\\
D \rightarrow \{C, C\}\\
E \rightarrow \{y, y\}\\
F \rightarrow \{E, E\}\\
G \rightarrow \{F, F\}\\
$

With of course the non-terminals $A$ to $G$ being reused to describe multiple points. So actually something that looks like it would be hideously inefficient can be compressed very efficiently. It is possible to easily infer such a grammar from a series of points (this is the subject of my research), using similar techniques as normal sequential grammar inference.

The cool feature of this type of grammar is it is possible for the grammar to encode complex patterns that are non-sequential (in this case graphical) in nature. 

This is all a work in progress but it might help you with your problem.