Evolution of Mona Lisa Via Genetic Programming 326
mhelander writes "In his weblog Roger Alsing describes how he used genetic programming to arrive at a remarkably good approximation of Mona Lisa using only 50 semi-transparent polygons. His blog entry includes a set of pictures that let you see how 'Poly Lisa' evolved over roughly a million generations. Both beautiful to look at and a striking way to get a feel for the power of evolutionary algorithms."
Sweet (Score:1, Interesting)
Awesome. That is all.
Triangles (Score:5, Interesting)
I would've liked to see it done with triangles... complex polygons just feels a bit like cheating. Not that it isn't super cool.
On reddit, someone posted another neat GA algorithm which evolves a car to match terrain:
http://www.wreck.devisland.net/ga/ [devisland.net]
A million generations.. (Score:2, Interesting)
Not genetic, still a good demonstration (Score:5, Interesting)
Its not genetic programming because theres only phenotype being evaluated each generation(the image). If the algorithm had 10 individual sets that traded polygons somehow, with a tendency for the pictures closer to the Mona Lisa to get reproduction preference, then it would be genetic.
Re:Not genetic, still a good demonstration (Score:4, Interesting)
Re:Brilliant! (Score:2, Interesting)
1) Image compression
2) Games (video cards use polygons to render 3D scenes, right?)
3)
The thing I'm also wondering is, is the output better or worse than a expert algorithm? Could the output of a expert algorithm be used as the input to get this genetic algorithm a head-start?
A similar project (Score:5, Interesting)
I did something very similar. Instead of random polygons, I used random circles. I would choose the best and then clone it... adding a random circle to each.
http://www.eigenfaces.com/ [eigenfaces.com]
An interesting thing, I found, was to take a handful of low-quality creations and "average" them out. You end up with more detail.
Re:Triangles (Score:3, Interesting)
it seems pretty random actually (i've run the program like 4-5 times). sometimes it starts off slow and then gets a little better. but sometimes it starts off with a really good design and then just gets worse. it seems pretty random overall.
the point of genetic evolution is for there to be progressive enhancements. it's not just randomly throwing the dice over and over again. you have to retain the positive enhancements of past iterations for it to "evolve." you could run this program all day long and it'll never get better than it was during the first 10 generations. that's because every time it mutates it throws out all the previous data. it's just non-directed randomness.
Re:A similar project (Score:5, Interesting)
Oh... I forgot to mention. I also tried it against some video. It seems that by adding motion, you percieve even more detail. This is about 20 frames with a resolution of about 1000 generations each.
http://www.eigenfaces.com/img/morphs/anim-100x20.gif [eigenfaces.com]
This was all done with Python / Pygame. A great little package for those who are keen to dabble
Really fun (Score:1, Interesting)
Genetic algo's are a great thing to do at home. I've been tinkering with Avida for the last few days, trying to get these programs to grow instead of shrink. Maybe they will gain some kind of structures then.
http://devolab.cse.msu.edu/ [msu.edu]
See also
http://www.framsticks.com/ [framsticks.com]
http://www.stellaralchemy.com/lee/virtual_creatures.html [stellaralchemy.com]
http://www.spiderland.org/ [spiderland.org]
Any of which are fun if you get them going. The joy in these things is sort of in tuning them. But I think a lot lately about GA's on GA's to adjust the parameters within certain windows. A lot of these models aren't open-ended enough to demonstrate intelligence. But you never know. Check out Polyworld, Achilles, and Critterding, too, if you're in Linux
image compression (Score:4, Interesting)
Could this be used as a new way to compress pictures? I would guess the compression itself would be computationally expensive, but the compression would be amazing.
Re:A similar project (Score:3, Interesting)
Since the circles are getting iteratively smaller, doesn't this ultimately amount to just guessing the value of the pixels?
Where the polygon Mona Lisa could be compressed to an extremely small number of points, yours is layer upon layer of color data, right?
Wouldn't a more equivalent approach be to weigh the value of the circles on their apparent size; bigger being more valuable?
Re:Brilliant! (Score:5, Interesting)
I have hobby expertise in this subject. I've studied the subject in general, I have studied the math behind it, and I have programmed several evolving systems.
You always need a target.
Nope. Evolution works great even when you don't have the faintest clue what a successful "target" might look like. In fact evolutionary methods are most valuable exactly when you lack a lack a target and when you are unable to "intelligently design" a solution yourself.
The technical term for what you need is a 'fitness function'.
However even that overstates what you need. While it is convenient if you have a function to numerically evaluate fitness, all you really need is a comparison ability - some means of comparing individual A and individual B and selecting which on is "better", for any definition of "better". It doesn't even have to be an absolute or accurate comparison - all you need is some means of selection that chooses the "better" individual more than 50% of the time.
As for this article, it is a visually nice demo for introducing people to the subject, but in fact it uses one of the most limited and least powerful aspects of evolving processes. It is a simple asexual hillclimbing of a single individual.
Sexual recombination in an evolving population is almost infinitely more powerful. There's some deep mathematics behind the power of sexual recombination, but it is so powerful that essentially all species above bacteria have seized on it. Asexual reproduction has many obvious advantages and simplicity, but virtually all species abandon it whenever possible because sexual recombination is where the real power lies in evolution.
-
Re:Any GA implementation.. woo (Score:4, Interesting)
Real world application?
At our Faculty (www.fer.hr), reservations for "lab practices" is done via genetic algorithms. It's kinda hard to assemble over 500 people for your class to be assigned times when they don't have any other class (there are numerous combinations of classes one can take), and to reduce the time which they have to wait after their last class ends before they are meant to go to the "lab practice".
In case I didn't make much sense -- optimal schedules for students!
Re:Triangles (Score:5, Interesting)
Which brings us to a real use for this kind of thing. Depending on how fast it runs, it could be an interesting form of image compression. 50 polygons is generally a lot less data than 914400 rectangles. For higher quality, you could add more polygons. You then get a resolution-independent version of the original image with some loss of quality. I'm not sure if it's more interesting than topology-based compression, but it's certainly an interesting avenue.
Re:Any GA implementation.. woo (Score:3, Interesting)
GA's can find some very bad solutions to poorly created problems. I once used a GA to solve a combat problem where the problem, meaning the evaluation function, was largely based on the length of the combat. Unfortunately, the solution it found was to kill it's own side, and the combat was over almost immediately.
There's usually a simple heuristic (for example, nearest neighbor for TSP) that does better than a random. You should check your GA solution compared to the heuristic to make sure that it's not doing something completely stupid.
Re:Feeding the troll... (Score:2, Interesting)
WORD!
I know there's no good karma to be had here (both figuratively and literally) by going after someone else's grammar, or by replying to a post rated zero. But I'm going to throw my lot in with the parent. The proliferation of misuses of "its" and "it's" is accelerating. I saw a post on WSJ the other day that corrected the writer of the article on this matter, only the correction was incorrect!
-t.
Re:A similar project (Score:3, Interesting)
Yes indeed. It turns out the more detailed things get, the smaller the circles get. Obviously. I set the software so that the minimum circle radius is larger than a pixel. Because of the alpha blending, color is not determined by just the circle, but also the overlap of other circles.
The first experiment I did was to actually randomize all pixels... and mutate a different pixel in each child. Not as nice as the circles. BTW, the code can just as well draw polygons. I made one with triangles. When it comes down to it... I simply like the way the circles look!
One thing the Mona Lisa example does that I will probably now try is the ability to make arbitrary polygons. Right now, mine are all "regular" polygons: square, triangle, pentagon, hex, octagon, etc.
I was never really concerned with compression so much as the idea, to be honest. Like yours did, my gut tells me the Mona Lisa would indeed compress better. But where one unit is "n points (x,y for each), color, alpha" on the Mona Lisa example, mine is just: x,y,radius,color, alpha.