Is this possible to code?
category: general [glöplog]
Hi,
look at this http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/
can somebody explain easily how it will be done?
look at this http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/
can somebody explain easily how it will be done?
Quote:
That explains it well. What remaining questions do you have?I created a small program that keeps a string of DNA for polygon rendering.
The procedure of the program is quite simple:
0) Setup a random DNA string (application start)
1) Copy the current DNA sequence and mutate it slightly
2) Use the new DNA to render polygons onto a canvas
3) Compare the canvas to the source image
4) If the new painting looks more like the source image than the previous painting did, then overwrite the current DNA with the new DNA
5) repeat from 1
Step 4 could be implemented e.g. by comparing the RGB values of the pixels of the current generated image with the original image and saving the sum of the differences. If it's less than the previous one, the current generated image will be taken as the better solution.
thats quiet hard to understand for me
fif the hard way...
In the end this is not genetic programming but a very crude randomized greedy search in the solution space. But what the heck.
Quote:
So I guessed right.Q) What is your fitness function?
A) The fitness function is a pixel by pixel compare where the fitness for each pixel is summed and compared to the parent.
http://www.wreck.devisland.net/ga/ - this is much cooler
The DNA is just a list of vertices of polygons and colors.
Supposing that every polygon have 4 vertices, the struct would be something like this:
struct Vertex
{
float x, y, z;
}
struct Polygon
{
struct Vertex v[4];
int color;
};
struct Polygon DNA[50];
So, that is your dna. To start, you fill the vertices and the colors with random values.
Then you render the polygons in a texture. Compare the texture with the image to generate (mona lisa) with SAD or any other method. It gives you a value of distance between the image to generate and the texture.
Then you modify a bit the values of the dna by adding a little random value to evey vertex position and color. Then you render again and compare the new texture with the mona lisa. If the given value is little (the distance between images is shorter), then it means the image is more similar to mona lisa, then you continue working on the new dna. If it is not, you continue working with the old dna.
You repeat the process until the result is similar enough or you are bored of waiting. Thats all.
Anyway this is not a genetic algorithm. It is a random hill climbing algoritm. I used the term "dna" just to call it the same way as the autor, but it is not completely correct... whatever
Supposing that every polygon have 4 vertices, the struct would be something like this:
struct Vertex
{
float x, y, z;
}
struct Polygon
{
struct Vertex v[4];
int color;
};
struct Polygon DNA[50];
So, that is your dna. To start, you fill the vertices and the colors with random values.
Then you render the polygons in a texture. Compare the texture with the image to generate (mona lisa) with SAD or any other method. It gives you a value of distance between the image to generate and the texture.
Then you modify a bit the values of the dna by adding a little random value to evey vertex position and color. Then you render again and compare the new texture with the mona lisa. If the given value is little (the distance between images is shorter), then it means the image is more similar to mona lisa, then you continue working on the new dna. If it is not, you continue working with the old dna.
You repeat the process until the result is similar enough or you are bored of waiting. Thats all.
Anyway this is not a genetic algorithm. It is a random hill climbing algoritm. I used the term "dna" just to call it the same way as the autor, but it is not completely correct... whatever
After my genetic algorithms course I learned one thing ... That making a brute force solution would be faster and more accurate :D.
a timelapse version of the video might be a lot more interesting actually.
bonzaj, sometimes what you say is true, but in this case a brute force could not be possible... but maybe a greedy algorithm would work fine.
I suppose - but I'm not completely sure - that a greedy algorithm could give the best solution possible if the polygon blending is aditive, but if the blending mode is transparency then the problem is very different...
I suppose - but I'm not completely sure - that a greedy algorithm could give the best solution possible if the polygon blending is aditive, but if the blending mode is transparency then the problem is very different...
i'm gonna go ahead and say NO, just for the heck of it
Quote:
http://www.wreck.devisland.net/ga/ - this is much cooler
This one is boring as hell
joining basically everyone else here, but fuck the bullshit about "dna". this is not a genetic algorithm. there's no population, just one single active solution, and neither is there any crossover.
it's a simple hill climbing algorithm, and given the way it was implemented, it's extremely prone to get stuck in local maxima. so, in all likelihood, this is nowhere near the best approximation of the mona lisa you can get with 50 quads.
mind, this would actually be an interesting problem to try and solve using more sophisticated search techniques, but that's not what the author is doing. a very simple way to improve the algorithm is to use simulated annealing instead of hill climbing: if the modified solution is better than the current one, always accept it, and if it's worse, accept it with a certain probability (which you succesively decrease during the iteration). just as easy to code and way less likely to get stuck in a local extremum; the only fiddly part is how to modify the acceptance probability over time (the "cooling schedule" in SA parlance).
of course you can also try genetic algorithms, but they all basically suck. at least i've never seen any case where they yielded quality superior to simpler schemes (such as SA), and they're goddamn slow besides.
finally, you can generally do far better than just wiggling vertices randomly. you want some random modifcations in (to avoid getting stuck), but you'll usually arrive at better results (and several orders of magnitude faster) by making more directed changes most of the time. for example, you could try to bias vertices to move motions towards edges in the source image.
it's a simple hill climbing algorithm, and given the way it was implemented, it's extremely prone to get stuck in local maxima. so, in all likelihood, this is nowhere near the best approximation of the mona lisa you can get with 50 quads.
mind, this would actually be an interesting problem to try and solve using more sophisticated search techniques, but that's not what the author is doing. a very simple way to improve the algorithm is to use simulated annealing instead of hill climbing: if the modified solution is better than the current one, always accept it, and if it's worse, accept it with a certain probability (which you succesively decrease during the iteration). just as easy to code and way less likely to get stuck in a local extremum; the only fiddly part is how to modify the acceptance probability over time (the "cooling schedule" in SA parlance).
of course you can also try genetic algorithms, but they all basically suck. at least i've never seen any case where they yielded quality superior to simpler schemes (such as SA), and they're goddamn slow besides.
finally, you can generally do far better than just wiggling vertices randomly. you want some random modifcations in (to avoid getting stuck), but you'll usually arrive at better results (and several orders of magnitude faster) by making more directed changes most of the time. for example, you could try to bias vertices to move motions towards edges in the source image.
guys please don't blaspheme against genetic algorithms, yes they are slow but they have reached the most perfect soluce :
texel: Actually I was thinking about a function optimisation problem, and not the one with Mona Lisa. On the other hand after reading what ryg said I must agree that a random generating of vertices + vertex biasing as a post step would be much better and faster. What's left is that genetic algorithms are very nice in theory :).
@Zest: You're wrong, this result will collapse in a few years.
The only problem is, that its not a photograph of mona lisa :P
genetic algorithms are teh future for robot brain science!
Quote:
“A robot may not injure a human being or, through inaction, allow a human being to come to harm.
A robot must obey orders given to it by human beings, except where such orders would conflict with the First Law.
A robot must protect its own existence as long as such protection does not conflict with the First or Second Law.”
Quote:
What if, instead of comparing pixels against the Mona Lisa to determine fitness, you allowed random internet users to vote on the “beauty” of each successive generation (say on a scale of -1 to 1) where users would compare the new generation to the old generation and vote on the improvement (or lack thereof). The goal of the program would be to obtain a consistently high rating. Given enough time, would we end up with a beautiful piece of abstract art or a muddled mess? Or what if the human evaluators were asked to judge not the beauty of the painting but whether each successive generation looked more or less like particular figure, such as a face. Would we be able to “crowd-source” our way toward something recognizable?
interesting comment!
hm... add some (gaussian) alpha gradient on the borders to those colored quads and you will have a very very nice compression technique! I mean, 50 quads is 650 uncompressed bytes more or less!! Regardless of his implementation of the optimization algorithm, I think the idea is really good. Gotta try this!
Quote:
http://video.google.nl/videosearch?q=jan+nortje&emb=0&aq=-1&oq=jan+nortj#q=jan%20nortje&emb=0