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) and ended up with
this . Using this
image as input, the objective is to evolve a new image constrained by a maximum number of polygons. Here is the result:
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 results 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.
you said each image in the population get 1 random polygon, but not each evolution a polygon is added. when does the algorithm decide to add a new polygon instead of just changing the existing?
ReplyDeletehello. when a new offspring is created by combining 2 parents through crossover, there is also a chance that the offspring will be mutated. there is a 45% chance that the mutation will result in a change in colour of one of the offspring's polygons, 45% chance that a polygon will move, 5% chance that a polygon will have an edge added or removed and finally, a 5% chance that a polygon will be added or removed from the offspring. you can view the (sorry a bit messy) code here http://parasec.net/evolve2/evolve.js if you are interested. thanks.
ReplyDeletethank you i will take a look^^. so you just add a poly randomly?
Delete