{"id":21,"date":"2013-01-28T15:54:25","date_gmt":"2013-01-28T15:54:25","guid":{"rendered":"http:\/\/drainthemainbrain.wordpress.com\/?p=21"},"modified":"2013-01-28T15:54:25","modified_gmt":"2013-01-28T15:54:25","slug":"21","status":"publish","type":"post","link":"http:\/\/blog.rajarshidas.com\/?p=21","title":{"rendered":"Mutating Random Polygons to Images"},"content":{"rendered":"

After being inspired by this link<\/a>, 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.<\/p>\n

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:<\/p>\n

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

    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:<\/p>\n

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

      The fitness function is a mean square error in color space.<\/p>\n

      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.<\/p>\n

      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.<\/p>\n

      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.<\/p>\n

      Results<\/strong><\/p>\n

      US flag video of evolution through all successful iterations:<\/p>\n

      [youtube http:\/\/www.youtube.com\/watch?v=4Sfl7GN5NMU&rel=0&h=126&w=224;]<\/p>\n

      Mona Lisa select images of evolution:
      \n\"image\"
      \nIn 18 samples…
      \n\"image\"\"image\"\"image\"\"image\"\"image\"\"image\"<\/p>\n

      \"image\"\"image\"\"image\"\"image\"\"image\"\"image\"<\/p>\n

      \"image\"\"image\"\"image\"\"image\"\"image\"\"image\"<\/p>\n","protected":false},"excerpt":{"rendered":"

      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.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[16,17,26],"class_list":["post-21","post","type-post","status-publish","format-standard","hentry","category-programming","tag-genetic-algorithm","tag-image-generation","tag-r"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/blog.rajarshidas.com\/index.php?rest_route=\/wp\/v2\/posts\/21","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.rajarshidas.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.rajarshidas.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.rajarshidas.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.rajarshidas.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=21"}],"version-history":[{"count":0,"href":"http:\/\/blog.rajarshidas.com\/index.php?rest_route=\/wp\/v2\/posts\/21\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.rajarshidas.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=21"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.rajarshidas.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=21"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.rajarshidas.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=21"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}