The Triangles Project

The goal of the Triangles Project is develop a program that takes an image as input and outputs its best replication of that image using **N** triangles.

In addition to the final program I personally hope to achieve three things:

1. Learn GPU programming.
2. Improve my understanding of genetic algorithms.
3. Improve my understanding of machine learning.

A prototype of this program (that I built some months ago) was used to generate the images of a red panda using 100, 250 and 500 triangles respectively.

Although the image is rudimentary, I think it shows promise that an improved version of this program can be built. The improvements I’d like to add are directly correlated to my learning goals listed above.

First, I’d like to speed up the execution of the program. I think this can be done by using a GPU to compare the images and draw the triangles (by far the most computationally intensive step in each generation). This could speed the program up by up to ~250x by my naive and optimistic estimation.

Second, the original program uses a very simple genetic algorithm. So simple that I’d say it is closer to Stochastic Beam Search than a true genetic algorithm. This is because its crossover step is *pretty lame* and of dubious value. In fact the 500 triangle red panda rendering uses no cross over at all. To correct this, I’d like to implement a 2-tier genetic algorithm, one for the ‘artists’ (strategies on how to to adjust triangle positions) and one for the ‘canvases’ (this list of triangles from which the rendered image is drawn).

Lastly there are many, many parameters that I wish to include in my program. Unfortunately I don’t know what are the ‘best’ parameters. I’ve played around with my prototype, adjusting certain parameters and taking notes of how this affects accuracy and effort. However I’d like to automate this process, with the program running the same image many times and by the end suggesting a best set of parameters. My hope is that over many images a good general set of parameters will emerge.

As I build this program I’ll update this blog with my design decisions, findings and of course lots of triangle images and animations!