Using Regular Expressions To Generate Images 25 Mar 2014

I came across this post today describing an interesting method of producing monochromatic images from regular expressions, and I decided to reimplement it in Python whilst changing a few details. I’m also going to throw in a brief explanation of regular expressions, all for free!

# Regular Expressions (briefly)

(See Wikipedia for more detail)

Regular expressions are strings that can be used to accept or reject other strings, with the set of all of the strings that a regular expression accepts being the language defined by that regular expression. These languages are known as regular languages. Every regular expression defines a single regular language, however each regular language can be defined by many regular expressions. Regular expressions are also declared over a specific alphabet, which is the set of all characters which can make up strings in the language. For our examples below, the alphabet is the set of alphanumeric characters.

Regular expressions themselves look daunting, but actually have a simple structure that specifies the makeup of strings that are accepted by that expression. In the simplest case, a regular expression comprised of a string containing no special characters (discussed soon) will only accept itself. For example, the regular expression `Ringo` defines the regular language `{Ringo}` as it accepts only that string.

Regular expressions start to get interesting when we introduce the previously mentioned special characters:

• `|`, which means OR. `Ringo|Charlie` defines the language `{Ringo, Charlie}`.
• `*`, the Kleene Star. It indicates that the preceeding portion of the regular expression may be repeated multiple times or ommitted completely. `Dogs*` defines the language `{Dog, Dogs, Dogss, ...}`.

Notice above how `*` binds to individual characters, whilst `|` binds to entire strings. Parentheses can be used for grouping in the usual way, permitting complex regular expressions to be constructed.

Therefore, over the alphabet `{0, 1}`,

``````(0(01)*)|(11*)
``````

defines the language `{0, 001, 00101, ..., 1, 11, 111, ...}`.

# Regular Expressions in Practise

Whilst the above specifies the strict definition of regular expressions, when used in practise for string matching other special characters have been introduced to make them easier to work with. Some of these are listed below (the exact extensions and their semantics is dependent on the specific implementation).

• `[...]` accepts any character within the square brackets.
• `.` accepts any character in the alphabet.
• `+` accepts the preceeding portion atleast once. `a+` defines the language `{a, aa, aaa, ...}`.
• `?` accepts the preceeding portion, or allows it to be ommitted. `Dogs?` defines the language `{Dog, Dogs}`.

These extra characters are syntactic macros for standard regular expression statements, and hence do not add extra string matching power. For example, `a+` is equivilent to `aa*`. This is not true of all extensions that have been made to regular expressions; backreferences can not be represented by raw regular expressions as defined above.

Many web tools which let you visualise the structure of regular expressions exist, which can help when writing your own. I recommend Debuggex.

# Image Generation

Now we can move on to the image generation. First, consider subdividing a rectangular image into quadrants such that we can label them `0` to `3`, clockwise from the top left.

This labelling can be continued further, allowing us to uniquely label portions of a square image with string identifiers over the alphabet `{0, 1, 2, 3}`. The number of times that we subdivide the image is referred to the resolution. For example, the image below has a resolution of 2 (just considering the top left quadrant), and as a result the region identifiers are two characters long.

We can then define monochromatic images, using these identifiers to specify regions which should be shaded in. The image below has resolution 2, with the regions `00`, `13` and `31` shaded in.

Evidently, the higher the resolution, the more detail can be expressed in the image.

From this shading scheme, we can use regular expressions to specify which areas of the image we want to shade, hence describing the image completely. This is done by supplying a regular expression that accepts region identifiers over the alphabet `{0, 1, 2, 3}` for regions that should be shaded, rejecting those that should stay clear.

# Examples

One of the simplest examples, with a resolution of 1, the regular expression `0|2` shades region `0` and region `2`.

A simple stripe is actually relatively complicated to generate using this system. This was produced using the regular expression `((0.*)|(1|3))*` with a resolution of 10.

A fractal, generated using `(1|2|3)*0(1|3)*0.*` with a resolution of 10 (idea taken from the post referenced earlier, which also has some other nice examples of what’s possible).

# Implementation

Python with Pillow were used for the implementation. Two main components were required - a way of converting pixel co-ordinates to the region identifiers discussed, and a way to use this to generate the image. Here is the implementation of the former (note that the image is initially sized so that each region is one pixel in size).

Wrapping my head around that was probably the trickiest part of the implementation, and I’m still not convinced that it’s the best way to do it.

Then, a function `generate(regex, resolution, size, output_file)` is implemented, which uses `get_region_identifier()` for each pixel of the image, building up the data before shifting it into an actual image object, resizing it if required and saving it to disk.

The full implementation can be found in a Gist here.