Polygon Farming
Posted on 2008-12-09 [direct link] Tags: Art Photo Polyfarm Programming Ramdaq.
Roger Alsing has an interesting post on his blog called Genetic Programming: Evolution of Mona Lisa. I'll quickly gloss over his experiment and the fact that I don't consider it to be genetic programming at all (more of a simple hill-climb algorithm) and acknowledge that the results are fascinating. He attempts to produce an approximation of the Mona Lisa using a fixed number of layered semi-transparent polygons. The trick is that the polygons are randomly created and then repeatedly tested and mutated, keeping only mutations that bring the output closer to the goal of the Mona Lisa.
If this had been done with a full genetic programming implementation it would have probably been a staggeringly good final image, if a little costly to produce in terms of CPU time. But what surprised me was that even the very simple hill-climb algorithm produced something that was recognizable within a few thousand generations. The remaining near-million generations brought a lot of improvements and details, but even a short run produced something good.
Generic programming, fitness functions and evolutionary strategy has been something of a reoccurring source of hobby projects for me. I even once wrote a system that could play board games against itself (or humans) and "learn" negotiating tactics... so I've been down this rabbit hole before. But I've never had a go at image outputs, even though I've wanted to since seeing William Latham's “Organic Television (Video Installation)" at the Manchester City Art Gallery in 1991. It was one of the days that cemented my ambition to really learn computer science rather than just play at programming. His procedural generation techniques were just something that I had to be able to recreate myself, simply seeing them (and even understanding them) wasn't enough.
I'm going to use the excuse of lack of computing power as to why I never actually got around to doing it. I did, however, co-write a half-baked L-System engine which was good enough to sell a handful of copies. So I managed to scratch the itch with the limited resouces I had at the time.
But anyway... Roger Alsing's post seemed to suggest that evolutionary/procedural generation of images is now the work of moments. So obviously I'm having a go at it.
My first target image is from Ramdaq's Alice In Wonderland series.
I've used 5,000 triangles as my polygon set. Each is black or white and has a random opacity. Subsequent generations are subjected to minor mutations to the polygon-vertex co-ordinates and the opacity. If the child is "fitter" then it is kept and the parent dies, otherwise the child dies and the parent lives Fitness is derived from the root mean squared error of the pixel values.
The image above shows the initial (random) population (left frame) and the population approx 20,000 tests later (right frame). The center frame is an overlay of the left and right frames to show areas of similarity.
The image below shows snapshot frames approximately every 2000 tests. There is a rapid convergence on something half-decent and then a very slow series of improvements. The improvements are actually quite subtle so you have to look closely to see them as points move and opacities shift.
I expect to revisit this later in the week and write something much better. The things I want to look at most pressingly are (in no particular order); different image comparison techniques (fitness function), allowing polygons to move on the Z axis (the rendering order, or their depth in the pile) and possibly allowing the splitting / joining of vertices. I may also implement colour, but I'm not sure if I want it. But before any of that interesting stuff I need to look at an improved binomial distribution for the mutations, allow for proper inheritance and crossover functions and put in place a sensible population model.
I probably won't get around to it. Maybe over Christmas ;)
Posted on 2008-12-09 [direct link] Tags: Art Photo Polyfarm Programming Ramdaq.
Roger Alsing has an interesting post on his blog called Genetic Programming: Evolution of Mona Lisa. I'll quickly gloss over his experiment and the fact that I don't consider it to be genetic programming at all (more of a simple hill-climb algorithm) and acknowledge that the results are fascinating. He attempts to produce an approximation of the Mona Lisa using a fixed number of layered semi-transparent polygons. The trick is that the polygons are randomly created and then repeatedly tested and mutated, keeping only mutations that bring the output closer to the goal of the Mona Lisa.
If this had been done with a full genetic programming implementation it would have probably been a staggeringly good final image, if a little costly to produce in terms of CPU time. But what surprised me was that even the very simple hill-climb algorithm produced something that was recognizable within a few thousand generations. The remaining near-million generations brought a lot of improvements and details, but even a short run produced something good.
Generic programming, fitness functions and evolutionary strategy has been something of a reoccurring source of hobby projects for me. I even once wrote a system that could play board games against itself (or humans) and "learn" negotiating tactics... so I've been down this rabbit hole before. But I've never had a go at image outputs, even though I've wanted to since seeing William Latham's “Organic Television (Video Installation)" at the Manchester City Art Gallery in 1991. It was one of the days that cemented my ambition to really learn computer science rather than just play at programming. His procedural generation techniques were just something that I had to be able to recreate myself, simply seeing them (and even understanding them) wasn't enough.
I'm going to use the excuse of lack of computing power as to why I never actually got around to doing it. I did, however, co-write a half-baked L-System engine which was good enough to sell a handful of copies. So I managed to scratch the itch with the limited resouces I had at the time.
But anyway... Roger Alsing's post seemed to suggest that evolutionary/procedural generation of images is now the work of moments. So obviously I'm having a go at it.
My first target image is from Ramdaq's Alice In Wonderland series.
I've used 5,000 triangles as my polygon set. Each is black or white and has a random opacity. Subsequent generations are subjected to minor mutations to the polygon-vertex co-ordinates and the opacity. If the child is "fitter" then it is kept and the parent dies, otherwise the child dies and the parent lives Fitness is derived from the root mean squared error of the pixel values.
The image above shows the initial (random) population (left frame) and the population approx 20,000 tests later (right frame). The center frame is an overlay of the left and right frames to show areas of similarity.
The image below shows snapshot frames approximately every 2000 tests. There is a rapid convergence on something half-decent and then a very slow series of improvements. The improvements are actually quite subtle so you have to look closely to see them as points move and opacities shift.
I expect to revisit this later in the week and write something much better. The things I want to look at most pressingly are (in no particular order); different image comparison techniques (fitness function), allowing polygons to move on the Z axis (the rendering order, or their depth in the pile) and possibly allowing the splitting / joining of vertices. I may also implement colour, but I'm not sure if I want it. But before any of that interesting stuff I need to look at an improved binomial distribution for the mutations, allow for proper inheritance and crossover functions and put in place a sensible population model.
I probably won't get around to it. Maybe over Christmas ;)
This article currently has 1 comment. Read it.
[2008-12-09 at 11:36 (updated many times)]
[views: 1156]
[direct link]Browse recent articles
Archives
Tag Cloud
Search
