Uncategorized

Image rendering with polygons

April 20, 2020 /

During my masters, I took a course called Physics of Algorithms – this is largely where I developed an interest in nature inspired algorithms. For my exam, I worked on an algorithm that could render images using polygons. This is not an original idea – Roger Johansson was one of the first to do this back in 2008. However at the time, I had not come across existing versions that would successfully run in Python 2.7 or 3.6, and the original program was written in .NET 2.0/VS.NET 2008. I therefore decided to recreate his project in Python for my final report, which you can take a look at here (all code for the program is included in the report – I will not reproduce it in this post).

If you don’t already know what a genetic algorithm is, I advise you to take a look at this post before reading on.

Details of the original program

Johansson does not reveal much about the parameter settings in his original program – and I didn’t understand the available source code binaries. I also didn’t have much interest in simply replicating his original code, i instead used the immediately available information as a guideline for my own implementation:

  • The image consists of 50 semitransparent polygons
  • Population size was only 2: a “current” candidate, and a mutation of the current candidate
  • It took 3 hours to obtain the following result
Roger's target image; a sepia version of the Mona Lisa.
Roger's final solution after 904,31 iterations.

With a population of only 2, it is arguable that Johansson does not truly employ the principles behind genetic programming and is rather solving the problem using hill climbing. This discussion isn’t relevant right now, but I acknowledge that we might not entirely be employing genetic programming.

Genetic programming is a metaheuristic that revolves around the propagation and modification of genetic material over time. Here, the genetic material should obviously be some string or array which describes the polygons

Performance of my solution

I’ll let you know straight away that I never managed to produce as impressive results as Johansson, but I did obtain recognisable results. In the following are a couple of comments on what affects the final solution. The main issue in this project was the time it took to to produce images – my program never performed at the speed of Johansson’s, and I never obtained images

Size matters

In the developing phase, the target picture of Mona Lisa was 800×1192 px, and it took >10 seconds to produce 10 images. Using a smaller version at just 270×402 px significantly improved the speed so that 10 images were produced in <10 seconds. I finally decided to use a small cut out of Mona Lisa of just 150×184 px.

monalisa_smaller

Triangles or polygons?

I personally couldn’t prove that it was beneficial to use triangles over polygons. It seemed to depend more on the parameter settings than some intrinsic quality, one shape should possess more than the other. All test were therefore performed in order to compare – take a look for yourself below and see what you think.

Initial test performance

The initial runs tested the performance after 10,000 iterations just to see if there was promising convergence towards the target picture.

