Mutating Random Polygons to Images

After being inspired by this link, I planned to implement a similar Genetic Algorithm. The algorithm uses a sequence of mutating polygons to recreate an image. Since I was taking a Coursera refresher in R, I decided to give it a shot in that language.

Although, this has been described as a Genetic Algorithm or Genetic Programming, I thought the description was kind of stretched. A more accurate description is a Hill Climbing Algorithm:

  1. Initialize: Start with a random polygon
  2. Incremental change: Add, mutate, or remove polygons
  3. Comparison: Use a fitness function to compare the change with original – the “winner” goes through to the next round
  4. Repeat steps 2 & 3

The mutations were done using some fixed parameters I picked arbitrarily while coding, but I haven’t had a chance to fiddle with them yet:

  1. Mutation probability – 25% chance of each polygon to mutate slightly
  2. Color mutation – 15% range for each RGB color value to change in polygon
  3. Height/Width mutation – 5% range for each point of the polygon to change
  4. Add polygon – 25% chance of a random new polygon to be added in a generation
  5. Remove polygon – 25% chance of a random polygon in current sequence to be removed in a generation
  6. Polygon vertices – 3, 4, or 5 points per polygon, chosen randomly
  7. Polygon transparency – 0.5 alpha in RGBA color space

The fitness function is a mean square error in color space.

There were a few issues I ran into using R for this, which I didn’t anticipate. R has a graphics device but I couldn’t figure out how to run my fitness function (a pixel by pixel comparison in color space) on it. Instead, I had to read & write images to disk, which was a big hurdle in computation. The alternative would be to do the comparison while the images are stored as matrices. However, I couldn’t figure out the conversion from multiple stacked RGBA polygons (polygons with transparency) to an RGB color.

I also coded the polygon vertices to be within the image dimensions, unless they mutate out. This boundary has a tendency to create a white space around the image. Maybe in the future I will fix that.

Regardless, I let it run a few times with different images. During the inauguration, I ran it with the US flag. Earlier, I did a test run with the Mona Lisa. I was impatient and used small images to speed up the results. I also ended the trials after the incremental mutations became too infrequent. As you can see below, the general shape is achievable, but getting the details would take a lot more iterations.

Results

US flag video of evolution through all successful iterations:

Mona Lisa select images of evolution:
image
In 18 samples…
imageimageimageimageimageimage

imageimageimageimageimageimage

imageimageimageimageimageimage

Advertisements

One thought on “Mutating Random Polygons to Images

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s