“Grammar inference” for 2-D images

Question

Others have studied the following question: given a set of words $w_1,w_2,\dots \in \Sigma^*$, find a regular grammar (or a context-free grammar) that generates all of those words, is "natural" in some sense, and is as small as possible. In the special case where we have a single word $w \in \Sigma^*$, if the grammar generates exactly the word $w$, we can think of this as a compression algorithm that compresses the word $w$ to the grammar produced by this inference algorithm. Of course, each word is a one-dimensional sequence of symbols.

Now consider a two-dimensional array of symbols, say an array $A[1\ldots m, 1\ldots n]$ where each $A[i,j] \in \Sigma$. Is there any corresponding algorithm that could be used to find a grammar of some sort that generates $A$? Could this be used as a compression algorithm for compressing images, i.e., one that compresses a two-dimensional image to its corresponding grammar?

I'm not even sure what kind of grammar would be suitable. Is there an analog of regular or context-free grammars that generates a two-dimensional output instead of a one-dimensional output? I've done some searching, and haven't found anything obvious.

• Of course we could linearize the image, by concatenating the rows of the array, to get a one-dimensional sequence, and then apply any of the above techniques -- but this does not preserve locality. In other words, elements that are vertically adjacent will no longer be near each other after this transformation. So this transformation does not seem useful.

• Perhaps we could build a quad-tree over the array and then consider tree automata over that quad-tree? Is there a grammar inference algorithm for such tree automata over quad-trees?

• Alternatively, it seems like there might be a natural extension of context-free grammars to two-dimensional output: just make the right-hand side of each rule be a two-dimensional array of terminals and non-terminals of arbitrary size, and then apply the obvious generation algorithm. Do such grammars have a standard name? Is there a grammar inference algorithm for such grammars?

Answer 1

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.