4 ms·

Genetic algorithms, Mona Lisa and JavaScript + Canvas

93 points by achudars 13y ago

justplay 13y ago
i played Mario there . lol.. btw ..excellent post .
raverbashing 13y ago
That's very interesting It seems the default mutation parameters are a bit low, if you increase it it may lead to better results I think the main problem with this is that it's using a fixed number of polygons, and apparently is mutating their vertice positions. If it could be changed for a range of polygons (with a range of vertices, let's say from 3-6) maybe it can converge faster (and better) But it is nonetheless a very nice experiment. GA/GP is one of those things that really can work with "untractable" questions.
tlarkworthy 13y ago
It would work better if you did a local optimization after every crossover and ditched random mutation. I think they call it a memetic algorithm (http://en.wikipedia.org/wiki/Memetic_algorithm http://en.wikipedia.org/wiki/Memetic_algorithm). So take your every triangle vertex (x,y) and differentiate against the fitness (using finite difference), then gradient accent on that parameterization. That will let the triangles fit the edges effectively (I am thinking Mondrian here primarily)
binarymax 13y ago
Wow - 2009. Excellent post. I recently entered a competition (February 2013) and used this technique without having seen this blog. I also used webworkers and SVG. Source: https://github.com/binarymax/randriaan https://github.com/binarymax/randriaan Demo: http://binarymax.com/randriaan.html http://binarymax.com/randriaan.html Sorry, FF or Chrome only (because of how I load the webworkers from the same page) @tlarkworthy - I had a version that did 12 images for each generation and chose the best - It was a better result but it really throttled the CPU and took down the browser on my weaker machine, so went with the single thread.
- aerique 13y ago
  I also did the same for that competition (while having seen the blog): http://github.com/aerique/vbwga http://github.com/aerique/vbwga My "artistic" spin was I wanted to reproduce the Victory Boogie Woogie using only circles (see vbw-example.pdf and vbw-example-2.pdf in previous link).
  - binarymax 13y ago
    How was the event? Still sorry I couldn't make it. Looks like it was a lot of fun.
    - aerique 13y ago
      It was good fun especially the drinks afterwards were a good occassion to talk with the other developers and organizers. The jury was heavily biased towards algorithms that created VBWs from nothing so we didn't stand a chance :-)
- guiambros 13y ago
  btw, the original article about using Genetic Algorithms to derive Mona Lisa's image also generated quite a bit of interesting discussions here, 4 years ago: https://news.ycombinator.com/item?id=389727 https://news.ycombinator.com/item?id=389727
DanielRibeiro 13y ago
Reminded me of this previous submission[1]: http://alteredqualia.com/visualization/evolve/ http://alteredqualia.com/visualization/evolve/ [1] comments: https://news.ycombinator.com/item?id=392036 https://news.ycombinator.com/item?id=392036
- niggler 13y ago
  Both reference http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/ http://rogeralsing.com/2008/12/07/genetic-programming-evolut...
cabirum 13y ago
Note how much faster it runs today: 1966 mutations took 120 minutes back then, today it performed ~2100 mutations in about 4 minutes.
- datr 13y ago
  Indeed, I ran the script for 12 minutes and managed 37511 mutations which came up with this: http://imgur.com/phA7Ocu http://imgur.com/phA7Ocu DNA here: http://pastebin.com/PEGwKvG4 http://pastebin.com/PEGwKvG4
wr1472 13y ago
It's super mario bros on the background. You can use your keys to control him.
- bsenftner 13y ago
  I noticed! Very cool.
- jjs 13y ago
  Not "Bros.", "Land"... (This game was a formative experience for me, so please bear with my nitpickery... :) http://en.wikipedia.org/wiki/Super_Mario_Land http://en.wikipedia.org/wiki/Super_Mario_Land
Somegui123 13y ago
This is really awesome. It took me a while but I think I found the perfect settings for "Mondrian" (but it really does take a long time) http://i.imgur.com/OhgYn6X.png http://i.imgur.com/OhgYn6X.png Different images work best with different polygon sizes, different cut-offs etc. and it's really sensitive. If I change the parent cutoff for example, a simple 0.01 change seems to ruin Mondrian from forming, even after waiting several thousand mutations.
gburt 13y ago
While not a "learning" technique directly, this reminds me of this amazing work: http://research.microsoft.com/en-us/um/people/kopf/pixelart/ http://research.microsoft.com/en-us/um/people/kopf/pixelart/
gburt 13y ago
I'm not trolling, but this appears to work pretty poorly. Does anyone know any better approaches to approximating images like this?
- binarymax 13y ago
  Poorly compared to what?
  - gburt 13y ago
    Sorry for not being clear, in a more "objective" sense of reproducing the original image as a stacked series of polygons in this case. I realize that that is only sort of the point (there's a lot of "cool technique demo" here).
jjs 13y ago
Next step: run a genetic meta-algorithm to optimize the initial parameters... judge fitness based on, say, result_quality / runtime... (Or fastest-to-achieve-reasonable-result...)

93 points by achudars 13y ago

i played Mario there . lol.. btw ..excellent post .

That's very interesting It seems the default mutation parameters are a bit low, if you increase it it may lead to better results I think the main problem with this is that it's using a fixed number of polygons, and apparently is mutating their vertice positions. If it could be changed for a range of polygons (with a range of vertices, let's say from 3-6) maybe it can converge faster (and better) But it is nonetheless a very nice experiment. GA/GP is one of those things that really can work with "untractable" questions.

tlarkworthy 13y ago

It would work better if you did a local optimization after every crossover and ditched random mutation. I think they call it a memetic algorithm (http://en.wikipedia.org/wiki/Memetic_algorithm http://en.wikipedia.org/wiki/Memetic_algorithm). So take your every triangle vertex (x,y) and differentiate against the fitness (using finite difference), then gradient accent on that parameterization. That will let the triangles fit the edges effectively (I am thinking Mondrian here primarily)

binarymax 13y ago

Wow - 2009. Excellent post. I recently entered a competition (February 2013) and used this technique without having seen this blog. I also used webworkers and SVG. Source: https://github.com/binarymax/randriaan https://github.com/binarymax/randriaan Demo: http://binarymax.com/randriaan.html http://binarymax.com/randriaan.html Sorry, FF or Chrome only (because of how I load the webworkers from the same page) @tlarkworthy - I had a version that did 12 images for each generation and chose the best - It was a better result but it really throttled the CPU and took down the browser on my weaker machine, so went with the single thread.

aerique 13y ago
I also did the same for that competition (while having seen the blog): http://github.com/aerique/vbwga http://github.com/aerique/vbwga My "artistic" spin was I wanted to reproduce the Victory Boogie Woogie using only circles (see vbw-example.pdf and vbw-example-2.pdf in previous link).
- binarymax 13y ago
  How was the event? Still sorry I couldn't make it. Looks like it was a lot of fun.
  - aerique 13y ago
    It was good fun especially the drinks afterwards were a good occassion to talk with the other developers and organizers. The jury was heavily biased towards algorithms that created VBWs from nothing so we didn't stand a chance :-)
guiambros 13y ago
btw, the original article about using Genetic Algorithms to derive Mona Lisa's image also generated quite a bit of interesting discussions here, 4 years ago: https://news.ycombinator.com/item?id=389727 https://news.ycombinator.com/item?id=389727

DanielRibeiro 13y ago

Reminded me of this previous submission[1]: http://alteredqualia.com/visualization/evolve/ http://alteredqualia.com/visualization/evolve/ [1] comments: https://news.ycombinator.com/item?id=392036 https://news.ycombinator.com/item?id=392036

niggler 13y ago
Both reference http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/ http://rogeralsing.com/2008/12/07/genetic-programming-evolut...

cabirum 13y ago

Note how much faster it runs today: 1966 mutations took 120 minutes back then, today it performed ~2100 mutations in about 4 minutes.

datr 13y ago
Indeed, I ran the script for 12 minutes and managed 37511 mutations which came up with this: http://imgur.com/phA7Ocu http://imgur.com/phA7Ocu DNA here: http://pastebin.com/PEGwKvG4 http://pastebin.com/PEGwKvG4

wr1472 13y ago

It's super mario bros on the background. You can use your keys to control him.

bsenftner 13y ago
I noticed! Very cool.
jjs 13y ago
Not "Bros.", "Land"... (This game was a formative experience for me, so please bear with my nitpickery... :) http://en.wikipedia.org/wiki/Super_Mario_Land http://en.wikipedia.org/wiki/Super_Mario_Land

Somegui123 13y ago

This is really awesome. It took me a while but I think I found the perfect settings for "Mondrian" (but it really does take a long time) http://i.imgur.com/OhgYn6X.png http://i.imgur.com/OhgYn6X.png Different images work best with different polygon sizes, different cut-offs etc. and it's really sensitive. If I change the parent cutoff for example, a simple 0.01 change seems to ruin Mondrian from forming, even after waiting several thousand mutations.

gburt 13y ago

While not a "learning" technique directly, this reminds me of this amazing work: http://research.microsoft.com/en-us/um/people/kopf/pixelart/ http://research.microsoft.com/en-us/um/people/kopf/pixelart/

gburt 13y ago

I'm not trolling, but this appears to work pretty poorly. Does anyone know any better approaches to approximating images like this?

binarymax 13y ago
Poorly compared to what?
- gburt 13y ago
  Sorry for not being clear, in a more "objective" sense of reproducing the original image as a stacked series of polygons in this case. I realize that that is only sort of the point (there's a lot of "cool technique demo" here).

jjs 13y ago

Next step: run a genetic meta-algorithm to optimize the initial parameters... judge fitness based on, say, result_quality / runtime... (Or fastest-to-achieve-reasonable-result...)