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:

img1

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.

img2

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:

img3

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):

test

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)*:

really_large_triangle_fractal

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:

also-cool-fractal bars  dots pik

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/

Advertisements

Generating Mozart from Markov Chains


Source code: https://dl.dropboxusercontent.com/u/19633784/AlMuGe.zip 

This post will detail a method of generating music from sampling MIDI-files. We’ll introduce an algebraic structure called a Markov chain, and use it to make our own MIDI-files.

A markov chain is a system of nodes connecting by edges. Each edge has an associated probability with it, which describes the probability that the system will progress to that node next round. Consider this graphical example:

200px-Markovkate_01.svg

This is a markov chain composed of two nodes, E and A and four edges – E to EE to A, A to A, A to E. If we start on node E, there is a 0.7 probability that we will progres to node A, and a 0.3 probability that we stay on node E. Sounds simple, right?

The basic concept is simple really, and that’s all we really need to utilize this system in our program, but there is in fact a lot of advanced mathematics regarding markov chains, but I won’t detail it.

Now, consider a system with twelve nodes, one for each musical note, and 144 edges connecting all the nodes to each other, but where do we get these probabilies from?

Introducing sampling. The program contains a module called midcrawler, which goes to a website, crawls it for .mid-files and constructs a large markov chain, which is a representation of the midi-files, it’s sampled. I have also included the feature of loading/saving these samples, so it’s not necessary to sample the entire webpage for every single generated bit. From this, it starts on a random note and starts traversing the system, generating the song for steps.

The rhythm however, is not generated. Upon using the program, you need to supply it with some rhythm information. There are some obvious problems with this technique though, it is not limited to a scale, so it may sometimes use a tritone or be very dissonant, making it sound less than good.

I used the program to sample the following page containing a bunch of Mozart .mid files: http://www.midiworld.com/mozart.htm and made the following .mid file:

https://dl.dropboxusercontent.com/u/19633784/mozart.mid

Personally however, I’m not able to play this MIDI file, so I converted it to an MP3 file, which everyone can play:

https://dl.dropboxusercontent.com/u/19633784/mozart.mp3

It doesn’t sound very Mozart-ish, but it’s very interesting to listen to, and I’m surprised that it doesn’t sound worse.

Here is an explanation of how to use the program, given the source code:

 Crawler c = new Crawler();
 c.crawlPage("URL_OF_WEBPAGE_CONTAINING_MIDI_FILES");
 c.processInternalData();
 Parser p = new Parser(c.getContents());
 p.parseContents();
 Generator g = new Generator(p.getNoteMatrix());
 g.generateSequence(LENGTH_OF_MIDI_FILE, "DESTINATION_PATH");