What is this?

A simulated annealing like optimization algorithm, a reimplementation of Roger Alsing's excellent idea.

The goal is to get an image represented as a collection of overlapping polygons of various colors and transparencies.

We start from random 50 polygons that are invisible. In each optimization step we randomly modify one parameter (like color components or polygon vertices) and check whether such new variant looks more like the original image. If it is, we keep it, and continue to mutate this one instead.

Fitness is a sum of pixel-by-pixel differences from the original image. Lower number is better.
Displayed fitness is now a percentage of how close the new image is to the original one (1-current difference/maximum difference). The best possible is 100%. This new fitness is normalized so that it's easier to compare different images and different sizes.

This implementation is based on Roger Alsing's description, though not on his code. There are probably some subtle differences in how the mutations are done, how the polygons are represented and how the fitness is computed as I tried to figure out how to have it running reasonably fast in JavaScript + <canvas> environment.

How does it look after some time?

• 50 polygons (4-vertex)
• ~15 minutes
• 644 benefitial mutations
• 6,120 candidates
• 88.74% fitness

• 50 polygons (6-vertex)
• ~15 minutes
• 646 benefitial mutations
• 6,024 candidates
• 89.04% fitness

• 50 polygons (10-vertex)
• ~15 minutes
• 645 benefitial mutations
• 5,367 candidates
• 87.01% fitness

• 50 polygons (6-vertex)
• ~45 minutes
• 1,476 benefitial mutations
• 23,694 candidates
• 93.35% fitness

• 50 polygons (6-vertex)
• ~60 minutes
• 1,595 benefitial mutations
• 28,888 candidates
• 93.46% fitness

• 50 polygons (6-vertex)
• ~120 minutes
• 1,966 benefitial mutations
• 50,500 candidates
• 93.89% fitness

• 50 polygons (6-vertex)
• ~4 hours
• 4,134 benefitial mutations
• 807,890 candidates
• 95.59% fitness
• Thanks to Sergei.

• 50 polygons (6-vertex)
• ~2 days
• 7,425 benefitial mutations
• 5,288,801 candidates
• 96.36% fitness
• Thanks to Julian.

• 1,000 polygons (12-vertex)
• ~7 days
• 21,135 benefitial mutations
• 8,143,969 candidates
• 97.12% fitness
• Thanks to Bogdan.

Does it work on all images?

It depends, success varies. The best seem to be color images with well defined features.

• 50 polygons (6-vertex)
• 4,358 benefitial mutations
• 227,852 candidates
• 95.97% fitness
• Thanks to Quialiss.
• Images from different runs.

• 50 polygons (6-vertex)
• 718+ benefitial mutations
• 22,440+ candidates
• 95.24% fitness
• Images from different runs.

• 100 polygons (6-vertex)
• 9,686 benefitial mutations
• 1,220,569 candidates
• 96.21% fitness
• Thanks to Steven.

• 100 polygons (5-vertex)
• 10,490 benefitial mutations
• 2,161,018 candidates
• 95.03% fitness
• Thanks to Asa, Will, Nic & Yuku.
• Images from different runs.

• 50 polygons (6-vertex)
• 6,280 benefitial mutations
• 683,806 candidates
• Thanks to alexs for the final image.
• Images from different runs.

• 100 polygons (5-vertex)
• 6,974 benefitial mutations
• 2,056,467 candidates
• 95.68% fitness
• Thanks to Yuku.

• 100 polygons (6-vertex)
• 6,557 benefitial mutations
• 44,212,346 candidates
• 99.43% fitness
• Thanks to Alex.

• 50 polygons (5-vertex)
• 8,031 benefitial mutations
• 1,099,366 candidates
• 96.14% fitness
• Thanks to Karol Masztalerz.

• 50 polygons (6-vertex)
• 4,296 benefitial mutations
• 2,404,942 candidates
• 97.6% fitness
• Thanks to Kyle.

• 50 polygons (6-vertex)
• 10,605 benefitial mutations
• 11,104,153 candidates
• 93.84% fitness
• Thanks to KRHAiNOS.

