Low-poly image generation using evolutionary algorithms in Ruby (2023)
114 points by thomascountz 3 days ago | 42 comments
  • jensenbox 2 days ago |
    Where is the scrollbar?
    • thomascountz 2 days ago |
      Hi, I haven't seen your scrollbar. Do you know where you've seen it last? Perhaps my CSS took it and put it somewhere?
      • crazygringo 2 days ago |
        See my sibling comment, looks like your CSS did take it and only you can put it back. ;)
    • crazygringo 2 days ago |
      For real... where is the scrollbar?

      It's not there in Chrome or Safari.

      It is there in Firefox.

      Edit: found the culprit in "monospace-web.css":

        ::-webkit-scrollbar {
    height: var(--line-height);
  }
      Turning that off brings the scrollbar back.
  • steve_gh 2 days ago |
    Camme for the evolutionary stuff (wrote mh PhD on it).

    Left having leaned that you can switch Tail Call Optimisation on or off in Ruby code.

    • thih9 2 days ago |
      I wondered why tail call optimization isn’t on by default. Found this in an article linked from the submission:

      > There was some talk of enabling tail call optimization by default around the time that Ruby 2.0 was released, however this hasn't come to be for a number of reasons: Primary concerns were that tail call optimization makes it difficult to implement set_trace_func and also causes backtrace weirdness due to the absence of a new stack frame.

      http://blog.tdg5.com/tail-call-optimization-in-ruby-backgrou...

    • matsemann 2 days ago |
      I've never seen the main loop of an ea be written recursively before, so got a bit surprised when I came to that part.

      Also came for ea, and also wrote my thesis (master's) on it (check my profile), so have a soft spot for it. I like how it can be used for all kinds of problems. We actually also use these traditional optimizations processes/algorithms quite a lot at work, even more than ML that's quite hyped, as it's just more in line with the problems we actually face.

      Cool article, OP, I like the esthetics of the final image.

      • thomascountz 2 days ago |
        Thanks for having a look! What do you use EAs/optimizations for in your work? As I was doing research for the project, I had a hard time coming across concrete applications
        • matsemann 2 days ago |
          I work in logistics. I can't write too much about it, but many things suit EAs well. Often it's a local search with a nice objective function that pops out when you model a problem. Like, "where should things be placed at the warehouse" is the state/solution, and the fitness function is "given last month of sales, how would these placements affect our operational metrics". And then scale it up from local search to EAs, since searching the solution space in parallel and cross-reuse good smaller parts between the solutions are beneficial.
          • thomascountz 2 days ago |
            Thanks! It sounds like a really satisfying domain to work in. If you're willing to share, in industry, is the work in modeling the domain to fit the EA tooling, or is there a lot of work done in tuning the various operations, i.e. crossover, mutation, etc.?
          • steve_gh 2 days ago |
            That sounds really interesting - I have used GAs to optimise scheduling partition problems: Given a set of postcodes, a volume of work in each postcode, and preferences in that postcode for appointment times, find a schema to divide a geographic area to be served by N teams (where the N areas don't have to be contiguous)
  • juliushuijnk 2 days ago |
    I tried something related many years ago; to evolve a image format that should be tiny:

    https://medium.com/@JuliusHuijnk/experiment-in-evolving-the-...

    To be honest I haven't yet read the original article, since it's huge. It seems to aim for something compareable.

    • thomascountz 2 days ago |
      Very cool results! Our approaches were similar, but I very quickly steered away from evolving geometry (squares/triangles) and went to points/coordinates and Delaunay triangulation. This also meant I avoided overlaps and gradients, which meant I was bound to the specific low-poly esthetic. Thank you for sharing; I think your intuits hypothesis of using EAs for compression is fascinating!
      • Lerc 2 days ago |
        I can't read the article for comparison, I think it got hugged to death.

        Here's my one https://fingswotidun.com/blag/shaderpic1/ You can drag and drop images to set a new goal image.

        I used coloured triangle pairs with a small set of combination operations and a soft edge falloff.

        A write up of sorts at http://blag.fingswotidun.com/2016/05/evolved-images-using-sh...

        I'll look later when the rush dies down to see how they compare.

        [edit] I just realised it's been almost 10 years and I'm back to doing the same thing in a different domain. Right now I have a computer training an AutoEncoder to make the best 128 byte 32x32RGB images it can.

        • thomascountz 2 days ago |
          Wow! You're interactive demo is awesome!

          I had to dig up the original post by Roger Alsing[1] as it seems to have inspired a few people. I hadn't thought of evolutionary algorithms being used for image compression before; evolving from pixels to polygons creates a tool artistic expression, but also has utility for data compression (even if it's lossy). I wonder what other data formats could be compressed via evolution!

          [1]: https://web.archive.org/web/20170116042711/https://rogerjoha...

    • SoothingSorbet 2 days ago |
      I love your idea of using it for compression.

      I didn't notice a link to any code, would you be open to sharing the code? I'd love to take a look at how you did things and play around with it myself.

  • basjacobs 2 days ago |
    Great write-up, I like the fitness graphs a lot.

    I did something similar in Julia a while ago in an attempt to learn the language: https://www.basjacobs.com/post/2020-11-18-image-triangulatio...

    • thomascountz 2 days ago |
      Thanks for sharing your blog and the paper. I think your results are really stunning! Especially the bluethroat portrait[1]. When I started researching evolutionary algorithms, the application to image reconstruction was mostly pedagogical. But your blog inspires me to refine things for artistry.

      [1]: https://www.basjacobs.com/post/2020-11-18-image-triangulatio...

  • Traubenfuchs 2 days ago |
    This was cool on 4chan 10 years ago. I remember writing my own implementation using lots of unsafe C#.
    • buffington 2 days ago |
      It's cool on Hacker News today as well.
  • antirez 2 days ago |
    Related, but in C language and with a different search algorithm: https://github.com/antirez/shapeme
    • thomascountz 2 days ago |
      Thank you for sharing this and for writing the README. I hadn't heard of simulated annealing, but you've produced really stunning results having started with so few randomly-colored and -positioned triangles!
  • jeroenvlek 2 days ago |
    Very cool! Like others here I've done something similar about a decade ago [0], but only with inheritance and mutation. This was C++ and Qt.

    [0] https://github.com/jeroenvlek/evopic

  • virtualritz 2 days ago |
    There seems to be a competition on making blogs as difficult to read as possible lately.

    A monospaced font with narrow line spacing. 40 years of typesetting tech and 500 years of typography and insights on what makes a text readable thrown out of the window.

    To get what exactly? Some fake retro charme?

    I gave up reading after the first three paragraphs.

    • lukan 2 days ago |
      Taste is different.

      I don't think it was the nicest font, but I have no problems reading a monospace font. I rather despise some fancy looking but actually hard to decode font some blogs use instead.

      "40 years of typesetting tech and 500 years of typography and insights on what makes a text readable thrown out of the window"

      Also not everyone did study that and not everyone wants to hire a style guide. I bet the person writing it, just choose a font he liked. And focused on the content.

    • thomascountz 2 days ago |
      OP here. Thanks for taking a look. I respect your critique; you're not alone. Check out the feedback/critiques on The Monospace Web (the design/framework I've used) from HN earlier this year[1]. I feel inspired to write when I look at my blog's design, which is why I chose it. But, I understand that not everyone who reads it feels that way.

      You can read or download the raw markdown format, hosted on Github[2], if you're interested in the content in a different format.

      The font is from iA Writer[3], called iA Writer Duo, which arguably is not meant for a wall of prose, but I chose it because I found it easier to read than its contemporaries.

      [1]: https://news.ycombinator.com/item?id=41370020

      [2]: https://github.com/Thomascountz/thomascountz/blob/main/_post...

      [3]: https://ia.net/topics/a-typographic-christmas

    • dahart 2 days ago |
      > 40 years of typesetting tech and 500 years of typography

      > some fake retro charme?

      That’s a bit hyperbolic, and borders on just being a bit mean. There is no right way to do typography… and that is what 500 years of typography has taught us. We had monospaced typewriters in global widespread use for a hundred years. We still use monospaced fonts for programming computers… and for style in many different contexts. You do you, it’s fine if you personally prefer certain fonts, but please don’t speak for the rest of us. Almost everyone can read monospaced fonts just fine.

    • javier_e06 2 days ago |
      Funny the site had the opposite effect on me. When co-mingling computer code and text I want the text resemble the code in some fashion, like header comments. Less distracting.
  • snats 2 days ago |
    I made some image generation with CLIP and Evolutionary algorithms not so long ago[1] and the results had a bit more life than I was expecting. It is still a contested area of research and you have some cool stuff like CLIPDraw[2] where they use gradient decent to approximate a vector to the embeddings of CLIP.

    [1] https://snats.xyz/pages/articles/optimizing_images.html [2] https://arxiv.org/pdf/2106.14843

  • jes 2 days ago |
    John Koza has something like three or four books on Genetic Programming. It's all in Lisp and I enjoyed working with different examples from his books. If I ever have enough free time, I'd like to go back and work with it again for a while.
  • chankstein38 2 days ago |
    I did something similar to this once and used a similarity algorithm for fitness. The result was really neat, the output image looked very similar to the input image when you were zoomed out but when you zoomed in it was unrecognizable. It was a really interesting result!
    • matsemann 2 days ago |
      Your comment kinda reminded me of "Rasterbator", a software I used 15 years ago to decorate a wall at my uni dorm. It took an image and a size, and gave you back a pdf with a4 pages to print. The pages were just dots up close, but when arranged in the grid with the other papers and looked at from afar it would be the original image.
      • tincholio 2 days ago |
        I actually wrote a (not so polished) clone of that in Ruby, way back when...