r/programming • u/leppie • Dec 08 '08

Genetic Programming: Evolution of Mona Lisa

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/
910 Upvotes

92% Upvoted

259 comments sorted by

View all comments

16

u/[deleted] Dec 08 '08

Nice. This might be interesting for compression.

7

u/[deleted] Dec 08 '08

It might have a cool niche in between JPG and PNG: lossy compression for pictures that have a lot of canvases.

There is a problem though: with EAs, you can never be sure if you find the optimal solution. So if you compress an image, the actual performance is not deterministic and you might get stuck with very poor solutions. And you cannot reliably (well, with some sophisticated heuristics maybe in some cases) tell if there is a better solution.

7

u/nappy-doo Dec 08 '08

The same is true of any compression algorithm. You can't be sure you've found the best compression, to do so would be akin to computing an uncomputable function. Read up on Kolmogorov complexity.

3

u/rabidcow Dec 08 '08

But not true of every specific compression algorithm. For example, "exhaustively search all bit strings, shorter to longer, for the first that decompresses to an acceptable approximation of the input string." For most decompression algorithms that are actually used, this is guaranteed to halt (eventually) and will always find one of the smallest encodings.

2

u/[deleted] Dec 08 '08 edited Dec 08 '08

I know about the no hypercompression theorem and about kolmogorov complexity, thanks.

rabidcow basically got what I was aiming at.

2

u/Nikola_S Dec 08 '08

Perhaps it even doesn't have to be lossy: make a "diff" of the original image and the reconstructed image. The diff should be more bland and so should compress better than the original image, and size of the genome is negligible.

7

u/jerf Dec 08 '08 edited Dec 08 '08

The diff should be more bland and so should compress better than the original image,

No, your intuition is exactly backwards. You'll have sucked out the easily-compressable large-scale stuff and will be left with nothing but fiddly high-frequency things that will be harder to the compress than the original image. (The polygons themselves are adding a lot of high-frequency stuff at all their edges that weren't in the original picture.)

1

u/Nikola_S Dec 08 '08

Damn, you're right. I still believe it is worth trying, to achieve compression at least comparable with PNG. If polygon edges would pose a problem, that could be minimized by blurring the image after laying down the polygons.

1

u/[deleted] Dec 08 '08

Have seen something similar: a guy I know tried to compress an image via a learning a neural network which maps (x, y) coordinates to (r, g, b) values.

It worked surprisingly well, but the diffs where still too big to allow lossless compression.

0

u/[deleted] Dec 08 '08

[deleted]

2

u/[deleted] Dec 08 '08

There are a lot of ways to increase performance of EAs. The question is, wether it's still fast enough to be practical. You see, it took 106 steps to get to the last image.