Uncategorized

Image rendering with polygons

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

If you don’t already know what a genetic algorithm is, I advise you to take a look at this post before reading on.

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
Roger's target image; a sepia version of the Mona Lisa.
Roger's final solution after 904,31 iterations.

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

Size matters

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.

monalisa_smaller

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
Using triangles.
Using polygons.

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
Using triangles.
Using polygons.

However, it quickly seemed to be a general problem.

50 polygons     3.5% mutation rate     100,000 iterations
Using triangles.
Using polygons.
50 polygons     3.5% mutation rate     240,000 iterations
Using triangles.
Using polygons.

Should we use more polygons?

100 polygons     3.5% mutation rate     120,000 iterations
Using triangles.
Using polygons.

Maybe even more?? This is actually the closest I managed to get to the target picture within the time frame.

300 polygons     5% mutation rate     100,000 iterations
Using triangles.
Using polygons.
300 polygons     5% mutation rate     400,000 iterations
Using triangles.
Using polygons.

169 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *