Genetic algorithms for image generation?



  • Hello, I have considered doing following project:

    Imagine that you have simple graphics (like some schematics, logo, etc). I'd like to investigate some other approaches to saving the image like traditional bitmap/vector files.

    It would use some kind of advanced algorithms to generate set of graphical operations (draw line/shape/curve, fill shape, draw text somewhere) that would be drawn to some bitmap. The program would then evaluate how much the generated image look like the original (like fitness function in GA), I mean, evaluate many solutions, find the best ones, combine/mutate them in some way to produce better results in the next generation.

    It would not be saving the image in the true sense of word, it would be more like finding algorithm on how to recreate it with the best precision using elementary graphical operations. Maybe it would be useless, maybe not.

    My question is, how should I start? I read something on the topic of genetic algorithms, but most of the articles dealt with using binary string (genes) for representing the operations (but wouldn't it be too long to encode many (tens, hundreds) graphical operations with parameters?) I mean, if we had about hundred operations (8-bit identifier) with average of four 16-bit parameters, it would be about 1008+1004*16=7200 bits of information to combine, mutate and eventually, evaluate.

    I know it will be painfully slow, to have some kind of fitness evaluation function that would need to draw image from the "genes", but this would be a research project. I am just wondering if something like this is possible (I think it could be), and if yes, someone could please point me in the right direction to start.

    thanks,
    axarydax



  • Sounds like an interesting idea. Should not be too hard to implement, too. Thumbs up. Remember to post some pictures of the results here.
    How to start? Well, go for the fitness function first. Maybe you want to choose an adaptive approach: in the first n iterations, render the picture to a resolution of (say) 8x8 pixels, to separate the "completely wrong" genes from those that produce a least a very rough representation of the target picture. Increase the representation when fitness scores become better.

    You might also consider continuously increasing the "length" of the genes (i.e. the number of graphical primitives each gene represents).





  • @JvdL said:



    It doesn't work.

    As the linked page says, it works, it's just that all the standard algorithms work much better.

    This should not come as a surprise to anybody familiar with genetic algorithms. Basically, they're a solution of last resort: if you cannot find any other way to solve an approximation or global optimisation problem, you can probably solve it with a genetic algorithm. For almost every problem, they are going to be the worst way to solve it (other than brute force or naive random search), but they will get you a solution - very slowly.

    If you can come up with any other feasible way to tackle a problem, it will usually work much better than a genetic algorithm.

    Genetic algorithms find applications in solving problems which are NP-complete, EXPTIME, or worse, and which are too complex for the Monte Carlo method (or related statistical techniques) to be easily applicable. Image compression is none of these things.



  • @asuffield said:

    Image compression is none of these things.

    Definitely. Then, I rather consider it some kind of artistic filter.



  • Thanks,

    I liked mostly the graduate student algorithm :D

    (the so-called "graduate student algorithm", consisting of locking up a grad student in a tiny office with a SGI workstation and not letting them out until they come up with a good IFS for your image).

    but seriously... I didn't intend to use it like a compression, more like the artistic approach



  • @axarydax said:



    but seriously... I didn't intend to use it like a compression, more like the artistic approach

    You'd be better off looking at computer vision techniques. 


Log in to reply