## Making pictures using triangles (an exercise in stochastic hill-climbing algorithms) – Part 1

### posted on: Tuesday, December 3, 2013 by Chase Stevens

In this blog post, I’d like to introduce a project I’ve been tinkering on and off (mostly off) with for the past few months. The idea behind the project was pretty simple: to write a program which, given a set number of triangles and a blank canvas, adjusts the coordinates, color, and transparency of the triangles over time in an attempt to replicate a given image. There were two primary motivations behind my project, at least initially:

• to create (lossily) compressed versions of the source images that still look decent (and might even reduce image noise), and
• to have those compressed versions themselves be scalable to any size.
While I found that my program met these goals fairly adequately, what I was both surprised and delighted by was its aesthetically pleasing and almost artful representations of the source images. Therefore, before delving into the more technical aspects of the implementation, I’d like to present a few samples of the program’s results. The first example uses 50 triangles, while the other two use 100.

#### Example 1

 Output at iteration 9,500Image size: 3.38KBCompressed SVG size: 0.88KB Output at iteration 50,000Image size: 2.95KBCompressed SVG size: 0.88KB Output at iteration 1,293,000Image size: 2.74KBCompressed SVG size: 0.88KB Original imageSize: 6.53KB
This was one of the very first tests of my program, and is in my opinion also one of its most successful and impressive recreations. As you might infer from the stark difference between iteration 9,500 and 50,000 and moderate difference between iteration 50,000 and 1,293,000, the program’s output approaches complete similarity to the target image roughly logarithmically with each iteration; this trend is plotted in the graph below.
The corresponding vector for the final result (below) is actually noticeably less accurate than the JPEG posted above, because the program has exploited JPEG artifacts as well as the specific dimensions of the target in creating its reproduction. When the triangles are used to create an SVG, these artifacts are no longer present and the image becomes less faithful.
One of the most noticeable issues with the program’s image is that it entirely fails to capture the eyes in the source image. I explored various methods of solving this issue, which I will discuss in a later post on implementation. Overall, though, I thought that the program produced a more pleasing (if less accurate) image, kilobyte-for-kilobyte, than comparable "traditional" compression techniques (as pictured below), especially if enlarged.
 Program’s final outputImage size: 2.74KBCompressed SVG size: 0.88KB Original imageSize: 6.53KB Image compressed with Paint.NETSize: 1.91KBCompressed size: 1.58KB
To finish off this example: a video of the program’s progress in making its output played at 30 frames per second, with frames produced every 500th iteration. The "jumps" in activity visible at 0:23 and 0:56 are instances when I made updates to the program.

#### Example 2

 Output at iteration 737,500Image size: 4.03KBCompressed SVG size: 1.54KB Original imageSize: 3.51KB
This example yet again highlighted an issue with the image similarity evaluation methods employed by the program. While many aspects of the source image are replicated with high fidelity, the facial features of Christian Bale are not. Below again is a video of the program’s progress over time.

#### Example 3

 Output at iteration 769,500Image size: 3.27KBCompressed SVG size: 1.54KB Original imageSize: 12.9KB
In this instance, I experimented with another evaluation method that incorporated a saliency comparison between the target image and the output. Although the results presented here seem promising, other tests using the method were lacklustre, especially given that the saliency map calculations added a lot of processing time to each iteration.

In my next post, I’ll detail the specifics of the program. In the meanwhile, the program itself can be downloaded here; it requires numpy and PIL to run.