During my masters, I took a course called Physics of Algorithms – this is largely where I developed an interest in nature inspired algorithms. For my exam, I worked on an algorithm that could render images using polygons. This is not an original idea – Roger Johansson was one of the first to do this back in 2008. However at the time, I had not come across existing versions that would successfully run in Python 2.7 or 3.6, and the original program was written in .NET 2.0/VS.NET 2008. I therefore decided to recreate his project in Python for my final report, which you can take a look at here (all code for the program is included in the report – I will not reproduce it in this post).
Details of the original program
Johansson does not reveal much about the parameter settings in his original program – and I didn’t understand the available source code binaries. I also didn’t have much interest in simply replicating his original code, i instead used the immediately available information as a guideline for my own implementation:
- The image consists of 50 semitransparent polygons
- Population size was only 2: a “current” candidate, and a mutation of the current candidate
- It took 3 hours to obtain the following result
With a population of only 2, it is arguable that Johansson does not truly employ the principles behind genetic programming and is rather solving the problem using hill climbing. This discussion isn’t relevant right now, but I acknowledge that we might not entirely be employing genetic programming.
Genetic programming is a metaheuristic that revolves around the propagation and modification of genetic material over time. Here, the genetic material should obviously be some string or array which describes the polygons
Performance of my solution
I’ll let you know straight away that I never managed to produce as impressive results as Johansson, but I did obtain recognisable results. In the following are a couple of comments on what affects the final solution. The main issue in this project was the time it took to to produce images – my program never performed at the speed of Johansson’s, and I never obtained images
In the developing phase, the target picture of Mona Lisa was 800×1192 px, and it took >10 seconds to produce 10 images. Using a smaller version at just 270×402 px significantly improved the speed so that 10 images were produced in <10 seconds. I finally decided to use a small cut out of Mona Lisa of just 150×184 px.
Triangles or polygons?
I personally couldn’t prove that it was beneficial to use triangles over polygons. It seemed to depend more on the parameter settings than some intrinsic quality, one shape should possess more than the other. All test were therefore performed in order to compare – take a look for yourself below and see what you think.
Initial test performance
The initial runs tested the performance after 10,000 iterations just to see if there was promising convergence towards the target picture.
Using either 50 triangles or 50 polygons and a mutation rate of 5%, the program converged to two pictures showing resemblance to the most predominant characteristics of the target picture (the chest area, the background, and the general face and hair traits, although not with impressive detail. These runs took about 50 minutes each on the computer I used.
50 polygons 5% mutation rate 10,000 iterations
Mutation rate and number of polygons
I realised quickly that my solutions stopped progressing much after a “short” while. To overcome this within my time frame, I tried to change both the number of polygons, and the mutation rate, but never ended up settling on anything. To begin with, the solutions for 50 polygons had not progressed much at 65,000 iterations:
50 polygons 5% mutation rate 65,000 iterations
However, it quickly seemed to be a general problem.
50 polygons 3.5% mutation rate 100,000 iterations
50 polygons 3.5% mutation rate 240,000 iterations
Should we use more polygons?
100 polygons 3.5% mutation rate 120,000 iterations
Maybe even more?? This is actually the closest I managed to get to the target picture within the time frame.