Using either 50 triangles or 50 polygons and a mutation rate of 5%, the program converged to two pictures showing resemblance to the most predominant characteristics of the target picture (the chest area, the background, and the general face and hair traits, although not with impressive detail. These runs took about 50 minutes each on the computer I used.

50 polygons     5% mutation rate      10,000 iterations
Using triangles.
Using polygons.

Mutation rate and number of polygons

I realised quickly that my solutions stopped progressing much after a “short” while. To overcome this within my time frame, I tried to change both the number of polygons, and the mutation rate, but never ended up settling on anything. To begin with, the solutions for 50 polygons had not progressed much at 65,000 iterations:

50 polygons     5% mutation rate      65,000 iterations
Using triangles.
Using polygons.

However, it quickly seemed to be a general problem.

50 polygons     3.5% mutation rate     100,000 iterations
Using triangles.
Using polygons.
50 polygons     3.5% mutation rate     240,000 iterations
Using triangles.
Using polygons.

Should we use more polygons?

100 polygons     3.5% mutation rate     120,000 iterations
Using triangles.
Using polygons.

Maybe even more?? This is actually the closest I managed to get to the target picture within the time frame.

300 polygons     5% mutation rate     100,000 iterations
Using triangles.
Using polygons.
300 polygons     5% mutation rate     400,000 iterations
Using triangles.
Using polygons.

29 Comments

  • maseczki na twarz

    December 24, 2020 at 04:02 Reply

    I’m extremely pleased to discover this website. I wanted to thank you for ones time just for this fantastic read!! I definitely enjoyed every part of it and i also have you bookmarked to see new stuff in your site.

  • cialis online

    December 24, 2020 at 12:54 Reply

    VIA Gras Golden Makeup I didn’t understand LIVE.Patients should be advised to discontinue sildenafil therapy in case of sudden loss of vision and to consult a doctor immediately.Whilst alcohol may help any anxiety or shyness, there is evidence to suggest that it helps arousal too.The differences are symbolic and are made by manufacturers in order not to pay for the patent.The PDE-5 inhibitors do not have any psychological or neurological effect.

  • maseczki z filtrem

    December 28, 2020 at 08:29 Reply

    I’m extremely pleased to discover this website. I wanted to thank you for ones time just for this fantastic read!! I absolutely enjoyed every part of it and i also have you bookmarked to see new stuff in your site.

  • estetika

    January 6, 2021 at 00:00 Reply

    Do you want to hit the jackpot in your SEO efforts? this online marketing offer is for you. I offer you the most advance and safe link building method thrive to your site top SERPS and traffic to your Website or Video.

  • cbd for sale

    January 7, 2021 at 03:15 Reply

    Needed to write you this very small word to help thank you very much yet again with your wonderful views you have shown on this website. This is so wonderfully open-handed with you to supply without restraint what exactly some people would have supplied for an electronic book to make some profit on their own, specifically since you might well have tried it in the event you wanted. Those tricks likewise worked to provide a great way to understand that the rest have the same zeal the same as my very own to understand whole lot more with respect to this problem. I think there are thousands of more pleasurable times up front for those who view your website.

  • remeron online

    January 9, 2021 at 02:35 Reply

    My husband and i felt now fortunate Emmanuel could conclude his investigation from your ideas he gained in your site. It’s not at all simplistic just to choose to be giving for free information that most people have been making money from. And we all do understand we have the website owner to be grateful to because of that. The explanations you’ve made, the easy site menu, the friendships you can give support to engender – it’s everything extraordinary, and it’s facilitating our son and our family feel that that idea is enjoyable, and that is highly important. Many thanks for all the pieces!

  • longchamp outlet

    January 16, 2021 at 14:37 Reply

    I wish to express some appreciation to this writer just for rescuing me from this type of setting. Just after looking out through the internet and obtaining ways that were not productive, I thought my entire life was well over. Existing devoid of the strategies to the issues you have solved by means of this article content is a crucial case, and those that might have adversely damaged my entire career if I had not come across your blog post. Your actual natural talent and kindness in dealing with the whole lot was excellent. I’m not sure what I would have done if I hadn’t discovered such a stuff like this. It’s possible to at this time look forward to my future. Thank you so much for the impressive and effective guide. I won’t hesitate to recommend your blog to any individual who ought to have guide about this subject.

  • off white hoodie

    January 16, 2021 at 14:38 Reply

    I’m writing to make you understand what a superb experience my cousin’s girl experienced checking your site. She mastered such a lot of issues, which included what it is like to have an incredible teaching mood to make others without problems completely grasp several grueling subject matter. You truly surpassed our expectations. Thanks for giving those powerful, safe, revealing and even unique guidance on your topic to Jane.

  • kawhi leonard shoes

    January 16, 2021 at 14:43 Reply

    My spouse and i have been so excited Jordan could do his homework through the entire ideas he received while using the weblog. It’s not at all simplistic just to find yourself giving freely steps which people may have been making money from. So we recognize we need the website owner to appreciate because of that. The most important illustrations you’ve made, the simple blog menu, the friendships you can help engender – it’s mostly fantastic, and it’s really assisting our son and us recognize that this idea is interesting, and that’s wonderfully important. Thanks for everything!

  • yeezy

    January 16, 2021 at 14:48 Reply

    I not to mention my buddies appeared to be going through the nice points on the website then immediately developed an awful feeling I had not expressed respect to the blog owner for those techniques. Most of the boys happened to be totally stimulated to read through all of them and already have without a doubt been loving those things. Thank you for being really kind as well as for using certain essential subject matter most people are really desperate to be aware of. Our honest regret for not expressing gratitude to sooner.

  • yeezy boost 350 v2

    January 16, 2021 at 14:53 Reply

    Thank you for your entire hard work on this website. My aunt really loves doing research and it’s really obvious why. My partner and i learn all of the dynamic ways you create advantageous tips via the web site and in addition recommend participation from some others on that subject then our favorite girl has been discovering a lot. Have fun with the remaining portion of the year. Your conducting a stunning job.

Leave a Reply

Your email address will not be published. Required fields are marked *