Mona Lisa in 50 polygons, using a genetic algorithm (2008)
rogeralsing.com
rogeralsing.com
In lieue of the source code, can anyone point me to a reference on GP and maybe something about image generation in C? In particular, what's an efficient graphics pipeline for converting all of these polygons to pixels? Something like bresenham for the edges and then additive coloring in the middle? And then how do I convert an RGB pixel array into some reasonable image format? I apologize for my ignorance, I don't even know what to start googling.
I think it would be a good exercise for me to write something like this from scratch on my own, just want some pointers to start.
For converting the polys to pixels I render it with OpenGL and then extract the resulting image. I use ppm for both input and output, they're just a plain text file, and any decent image editor can convert to or from them.
HN post here: http://news.ycombinator.com/item?id=392036
Had to write my own bitmap processing library, since couldn't find anything fast enough off the shelf :-D Handled alpha blending, file i/o, etc (checkout the bitmap.lisp and color.lisp files in the repo).
Here's a video of it 'evolving' a picture of John McCarthy (best individual from each generation): http://www.youtube.com/watch?v=-_VFZ_ON0A8
And here it is doing the Mona Lisa: http://www.youtube.com/watch?v=S1ZPSbImvFE
Q) Is this Genetic Programming?, I think it is a GA or even a hill climbing algorithm.
A) I will claim that this is a GP due to the fact that the application clones and mutates an executable Abstract Syntax Tree (AST).
Even if the population is small, there is still competition between the parent and the child, the best fit of the two will survive.
The whole point of GAs is giving you a very simple heuristic for avoid local optima. How are you going to do that if your population size is only 2?
I would expect that a true GA might work better, but not be the best choice. In my semi-related experience, Particle Swarm Optimization [2] works much better for continuous valued problems.
[1] http://en.wikipedia.org/wiki/Random_optimization
[2] http://en.wikipedia.org/wiki/Particle_swarm_optimization
Some clarifications from my part here, 4 years after the post was released:
1) No this does not qualify as a true GA/GP. by definition GP need to have an computational AST, EvoLisa has an declarative AST. There is also no cross over in play here. (see 3* for explatation on this)
2) Hill climbing or not? According to wikipedia, Hill climbing only changes _one_ value of the problem solving vector per generation. ""At each iteration, hill climbing will adjust a single element in X and determine whether the change improves the value of f(X)""
So it doesn't quite fit the hill climbing definition either, also the DNA/vector is of dynamic size in EvoLisa while Hill climbing AFAIK uses fixed size vectors (?)
3) Why wasn't a larger population used and why no cross over?
This is the part that most of you get wrong, increasing the population size and adding cross over will NOT benefit this specific problem.
The polygons are semi transparend and overlap, thus, adding/removing polygons will have a high impact on the fitness level, in pretty much every case in the wrong direction.
Let's use words as an example here:
organism1: "The Mona Lisa" organism2: "La Gioconda"
Both may have similar fitness level, but completely different sets of polygons (letters in this naive example)
combining those will very very rarely yeild an improvement.
e.g. child(result of org1 and org2) "Lae Mocondisa" that is complete nonsense and the fitness level falls back to pretty much random levels.
Thus, you can just as well use pure mutation instead of cross over here.
If the problem instead had been based on genes that paint individual parts, e.g. a gene for the face, a gene for the background, a gene for the body etc.
THEN it would have made sense to use crossover. In such case it would be possible to combine a good face gene with a good background gene and the fitness level would improve.
However, due to the nature of this specific problem where the polygons span the entire image, this is not effective.
And if crossover is not benefitial, then a larger population gets less interesting also since you cannot combine them.
Increasing the population will only make more separate individuals compete against eachother with no additative effect in any way.
see it like this.
If we have one sprinter running 100meters, if he might complete the run in about 10 sec.
If we add 1000 sprinters to the population, each of them might complete the run in about 10 sec each.
Thus, the problem is not solved any faster by adding more individuals here. Also, by increasing the population size, there will be much more data to evaluate for each generation, so even if we can bring down the number of generations needed to solve the problem, the actual real world time to complete it would increase due to evaluation logic.
Anyway, nice to see that people still find this somewhat interesting. It was pretty much a single evening hack back 4 years ago..
//Roger
That code uses real crossover and a large population in order to crack black boxed formulas.
But I do agree, GA's have limited use.
Much appreciated.
http://mattdw.github.com/experiments/image-evo/
It's more strictly a genetic algorithm than the OP, too, as it's mutating a population, and instances age and eventually die.
Also worth checking out, the gallery with more paintings: http://rogeralsing.com/2008/12/11/genetic-gallery/
Realistically, it looks like the final result has somewhere upwards of 200 unique areas created by various overlaps of the 50 polygons.
Here is the result of my first trial after 5000 generations:
For this run, I used 50 triangles, each at 50% alpha (fixed), a GA population size of 200, a crossover rate of 0.91 and a mutation rate of 0.01. It took around 12 hours to run, but that's mainly because I opted to do it in Perl and didn't spend any time optimizing it.
A human generation is said to be round about 25 years.
;-)
And some reconstructions from data. http://screamingduck.com/Lerc/showit.html http://screamingduck.com/Lerc/showit2.html
A given number of n-sided polygons represent a choice of basis set. This can be viewed as an optimization problem, where you try to minimize the difference between the rendered polygon image and the original image.
I wonder if this basis set is ideal? That is, is there a basis set you can choose, that represents the original image equally well, but uses less information?
Each n-sided polygon uses 2n+4 numbers (2n for the points and 4 for the color (RGB) and opacity). What is the ideal number of points in the polygon basis?
One could imaging using a set of orthogonal functions to represent the image. Coming up with a good set that isn't overfit to a training set might be a challenge. Perhaps one can make use of features of the human eye to come up with a good basis (maybe similar how MP3 does this for audio).
For evolving The best basis is some representation that represents the widest ranges of perceived images while keeping some similarity between images with similar data sets.
The range of perceived images is a tricky problem in itself. Many images of noise can be perceived to be the same whereas images of a face will look significantly different with a small change to the nose.
The polygon approach is obviously not good at expressing fine textures. It would be interesting to construct the image allowing rendering into different representations of the same frame buffer. Allow drawing directly into a frequency domain for instance.
You can use whatever basis you want, but I wouldn't call it ideal in any practical sense if you have to run a GA for a several hours to encode an image.
Children play without self-consciousness. ie, they don't think about what other people think or what they're trying to accomplish.
Children play for fun. This is where creativity starts.
Can we have this, please? Someone?
Another advantage is that the compressed format would be vectorial instead of raster, so it would provide smooth scaling.
Storing 4 times the X and Y resolution than a 2 bit per pixel jpeg would yield the same compressed data size. (say a 4096x4096 image compared to a 1024x1024 jpeg. Both 256k). That could also be thought of as storing it as scalable 64x64 blocks.
What you end up with could be a fairly minimal way to represent the image.
Though yes, clearly, the amount of processing required to reach that compression is absurd. But then, most ultra-efficient compression algorithms have this problem at least initially.
Edit: albeit the colors.
And that's overestimating vertex positioning (at that size, 1 or maybe 2 bytes would suffice). Encoding an image like that would be very slow though.
https://news.ycombinator.com/item?id=389727
Discussion about bd's javascript reimplementation:
Slightly harder psnr. http://en.wikipedia.org/wiki/Peak_signal-to-noise_ratio
Harder again... ssim http://en.wikipedia.org/wiki/Structural_similarity
There isn't any real solution to automating similarity as a human sees it. Humans are tricky.
He just loops over the whole image and does a pixel-by-pixel comparison, taking the difference between each of the R, G, and B channels and summing them all.