An enigma in triangles

After finishing, tidying up and checking in my code for evolving minimal sorting networks, I decided to move on to the more aesthetically pleasing challenge of evolving images out of triangles.

This experiment was first carried out back in 2008 by Roger Johansson. You can read his blog post and results in full, but the essence is that he took a black background then iteratively added polygons to it, mutating their positions, shapes and colours, until they looked like an image of the Mona Lisa.

Each of the polygons could have three or more sides, could be partially transparent and were made of a single colour. The fitness function was the sum of differences between each pixel of his evolved image and a stock image of the Mona Lisa i.e. the distance in colour space from the target pixel. His population had a single member, which was only replaced if its single offspring  was of higher fitness (often termed 1+1 evolution). He also limited his image to using 50 polygons.

After 904,314 generations, this was the result (see his post for snapshots of her lineage):

screen-shot-2016-10-08-at-12-02-37

Since he made his post, several people have provided online Mona evolvers so we can all have a go at evolving our own images. You should go and have a play here or here (or anywhere else a simple Google search sends you).

Experimental setup

To implement an image evolver into my system (currently named EvoKit), I needed a way to render a list of triangles and compare the result to some target image. I initially opted for OpenGL as it’s cross-platform, written in C, an industry standard and I’ve used it before. However, it’s also relatively low-level and doesn’t come with any sort of portable windowing system to allow me to display the results to screen. To do the heavy lifting for me I ended up going with SFML, as it’s relatively lightweight (one library for each component you need out of graphics, windows, audio etc), cross-platform, easy to use and you can do direct calls to OpenGL if you need to (thanks to my friend Daniel for this suggestion).

The phenotype of the individuals being evolved was an array of triangles, with each vertex having a 2D position and a colour. To start with I made each triangle a single colour (including level of transparency). Mutations were to add a triangle, remove a triangle, move a single point of a triangle or change the colour of the whole triangle.

To aid evolution, each triangle is tiny when added (only taking up a couple of pixels in each direction), completely transparent and coloured to black (black and invisible being totally different to white and invisible, of course). A good rule of thumb is that any mutation should only have a small effect on the fitness of the individual. Adding a tiny, transparent triangle has exactly zero effect on the fitness.

To match Roger’s experiment, I also started off with a black background and had one child per generation, from a stable population size of one. I also only had one mutation per child (which essentially makes the algorithm hill-climbing).

The following are a series of snapshots, doubling the number of generations between images (starting with generation 8 and ending with generation 2,097,152). Click on any image to expand it.

While Roger had 50 n-sided polygons, I allowed up to 1,000 triangles. After that, the system would have to remove a triangle before adding another one.

Here’s a larger version of the final image after 2 million generations:

2097152

While the initial results seemed passable, it’s hard to compare against Roger’s original attempt without knowing his exact setup. Looking at the latest version of his source code, the polygons maxed out at 10 sides, though whether that reasonably equates to 8 triangles or less or otherwise, I’m not exactly sure.

My results also look more colourful than his. From his project (available here) it looks like his target image is quite sepia toned and less varied in colour, which undoubtedly makes it easier to evolve. I do think my 1,000 triangles gave me an unfair advantage over his 400-ish, because: maths.

A little more freedom

While the initial results were reasonable (and had a nice “smashed glass” effect during evolution), I thought I could do better using a few extra pieces of easily available functionality. Firstly, I changed the triangles so that each vertex could have a different colour. OpenGL then nicely interpolates between the colours for every pixel inside the triangle, giving an effect like this:

triangle

Each corner can also have its own transparency setting, so the triangle can fade in or out between vertices. I also let the evolver mutate the background colour of the image, black not always being the most suitable colour.

Here’s the result of generations 8, 16, 32….2,097,152:

The chance of changing the background for any given child was pretty small (as it’s something that isn’t of much use after the first few generations). It looks like it settled on a final colour at around 64,000 generations.

Comparing the final result from my previous run with the new run, it’s a definite improvement:

2097152           2097152

Everything looks smoother, with less harsh lines and colour gradients (no surprise there). The difference in cost is that the left hand image has 1,000 triangles, each with three positions and one colour, totalling 10k of data. The image on the right has the same number of triangles, but each one has three colours (one for each vertex), totalling 18k of data (if you want a very slow compression algorithm with worse results than a similarly-sized jpg, then I have some code to sell you)

Then I left it running overnight to 8 million generations. Here’s the result with the original image to compare it to:

mona_lisa_crop           8388608

This version gave a few subtle improvements around the face, but mostly around the edges of the image. Definitely a pleasing result. From a metre or so away, I can’t distinguish between the two (people with better eyesight might have something to say about that).

As discussed earlier, it’s hard to know how to compare Roger’s original result with 50 n-sided polygons, with my 1,000 triangle attempts. So I thought it only fair to produce examples with a variety of number of triangles. The following have 100, 200, 300, 400 and 500 triangles in them (click to expand).

Here’s Roger’s original again:

screen-shot-2016-10-08-at-12-02-37

 

Next I was inspired by a couple of posts on Facebook to go a little more one dimensional.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s