Genetic Algorithm for Image Evolution

Thu Jan 05 19:45:00 UTC 2012

Original

Best so far

Evolving

Experiment

Some time ago I came across this, this and this - an interesting idea to reproduce an image given a minimal set of polygons, utilising evolutionary search. The original idea used a hill climbing strategy to randomly mutate a collection of polygons, keeping a mutation only if the change yielded an improvement, defined by the sum of pixel by pixel differences between the original image and the collection of polygons in the new image. I was curious if the method could be improved by using a genetic algorithm (using a population of candidate solutions instead of just 1).

The algorithm initialises a population of candidate images where each image contains 1 randomly coloured and positioned polygon. At each evolutionary step, each individual (candidate image) in the population is evaluated according to a fitness function which determines the closeness of the candidate image from the original and then assigned a fitness score. Then, individuals from the population are selected using fitness proportionate selection such that individuals with greater fitness (closer proximity to original image) have a greater chance of mating. Selected individuals then produce offspring using a genetic crossover technique and are then subject to mutation. Crossover involved copying polygons from each parent to form new offspring, while mutation involved random changes to polygon structure and colour as well as the possibility to add or remove a polygon from the newly created offspring.

The main difficulty with using a GA for this problem is the choice of crossover function. I tried a number of schemes and found them to be destructive - Ultimately mutation led the search for image improvements. However this simply resulted in random search. The second difficulty is the quality of the fitness function: I tried the sum of differences between the original image and the candidate image over each RGB value, histogram comparison and a combination of both. Ultimately, I could not really improve on random search so am thinking of new ways to encode the problem so that the search space is better defined.

Code

The javascript code for this experiemnt is available here for anyone interested.

Some other examples

From a photograph

The following example shows a sequence of image evolution snapshots. The example photograph is of the old Eastern Telegraph Building in Syros, Greece.

Judith Beheading Holofernes

This example shows a sequence of snapshots from the evolution of this painting by Caravaggio.