• 50 polygons (6-vertex)
• 11,147 benefitial mutations
• 1,021,165 candidates
• 95.04% fitness
• Thanks to Simon.

See also Firefox logo evolution video. Thanks to Brooss.

• Distributed computing effort: original image size 600px X 900px, divided into 24 parts each 150px X 150px
• 24 x 100 polygons (6-vertex)
• 109,438+ benefitial mutations (total)
• 8,243,441+ candidates (total)
• Fitness: min 95.01%, max 99.08%, mean 96.59%, median 96.65%
• Thanks to Agro momusuindo.net (Indonesia).
• Full resolution final image

• Multiple 50-polygon pieces, exported to SVG, joined in Illustrator
• Thanks to Antonio Ares.
• Full resolution final image

• 6,278 benefitial mutations
• 267,623 candidates
• 96.95% fitness

• 4,208 benefitial mutations
• 8,451,873 candidates
• 97.88% fitness

• 6,250 benefitial mutations
• 10,418,975 candidates
• 98.38% fitness

• 6,281 benefitial mutations
• 226,689 candidates
• 96.75% fitness
• Thanks to Marinka for South Park characters.

• 100 polygons (5-vertex)
• 7,310 benefitial mutations
• 5,430,510 candidates
• 96.53% fitness
• Thanks to Magnus Hansen.

• 95.79% fitness
• 1 day 9 hours
• Thanks to Christian Grosser.

What is DNA import/export?

Warning: Another experimental (that is not tested at all) feature. Most of the bugs should be fixed now.

Click Export DNA to copy polygon representation of the current best image to the clipboard. You can use it to save your optimization state, for example to send it to somebody by mail or post it on the web.

If you have such saved DNA string, you can later on paste it into the clipboard and click on Import DNA. This should reproduce the optimization state from the time it was saved via export.

Please note that DNA is independent of the original image. It means that if you used a custom image, you should also set this image (via image form) to reproduce a complete state. (Or you could play with switching images/DNA midway)

DNA format is very simple (all numbers are INTs except for ALPHA which is FLOAT):

NUMBER_OF_VERTICES NUMBER_OF_POLYGONS R G B ALPHA X0 Y0 X1 Y1 ... XN YN ... R G B ALPHA X0 Y0 X1 Y1 ... XN YN ...

Click Export DNA as SVG to get vector image from your current best DNA. Thanks to Martin for SVG export.

Requirements

Tested and works on (example mutation speed for Mona Lisa at the start of optimization on my notebook):

• Firefox 29 (~222 mutations per second)
• Chrome 34 (~209 mutations per second)
• Explorer 11 (~182 mutations per second)

Frequently asked questions

[Q] I want to play with the algorithm, but my local copy doesn't want to run. What should I do?

[A] The problem is JavaScript's same origin security policy. You must access the page via local webserver using http://localhost instead of just file://. You can use for example Apache from XAMPP.

Then it would still work just on local images (located at the same server, access via "http://"). If you want to access images from remote sites, you need to work around, for example by creating a proxy, so that images would be coming from your server. PHP Curl is one possible way how to do a simple proxy.

[Q] How do I compute a new fitness from the old one?

[A] new fitness = 100 * (1 - old fitness / (width*height*3*255))

[Q] Can I have a compiled version to run it really fast on my computer locally?

[A] You can download Roger Alsing's original binaries and C# sources. Also there is a C version for Linux by Nick Welch.

[Q] What are different mutations?

• Soft mutations change exactly one parameter (R, G, B, A, X, Y) by a small delta.
• Medium mutations change exactly one parameter to a completely random number.
• Hard mutations change a color and transparency of one polygon to a completely random value together with changing one vertex to a completely random point.
• Gaussian mutations change one parameter by delta picked from normal distribution of values around the current value. Thanks to Fritz for Gaussian mutations.

Contact

Feel free to improve on my implementation. The code is rather ugly, though some ugliness is there for performance reasons.

Source is released under MIT License.