Generating Images from Regular Expressions

There is an update to this post, which includes colors: https://ssodelta.wordpress.com/2014/03/25/creating-colored-images-from-regular-expressions/

Source code complete with Javadoc can be found at: http://pastebin.com/ccRK75aq

This post will detail a method for using regular expressions to generate images.

A regular expression is an array of characters, which represents a series of instructions, which for any input either matches or doesn’t match. For a simple example, the regular expression

`ssodelta`

Only matches the string ssodelta. This makes sense, but we can do pretty nice things with regular expressions. If we for example write

`ssodelta|delta`

Then the regular expression either matches ssodelta or the string delta. This is because the vertical bar | represents the symbol or. We also have so called quantifiers, the most important of which is the kleene star *.

`sso(delta)*`

The parentheses group strings together, like regular parentheses in mathematical expressions (2+4)*3, for example. The kleene star * means zero or more, meaning that there can be zero or more delta and it will still match the regular expression. A few matches include ssodelta, ssodeltadelta, ssodeltadeltadelta and so on…

I won’t completely detail regular expression, but if want to read up on it, I suggest close-reading the wikipedia article on the matter, but the bottom line is that regular expressions are really cool. But how can they be used to generate images?

Consider a completely square image, which is divided into 4 quadrants:

We can refer to each of these four quadrants by their numbers 0,1,2,3, and we can further divide these quadrants into four numbers, and label them accordingly.

But what does this have to do with regular expresssions? Well, we can have a regular expression, which only uses the characters 0,1,2,3 and every string adresses an area in this area. For example, the string 022 represents the area marked with red:

We can decide on a resolution n, and generate all strings of length n, parse them through a regular expression, and if it matches, paint it black. For example, the regular expression (0|2)(0+1+2+3)* generates the following image (for any resolution >= 2):

This is because the regular expression only matches if the cell begins with a 0 or a 2, which is why the 0th and the 2nd quadrants are painted black, and the rest aren’t.

We aren’t limited to boring checkers though, if we feed the generator the regular expression (1+2+3)*0(1+3)*0(0+1+2+3)*:

Notice the self-similarity in the image, that’s because this image is actually a fractal.

Here is a gallery of other images generated using this technique:

Notice how often triangles appear in these images.

Although the .java file has an included Javadoc, here’s how you use it to generate images:

```Generator g = new Generator(RESOLUTION, IMAGE_SIZE);
g.generateAndExport("REGULAR_EXPRESSION", "EXPORTED_FILE_PATH.png"); //Must be a .png file```

If you prefer Python code, check out Jack Morris’ post on the same subject, where he implements it in Python: http://jackm.co.uk/posts/2014/03/25/Using-Regular-Expressions-To-Generate-Images/

13 thoughts on “Generating Images from Regular Expressions”

1. RedditBait says:

Cool program. The first regex creates a half black and half white rectangle for me.

And for pete’s sake don’t post such a cool program like this on pastebin, it makes you look sloppy.

1. Hmm, it’s because the program apparently converts it to [0|1][2+1+3+0]* first. I’ll make a fix ASAP.

Edit: It’s because it maps the entire string unto 0,1,2,3 if it encounters a single invalid character, and 4 is not valid, so it converts it. Try (0|2)(0+1+2+3)* instead 🙂

And I don’t personally consider that sloppy, I prefer to be able to read the source code without downloading it as a .java file first, but hey – that’s just my personal

1. RedditBait says:

Most people use github’s gist service you should try it.

It works now.

2. Thanks 🙂 I’ll look into it

2. inetic says:

Cool idea and nice images. Few nitpicking though. First one is that the Kleene star is defined as “zero or more times”.

http://en.wikipedia.org/wiki/Kleene_star

The second one is that you’ve not defined what the + and | symbols mean. When using e.g. PERL, or grep, the + sign usually means “one or more times” and | means “or”.

1. Thanks for the feedback 🙂 I’ll correct the mistakes ASAP.

1. Hey nice! I have referenced your article in my post, if anyone would be more interested in Python code.

1. jackmorris10 says:

Thanks! (By the way, I’m Jack Morris, not Morrison :P)

3. Max says:

This is an instance of a Language-Restricted Iterated Function System (LRIFS) which I believe were introduced by Prusinkiewicz and Hammel — where you’ve divided each square into four equal subsquares, they allow a variety of transformations. Example 1 (illustrated in figures 5b and 6b) in their paper “Escape-time visualization method for language-restricted iterated function systems” (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.1705&rep=rep1&type=pdf) simulates your technique closely.